Title

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

Additional URL

http://dx.doi.org/10.1007/pl00009805