Name
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 $O\left(n^{2+o(1)}\right)$, whereas for n 0.294 D ≤ n , it can be solved within time complexity $O\left(n^{1.843} D^{0.533}\right)$. We also provide an alternative approach not involving algebraic matrix multiplication, which has the time complexity $O\left(n^2D/\log^2 D\right)$ with small constant, and is effective for practical use. Moreover, for arbitrary large alphabet set, an algorithm with the time complexity $O\left(n^2\sqrt{D}\right)$ is obtained for 0 D ≤ n 0.294, whereas the time complexity is $O\left(n^{1.921} D^{0.767}\right)$ 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02882-3_21 | COCOON |
Keywords | DocType | Volume |
closest pair problem,closest pair,practical use,algebraic matrix multiplication,arbitrary large alphabet set,open problem,alternative approach,fundamental problem,binary alphabet set,time complexity,hamming metric,matrix multiplication | Conference | 5609 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.39 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kerui Min | 1 | 103 | 5.33 |
| Ming-Yang Kao | 2 | 1520 | 159.74 |
| Hong Zhu | 3 | 179 | 23.67 |