Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 150 for “"edit-distance"”.
-
Theory of graph traversal edit distance, extensions, and applications
… a new graph kernel which we call graph traversal edit distance (GTED). We introduce the GTED problem and give the first polynomial time algorithm for it. Informally, the graph traversal edit distance is the minimum edit distance between two strings formed by the edge labels of respective Eulerian …
-
Efficient String Similarity Search with an Edit Distance Threshold
… efficient exact query processing algorithms for edit similarity queries and their variants. An edit similarity query finds database strings within edit distance threshold t from the query string. It plays an important role in many application areas, such as deduplication, data integration and …
-
Fast edit distance calculation methods for NGS sequence similarity
… very large numbers of pairs of NGS sequences.The edit distance has been widely used to determine the dissimilarity between pairs of strings. All the known methods for the edit distance calculation run in near quadratic time with respect to string lengths, and it may take days or weeks to compute …
-
Spotting Keywords in Offline Handwritten Documents Using Hausdorff Edit Distance
… due to high computational costs. The graph edit distance, a powerful and versatile method for matching any type of labeled graph, has exponential time complexity to calculate the similarities of graphs. Hence, the use of graph edit distance is constrained to small size graphs. The recently …
-
Pseudorandom Constructions: Computing in Parallel and Applications to Edit Distance Codes
… to build error correcting codes (ECCs) for edit distance. ECCs project messages to codewords in a metric space s.t. one can recover the codewords even if there are bounded number of errors which can drive the codeword away by some bounded distance. They are widely used in both the …
-
SYNTACTIC DIFFERENCE SCORE: EDIT DISTANCE METRIC FOR EVALUATING FIREWALL POLICY INFERENCE
… Score (SDS), a novel metric inspired by edit distance algorithms that quantifies the structural dissimilarity of two firewall rule sets, to provide a more efficient method for evaluating inference accuracy with the objective of investigating whether SDS can meaningfully predict behavioral …
-
On the edit distance from a cycle- and squared cycle-free graph
<p>The edit distance from a hereditary property is the fraction of edges in a graph that must be added or deleted for a graph to become a member of that hereditary property. Let Forb(<em>C<sub>h</sub></em>) and Forb(<em>C<sup>2</sup><sub>h</sub></em>) denote the hereditary properties containing …
-
The edit distance function: Forbidding induced powers of cycles and other questions
<p>The edit distance between two graphs on the same labeled vertex set is defined to be the size of the symmetric difference of the edge sets. The edit distance between a graph, $G$, and a graph property, $\mathcal{H}$, is the minimum edit distance between $G$ and a graph in $\mathcal{H}$. The edit …
-
The edit distance function for graphs: an exploration of the case of forbidden induced K<sub>2,t</sub> and other questions
<p>This thesis examines the edit distance function for principal hereditary properties of the form Forb(K<sub>2,t</sub>), the hereditary property of graphs containing no induced bipartite subgraph on 2 and t vertices. It explores applications of several methods from the literature for determining …
-
Efficient String and Graph Algorithms in Modern Settings
Fundamental computer science problems such as edit distance have been well-studied for decades, and algorithms for these problems have become established and widespread. In modern times, however, achieving even faster algorithms for more specific scenarios finds increasing value as dataset sizes …
-
Automated Grading and Feedback of Regular Expressions
… of evaluating regexes. We call this the regex edit distance. The idea behind this is to find the minimal changes that we could make in a wrong answer to make its language equivalent to that of a correct answer. This approach is along the lines of the one used by Automata Tutor to grade DFAs. We …
-
Web Document Classification Using Edit Distances Between XML Document & Schemata
… of structural similarity between documents. Tree edit distance would be a misleading measure of similarity for documents having similar structure but a large difference in size – the edit distance would be high owing to the size difference. Schema would be a much better representation of document …
-
Enhancing License Plate Matching Algorithm: A New Evaluation Measurement and Threshold Determination
… to automated. The text-mining technique of edit distance has been crucial to this improvement. Edit distance is not without limitations, such as determining a threshold, intuitiveness of the measurement, and character length issues.</p> <p>This paper proposes an alternative evaluation method …
-
Efficient sequence comparison via combining alignment and alignment-free techniques: algorithms and bioinformatics research
… involving textual representations of data. Edit distance is the most widely used measure to quantify the similarity of two sequences. Edit distance can be defined as the minimal total cost of a sequence of edit operations required to transform one sequence into the other. <br/>The motivation …
-
Techniques for Automatic Normalization of Orthographically Variant Yiddish Texts
… rules, an off-the-shelf spell checker, edit distance minimization with manually set weights, and edit distance minimization with weights learned through a training set. Performance was evaluated by calculating the proportion of correctly normalized words in a test set, and by measuring …
-
Temporal Graph Record Linkage and k-Safe Approximate Match
… this multi-data without redundancy and use edit-distance for approximate string matching. However, due to high computational complexity, edit-distance will not scale well with big data problems. We developed two methodologies for resolving the aforementioned issues: PSH and ALIM. PSH – The …
-
Exploring word and sentence similarity in corpus
… and iterative. The system combines the Edit distance and the incremental results as a way for accurate similarity measure. Moreover, a sentence similarity system is developed on top of the word similarity model. Naturally, the proposed model rests on observing the words behavior in large …
-
Effects of OCR errors on text categorization
… process. This algorithm is based on edit distance techniques and information from highly weighted words in the categorizers.
-
USE OF LANGUAGE TECHNOLOGY TO IMPROVE MATCHING AND RETRIEVAL IN TRANSLATION MEMORY
… did not retrieve better matches than simple edit-distance. Two approaches for retrieving segments from a TM using deep learning are investigated. The first one is based on Long Short Term Memory (LSTM) networks, while the other one is based on Tree Structured Long Short Term Memory …
-
Shakespeare in the Eighteenth Century: Algorithm for Quotation Identification
… to identifying modified quotes by adapting the Edit Distance metric, which is character based, to a word based approach. This paper offers an introduction to previous uses of this metric within a multitude of fields, describes the implementation of the different methodologies used for quote …
Page 1 of 8