Conference Proceeding Article
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.
Hash-table representations, data storage representations, Information storage systems
Computer Sciences | Systems Architecture
Intelligent Systems and Decision Analytics
STOC 96: 28th ACM Symposium on the Theory of Computing
City or Country
LINIAL, Nathan and SASSON, Ori.
Non-Expansive Hashing. (1996). STOC 96: 28th ACM Symposium on the Theory of Computing. 509-518. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1250