Non-Expansive Hashing
Publication Type
Conference Proceeding Article
Publication Date
10-1996
Abstract
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.
Keywords
Hash-table representations, data storage representations, Information storage systems
Discipline
Computer Sciences | Systems Architecture
Publication
STOC 96: 28th ACM Symposium on the Theory of Computing
First Page
509
Last Page
518
ISBN
9780897917858
Identifier
10.1145/237814.237999
Publisher
ACM
City or Country
New York
Citation
LINIAL, Nathan and SASSON, Ori.
Non-Expansive Hashing. (1996). STOC 96: 28th ACM Symposium on the Theory of Computing. 509-518.
Available at: https://ink.library.smu.edu.sg/sis_research/1250
Additional URL
http://dx.doi.org/10.1145/237814.237999