Metric Violation and Similarity

Simple item page
dc.contributor.advisorRaichel, Benjamin
dc.creatorFan, Chenglin
dc.date.accessioned2020-10-09T15:32:58Z
dc.date.available2020-10-09T15:32:58Z
dc.date.created2019-05
dc.date.issued2019-05
dc.date.submittedMay 2019
dc.date.updated2020-10-09T15:32:59Z
dc.description.abstractMetric data plays an important role in various settings, for example, in metric-based indexing, clustering, classification, and approximation algorithms in general. Often such tasks require the data to be metric, though for various reasons this basic property may not be satisfied. The first topic we consider is the metric violation distance problem, which seeks to minimally modify the data to make it metric, and thereby finding the nearest metric data set. Three variants are considered, one admitting a polynomial time algorithm. The other variants are shown to be APX-hard, and an approximation is given. We also introduce and give results for the generalized metric violation distance problem, where there are no longer constraints on all pairs. The second topic concerns the fundamental computational task of assessing the similarity of ordered data sets, i.e. the similarity of two trajectories. Here we introduce the Fréchet gap distance, which in some ways better captures the intuitive notions of curve similarity when comparing to the previous Standard Fréchet distance. In addition, a polynomial time exact algorithm and a much faster 1 + approximation to compute this measure will be given.
dc.description.sponsorshipNSF CRII Award 1566137 and CAREER Award 1750780
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/10735.1/8999
dc.language.isoen
dc.rights©2019 Chenglin Fan. All rights reserved.
dc.subjectSimilarity (Geometry)
dc.subjectData sets
dc.subjectFréchet spaces
dc.subjectComputer algorithms
dc.titleMetric Violation and Similarity
dc.typeDissertation
dc.type.materialtext
thesis.degree.departmentComputer Science
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.levelDoctoral
thesis.degree.namePHD

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
ETD-5608-011D-262073.66.pdf
Size:
947.51 KB
Format:
Adobe Portable Document Format
Description:
Dissertation
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
5.84 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download

Collections

UTD Theses and Dissertations