Succinct data structures (Record no. 48787)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 01638nam a2200253Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2001||||xx |||||||||||||| ||und|| |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | UNM Th-74 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Srinivasa Rao, S. |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Succinct data structures |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2001 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | v; 100p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2001 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | University of Madras |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | 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. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Data Structures |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Suffix Array |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Suffix Tree |
| 720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Venkatesh, Raman |
| Relator term | Thesis advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/99 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | THESIS & DISSERTATION |
| Withdrawn status | Lost status | Damaged status | Not for loan | Current library | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
|---|---|---|---|---|---|---|---|---|
| IMSc Library | UNM Th-74 | 56255 | http://www.imsc.res.in/xmlui/handle/123456789/99 | THESIS & DISSERTATION |