Back to search

University of Waterloo

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

Abstract

dc:description.abstract

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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • El-Zein, Hicham
Advisor dc:contributor.advisor
  • Munro, J. Ian

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/13200

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

El-Zein, Hicham. Space Efficient Data Structures and Algorithms in the Word-RAM Model. University of Waterloo, 2018. http://hdl.handle.net/10012/13200