{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T14:45:03Z","timestamp":1768488303153,"version":"3.49.0"},"reference-count":38,"publisher":"Elsevier BV","issue":"5","content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information Systems"],"published-print":{"date-parts":[[2013,7]]},"DOI":"10.1016\/j.is.2013.01.005","type":"journal-article","created":{"date-parts":[[2013,1,30]],"date-time":"2013-01-30T20:01:28Z","timestamp":1359576088000},"page":"635-655","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":21,"title":["Space-efficient representations of rectangle datasets supporting orthogonal range querying"],"prefix":"10.1016","volume":"38","author":[{"given":"Nieves R.","family":"Brisaboa","sequence":"first","affiliation":[]},{"given":"Miguel R.","family":"Luaces","sequence":"additional","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]},{"given":"Diego","family":"Seco","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"9","key":"10.1016\/j.is.2013.01.005_bib1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary search trees used for associative searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Communications of the ACM"},{"issue":"3","key":"10.1016\/j.is.2013.01.005_bib2","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1137\/0217026","article-title":"A functional approach to data structures and its use in multidimensional searching","volume":"17","author":"Chazelle","year":"1988","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"10.1016\/j.is.2013.01.005_bib3","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","article-title":"Orthogonal range searching in linear and almost-linear space","volume":"42","author":"Nekrich","year":"2009","journal-title":"Computational Geometry"},{"key":"10.1016\/j.is.2013.01.005_bib4","doi-asserted-by":"crossref","unstructured":"P. Bose, M. He, A. Maheshwari, P. Morin, Succinct orthogonal range search structures on a grid with applications to text indexing, in: Proceedings of the 11th WADS, 2009, pp. 98\u2013109.","DOI":"10.1007\/978-3-642-03367-4_9"},{"issue":"2","key":"10.1016\/j.is.2013.01.005_bib5","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1145\/280277.280279","article-title":"Multidimensional access methods","volume":"30","author":"Gaede","year":"1998","journal-title":"ACM Computing Surveys"},{"issue":"3","key":"10.1016\/j.is.2013.01.005_bib6","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1080\/13658810701626343","article-title":"Geographical information retrieval","volume":"22","author":"Jones","year":"2008","journal-title":"Journal of Geographical Information Science"},{"key":"10.1016\/j.is.2013.01.005_bib7","doi-asserted-by":"crossref","unstructured":"N.R. Brisaboa, M.R. Luaces, G. Navarro, D. Seco, Range queries over a compact representation of minimum bounding rectangles, in: Proceedings of the 29th ER Work, 2009, pp. 33\u201342.","DOI":"10.1007\/978-3-642-16385-2_5"},{"key":"10.1016\/j.is.2013.01.005_bib8","doi-asserted-by":"crossref","unstructured":"N.R. Brisaboa, M.R. Luaces, G. Navarro, D. Seco, A fun application of compact data structures to indexing geographic data, in: Proceedings of the Fifth FUN, 2010, pp. 77\u201388.","DOI":"10.1007\/978-3-642-13122-6_10"},{"issue":"2","key":"10.1016\/j.is.2013.01.005_bib9","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1145\/376284.375679","article-title":"Optimizing multidimensional index trees for main memory access","volume":"30","author":"Kim","year":"2001","journal-title":"SIGMOD Record"},{"key":"10.1016\/j.is.2013.01.005_bib10","doi-asserted-by":"crossref","unstructured":"K.V.R. Kanth, A.K. Singh, Optimal dynamic range searching in non-replicating index structures, in: Proceedings of the Seventh ICDT, 1999, pp. 257\u2013276.","DOI":"10.1007\/3-540-49257-7_17"},{"key":"10.1016\/j.is.2013.01.005_bib11","doi-asserted-by":"crossref","unstructured":"G.S. Lueker, A data structure for orthogonal range queries, in: Proceedings of the 19th FOCS, IEEE, 1978, pp. 28\u201334.","DOI":"10.1109\/SFCS.1978.1"},{"key":"10.1016\/j.is.2013.01.005_bib12","unstructured":"R. Grossi, A. Gupta, J. Vitter, High-order entropy-compressed text indexes, in: Proceedings of the 14th SODA, 2003, pp. 841\u2013850."},{"issue":"3","key":"10.1016\/j.is.2013.01.005_bib13","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/j.tcs.2007.07.013","article-title":"Rank and select revisited and extended","volume":"387","author":"M\u00e4kinen","year":"2007","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/j.is.2013.01.005_bib14","doi-asserted-by":"crossref","unstructured":"T. Chan, K. Larsen, M. Patrascu, Orthogonal range searching on the RAM, revisited, in: Proceedings of the 27th SoCG, 2011, pp. 1\u201310.","DOI":"10.1145\/1998196.1998198"},{"key":"10.1016\/j.is.2013.01.005_bib15","doi-asserted-by":"crossref","unstructured":"A. Guttman, R-Trees: a dynamic index structure for spatial searching, in: Proceedings of the SIGMOD, ACM Press, 1984, pp. 47\u201357.","DOI":"10.1145\/971697.602266"},{"key":"10.1016\/j.is.2013.01.005_bib16","series-title":"R-Trees","author":"Manolopoulos","year":"2005"},{"key":"10.1016\/j.is.2013.01.005_bib17","doi-asserted-by":"crossref","unstructured":"G. Navarro, Wavelet trees for all, in: Proceedings of the 23rd CPM, 2012, pp. 2\u201326.","DOI":"10.1007\/978-3-642-31265-6_2"},{"issue":"2","key":"10.1016\/j.is.2013.01.005_bib18","doi-asserted-by":"crossref","first-page":"article 20","DOI":"10.1145\/1240233.1240243","article-title":"Compressed representations of sequences and full-text indexes","volume":"3","author":"Ferragina","year":"2007","journal-title":"ACM Transactions on Algorithms"},{"key":"10.1016\/j.is.2013.01.005_bib19","doi-asserted-by":"crossref","unstructured":"Y.-F. Chien, W.-K. Hon, R. Shah, J.S. Vitter, Geometric Burrows\u2013Wheeler transform: linking range searching and text indexing, in: Proceedings of the 18th DCC, 2008, pp. 252\u2013261.","DOI":"10.1109\/DCC.2008.67"},{"key":"10.1016\/j.is.2013.01.005_bib20","unstructured":"N. V\u00e4lim\u00e4ki, V. M\u00e4kinen, Space-efficient algorithms for document retrieval, in: Proceedings of the 18th CPM, vol. 4580 of LNCS, 2007, pp. 205\u2013215."},{"key":"10.1016\/j.is.2013.01.005_bib21","doi-asserted-by":"crossref","unstructured":"V. M\u00e4kinen, G. Navarro, On self-indexing images\u2014image compression with added value, in: Proceedings of the 18th DCC, 2008, pp. 422\u2013431.","DOI":"10.1109\/DCC.2008.47"},{"key":"10.1016\/j.is.2013.01.005_bib22","doi-asserted-by":"crossref","unstructured":"F. Claude, G. Navarro, Practical rank\/select queries over arbitrary sequences, in: Proceedings of the 15th SPIRE, 2008, pp. 176\u2013187.","DOI":"10.1007\/978-3-540-89097-3_18"},{"key":"10.1016\/j.is.2013.01.005_bib23","doi-asserted-by":"crossref","unstructured":"G. Jacobson, Space-efficient static trees and graphs, in: Proceedings of the 30th FOCS, 1989, pp. 549\u2013554.","DOI":"10.1109\/SFCS.1989.63533"},{"key":"10.1016\/j.is.2013.01.005_bib24","doi-asserted-by":"crossref","unstructured":"I. Munro, Tables, in: Proceedings of the 16th FSTTCS, 1996, pp. 37\u201342.","DOI":"10.1007\/3-540-62034-6_35"},{"key":"10.1016\/j.is.2013.01.005_bib25","unstructured":"R. Gonz\u00e1lez, S. Grabowski, V. M\u00e4kinen, G. Navarro, Practical implementation of rank and select queries, in: Poster Proceedings of the Fourth WEA, CTI Press and Ellinika Grammata, 2005, pp. 27\u201338."},{"key":"10.1016\/j.is.2013.01.005_bib26","doi-asserted-by":"crossref","unstructured":"F. Claude, P.K. Nicholson, D. Seco, Space efficient wavelet tree construction, in: Proceedings of the 18th SPIRE, 2011, pp. 185\u2013196.","DOI":"10.1007\/978-3-642-24583-1_19"},{"key":"10.1016\/j.is.2013.01.005_bib27","doi-asserted-by":"crossref","unstructured":"G. Tischler, On wavelet tree construction, in: Proceedings of the 22nd CPM, 2011, pp. 208\u2013218.","DOI":"10.1007\/978-3-642-21458-5_19"},{"key":"10.1016\/j.is.2013.01.005_bib28","doi-asserted-by":"crossref","unstructured":"N.R. Brisaboa, M.R. Luaces, G. Navarro, D. Seco, A new point access method based on wavelet trees, in: Proceedings of the 28th ER Work, 2009, pp. 297\u2013306.","DOI":"10.1007\/978-3-642-04947-7_36"},{"key":"10.1016\/j.is.2013.01.005_bib29","doi-asserted-by":"crossref","unstructured":"H.N. Gabow, J.L. Bentley, R.E. Tarjan, Scaling and related techniques for geometry problems, in: Proceedings of the 16th STOC, ACM, 1984, pp. 135\u2013143.","DOI":"10.1145\/800057.808675"},{"key":"10.1016\/j.is.2013.01.005_bib30","series-title":"Computational Geometry\u2014Algorithms and Applications","author":"de Berg","year":"2000"},{"key":"10.1016\/j.is.2013.01.005_bib31","series-title":"Data Compression","author":"Salomon","year":"2004"},{"key":"10.1016\/j.is.2013.01.005_bib32","doi-asserted-by":"crossref","unstructured":"J.M. Schmidt, Interval stabbing problems in small integer ranges, in: Proceedings of the 20th ISAAC, 2009, pp. 163\u2013172.","DOI":"10.1007\/978-3-642-10631-6_18"},{"key":"10.1016\/j.is.2013.01.005_bib33","doi-asserted-by":"crossref","unstructured":"K. Sadakane, G. Navarro, Fully-functional succinct trees, in: Proceedings of the 21st SODA, SIAM, 2010, pp. 134\u2013149.","DOI":"10.1137\/1.9781611973075.13"},{"key":"10.1016\/j.is.2013.01.005_bib34","doi-asserted-by":"crossref","unstructured":"D. Arroyuelo, R. C\u00e1novas, G. Navarro, K. Sadakane, Succinct trees in practice, in: Proceedings of the 12th ALENEX, SIAM, 2010, pp. 84\u201397.","DOI":"10.1137\/1.9781611972900.9"},{"key":"10.1016\/j.is.2013.01.005_bib35","unstructured":"J. Barbay, G. Navarro, Compressed representations of permutations, and applications, in: Proceedings of the 26th STACS, 2009, pp. 111\u2013122."},{"issue":"1","key":"10.1016\/j.is.2013.01.005_bib36","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","article-title":"On computing the length of longest increasing subsequences","volume":"11","author":"Fredman","year":"1975","journal-title":"Discrete Mathematics"},{"issue":"2","key":"10.1016\/j.is.2013.01.005_bib37","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/93605.98741","article-title":"The R\u204e-tree","volume":"19","author":"Beckmann","year":"1990","journal-title":"SIGMOD Record"},{"key":"10.1016\/j.is.2013.01.005_bib38","doi-asserted-by":"crossref","first-page":"4414","DOI":"10.1016\/j.tcs.2009.07.022","article-title":"Rank\/select on dynamic compressed sequences and applications","volume":"410","author":"Gonz\u00e1lez","year":"2008","journal-title":"Theoretical Computer Science"}],"container-title":["Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0306437913000069?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0306437913000069?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T18:56:16Z","timestamp":1745952976000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0306437913000069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7]]},"references-count":38,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["S0306437913000069"],"URL":"https:\/\/doi.org\/10.1016\/j.is.2013.01.005","relation":{},"ISSN":["0306-4379"],"issn-type":[{"value":"0306-4379","type":"print"}],"subject":[],"published":{"date-parts":[[2013,7]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Space-efficient representations of rectangle datasets supporting orthogonal range querying","name":"articletitle","label":"Article Title"},{"value":"Information Systems","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.is.2013.01.005","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2013 Elsevier Ltd. All rights reserved.","name":"copyright","label":"Copyright"}]}}