Name
Abstract | ||
|---|---|---|
In this paper we examined an algorithm for the All-k-Nearest-Neighbor problem proposed in 1980s, which was claimed to have an \(O(n\log {n})\) upper bound on the running time. We find the algorithm actually exceeds the so claimed upper bound, and prove that it has an \(\varOmega (n^2)\) lower bound on the time complexity. Besides, we propose a new algorithm that truly achieves the \(O(n\log {n})\) bound. Detailed and rigorous theoretical proofs are provided to show the proposed algorithm runs exactly in \(O(n\log {n})\) time. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-36412-0_29 | COCOA |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heng-Zhao Ma | 1 | 1 | 1.71 |
| Jianzhong Li | 2 | 3196 | 304.46 |