کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10331854 686805 2014 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Improving the performance of Invertible Bloom Lookup Tables
ترجمه فارسی عنوان
بهبود عملکرد جداول مراجعه به شمع برگشت پذیر
کلمات کلیدی
الگوریتم ها، فیلترهای بلوم، هش، ساختارهای داده،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 114, Issue 4, April 2014, Pages 185-191
نویسندگان
, , ,