Non-expansive hashing
Nathan Linial, Ori Sasson · 1996
In a non-e~pansive hashing scheme, similar inputs are stored in memory locations which are close.We develop a non-expansive hashing scheme wherein any set of size O (R1-C) from a large universe may be stored in a memory of size R (any e > 0, and R > Ro(c)), and where ret rieval takes O(1) operations.We explain how to use non-expansive hashing schemes for efficient storage and retrieval of noisy data.A dynamic version of this hashing scheme is presented as well.