DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2021.20

A Faster Algorithm for Finding Closest Pairs in Hamming Metric

Authors: Andre Esser, Robert Kübler, and Floyd Zweydinger

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract

We study the Closest Pair Problem in Hamming metric, which asks to find the pair with the smallest Hamming distance in a collection of binary vectors. We give a new randomized algorithm for the problem on uniformly random input outperforming previous approaches whenever the dimension of input points is small compared to the dataset size. For moderate to large dimensions, our algorithm matches the time complexity of the previously best-known locality sensitive hashing based algorithms. Technically our algorithm follows similar design principles as Dubiner (IEEE Trans. Inf. Theory 2010) and May-Ozerov (Eurocrypt 2015). Besides improving the time complexity in the aforementioned areas, we significantly simplify the analysis of these previous works. We give a modular analysis, which allows us to investigate the performance of the algorithm also on non-uniform input distributions. Furthermore, we give a proof of concept implementation of our algorithm which performs well in comparison to a quadratic search baseline. This is the first step towards answering an open question raised by May and Ozerov regarding the practicability of algorithms following these design principles.

Cite as

Andre Esser, Robert Kübler, and Floyd Zweydinger. A Faster Algorithm for Finding Closest Pairs in Hamming Metric. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{esser_et_al:LIPIcs.FSTTCS.2021.20,
  author =	{Esser, Andre and K\"{u}bler, Robert and Zweydinger, Floyd},
  title =	{{A Faster Algorithm for Finding Closest Pairs in Hamming Metric}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{20:1--20:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.20},
  URN =		{urn:nbn:de:0030-drops-155317},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.20},
  annote =	{Keywords: closest pair problem, LSH, nearest neighbor}
}

Search Results

Documents authored by Kübler, Robert

A Faster Algorithm for Finding Closest Pairs in Hamming Metric

Abstract

Cite as

Thanks for your feedback!

Could not send message