IEEE/ACM Transactions on Networking · 2008 · 35 citations · 16 references
ComputingComputer ScienceAlgorithmsData MiningData StructuresDatabase ManagementHash FunctionsHash TablesLookup TablesQuery ProcessingHash Table ImplementationsHash Table Search AlgorithmsHashing
In a multiple-choice hashing scheme, each item is stored in one of d ges 2 possible hash table buckets. The availability of these multiple choices allows for a substantial reduction in the maximum load of the buckets. However, a lookup may now require examining each of the locations. For applications where this cost is undesirable, Song propose keeping a summary that allows one to determine which of the locations is appropriate for each item, where the summary may allow false positives for items not in hash table. We propose alternative, simple constructions of such summaries that use less space for both the summary and the underlying hash table. Moreover, our constructions are easily analyzable and tunable.
16
Space/time trade-offs in hash coding with allowable errors
Burton H. Bloom · Communications of the ACM · 1970 · 7.5K citations · Full text
Network Applications of Bloom Filters: A Survey
Andrei Broder, Michael Mitzenmacher · Internet Mathematics · 2004 · 2K citations · Full text
Yossi Azar, Andrei Broder, Anna R. Karlin et al. · SIAM Journal on Computing · 1999 · 754 citations