Non-Expansive Hashing |
| |
Authors: | Nathan Linial Ori Sasson |
| |
Affiliation: | (1) Hebrew University, Jerusalem, Israel. E-mail: nati@cs.huji.ac.il, IL;(2) Hebrew University, Jerusalem, Israel. E-mail: ori@cs.huji.ac.il, IL |
| |
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. Received: February 5, 1996 |
| |
Keywords: | AMS Subject Classification (1991) Classes: 68R05, 68P05 |
本文献已被 SpringerLink 等数据库收录! |
|