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 {n^2 \choose m}\) is the entropy of the set. This representation supports range counting, range reporting, and point selection queries, with a performance that is comparable to that of uncompressed structures and that improves upon the only previous compressed structure. Operating within entropy-bounded space opens a new line of research on an otherwise well-studied area, and is becoming extremely important for handling large datasets.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alstrup, S., Brodal, G., Rauhe, T.: New data structures for orthogonal range searching. In: Proc. 41st FOCS, pp. 198–207 (2000)
Barbay, J., Claude, F., Navarro, G.: Compact rich-functional binary relation representations. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 172–185. Springer, Heidelberg (2010)
Bender, M., Farach-Colton, M.: The level ancestor problem simplified. Theoretical Computer Science 321(1), 5–12 (2004)
Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: Proc. 11th WADS, pp. 98–109 (2009)
Chan, T., Pătraşcu, M.: Counting inversions, offline orthogonal range counting, and related problems. In: Proc. 21st SODA, pp. 161–173 (2010)
Chazelle, B.: Filtering search: A new approach to query-answering. SIAM Journal of Computing 15, 703–724 (1986)
Chazelle, B.: Lower bounds for orthogonal range searching: II. The arithmetic model. Journal of the ACM 37(3), 430–463 (1990)
Clark, D.: Compact Pat Trees. PhD thesis, University of Waterloo, Canada (1996)
Golynski, A.: Optimal lower bounds for rank and select indexes. Theoretical Computer Science 387(3), 348–359 (2007)
Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th SODA (2003)
Gupta, A., Hon, W.-K., Shah, R., Vitter, J.S.: Compressed data structures: Dictionaries and data-aware measures. In: Proc. 16th DCC, pp. 213–222 (2006)
Já Já, J., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 558–568. Springer, Heidelberg (2004)
Munro, I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol. 1180, pp. 37–42. Springer, Heidelberg (1996)
Nekrich, Y.: Space efficient dynamic orthogonal range reporting. In: Proc. 21st SCG, pp. 306–313 (2005)
Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. Computational Geometry: Theory and Applications 42(4), 342–351 (2009)
Okanohara, D., Sadakane, K.: Practical entropy-compressed rank/select dictionary. In: Proc. 9th ALENEX (2007)
Pătraşcu, M.: Lower bounds for 2-dimensional range counting. In: Proc. 39th STOC, pp. 40–46 (2007)
Pătraşcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. 38th STOC, pp. 232–240 (2006)
Raman, R., Raman, V., Srinivasa Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th SODA, pp. 233–242 (2002)
Willard, D.: Log-logarithmic worst-case range queries are possible in space θ(n). Information Processing Letters 17(2), 81–84 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farzan, A., Gagie, T., Navarro, G. (2010). Entropy-Bounded Representation of Point Grids. In: Cheong, O., Chwa, KY., Park, K. (eds) Algorithms and Computation. ISAAC 2010. Lecture Notes in Computer Science, vol 6507. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17514-5_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-17514-5_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17513-8
Online ISBN: 978-3-642-17514-5
eBook Packages: Computer ScienceComputer Science (R0)