{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T20:00:10Z","timestamp":1725912010449},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319684734"},{"type":"electronic","value":"9783319684741"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-68474-1_16","type":"book-chapter","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T15:15:48Z","timestamp":1506525348000},"page":"234-246","source":"Crossref","is-referenced-by-count":1,"title":["Practical Space-Efficient Data Structures for High-Dimensional Orthogonal Range Searching"],"prefix":"10.1007","author":[{"given":"Kazuki","family":"Ishiyama","sequence":"first","affiliation":[]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,9,28]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","first-page":"3.7","DOI":"10.1145\/1498698.1564507","volume":"14","author":"J Barbay","year":"2009","unstructured":"Barbay, J., L\u00f3pez-Ortiz, A., Lu, T., Salinger, A.: An experimental investigation of set intersection algorithms for text searching. ACM J. Exp. Algorithmics 14, 3.7\u20133.24 (2009)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"9","key":"16_CR2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JS Bentley","year":"1975","unstructured":"Bentley, J.S.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"issue":"5","key":"16_CR3","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"JS Bentley","year":"1979","unstructured":"Bentley, J.S.: Decomposable searching problems. Inf. Process. Lett. 8(5), 244\u2013251 (1979)","journal-title":"Inf. Process. Lett."},{"key":"16_CR4","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). doi: 10.1007\/978-3-642-03367-4_9"},{"issue":"3","key":"16_CR5","doi-asserted-by":"crossref","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 J. Comput. 17(3), 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"key":"16_CR6","unstructured":"Clark, D.: Compact pat trees. PhD thesis, University of Waterloo (1997)"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pp. 135\u2013143. ACM (1984)","DOI":"10.1145\/800057.808675"},{"key":"16_CR8","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.tcs.2011.12.002","volume":"426","author":"T Gagie","year":"2012","unstructured":"Gagie, T., Navarro, G., Puglisi, S.J.: New algorithms on wavelet trees and applications to information retrieval. Theoret. Comput. Sci. 426, 25\u201341 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-07959-2_28","volume-title":"Experimental Algorithms","author":"S Gog","year":"2014","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326\u2013337. Springer, Cham (2014). doi: 10.1007\/978-3-319-07959-2_28"},{"key":"16_CR10","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841\u2013850. Society for Industrial and Applied Mathematics (2003)"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Ishiyama, K., Sadakane, K.: A succinct data structure for multidimensional orthogonal range searching. In: Proceedings of Data Compression Conference 2017, pp. 270\u2013279. IEEE (to be published, 2017)","DOI":"10.1109\/DCC.2017.47"},{"key":"16_CR12","unstructured":"Jacobson, G.J.: Succinct static data structures. PhD thesis, Carnegie Mellon University (1988)"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/11682462_64","volume-title":"LATIN 2006: Theoretical Informatics","author":"V M\u00e4kinen","year":"2006","unstructured":"M\u00e4kinen, V., Navarro, G.: Position-restricted substring searching. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 703\u2013714. Springer, Heidelberg (2006). doi: 10.1007\/11682462_64"},{"key":"16_CR14","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.jda.2013.07.004","volume":"25","author":"G Navarro","year":"2014","unstructured":"Navarro, G.: Wavelet trees for all. J. Discrete Algorithms 25, 2\u201320 (2014)","journal-title":"J. Discrete Algorithms"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Okajima, Y., Maruyama, K.: Faster linear-space orthogonal range searching in arbitrary dimensions. In: ALENEX, pp. 82\u201393. SIAM (2015)","DOI":"10.1137\/1.9781611973754.8"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"O\u2019Rourke, J., Goodman, J.E.: Handbook of Discrete and Computational Geometry. CRC Press (2004)","DOI":"10.1201\/9781420035315"},{"issue":"4","key":"16_CR17","doi-asserted-by":"crossref","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 Trans. Algorithms (TALG) 3(4), 43 (2007)","journal-title":"ACM Trans. Algorithms (TALG)"}],"container-title":["Lecture Notes in Computer Science","Similarity Search and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68474-1_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,18]],"date-time":"2020-10-18T10:17:10Z","timestamp":1603016230000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68474-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319684734","9783319684741"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68474-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}