Optimal Hash Functions for Approximate Matches on the $n$-Cube

Daniel M. Gordon, Victor S. Miller, Peter Ostapenko

IEEE Transactions on Information Theory · 2010 · 12 citations · 14 references

Concepts

Abstract

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> One way to find near-matches in large datasets is to use hash functions. In recent years locality-sensitive hash functions for various metrics have been given; for the Hamming metric projecting onto <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$k$</tex></formula></emphasis> bits is simple hash function that performs well. In this paper, we investigate alternatives to projection. For various parameters hash functions given by complete decoding algorithms for error-correcting codes work better, and asymptotically random codes perform better than projection. </para>

References

14