Queries on compressed data

Abstract

Low-latency, high-throughput interactive query systems must serve massive datasets and increasingly rich operations. In-memory approaches are fast but falter once data exceeds DRAM capacity, while alternatives often support only limited queries. This dissertation develops algorithmic and data-structure solutions centered on querying compressed data. It presents Succinct for search, random access, range, and wildcard queries over compressed representations; BlowFish for dynamically trading storage against performance; ZipG for memory-efficient graph queries; and Sprint for regular expression queries through query rewriting.

BibTeX

@book{phdthesis,
  title = {{Queries on compressed data}},
  author = {Khandelwal, Anurag},
  month = dec,
  year = {2019},
  publisher = {University of California, Berkeley}
}