Document Open Access Logo

Approximating the Geometric Edit Distance

Authors Kyle Fox, Xinyi Li

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.23.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Kyle Fox
  • The University of Texas at Dallas, USA
Xinyi Li
  • The University of Texas at Dallas, USA

Acknowledgements

The authors would like to thank Anne Driemel and Benjamin Raichel for helpful discussions.

Cite AsGet BibTex

Kyle Fox and Xinyi Li. Approximating the Geometric Edit Distance. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.23

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Computational geometry
Keywords
  • Geometric edit distance
  • Approximation
  • Randomized algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, pages 59-78, 2015. Google Scholar
  2. Pankaj K Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating dynamic time warping and edit distance for a pair of point sequences. In Proceedings of the 32nd International Symposium on Computational Geometry, pages 6:1-6:16, 2016. Google Scholar
  3. Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Polylogarithmic approximation for edit distance and the asymmetric query complexity. In Proceedings of the IEEE 51st Annual Symposium on Foundations of Computer Science, pages 377-386, 2010. Google Scholar
  4. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 51-58, 2015. Google Scholar
  5. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, pages 661-670, 2014. Google Scholar
  6. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, pages 79-97, 2015. Google Scholar
  7. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. JoCG, 7(2):46-76, 2016. Google Scholar
  8. Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucky, and Michael Saks. Approximating edit distance within constant factor in truly sub-quadratic time. In Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 979-990. IEEE, 2018. Google Scholar
  9. Timothy M Chan and Zahed Rahmati. An improved approximation algorithm for the discrete Fréchet distance. Information Processing Letters, pages 72-74, 2018. Google Scholar
  10. Lei Chen and Raymond Ng. On the marriage of Lp-norms and edit distance. In Proceedings of the 30th International Conference on Very Large Databases, pages 792-803, 2004. Google Scholar
  11. Lei Chen, M Tamer Özsu, and Vincent Oria. Robust and fast similarity search for moving object trajectories. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, pages 491-502, 2005. Google Scholar
  12. Omer Gold and Micha Sharir. Dynamic time warping and geometric edit distance: Breaking the quadratic barrier. ACM Transactions on Algorithms, 14(4):50, 2018. Google Scholar
  13. Sariel Har-Peled. Geometric approximation algorithms, chapter 11, Random Partition via Shifting, pages 151-162. American Mathematical Soc., 2011. Google Scholar
  14. William Kuszmaul. Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation. In Proceedings of the 46th International Colloquium on Automata, Languages and Programming, 2019. Google Scholar
  15. Gad M Landau, Eugene W Myers, and Jeanette P Schmidt. Incremental string comparison. SIAM Journal on Computing, 27(2):557-582, 1998. Google Scholar
  16. Pierre-François Marteau. Time warp edit distance with stiffness adjustment for time series matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(2):306-318, 2009. Google Scholar
  17. William J Masek and Michael S Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18-31, 1980. Google Scholar
  18. Swaminathan Sankararaman, Pankaj K Agarwal, Thomas Mølhave, Jiangwei Pan, and Arnold P Boedihardjo. Model-driven matching and segmentation of trajectories. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 234-243, 2013. Google Scholar
  19. Aleksandar Stojmirovic and Yi-kuo Yu. Geometric aspects of biological sequence comparison. Journal of Computational Biology, 16(4):579-611, 2009. Google Scholar
  20. Esko Ukkonen. Algorithms for approximate string matching. Information and Control, 64(1-3):100-118, 1985. Google Scholar
  21. Robert A Wagner and Michael J Fischer. The string-to-string correction problem. Journal of the ACM, 21(1):168-173, 1974. Google Scholar
  22. Xiaoyue Wang, Abdullah Mueen, Hui Ding, Goce Trajcevski, Peter Scheuermann, and Eamonn Keogh. Experimental comparison of representation methods and distance measures for time series data. Data Mining and Knowledge Discovery, 26(2):275-309, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact