{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:17:54Z","timestamp":1725484674328},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434009"},{"type":"electronic","value":"9783540459958"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45995-2_20","type":"book-chapter","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T22:33:34Z","timestamp":1180478014000},"page":"181-195","source":"Crossref","is-referenced-by-count":13,"title":["A Metric Index for Approximate String Matching"],"prefix":"10.1007","author":[{"given":"Edgar","family":"Ch\u00e1vez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,14]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"A. Apostolico. The myriad virtues of subword trees. In Combinatorial Algorithms on Words, NATO ISI Series, pages 85\u201396. Springer-Verlag, 1985.","DOI":"10.1007\/978-3-642-82456-2_6"},{"key":"20_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-82456-2","volume-title":"Combinatorial Algorithms on Words","author":"A. Apostolico","year":"1985","unstructured":"A. Apostolico and Z. Galil. Combinatorial Algorithms on Words. Springer-Verlag, New York, 1985."},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"R. Baeza-Yates and G. Navarro. Block-addressing indices for approximate text retrieval. In Proc. ACM CIKM\u201997, pages 1\u20138, 1997.","DOI":"10.1145\/266714.266719"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"R. Baeza-Yates and G. Navarro. Fast approximate string matching in a dictionary. In Proc. SPIRE\u201998, pages 14\u201322. IEEE Computer Press, 1998.","DOI":"10.1109\/SPIRE.1998.712978"},{"key":"20_CR5","unstructured":"R. Baeza-Yates and G. Navarro. A practical q-gram index for text retrieval allowing errors. CLEI Electronic Journal, 1(2), 1998. http:\/\/www.clei.cl ."},{"issue":"1","key":"20_CR6","first-page":"205","volume":"1","author":"R. Baeza-Yates","year":"2000","unstructured":"R. Baeza-Yates and G. Navarro. A hybrid indexing method for approximate string matching. J. of Discrete Algorithms (JDA), 1(1):205\u2013239, 2000. Special issue on Matching Patterns.","journal-title":"J. of Discrete Algorithms (JDA)"},{"issue":"2","key":"20_CR7","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/93605.98741","volume":"19","author":"Norbert Beckmann","year":"1990","unstructured":"N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In Proc. ACM SIGMOD\u201990, pages 322\u2013331, 1990.","journal-title":"ACM SIGMOD Record"},{"key":"20_CR8","unstructured":"E. Bugnion, T. Roos, F. Shi, P. Widmayer, and F. Widmer. Approximate multiple string matching using spatial indexes. In Proc. 1st South American Workshop on String Processing (WSP\u201993), pages 43\u201354, 1993."},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"E. Ch\u00e1vez and G. Navarro. An effective clustering algorithm to index high dimensional metric spaces. In Proc. SPIRE\u20192000, pages 75\u201386. IEEE CS Press, 2000.","DOI":"10.1109\/SPIRE.2000.878182"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"E. Ch\u00e1vez, G. Navarro, R. Baeza-Yates, and J. Marroqu\u00edn. Searching in metric spaces. ACM Comp. Surv., 2001. To appear.","DOI":"10.1145\/502807.502808"},{"key":"20_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/3-540-60044-2_33","volume-title":"Fast approximate matching using suffix trees","author":"A. Cobbs","year":"1995","unstructured":"A. Cobbs. Fast approximate matching using suffix trees. In Proc. CPM\u201995, pages 41\u201354, 1995. LNCS 937."},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"45","author":"M. Crochemore","year":"1986","unstructured":"M. Crochemore. Transducers and repetitions. Theor. Comp. Sci., 45:63\u201386, 1986.","journal-title":"Theor. Comp. Sci."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"C. Faloutsos and I. Kamel. Beyond uniformity and independence: analysis of Rtrees using the concept of fractal dimension. In Proc. ACM PODS\u201994, pages 4\u201313, 1994.","DOI":"10.1145\/182591.182593"},{"issue":"2","key":"20_CR14","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"V. Gaede","year":"1998","unstructured":"V. Gaede and O. G\u00fcnther. Multidimensional access methods. ACM Comp. Surv., 30(2):170\u2013231, 1998.","journal-title":"ACM Comp. Surv."},{"key":"20_CR15","series-title":"Technical report","volume-title":"A tutorial introduction to Computational Biochemistry using Darwin","author":"G. Gonnet","year":"1992","unstructured":"G. Gonnet. A tutorial introduction to Computational Biochemistry using Darwin. Technical report, Informatik E.T.H., Zuerich, Switzerland, 1992."},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"A. Guttman. R-trees: a dynamic index structure for spatial searching. In Proc. ACM SIGMOD\u201984, pages 47\u201357, 1984.","DOI":"10.1145\/602259.602266"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"P. Jokinen and E. Ukkonen. Two algorithms for approximate string matching in static texts. In Proc. MFCS\u201991, volume 16, pages 240\u2013248, 1991.","DOI":"10.1007\/3-540-54345-7_67"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"I. Kamel and C. Faloutsos. On packing R-trees. In Proc. ACM CIKM\u201993, pages 490\u2013499, 1993.","DOI":"10.1145\/170088.170403"},{"key":"20_CR19","first-page":"8","volume":"1","author":"V. Levenshtein","year":"1965","unstructured":"V. Levenshtein. Binary codes capable of correcting spurious insertions and deletions of ones. Problems of Information Transmission, 1:8\u201317, 1965.","journal-title":"Problems of Information Transmission"},{"issue":"5","key":"20_CR20","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"Udi Manber","year":"1993","unstructured":"U. Manber and E. Myers. Suffix arrays: a new method for on-line string searches. SIAM J. on Computing, pages 935\u2013948, 1993.","journal-title":"SIAM Journal on Computing"},{"key":"20_CR21","unstructured":"U. Manber and S. Wu. glimpse: A tool to search through entire file systems. In Proc. USENIX Technical Conference, pages 23\u201332, Winter 1994."},{"issue":"2","key":"20_CR22","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E. McCreight","year":"1976","unstructured":"E. McCreight. A space-economical suffix tree construction algorithm. J. of the ACM, 23(2):262\u2013272, 1976.","journal-title":"J. of the ACM"},{"issue":"4","key":"20_CR23","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D. Morrison","year":"1968","unstructured":"D. Morrison. PATRICIA-practical algorithm to retrieve information coded in alphanumeric. J. of the ACM, 15(4):514\u2013534, 1968.","journal-title":"J. of the ACM"},{"key":"20_CR24","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF01185432","volume":"12","author":"E. Myers","year":"1994","unstructured":"E. Myers. A sublinear algorithm for approximate keyword searching. Algorithmica, 12(4\/5):345\u2013374, Oct\/Nov 1994.","journal-title":"Algorithmica"},{"issue":"1","key":"20_CR25","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"G. Navarro. A guided tour to approximate string matching. ACM Comp. Surv., 33(1):31\u201388, 2001.","journal-title":"ACM Comp. Surv."},{"key":"20_CR26","unstructured":"B. Pagel, H. Six, H. Toben, and P. Widmayer. Towards an analysis of range queries. In Proc. ACM PODS\u201993, pages 241\u2013221, 1993."},{"issue":"4","key":"20_CR27","first-page":"343","volume":"4","author":"D. Papadias","year":"1997","unstructured":"D. Papadias, Y. Theodoridis, and E. Stefanakis. Multidimensional range queries with spatial relations. Geographical Systems, 4(4):343\u2013365, 1997.","journal-title":"Geographical Systems"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"J. Robinson. The K-D-B-tree: a search structure for large multidimensional dynamic indexes. In Proc. ACM PODS\u201981, pages 10\u201318, 1981.","DOI":"10.1145\/582318.582321"},{"key":"20_CR29","unstructured":"R. Sedgewick and P. Flajolet. Analysis of Algorithms. Addison-Wesley, 1996."},{"key":"20_CR30","unstructured":"F. Shi. Fast approximate string matching with q-blocks sequences. In Proc. WSP\u201996, pages 257\u2013271. Carleton University Press, 1996."},{"key":"20_CR31","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/3-540-61258-0_4","volume-title":"Filtration with q-samples in approximate string matching","author":"E. Sutinen","year":"1996","unstructured":"E. Sutinen and J. Tarhio. Filtration with q-samples in approximate string matching. In Proc. CPM\u201996, LNCS 1075, pages 50\u201361, 1996."},{"key":"20_CR32","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Probabilistic analysis of generalized suffix trees","author":"W. Szpankowski","year":"1992","unstructured":"W. Szpankowski. Probabilistic analysis of generalized suffix trees. In Proc. CPM\u201992, LNCS 644, pages 1\u201314, 1992."},{"key":"20_CR33","doi-asserted-by":"crossref","unstructured":"Y. Thedoridis and T. Sellis. A model for the prediction of R-tree performance. In Proc. ACM PODS\u201996, pages 161\u2013171, 1996.","DOI":"10.1145\/237661.237705"},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"E. Ukkonen. Approximate string matching over suffix trees. In Proc. CPM\u201993, pages 228\u2013242, 1993.","DOI":"10.1007\/BFb0029808"},{"issue":"3","key":"20_CR35","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"E. Ukkonen. Constructing suffix trees on-line in linear time. Algorithmica, 14(3):249\u2013260, 1995.","journal-title":"Algorithmica"},{"key":"20_CR36","unstructured":"D. White and R. Jain. Algorithms and strategies for similarity retrieval. Technical Report VCL-96-101, Visual Comp. Lab., Univ. of California, July 1996."}],"container-title":["Lecture Notes in Computer Science","LATIN 2002: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45995-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T08:30:40Z","timestamp":1556440240000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45995-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434009","9783540459958"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-45995-2_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}