The closest pair problem under the hamming metric

Kerui Min*, Ming-Yang Kao, Hong Zhu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

Finding the closest pair among a given set of points under Hamming Metric is a fundamental problem with many applications. Let n be the number of points and D the dimensionality of all points. We show that for 0<D≤n 0.294, the problem, with the binary alphabet set, can be solved within time complexity , whereas for n 0.294<D≤n, it can be solved within time complexity . We also provide an alternative approach not involving algebraic matrix multiplication, which has the time complexity with small constant, and is effective for practical use. Moreover, for arbitrary large alphabet set, an algorithm with the time complexity is obtained for 0<D≤n 0.294, whereas the time complexity is for n 0.294<D≤n. In addition, the algorithms propose in this paper provides a solution to the open problem stated by Kao et al.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings
Pages205-214
Number of pages10
DOIs
StatePublished - Dec 1 2009
Event15th Annual International Conference on Computing and Combinatorics, COCOON 2009 - Niagara Falls, NY, United States
Duration: Jul 13 2009Jul 15 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5609 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th Annual International Conference on Computing and Combinatorics, COCOON 2009
CountryUnited States
CityNiagara Falls, NY
Period7/13/097/15/09

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Min, K., Kao, M-Y., & Zhu, H. (2009). The closest pair problem under the hamming metric. In Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings (pp. 205-214). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5609 LNCS). https://doi.org/10.1007/978-3-642-02882-3_21