Show simple item record

dc.contributor.advisorFox, Kyle
dc.creatorLi, Xinyi
dc.date.accessioned2019-10-04T00:07:26Z
dc.date.available2019-10-04T00:07:26Z
dc.date.created2019-05
dc.date.issued2019-05
dc.date.submittedMay 2019
dc.identifier.urihttps://hdl.handle.net/10735.1/6963
dc.description.abstractEdit distance is a measurement of similarity between two sequences such as strings, point sequences, or polygonal curves. Because many matching problems from a variety of areas, such as signal analysis, bioinformatics, etc., need to be solved in a geometric space, the geometric edit distance (GED) has been studied. In this thesis, we focus on approximating the GED between two point sequences. Previous work has proved that there is no O(n^{2−δ})(δ > 0) exact algorithm unless SETH fails. We present a randomized O(n log² n) time O(√n)-approximation algorithm. We then generalize our result to give a randomized α-approximation algorithm for any α ∈ [1, √n], running in time O˜(n²/α²). Both algorithms are Monte Carlo and return approximately optimal solutions with high probability.
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.rights©2019 Xinyl Li
dc.subjectSimilarity (Geometry)
dc.subjectApproximation algorithms
dc.subjectMonte Carlo method
dc.subjectMatching theory
dc.titleApproximating the Geometric Edit Distance
dc.typeThesis
dc.date.updated2019-10-04T00:09:36Z
dc.type.materialtext
dc.contributor.committeeMemberDaescu, Ovidiu
dc.contributor.committeeMemberRaichel, Benjamin
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.departmentComputer Science
thesis.degree.levelMasters
thesis.degree.nameMSCS


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record