{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T01:50:47Z","timestamp":1676944247981},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,1,7]],"date-time":"2014-01-07T00:00:00Z","timestamp":1389052800000},"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,6]]},"DOI":"10.1007\/s00453-013-9863-3","type":"journal-article","created":{"date-parts":[[2014,1,6]],"date-time":"2014-01-06T21:15:32Z","timestamp":1389042932000},"page":"515-538","source":"Crossref","is-referenced-by-count":4,"title":["Compressing Dictionary Matching Index via Sparsification Technique"],"prefix":"10.1007","volume":"72","author":[{"given":"Wing-Kai","family":"Hon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsung-Han","family":"Ku","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siu-Lung","family":"Tam","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":[[2014,1,7]]},"reference":[{"issue":"6","key":"9863_CR1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A. Aho","year":"1975","unstructured":"Aho, A., Corasick, M.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"9863_CR2","first-page":"534","volume-title":"Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS\u201998)","author":"S. Alstrup","year":"1998","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS\u201998), pp. 534\u2013544 (1998)"},{"key":"9863_CR3","first-page":"760","volume-title":"Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS\u201991)","author":"A. Amir","year":"1991","unstructured":"Amir, A., Farach, M.: Adaptive dictionary matching. In: Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS\u201991), pp. 760\u2013766 (1991)"},{"issue":"2","key":"9863_CR4","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/S0022-0000(05)80047-9","volume":"49","author":"A. Amir","year":"1994","unstructured":"Amir, A., Farach, M., Galil, Z., Giancarlo, R., Park, K.: Dynamic dictionary matching. J. Comput. Syst. Sci. 49(2), 208\u2013222 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9863_CR5","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1006\/inco.1995.1090","volume":"119","author":"A. Amir","year":"1995","unstructured":"Amir, A., Farach, M., Idury, R., Poutre, A.L., Schaffer, A.: Improved dynamic dictionary matching. Inf. Comput. 119(2), 258\u2013282 (1995)","journal-title":"Inf. Comput."},{"issue":"2","key":"9863_CR6","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1006\/jagm.2000.1104","volume":"37","author":"A. Amir","year":"2000","unstructured":"Amir, A., Keselman, D., Landau, G.M., Lewenstein, M., Lewenstein, N., Rodeh, M.: Text indexing and dictionary matching with one error. J. Algorithms 37(2), 309\u2013325 (2000)","journal-title":"J. Algorithms"},{"issue":"6","key":"9863_CR7","doi-asserted-by":"crossref","first-page":"1488","DOI":"10.1137\/S009753970240481X","volume":"32","author":"L. Arge","year":"2003","unstructured":"Arge, L., Vitter, J.S.: Optimal external memory interval management. SIAM J. Comput. 32(6), 1488\u20131508 (2003)","journal-title":"SIAM J. Comput."},{"key":"9863_CR8","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/978-3-642-13509-5_9","volume-title":"Proceedings of Symposium on Combinatorial Pattern Matching (CPM\u201910)","author":"D. Belazzougui","year":"2010","unstructured":"Belazzougui, D.: Succinct dictionary matching with no slowdown. In: Proceedings of Symposium on Combinatorial Pattern Matching (CPM\u201910), pp. 88\u2013100 (2010)"},{"key":"9863_CR9","first-page":"152","volume-title":"Proceedings of European Symposium on Algorithms (ESA\u201902)","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: Proceedings of European Symposium on Algorithms (ESA\u201902), pp.\u00a0152\u2013164 (2002)"},{"issue":"2","key":"9863_CR10","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2), 75\u201394 (2005)","journal-title":"J. Algorithms"},{"key":"9863_CR11","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1186810.1186812","volume":"3","author":"H.L. Chan","year":"2007","unstructured":"Chan, H.L., Hon, W.K., Lam, T.W., Sadakane, K.: Compressed indexes for dynamic text collections. ACM Trans. Algorithms 3, 2 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9863_CR12","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1109\/DCC.2008.67","volume-title":"Proceedings of IEEE Data Compression Conference (DCC\u201908)","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 IEEE Data Compression Conference (DCC\u201908), pp.\u00a0252\u2013261 (2008)"},{"key":"9863_CR13","first-page":"91","volume-title":"Proceedings of ACM Symposium on Theory of Computing (STOC\u201904)","author":"R. Cole","year":"2004","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of ACM Symposium on Theory of Computing (STOC\u201904), pp. 91\u2013100 (2004)"},{"key":"9863_CR14","first-page":"365","volume-title":"Proceedings of ACM Symposium on Theory of Computing (STOC\u201987)","author":"P.F. Dietz","year":"1987","unstructured":"Dietz, P.F., Sleator, D.D.: Two algorithms for maintaining order in a list. In: Proceedings of ACM Symposium on Theory of Computing (STOC\u201987), pp. 365\u2013372 (1987)"},{"issue":"2","key":"9863_CR15","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 search in external memory and its applications. J. ACM 46(2), 236\u2013280 (1999)","journal-title":"J. ACM"},{"issue":"4","key":"9863_CR16","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"},{"issue":"1","key":"9863_CR17","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"372","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theor. Comput. Sci. 372(1), 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9863_CR18","first-page":"483","volume-title":"Proceedings of ACM Symposium on Theory of Computing (STOC\u201999)","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Muthukrishnan, S., de Berg, M.: Multi-method dispatching: a geometric approach with applications to string matching problems. In: Proceedings of ACM Symposium on Theory of Computing (STOC\u201999), pp. 483\u2013491 (1999)"},{"issue":"2","key":"9863_CR19","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J. Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9863_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."},{"issue":"1","key":"9863_CR21","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms 41(1), 69\u201385 (2001)","journal-title":"J. Algorithms"},{"key":"9863_CR22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1109\/DCC.2008.62","volume-title":"Proceedings of IEEE Data Compression Conference (DCC\u201908)","author":"W.K. Hon","year":"2008","unstructured":"Hon, W.K., Lam, T.W., Shah, R., Tam, S.L., Vitter, J.S.: Compressed index for dictionary matching. In: Proceedings of IEEE Data Compression Conference (DCC\u201908), pp. 23\u201332 (2008)"},{"key":"9863_CR23","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 (SPIRE\u201909)","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 (SPIRE\u201909), pp. 75\u201389 (2009)"},{"key":"9863_CR24","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/978-3-642-16321-0_19","volume-title":"Proceedings of International Symposium on String Processing and Information Retrieval (SPIRE\u201910)","author":"W.K. Hon","year":"2010","unstructured":"Hon, W.K., Ku, T.H., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster compressed dictionary matching. In: Proceedings of International Symposium on String Processing and Information Retrieval (SPIRE\u201910), pp. 191\u2013200 (2010)"},{"key":"9863_CR25","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 (COCOON\u201996)","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 (COCOON\u201996), pp. 219\u2013230 (1996)"},{"issue":"5","key":"9863_CR26","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":"9863_CR27","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"},{"issue":"2","key":"9863_CR28","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E.M. McCreight","year":"1985","unstructured":"McCreight, E.M.: Priority search trees. SIAM J. Comput. 14(2), 257\u2013276 (1985)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9863_CR29","doi-asserted-by":"crossref","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. J. Algorithms 9(2), 254\u2013275 (1988)","journal-title":"J. Algorithms"},{"issue":"4","key":"9863_CR30","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst. 41(4), 589\u2013607 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9863_CR31","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":"9863_CR32","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 \u0398(N). Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9863-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9863-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9863-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,5]],"date-time":"2019-08-05T22:36:31Z","timestamp":1565044591000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9863-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,7]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["9863"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9863-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,7]]}}}