Non-Expansive Hashing

• Main Authors: LINIAL, Nathan, SASSON, Ori
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 1996
• Subjects: Hash-table representations; data storage representations; Information storage systems; Computer Sciences; Systems Architecture
• Online Access: https://ink.library.smu.edu.sg/sis_research/1250; http://dx.doi.org/10.1145/237814.237999
• Institution: Singapore Management University

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) ope...