Non-Expansive Hashing
Publication Type
Journal Article
Publication Date
1998
Abstract
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.
Discipline
Numerical Analysis and Scientific Computing | Software Engineering
Research Areas
Software Systems
Publication
Combinatorica
Volume
18
Issue
1
First Page
121
Last Page
132
ISSN
0209-9683
Identifier
10.1007/pl00009805
Publisher
Springer Verlag
Citation
LINIAL, N. and SASSON, Ori.
Non-Expansive Hashing. (1998). Combinatorica. 18, (1), 121-132.
Available at: https://ink.library.smu.edu.sg/sis_research/15
Additional URL
http://dx.doi.org/10.1007/pl00009805