[PDF][PDF] Non-expansive hashing
N Linial, O Sasson - Proceedings of the twenty-eighth annual ACM …, 1996 - dl.acm.org
N Linial, O Sasson
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996•dl.acm.orgIn a non-e~ pansive 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 ret rieval 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.
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 ret rieval 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.
Abstract
In a non-e~ pansive 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 ret rieval 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.
ACM Digital Library