{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:54:27Z","timestamp":1743155667450,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_45","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"577-586","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Compressed Data Structures for Range Searching"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[]},{"given":"S\u00f8ren","family":"Vind","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"issue":"1","key":"45_CR1","first-page":"9","volume":"4","author":"L Arge","year":"2008","unstructured":"Arge, L., Berg, M.D., Haverkort, H., Yi, K.: The Priority R-tree: A practically efficient and worst-case optimal R-tree. ACM TALG 4(1), 9 (2008)","journal-title":"ACM TALG"},{"key":"45_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-642-12200-2_17","volume-title":"LATIN 2010: Theoretical Informatics","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. 6034, pp. 170\u2013183. Springer, Heidelberg (2010)"},{"issue":"3","key":"45_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.: Organization and maintenance of large ordered indexes. Acta Informatica 1(3), 173\u2013189 (1972)","journal-title":"Acta Informatica"},{"issue":"9","key":"45_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Comm. ACM 18(9), 509\u2013517 (1975)","journal-title":"Comm. ACM"},{"key":"45_CR5","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1109\/TSE.1979.234200","volume":"4","author":"JL Bentley","year":"1979","unstructured":"Bentley, J.L.: Multidimensional binary search trees in database applications. IEEE Trans. Softw. Eng. 4, 333\u2013340 (1979)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"4","key":"45_CR6","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I. Static-to-dynamic transformation. J. Algorithms 1(4), 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"key":"45_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-319-02432-5_14","volume-title":"String Processing and Information Retrieval","author":"G de Bernardo","year":"2013","unstructured":"de Bernardo, G., \u00c1lvarez-Garc\u00eda, S., Brisaboa, N.R., Navarro, G., Pedreira, O.: Compact querieable representations of raster data. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 96\u2013108. Springer, Heidelberg (2013)"},{"key":"45_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-03367-4_9","volume-title":"Algorithms and Data Structures","author":"P Bose","year":"2009","unstructured":"Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 98\u2013109. Springer, Heidelberg (2009)"},{"key":"45_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-642-03784-9_3","volume-title":"String Processing and Information Retrieval","author":"NR Brisaboa","year":"2009","unstructured":"Brisaboa, N.R., Ladra, S., Navarro, G.: k$$^2$$-trees for compact web graph representation. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 18\u201330. Springer, Heidelberg (2009)"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Fast algorithms for the all nearest neighbors problem. In: Proc. 24th FOCS, vol. 83, pp. 226\u2013232 (1983)","DOI":"10.1109\/SFCS.1983.16"},{"issue":"2","key":"45_CR11","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D Comer","year":"1979","unstructured":"Comer, D.: Ubiquitous B-tree. ACM CSUR 11(2), 121\u2013137 (1979)","journal-title":"ACM CSUR"},{"issue":"1","key":"45_CR12","first-page":"67","volume":"28","author":"C Dick","year":"2009","unstructured":"Dick, C., Schneider, J., Westermann, R.: Efficient geometry compression for gpu-based decoding in realtime terrain rendering. CGF 28(1), 67\u201383 (2009)","journal-title":"CGF"},{"issue":"4","key":"45_CR13","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1145\/322217.322228","volume":"27","author":"PJ Downey","year":"1980","unstructured":"Downey, P.J., Sethi, R., Tarjan, R.E.: Variations on the common subexpression problem. J. ACM 27(4), 758\u2013771 (1980)","journal-title":"J. ACM"},{"key":"45_CR14","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Goodrich, M.T., Sun, J.Z.: Skip quadtrees: Dynamic data structures for multidimensional point sets. IJCGA 18(01n02), 131\u2013160 (2008)","DOI":"10.1142\/S0218195908002568"},{"issue":"1","key":"45_CR15","first-page":"1","volume":"47","author":"A Farzan","year":"2014","unstructured":"Farzan, A., Gagie, T., Navarro, G.: Entropy-bounded representation of point grids. CGTA 47(1), 1\u201314 (2014)","journal-title":"CGTA"},{"issue":"2","key":"45_CR16","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"V Gaede","year":"1998","unstructured":"Gaede, V., G\u00fcnther, O.: Multidimensional access methods. ACM CSUR 30(2), 170\u2013231 (1998)","journal-title":"ACM CSUR"},{"key":"45_CR17","unstructured":"Galli, N., Seybold, B., Simon, K.: Compression of sparse matrices: Achieving almost minimal table size. In: Proc. ALEX, pp. 27\u201333 (1998)"},{"key":"45_CR18","doi-asserted-by":"crossref","unstructured":"Alvarez Garcia, S., Brisaboa, N.R., de Bernardo, G., Navarro, G.: Interleaved k2-tree: indexing and navigating ternary relations. In: Proc. DCC, pp. 342\u2013351 (2014)","DOI":"10.1109\/DCC.2014.56"},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proc. 1984 ACM SIGMOD, vol. 14, pp. 47\u201357 (1984)","DOI":"10.1145\/971697.602266"},{"issue":"4","key":"45_CR20","first-page":"1479","volume":"29","author":"S Haegler","year":"2010","unstructured":"Haegler, S., Wonka, P., Arisona, S.M., Van Gool, L., Mueller, P.: Grammar-based encoding of facades. CGF 29(4), 1479\u20131487 (2010)","journal-title":"CGF"},{"key":"45_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/3-540-49257-7_17","volume-title":"Database Theory - ICDT\u201999","author":"KVR Kanth","year":"1998","unstructured":"Kanth, K.V.R., Singh, A.K.: Optimal dynamic range searching in non-replicating index structures. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 257\u2013276. Springer, Heidelberg (1998)"},{"issue":"1\u20136","key":"45_CR22","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1007\/BF01759075","volume":"6","author":"MJ van Kreveld","year":"1991","unstructured":"van Kreveld, M.J., Overmars, M.H.: Divided k-d trees. Algorithmica 6(1\u20136), 840\u2013858 (1991)","journal-title":"Algorithmica"},{"issue":"3","key":"45_CR23","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1145\/320613.320618","volume":"5","author":"D Lee","year":"1980","unstructured":"Lee, D., Wong, C.: Quintary trees: a file structure for multidimensional datbase sytems. ACM TODS 5(3), 339\u2013353 (1980)","journal-title":"ACM TODS"},{"key":"45_CR24","doi-asserted-by":"crossref","unstructured":"Lueker, G.S.: A data structure for orthogonal range queries. In: Proc. 19th FOCS, pp. 28\u201334 (1978)","DOI":"10.1109\/SFCS.1978.1"},{"issue":"3","key":"45_CR25","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. TCS 387(3), 332\u2013347 (2007)","journal-title":"TCS"},{"issue":"4","key":"45_CR26","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0020-0190(82)90027-8","volume":"14","author":"JA Orenstein","year":"1982","unstructured":"Orenstein, J.A.: Multidimensional tries used for associative searching. Inform. Process. Lett. 14(4), 150\u2013157 (1982)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"45_CR27","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1109\/83.826774","volume":"9","author":"R Pajarola","year":"2000","unstructured":"Pajarola, R., Widmayer, P.: An image compression method for spatial search. IEEE Trans. Image Processing 9(3), 357\u2013365 (2000)","journal-title":"IEEE Trans. Image Processing"},{"key":"45_CR28","doi-asserted-by":"crossref","unstructured":"Procopiuc, O., Agarwal, P.K., Arge, L., Vitter, J.S.: Bkd-tree: a dynamic scalable kd-tree. In: Proc. 8th SSTD, pp. 46\u201365 (2003)","DOI":"10.1007\/978-3-540-45072-6_4"},{"key":"45_CR29","doi-asserted-by":"crossref","unstructured":"Robinson, J.T.: The KDB-tree: a search structure for large multidimensional dynamic indexes. In: Proc. 1981 ACM SIGMOD, pp. 10\u201318 (1981)","DOI":"10.1145\/582318.582321"},{"key":"45_CR30","doi-asserted-by":"crossref","unstructured":"Samet, H.: Applications of spatial data structures. Addison-Wesley (1990)","DOI":"10.1007\/3-540-52208-5_28"},{"key":"45_CR31","doi-asserted-by":"crossref","unstructured":"Schindler, G., Krishnamurthy, P., Lublinerman, R., Liu, Y., Dellaert, F.: Detecting and matching repeated patterns for automatic geo-tagging in urban environments. In: CVPR, pp. 1\u20137 (2008)","DOI":"10.1109\/CVPR.2008.4587461"},{"issue":"1","key":"45_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0165-0270(00)00336-8","volume":"105","author":"IV Tetko","year":"2001","unstructured":"Tetko, I.V., Villa, A.E.: A pattern grouping algorithm for analysis of spatiotemporal patterns in neuronal spike trains. J. Neurosci. Meth. 105(1), 1\u201314 (2001)","journal-title":"J. Neurosci. Meth."},{"key":"45_CR33","unstructured":"Zhu, Q., Yao, X., Huang, D., Zhang, Y.: An Efficient Data Management Approach for Large Cyber-City GIS. ISPRS Archives, 319\u2013323 (2002)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T04:15:27Z","timestamp":1676434527000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}