The closest pair problem under the hamming metric

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.