The closest pair problem under the hamming metric

Kerui Min; Ming-Yang Kao; Hong Zhu

doi:10.1007/978-3-642-02882-3_21

The closest pair problem under the hamming metric

Kerui Min^*, Ming-Yang Kao, Hong Zhu

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings
Pages	205-214
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-02882-3_21
State	Published - Dec 1 2009
Event	15th Annual International Conference on Computing and Combinatorics, COCOON 2009 - Niagara Falls, NY, United States Duration: Jul 13 2009 → Jul 15 2009

Publication series

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

Other

Other	15th Annual International Conference on Computing and Combinatorics, COCOON 2009
Country	United States
City	Niagara Falls, NY
Period	7/13/09 → 7/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

@inproceedings{40e65fcecd4b4f0ba4e3be54d3ab20c3,

title = "The closest pair problem under the hamming metric",

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.",

author = "Kerui Min and Ming-Yang Kao and Hong Zhu",

year = "2009",

month = dec

day = "1",

doi = "10.1007/978-3-642-02882-3_21",

language = "English (US)",

isbn = "3642028810",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "205--214",

booktitle = "Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings",

note = "15th Annual International Conference on Computing and Combinatorics, COCOON 2009 ; Conference date: 13-07-2009 Through 15-07-2009",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5609 LNCS, pp. 205-214, 15th Annual International Conference on Computing and Combinatorics, COCOON 2009, Niagara Falls, NY, United States, 7/13/09. https://doi.org/10.1007/978-3-642-02882-3_21

The closest pair problem under the hamming metric. / Min, Kerui; Kao, Ming-Yang; Zhu, Hong.

Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings. 2009. p. 205-214 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5609 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The closest pair problem under the hamming metric

AU - Min, Kerui

AU - Kao, Ming-Yang

AU - Zhu, Hong

PY - 2009/12/1

Y1 - 2009/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=76249117802&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=76249117802&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02882-3_21

DO - 10.1007/978-3-642-02882-3_21

M3 - Conference contribution

AN - SCOPUS:76249117802

SN - 3642028810

SN - 9783642028816

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 205

EP - 214

BT - Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings

T2 - 15th Annual International Conference on Computing and Combinatorics, COCOON 2009

Y2 - 13 July 2009 through 15 July 2009

ER -

Access to Document

10.1007/978-3-642-02882-3_21