Space Efficient Data Structures and Algorithms in the Word-RAM Model

Algorithms;Data Structures;Space Efficient;Range Searching;Permutations

El-Zein, Hichamadvisor:Munro, J. Ian ; affiliation1:Faculty of Mathematics ; Munro, J. Ian ;

University of Waterloo

关键词: Permutations;    Algorithms;    Space Efficient;    Data Structures;    Range Searching;    Doctoral Thesis;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/13200/3/el-zein_hicham.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In modern computation the volume of data-sets has increased dramatically.Since the majority of these data-sets are stored in internal memory, reducing their storage requirement is an important research topic.One way of reducing storage is using succinct and compact data structures which maintain the data in compressed form with extra data structures over it in a way that allows efficient access and query of the data.In this thesis we study space-efficient data structures for various combinatorial objects.We focus on succinct and compact data structures.Succinct data structures are data structures whose size is within the information theoretic lower bound plus a lower order term,whereas compact data structures are data structures whose size is a constant factor from the information theoretic lower bound.