文章基本信息

标题：Approximating the Geometric Edit Distance
本地全文：下载
作者：Kyle Fox ; Xinyi Li
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：149
页码：1-16
DOI：10.4230/LIPIcs.ISAAC.2019.23
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Edit distance is a measurement of similarity between two sequences such as strings, point sequences, or polygonal curves. Many matching problems from a variety of areas, such as signal analysis, bioinformatics, etc., need to be solved in a geometric space. Therefore, the geometric edit distance (GED) has been studied. In this paper, we describe the first strictly sublinear approximate near-linear time algorithm for computing the GED of two point sequences in constant dimensional Euclidean space. Specifically, we present a randomized O(n log^2n) time O(sqrt n)-approximation algorithm. Then, we generalize our result to give a randomized alpha-approximation algorithm for any alpha in [1, sqrt n], running in time O~(n^2/alpha^2). Both algorithms are Monte Carlo and return approximately optimal solutions with high probability.
关键词：Geometric edit distance; Approximation; Randomized algorithms