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 | |
| 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
}
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
ER -