Compressed Data Structures for Range Searching

Philip Bille, Inge Li Gørtz, Søren Juhl Vind

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

238 Downloads (Pure)

Abstract

We study the orthogonal range searching problem on points that have a significant number of geometric repetitions, that is, subsets of points that are identical under translation. Such repetitions occur in scenarios such as image compression, GIS applications and in compactly representing sparse matrices and web graphs. Our contribution is twofold. First, we show how to compress geometric repetitions that may appear in standard range searching data structures (such as K-D trees, Quad trees, Range trees, R-trees, Priority R-trees, and K-D-B trees), and how to implement subsequent range queries on the compressed representation with only a constant factor overhead. Secondly, we present a compression scheme that efficiently identifies geometric repetitions in point sets, and produces a hierarchical clustering of the point sets, which combined with the first result leads to a compressed representation that supports range searching.
Original languageEnglish
Title of host publicationProceedings of the 9th International Conference on Language and Automata Theory and Applications (LATA 2015)
EditorsAdrian-Horia Dediu, Enrico Formenti, Carlos Martín-Vide, Bianca Truthe
PublisherSpringer
Publication date2015
Pages577-586
ISBN (Print)978-3-319-15578-4
ISBN (Electronic)978-3-319-15579-1
DOIs
Publication statusPublished - 2015
Event9th International Conference on Language and Automata Theory and Applications (LATA 2015) - Nice, France
Duration: 2 Mar 20156 Mar 2015
Conference number: 9
http://grammars.grlmc.com/lata2015/

Conference

Conference9th International Conference on Language and Automata Theory and Applications (LATA 2015)
Number9
CountryFrance
CityNice
Period02/03/201506/03/2015
Internet address
SeriesLecture Notes in Computer Science
Volume8977
ISSN0302-9743

Keywords

  • Data and image compression
  • Range searching
  • Relative tree
  • DAG compression
  • Hierarchical clustering

Fingerprint Dive into the research topics of 'Compressed Data Structures for Range Searching'. Together they form a unique fingerprint.

Cite this