Succinct data structures
Material type:
TextPublication details: 2001Description: v; 100pSubject(s): Online resources: Dissertation note: 2001Ph.DUniversity of Madras Abstract: This thesis aims to develop space efficient structures for some of the most fundamental problems in the area of data structures. The design of data structures that use almost optimal space while supporting the operations efficiently, is the focus in particular. The representations of suffix trees, suffix arrays, static dictionaries supporting rank, cardinal trees, a list of numbers supporting partial sum queries, dynamic bit vectors and dynamic arrays are some of the problems considered for this study. These problems are studied in the extended RAM model which supports all arithmetic and bitwise boolean operations on words in constant time. The problem of static dictionary also is considered in the bitprobe model. Two index structures are developed with better space complexity, supporting a restricted set of indexing queries. A compressed suffix array implementation is given in constant time, as the extension of ideas of Grossi and Vitter.
THESIS & DISSERTATION
| Home library | Call number | Materials specified | URL | Status | Date due | Barcode | |
|---|---|---|---|---|---|---|---|
| IMSc Library | UNM Th-74 (Browse shelf(Opens below)) | Link to resource | Available | 56255 |
2001
Ph.D
University of Madras
This thesis aims to develop space efficient structures for some of the most fundamental problems in the area of data structures. The design of data structures that use almost optimal space while supporting the operations efficiently, is the focus in particular. The representations of suffix trees, suffix arrays, static dictionaries supporting rank, cardinal trees, a list of numbers supporting partial sum queries, dynamic bit vectors and dynamic arrays are some of the problems considered for this study. These problems are studied in the extended RAM model which supports all arithmetic and bitwise boolean operations on words in constant time. The problem of static dictionary also is considered in the bitprobe model. Two index structures are developed with better space complexity, supporting a restricted set of indexing queries. A compressed suffix array implementation is given in constant time, as the extension of ideas of Grossi and Vitter.
There are no comments on this title.