Conference paper · Book chapter
Compressed Data Structures for Range Searching
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.
Language: | English |
---|---|
Publisher: | Springer |
Year: | 2015 |
Pages: | 577-586 |
Proceedings: | 9th International Conference on Language and Automata Theory and Applications (LATA 2015)International Conference on Language and Automata Theory and Applications |
Series: | Lecture Notes in Computer Science |
ISBN: | 3319155784 , 3319155792 , 9783319155784 and 9783319155791 |
ISSN: | 03029743 and 16113349 |
Types: | Conference paper and Book chapter |
DOI: | 10.1007/978-3-319-15579-1_45 |
ORCIDs: | Bille, Philip and Gørtz, Inge Li |