http://www.bibsonomy.org/burst/concept/tag/editdistanceBibSonomy BuRST Feed for /concept/tag/editdistance2008-10-16T08:58:55+02:00http://www.bibsonomy.org/bibtex/22dc39ced734a4493e5b1b054b6795428/danieltdanielt2008-03-10T19:55:03+01:00distance dipl_literatur similarity <span style="color:#555555;">Inderjit S. <a href="http://www.bibsonomy.org/author/Dhillon">Dhillon</a> und Dharmendra S. <a href="http://www.bibsonomy.org/author/Modha">Modha</a> </span><em>Machine Learning</em><em>42(1/2):143--175</em>(<em>2001</em>)Mon Mar 10 19:55:03 CET 2008Machine Learning1/2143--175Concept Decompositions for Large Sparse Text Data Using Clustering422001distance dipl_literatur similarity dblphttp://www.bibsonomy.org/bibtex/2f1049d996acc0bed1a3cfcdc2a1ee47e/danieltdanielt2008-03-10T12:58:59+01:00dipl_literatur tree editdistance <span style="color:#555555;">Stanley M. <a href="http://www.bibsonomy.org/author/Selkow">Selkow</a> </span><em>Inf. Process. Lett.</em><em>6(6):184-186</em>(<em>1977</em>)Mon Mar 10 12:58:59 CET 2008Inf. Process. Lett.6184-186The Tree-to-Tree Editing Problem.61977dipl_literatur tree editdistance dblphttp://www.bibsonomy.org/bibtex/2804fda1b650f112384b3262902556222/danieltdanielt2008-03-10T12:19:41+01:00dipl_literatur tree editdistance <span style="color:#555555;">Sudarshan S. <a href="http://www.bibsonomy.org/author/Chawathe">Chawathe</a> </span><em>VLDB, </em><em>Seite90-101. </em><em>Morgan Kaufmann, </em>(<em>1999</em>)Mon Mar 10 12:19:41 CET 2008VLDBConfVldb9990-101Comparing Hierarchical Data in External Memory.1999dipl_literatur tree editdistance http://www.bibsonomy.org/bibtex/22e8ff52c47ffb2e9813491ea9c7cb649/danieltdanielt2008-03-06T09:14:06+01:00template dipl_literatur tree editdistance <span style="color:#555555;">Kuo-Chung <a href="http://www.bibsonomy.org/author/Tai">Tai</a> </span><em>J. ACM</em><em>26(3):422-433</em>(<em>1979</em>)Thu Mar 06 09:14:06 CET 2008J. ACM3422-433The Tree-to-Tree Correction Problem.261979template dipl_literatur tree editdistance http://www.bibsonomy.org/bibtex/2d108b63846ebdfe016a7166444290c89/danieltdanielt2008-03-05T15:33:36+01:00dipl_literatur editdistance <span style="color:#555555;">Vladimir <a href="http://www.bibsonomy.org/author/Levenshtein">Levenshtein</a> </span><em>Soviet Physics Doklady</em><em>10(8):707-710</em>(<em>1966</em>)Wed Mar 05 15:33:36 CET 2008Soviet Physics Doklady8707-710{Binary Codes Capable of Correcting Deletions and Insertions and Reversals}101966dipl_literatur editdistance http://www.bibsonomy.org/bibtex/291aa4f4f1204767f2806e5c6848774d8/danieltdanielt2008-03-05T15:18:08+01:00distance dipl_literatur tree parser <span style="color:#555555;">Gabriel <a href="http://www.bibsonomy.org/author/Valiente">Valiente</a> </span><em>SPIRE, </em><em>Seite212-219. </em>(<em>2001</em>)Wed Mar 05 15:18:08 CET 2008SPIRE212-219An Efficient Bottom-Up Distance between Trees2001distance dipl_literatur tree parser http://www.bibsonomy.org/bibtex/2178ed45db2e88dbe35ca2abd7775aa0f/danieltdanielt2008-03-05T15:17:59+01:00dipl_literatur tree parser <span style="color:#555555;">Karane <a href="http://www.bibsonomy.org/author/Vieira">Vieira</a> und Altigran S. <a href="http://www.bibsonomy.org/author/da Silva">da Silva</a> und Nick <a href="http://www.bibsonomy.org/author/Pinto">Pinto</a> und Edleno S. <a href="http://www.bibsonomy.org/author/de Moura">de Moura</a> und Joao M. B. <a href="http://www.bibsonomy.org/author/Cavalcanti">Cavalcanti</a> und Juliana <a href="http://www.bibsonomy.org/author/Freire">Freire</a> </span><em>CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management, </em><em>Seite258--267. </em><em>New York, NY, USA, </em><em>ACM Press, </em>(<em>2006</em>)Wed Mar 05 15:17:59 CET 2008New York, NY, USACIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management258--267A fast and robust method for web page template detection and removal2006dipl_literatur tree parser http://www.bibsonomy.org/bibtex/251b916d5e38002481b3530f7a97a2a2f/danieltdanielt2008-03-05T15:12:26+01:00template dipl_literatur tree editdistance <span style="color:#555555;">Dennis <a href="http://www.bibsonomy.org/author/Shasha">Shasha</a> und Kaizhong <a href="http://www.bibsonomy.org/author/Zhang">Zhang</a> </span><em>J. Algorithms</em><em>11(4):581-621</em>(<em>1990</em>)Wed Mar 05 15:12:26 CET 2008J. Algorithms4581-621Fast Algorithms for the Unit Cost Editing Distance Between Trees111990template dipl_literatur tree editdistance http://www.bibsonomy.org/bibtex/25aeaeb9b596d820181ec4488ad2cf9d6/danieltdanielt2008-03-05T15:12:08+01:00template dipl_literatur tree editdistance <span style="color:#555555;">Jason Tsong-Li <a href="http://www.bibsonomy.org/author/Wang">Wang</a> und Kaizhong <a href="http://www.bibsonomy.org/author/Zhang">Zhang</a> </span><em>Pattern Recognition</em><em>34(1):127-137</em>(<em>2001</em>)Wed Mar 05 15:12:08 CET 2008Pattern Recognition1127-137Finding similar consensus between trees: an algorithm and a distance hierarchy342001template dipl_literatur tree editdistance http://www.bibsonomy.org/bibtex/230af7cf6b221e46de3f6f4eca27900aa/tmalsburgtmalsburg2007-12-10T12:10:27+01:00vision perception scanpaths editdistance attention <span style="color:#555555;">Sheree <a href="http://www.bibsonomy.org/author/Josephson">Josephson</a> und Michael E. <a href="http://www.bibsonomy.org/author/Holmes">Holmes</a> </span><em>Proceedings of the symposium on Eye tracking research \&amp; applications</em>(<em>2002</em>)Mon Dec 10 12:10:27 CET 2007Proceedings of the symposium on Eye tracking research \& applications43--49{Visual attention to repeated internet images: testing the scanpath theory on the world wide web}2002vision perception scanpaths editdistance attention The somewhat controversial and often-discussed theory of visual perception, that of scanpaths, was tested using Web pages as visual stimuli. In 1971, Noton and Stark defined "scanpaths" as repetitive sequences of fixations and saccades that occur upon re-exposure to a visual stimulus, facilitating recognition of that stimulus. Since Internet users are repeatedly exposed to certain visual displays of information, the Web is an ideal stimulus to test this theory. Eye-movement measures were recorded while subjects repeatedly viewed three different kinds of Internet pages -- a portal page, an advertising page and a news story page -- over the course of a week. Scanpaths were compared by using the string-edit methodology that measures resemblance between sequences. Findings show that on the World Wide Web, with somewhat complex visual digital images, some viewers' eye movements may follow a habitually preferred path -- a scanpath -- across the visual display. In addition, strong similarity among eye-path sequences of different viewers may indicate that other forces such as features of the Web site or memory are important.A technique for computer detection and correction of spelling errorshttp://www.bibsonomy.org/bibtex/2668a64114d9dedf793cb2644e05dac14/tmalsburgtmalsburg2007-05-22T14:19:45+02:00stringsimilarity editdistance informationtheory B_scanpathsimilarity algorithm <span style="color:#555555;">Fred J. <a href="http://www.bibsonomy.org/author/Damerau">Damerau</a> </span><em>Commun. ACM</em><em>7(3):171--176</em>(<em>1964</em>)Tue May 22 14:19:45 CEST 2007New York, NY, USACommun. ACM3171--176A technique for computer detection and correction of spelling errors71964stringsimilarity editdistance informationtheory B_scanpathsimilarity algorithm Exact Indexing of Dynamic Time Warping - Keogh (ResearchIndex)http://www.bibsonomy.org/bibtex/2f20e09e3ada7200aed0d7cfb87096940/tmalsburgtmalsburg2007-02-17T12:59:51+01:00dynamictimewarping timeseries editdistance distancemeasure B_scanpathsimilarity <span style="color:#555555;">Eamonn <a href="http://www.bibsonomy.org/author/Keogh">Keogh</a> </span>(<em>2002</em>)Sat Feb 17 12:59:51 CET 2007Exact indexing of dynamic time warping2002dynamictimewarping timeseries editdistance distancemeasure B_scanpathsimilarity The problem of indexing time series has attracted much research interest in the database community. Most algorithms used to index time series utilize the Euclidean distance or some variation thereof. However is has been forcefully shown that the Euclidean distance is a very brittle distance measure. Dynamic Time Warping (DTW) is a much more robust distance measure for time series, allowing similar shapes to match even if they are out of phase in the time axis. Because of this flexibility, DTW is widely used in science, medicine, industry and finance. Unfortunately however, DTW does not obey the triangular inequality, and thus has resisted attempts at exact indexing. Instead, many researchers have introduced approximate indexing techniques, or abandoned the idea of indexing and concentrated on speeding up sequential search. In this work we introduce a novel technique for the exact indexing of DTW. We prove that our method guarantees no false dismissals and we demonstrate its vast superiority over all competing approaches in the largest and most comprehensive set of time series indexing experiments ever undertaken. about Levenshtein and Damerau editdistanz from dblphttp://www.bibsonomy.org/bibtex/27647daf53f3c46bff7ab25d918717763/tmalsburgtmalsburg2006-05-14T11:44:27+02:00stringsimilarity article editdistance toread B_scanpathsimilarity algorithm <span style="color:#555555;">Heikki <a href="http://www.bibsonomy.org/author/Hyyrö">Hyyr&#246;</a> </span><em>Nord. J. Comput.</em><em>10(1):29-39</em>(<em>2003</em>)Sun May 14 11:44:27 CEST 2006Nord. J. Comput.129-39A Bit-Vector Algorithm for Computing Levenshtein and Damerau Edit Distances.102003stringsimilarity article editdistance toread B_scanpathsimilarity algorithm The edit distance between strings A and B is defined as the minimum number of edit operations needed in converting A into B or vice versa. The Levenshtein edit distance allows three types of operations: an insertion, a deletion or a substitution of a character. The Damerau edit distance allows the previous three plus in addition a transposition between two adjacent characters. To our best knowledge the best current practical algorithms for computing these edit distances run in time O(dm) and O(⌈m/w⌉(n + σ)), where d is the edit distance between the two strings, m and n are their lengths (m ≤ n), w is the computer word size and σ is the size of the alphabet. In this paper we present an algorithm that runs in time O(⌈d/w⌉m + ⌈n/w⌉σ) or O(⌈d/w⌉n + ⌈m/w⌉σ). The structure of the algorithm is such, that in practice it is mostly suitable for testing whether the edit distance between two strings is within some pre-determined error threshold. We also present some initial test results with thresholded edit distance computation. In them our algorithm works faster than the original algorithm of Myers.