Name
Abstract | ||
|---|---|---|
Invertible Bloom Lookup Tables (IBLTs) have been recently introduced as an extension of traditional Bloom filters. IBLTs store key-value pairs. Unlike traditional Bloom filters, IBLTs support both a lookup operation (given a key, return a value) and an operation that lists out all the key-value pairs stored. One issue with IBLTs is that there is a probability that a lookup operation will return ''not found'' for a key. In this paper, a technique to reduce this probability without affecting the storage requirement and only moderately increasing the search time is presented and evaluated. The results show that it can significantly reduce the probability of not returning a value that is actually stored in the IBLT. The overhead of the modified search procedure, compared to the standard IBLT search procedure, is small and has little impact on the average search time. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.ipl.2013.11.015 | Inf. Process. Lett. |
Keywords | Field | DocType |
key-value pair,standard iblt search procedure,traditional bloom filter,modified search procedure,lookup operation,iblts store key-value pair,storage requirement,search time,invertible bloom lookup tables,average search time,algorithms,data structures,hash,bloom filters | Data structure,Bloom filter,Lookup table,Bloom,Computer science,Search procedure,Algorithm,Hash function,Invertible matrix,Recursion | Journal |
Volume | Issue | ISSN |
114 | 4 | 0020-0190 |
Citations | PageRank | References |
2 | 0.44 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Salvatore Pontarelli | 1 | 368 | 54.05 |
| Pedro Reviriego | 2 | 527 | 75.56 |
| Michael Mitzenmacher | 3 | 7386 | 730.89 |