Non-Expansive Hashing

• Main Authors: LINIAL, Nathan, SASSON, Ori
• 格式: text
• 語言: English
• 出版: Institutional Knowledge at Singapore Management University 1996
• 主題: Hash-table representations; data storage representations; Information storage systems; Computer Sciences; Systems Architecture
• 在線閱讀: https://ink.library.smu.edu.sg/sis_research/1250; http://dx.doi.org/10.1145/237814.237999
• 機構: 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...