Name
Abstract | ||
|---|---|---|
We give the first fully compressed representation of a set of m points on an n×n grid, taking H+o(H) bits of space, where H=lg(n2m) is the entropy of the set. This representation supports range counting, range reporting, and point selection queries, with complexities that go from O(1) to O(lg2n/lglgn) per answer as the entropy of the grid decreases. Operating within entropy-bounded space, as well as relating time complexity with entropy, opens a new line of research on an otherwise well-studied area. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.comgeo.2013.08.002 | Computational Geometry |
Keywords | DocType | Volume |
Compressed data structures,Geometric grids,Range queries | Journal | 47 |
Issue | ISSN | Citations |
1 | 0925-7721 | 5 |
PageRank | References | Authors |
0.40 | 32 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arash Farzan | 1 | 136 | 11.07 |
| Travis Gagie | 2 | 643 | 63.61 |
| Gonzalo Navarro | 3 | 6088 | 345.16 |