{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:04Z","timestamp":1760202604586},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642033667"},{"type":"electronic","value":"9783642033674"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03367-4_9","type":"book-chapter","created":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T03:56:42Z","timestamp":1248062202000},"page":"98-109","source":"Crossref","is-referenced-by-count":43,"title":["Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing"],"prefix":"10.1007","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[]},{"given":"Meng","family":"He","sequence":"additional","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.tcs.2007.07.013","volume":"387","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Rank and select revisited and extended. Theor. Comput. Sci.\u00a0387, 332\u2013347 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Chien, Y.F., Hon, W.K., Shah, R., Vitter, J.S.: Geometric burrows-wheeler transform: Linking range searching and text indexing. In: DCC, pp. 252\u2013261 (2008)","DOI":"10.1109\/DCC.2008.67"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: STOC, pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"issue":"3","key":"9_CR4","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing\u00a017(3), 427\u2013462 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"9_CR5","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0196-6774(88)90041-7","volume":"9","author":"M.H. Overmars","year":"1988","unstructured":"Overmars, M.H.: Efficient data structures for range searching on a grid. Journal of Algorithms\u00a09(2), 254\u2013275 (1988)","journal-title":"Journal of Algorithms"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: FOCS, pp. 198\u2013207 (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"issue":"4","key":"9_CR7","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":"9_CR8","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: FOCS, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"4","key":"9_CR9","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R. Raman","year":"2007","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms\u00a03(4), 43 (2007)","journal-title":"ACM Transactions on Algorithms"},{"key":"9_CR10","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA, pp. 841\u2013850 (2003)"},{"issue":"3","key":"9_CR11","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/j.tcs.2007.07.015","volume":"387","author":"J. Barbay","year":"2007","unstructured":"Barbay, J., Golynski, A., Munro, J.I., Rao, S.S.: Adaptive searching in succinctly encoded binary relations and tree-structured documents. Theoretical Computer Science\u00a0387(3), 284\u2013297 (2007)","journal-title":"Theoretical Computer Science"},{"key":"9_CR12","unstructured":"Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: SODA, pp. 680\u2013689 (2007)"},{"issue":"4","key":"9_CR13","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/1198513.1198516","volume":"2","author":"R.F. Geary","year":"2006","unstructured":"Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. ACM Transactions on Algorithms\u00a02(4), 510\u2013534 (2006)","journal-title":"ACM Transactions on Algorithms"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: FOCS, pp. 184\u2013196 (2005)","DOI":"10.1109\/SFCS.2005.69"},{"issue":"2","key":"9_CR15","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/1240233.1240243","volume":"3","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Alg.\u00a03(2), 20 (2007)","journal-title":"ACM Trans. Alg."},{"issue":"2","key":"9_CR16","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0304-3975(96)00201-0","volume":"175","author":"F. Bauern\u00f6ppel","year":"1997","unstructured":"Bauern\u00f6ppel, F., Kranakis, E., Krizanc, D., Maheshwari, A., Sack, J.R., Urrutia, J.: Planar stage graphs: Characterizations and applications. Theoretical Computer Science\u00a0175(2), 239\u2013255 (1997)","journal-title":"Theoretical Computer Science"},{"key":"9_CR17","unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage. In: SODA, pp. 383\u2013391 (1996)"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03367-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T11:28:51Z","timestamp":1558438131000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03367-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033667","9783642033674"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03367-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}