Title

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

Research Areas

Intelligent Systems and Decision Analytics

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

Additional URL

http://dx.doi.org/10.1145/237814.237999