{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:14Z","timestamp":1759637594234},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175138"},{"type":"electronic","value":"9783642175145"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_28","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T15:09:23Z","timestamp":1291388963000},"page":"327-338","source":"Crossref","is-referenced-by-count":4,"title":["Entropy-Bounded Representation of Point Grids"],"prefix":"10.1007","author":[{"given":"Arash","family":"Farzan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G., Rauhe, T.: New data structures for orthogonal range searching. In: Proc. 41st FOCS, pp. 198\u2013207 (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"key":"28_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/978-3-642-14335-9","volume-title":"Proc. 9th LATIN","author":"J. Barbay","year":"2010","unstructured":"Barbay, J., Claude, F., Navarro, G.: Compact rich-functional binary relation representations. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 172\u2013185. Springer, Heidelberg (2010)"},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"M. Bender","year":"2004","unstructured":"Bender, M., Farach-Colton, M.: The level ancestor problem simplified. Theoretical Computer Science\u00a0321(1), 5\u201312 (2004)","journal-title":"Theoretical Computer Science"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"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\u2013109 (2009)","DOI":"10.1007\/978-3-642-03367-4_9"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Chan, T., P\u0103tra\u015fcu, M.: Counting inversions, offline orthogonal range counting, and related problems. In: Proc. 21st SODA, pp. 161\u2013173 (2010)","DOI":"10.1137\/1.9781611973075.15"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: A new approach to query-answering. SIAM Journal of Computing\u00a015, 703\u2013724 (1986)","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"28_CR7","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1145\/79147.79149","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B.: Lower bounds for orthogonal range searching: II. The arithmetic model. Journal of the ACM\u00a037(3), 430\u2013463 (1990)","journal-title":"Journal of the ACM"},{"key":"28_CR8","unstructured":"Clark, D.: Compact Pat Trees. PhD thesis, University of Waterloo, Canada (1996)"},{"issue":"3","key":"28_CR9","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A. Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. Theoretical Computer Science\u00a0387(3), 348\u2013359 (2007)","journal-title":"Theoretical Computer Science"},{"key":"28_CR10","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th SODA (2003)"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hon, W.-K., Shah, R., Vitter, J.S.: Compressed data structures: Dictionaries and data-aware measures. In: Proc. 16th DCC, pp. 213\u2013222 (2006)","DOI":"10.1109\/DCC.2006.12"},{"key":"28_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1007\/978-3-540-30551-4_49","volume-title":"Algorithms and Computation","author":"J. J\u00e1 J\u00e1","year":"2004","unstructured":"J\u00e1 J\u00e1, 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.\u00a03341, pp. 558\u2013568. Springer, Heidelberg (2004)"},{"key":"28_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"I. Munro","year":"1996","unstructured":"Munro, I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Nekrich, Y.: Space efficient dynamic orthogonal range reporting. In: Proc. 21st SCG, pp. 306\u2013313 (2005)","DOI":"10.1145\/1064092.1064139"},{"issue":"4","key":"28_CR15","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","volume":"42","author":"Y. Nekrich","year":"2009","unstructured":"Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. Computational Geometry: Theory and Applications\u00a042(4), 342\u2013351 (2009)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: Proc. 9th ALENEX (2007)","DOI":"10.1137\/1.9781611972870.6"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M.: Lower bounds for 2-dimensional range counting. In: Proc. 39th STOC, pp. 40\u201346 (2007)","DOI":"10.1145\/1250790.1250797"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. 38th STOC, pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"key":"28_CR19","unstructured":"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\u2013242 (2002)"},{"issue":"2","key":"28_CR20","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D. Willard","year":"1983","unstructured":"Willard, D.: Log-logarithmic worst-case range queries are possible in space \u03b8(n). Information Processing Letters\u00a017(2), 81\u201384 (1983)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T15:49:14Z","timestamp":1559836154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}