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 from a large universe may be stored in a memory of size (any , and ), and where retrieval takes 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.
Numerical Analysis and Scientific Computing | Software Engineering
LINIAL, N. and SASSON, Ori.
Non-Expansive Hashing. (1998). Combinatorica. 18, (1), 121-132. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/15