{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T22:59:37Z","timestamp":1705013977175},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,5,10]],"date-time":"2013-05-10T00:00:00Z","timestamp":1368144000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,2]]},"DOI":"10.1007\/s00453-013-9792-1","type":"journal-article","created":{"date-parts":[[2013,5,9]],"date-time":"2013-05-09T19:42:12Z","timestamp":1368128532000},"page":"258-278","source":"Crossref","is-referenced-by-count":13,"title":["Geometric BWT: Compressed Text Indexing via Sparse Suffixes and Range Searching"],"prefix":"10.1007","volume":"71","author":[{"given":"Yu-Feng","family":"Chien","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wing-Kai","family":"Hon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,5,10]]},"reference":[{"key":"9792_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume":"23","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. Adv. Discret. Comput. Geom. 23, 1\u201356 (1999)","journal-title":"Adv. Discret. Comput. Geom."},{"issue":"9","key":"9792_CR2","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1998","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1998)","journal-title":"Commun. ACM"},{"issue":"2\u20133","key":"9792_CR3","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1023\/A:1012809914301","volume":"17","author":"W.G. Aref","year":"2001","unstructured":"Aref, W.G., Ilyas, I.F.: SP-GiST: an extensible database index for supporting space partitioning trees. J. Intell. Inf. Syst. 17(2\u20133), 215\u2013240 (2001)","journal-title":"J. Intell. Inf. Syst."},{"key":"9792_CR4","first-page":"160","volume-title":"Proceedings of Symposium on Computational Geometry","author":"L. Arge","year":"2005","unstructured":"Arge, L., Brodal, G.S., Fagerberg, R., Laustsen, M.: Cache-oblivious planar orthogonal range searching and counting. In: Proceedings of Symposium on Computational Geometry, pp. 160\u2013169 (2005)"},{"key":"9792_CR5","first-page":"346","volume-title":"Proceedings of Symposium on Principles of Database Systems","author":"L. Arge","year":"1999","unstructured":"Arge, L., Samoladas, V., Vitter, J.S.: Two-dimensional indexability and optimal range search indexing. In: Proceedings of Symposium on Principles of Database Systems, pp. 346\u2013357 (1999)"},{"key":"9792_CR6","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-540-73437-6_11","volume-title":"Proceedings of Symposium on Combinatorial Pattern Matching","author":"D. Arroyuelo","year":"2007","unstructured":"Arroyuelo, D., Navarro, G.: A Lempel-Ziv text index on secondary storage. In: Proceedings of Symposium on Combinatorial Pattern Matching, pp. 83\u201394 (2007)"},{"issue":"6","key":"9792_CR7","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1016\/0306-4379(96)00025-7","volume":"21","author":"R. Baeza-Yates","year":"1996","unstructured":"Baeza-Yates, R., Barbosa, E.F., Ziviani, N.: Hierarchies of indices for text searching. Inf. Syst. 21(6), 497\u2013514 (1996)","journal-title":"Inf. Syst."},{"key":"9792_CR8","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical report 124, Digital Equipment Corporation, Paolo Alto CA, USA (1994)"},{"key":"9792_CR9","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/77600.77614","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B.: Lower bounds for orthogonal range searching. I: The reporting case. J. ACM 37, 200\u2013212 (1990)","journal-title":"J. ACM"},{"key":"9792_CR10","first-page":"383","volume-title":"Proceedings of Symposium on Discrete Algorithms","author":"D. Clark","year":"1996","unstructured":"Clark, D., Munro, I.: Efficient suffix trees on secondary storage. In: Proceedings of Symposium on Discrete Algorithms, pp. 383\u2013391 (1996)"},{"key":"9792_CR11","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1109\/DCC.2008.67","volume-title":"Proceedings of Data Compression Conference","author":"Y.F. Chien","year":"2008","unstructured":"Chien, Y.F., Hon, W.K., Shah, R., Vitter, J.S.: Geometric Burrows-Wheeler transform: linking range searching and text indexing. In: Proceedings of Data Compression Conference, pp. 252\u2013261 (2008)"},{"key":"9792_CR12","first-page":"426","volume-title":"Proceedings of Data Compression Conference","author":"S.Y. Chiu","year":"2010","unstructured":"Chiu, S.Y., Hon, W.K., Shah, R., Vitter, J.S.: I\/O-efficient compressed text indexes: from theory to practice. In: Proceedings of Data Compression Conference, pp. 426\u2013434 (2010)"},{"issue":"2","key":"9792_CR13","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string B-tree: a new data structure for string searching in external memory and its application. J. ACM 46(2), 236\u2013280 (1999)","journal-title":"J. ACM"},{"issue":"4","key":"9792_CR14","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"9792_CR15","first-page":"690","volume-title":"Proceedings of Symposium on Discrete Algorithms","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. In: Proceedings of Symposium on Discrete Algorithms, pp. 690\u2013696 (2007)"},{"key":"9792_CR16","first-page":"327","volume-title":"Proceedings of Latin American Theoretical Informatics","author":"J. Fischer","year":"2012","unstructured":"Fischer, J., Gagie, T., Kopelowitz, T., Lewenstein, M., M\u00e4kinen, V., Salmela, L., V\u00e4lim\u00e4ki, N.N.: Forbidden patterns. In: Proceedings of Latin American Theoretical Informatics, pp. 327\u2013337 (2012)"},{"key":"9792_CR17","unstructured":"Gagie, T., Gawrychowski, P.: Linear-space substring range counting over polylogarithmic alphabets. (2012). CoRR. arXiv:1202.3208 [cs.DS]"},{"key":"9792_CR18","first-page":"80","volume-title":"Proceedings of International Workshop on Combinatorial Algorithms","author":"R. Gonz\u00e1lez","year":"2007","unstructured":"Gonz\u00e1lez, R., Navarro, G.: A compressed text index on secondary memory. In: Proceedings of International Workshop on Combinatorial Algorithms, pp. 80\u201391 (2007)"},{"key":"9792_CR19","first-page":"841","volume-title":"Proceedings of Symposium on Discrete Algorithms","author":"R. Grossi","year":"2003","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of Symposium on Discrete Algorithms, pp. 841\u2013850 (2003)"},{"issue":"2","key":"9792_CR20","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R. Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"9792_CR21","first-page":"47","volume-title":"Proceedings of International Conference on Management of Data","author":"A. Guttman","year":"1984","unstructured":"Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proceedings of International Conference on Management of Data, pp. 47\u201357 (1984)"},{"key":"9792_CR22","first-page":"562","volume-title":"Proceedings of International Conference on Very Large Data Bases","author":"J.M. Hellerstein","year":"1995","unstructured":"Hellerstein, J.M., Naughton, J.F., Pfeffer, A.: Generalized search trees for database systems. In: Proceedings of International Conference on Very Large Data Bases, pp. 562\u2013573 (1995)"},{"key":"9792_CR23","doi-asserted-by":"crossref","first-page":"1034","DOI":"10.1007\/978-3-642-10631-6_104","volume-title":"Proceedings of Symposium on Algorithms and Computation","author":"W.K. Hon","year":"2009","unstructured":"Hon, W.K., Lam, T.W., Shah, R., Lung, S.L., Vitter, J.S.: Succinct index for dynamic dictionary matching. In: Proceedings of Symposium on Algorithms and Computation, pp. 1034\u20131043 (2009)"},{"key":"9792_CR24","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1109\/DCC.2008.62","volume-title":"Proceedings of Data Compression Conference","author":"W.K. Hon","year":"2008","unstructured":"Hon, W.K., Lam, T.W., Shah, R., Lung, S.L., Vitter, J.S.: Compressed index for dictionary matching. In: Proceedings of Data Compression Conference, pp. 23\u201332 (2008)"},{"key":"9792_CR25","unstructured":"Hon, W.K., Shah, R., Vitter, J.S.: Ordered pattern matching: towards full-text retrieval. Technical report TR-06-008, Purdue University (2006)"},{"key":"9792_CR26","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-642-03784-9_8","volume-title":"Proceedings of International Symposium on String Processing and Information Retrieval","author":"W.K. Hon","year":"2009","unstructured":"Hon, W.K., Shah, R., Thankachan, S.V., Vitter, J.S.: On entropy-compressed text indexing in external memory. In: Proceedings of International Symposium on String Processing and Information Retrieval, pp. 75\u201389 (2009)"},{"key":"9792_CR27","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/978-3-642-24583-1_26","volume-title":"Proceedings of International Symposium on String Processing and Information Retrieval","author":"W.K. Hon","year":"2011","unstructured":"Hon, W.K., Ku, T.H., Shah, R., Thankachan, S.V., Vitter, J.S.: Compressed text indexing with wildcards. In: Proceedings of International Symposium on String Processing and Information Retrieval, pp. 267\u2013277 (2011)"},{"key":"9792_CR28","first-page":"113","volume-title":"Proceedings of Data Compression Conference","author":"W.K. Hon","year":"2011","unstructured":"Hon, W.K., Ku, T.H., Shah, R., Thankachan, S.V., Vitter, J.S.: Compressed dictionary matching with one errors. In: Proceedings of Data Compression Conference, pp. 113\u2013122 (2011)"},{"key":"9792_CR29","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/978-3-642-13509-5_24","volume-title":"Proceedings of Symposium on Combinatorial Pattern Matching","author":"W.K. Hon","year":"2010","unstructured":"Hon, W.K., Shah, R., Vitter, J.S.: Compression, indexing, and retrieval for massive string data. In: Proceedings of Symposium on Combinatorial Pattern Matching, pp. 260\u2013274 (2010)"},{"key":"9792_CR30","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/SFCS.1989.63533","volume-title":"Proceedings of Symposium on Foundations of Computer Science","author":"G. Jacobson","year":"1989","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of Symposium on Foundations of Computer Science, pp. 549\u2013554 (1989)"},{"key":"9792_CR31","first-page":"257","volume-title":"Proceedings of International Conference on Database Theory","author":"K.V.R. Kanth","year":"1999","unstructured":"Kanth, K.V.R., Singh, A.K.: Optimal dynamic range searching in non-replicating index structures. In: Proceedings of International Conference on Database Theory, pp. 257\u2013276 (1999)"},{"key":"9792_CR32","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/3-540-61332-3_155","volume-title":"Proceedings of International Conference on Computing and Combinatorics","author":"J. K\u00e4rkk\u00e4inen","year":"1996","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Sparse suffix trees. In: Proceedings of International Conference on Computing and Combinatorics, pp. 219\u2013230 (1996)"},{"key":"9792_CR33","volume-title":"International Conference on Data Compression, Communications and Processing","author":"R. Kolpakov","year":"2011","unstructured":"Kolpakov, R., Kucherov, G., Starikovskaya, T.A.: Pattern matching on sparse suffix trees. In: International Conference on Data Compression, Communications and Processing (2011). doi: 10.1109\/CCP.2011.45"},{"key":"9792_CR34","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Navarro, G.: Compressed full-text indexes. ACM Comput. Surv. 39(1) (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"9792_CR35","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Navarro, G.: Dynamic entropy-compressed sequences and full-text indexes. Technical report TR\/DCC-2006-10, University of Chile (2006)","DOI":"10.1007\/11780441_28"},{"key":"9792_CR36","first-page":"703","volume-title":"Proceedings of Latin American Theoretical Informatics Symposium","author":"V. M\u00e4kinen","year":"2006","unstructured":"M\u00e4kinen, V., Navarro, G.: Position-restricted substring searching. In: Proceedings of Latin American Theoretical Informatics Symposium, pp. 703\u2013714 (2006)"},{"key":"9792_CR37","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1007\/978-3-540-30551-4_59","volume-title":"Proceedings of Symposium on Algorithms and Computation","author":"V. M\u00e4kinen","year":"2004","unstructured":"M\u00e4kinen, V., Navarro, G., Sadakane, K.: Advantages of backward searching-efficient secondary memory and distributed implementation of compressed suffix arrays. In: Proceedings of Symposium on Algorithms and Computation, pp. 681\u2013692 (2004)"},{"issue":"5","key":"9792_CR38","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9792_CR39","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23(2), 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"9792_CR40","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Proceedings of Conference on Foundations of Software Technology and Theoretical Computer Science","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Proceedings of Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 37\u201342 (1996)"},{"issue":"4","key":"9792_CR41","first-page":"53","volume":"7","author":"L.M.S. Russo","year":"2011","unstructured":"Russo, L.M.S., Navarro, G., Oliveira, A.L.: Fully compressed suffix trees. ACM Trans. Algorithms 7(4), 53 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"9792_CR42","doi-asserted-by":"crossref","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst. 589\u2013607(2007)","DOI":"10.1007\/s00224-006-1198-x"},{"issue":"2","key":"9792_CR43","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1145\/356924.356930","volume":"16","author":"H. Samet","year":"1984","unstructured":"Samet, H.: The quadtree and related hierarchical data structures. ACM Comput. Surv. 16(2), 187\u2013260 (1984)","journal-title":"ACM Comput. Surv."},{"key":"9792_CR44","first-page":"378","volume-title":"Proceedings of Symposium on Discrete Algorithms","author":"S. Subramanian","year":"1995","unstructured":"Subramanian, S., Ramaswamy, S.: The P-range tree: a new data structure for range searching in secondary memory. In: Proceedings of Symposium on Discrete Algorithms, pp. 378\u2013387 (1995)"},{"key":"9792_CR45","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/978-3-642-24583-1_40","volume-title":"Proceedings of International Symposium on String Processing and Information Retrieval","author":"S.V. Thankachan","year":"2011","unstructured":"Thankachan, S.V.: Compressed indexes for aligned pattern matching. In: Proceedings of International Symposium on String Processing and Information Retrieval, pp. 410\u2013419 (2011)"},{"key":"9792_CR46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/SWAT.1973.13","volume-title":"Proceedings of Symposium on Switching and Automata Theory","author":"P. Weiner","year":"1973","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)"},{"issue":"2","key":"9792_CR47","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \u03b8(N). Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."},{"key":"9792_CR48","first-page":"96","volume-title":"Proceedings of International Computing and Combinatorics Conference","author":"C.C. Yu","year":"2009","unstructured":"Yu, C.C., Hon, W.K., Wang, B.F.: Efficient data structures for orthogonal range successor problem. In: Proceedings of International Computing and Combinatorics Conference, pp. 96\u2013105 (2009)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9792-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9792-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9792-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T16:28:20Z","timestamp":1563035300000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9792-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,10]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["9792"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9792-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,10]]}}}