Non-Expansive Hashing - LINIAL, Nathan (Institutional Knowledge at Singapore Management University, 1996)
In a non-expansive 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 retrieval 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.