NON-EXPANSIVE HASHING

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-epsilon) from a large universe may be sto red in a memory of size R (any epsilon > 0, and R > R-0(epsilon)), and where retrieval takes O(1) operations. We explain how to use non-expa nsive hashing schemes for efficient storage and retrieval of noisy dat a. A dynamic version of this hashing scheme is presented as well.