| Title | A shifting bloom filter framework for set queries |
| Authors | Yang, Tong Liu, Alex X. Shahzad, Muhammad Zhong, Yuankun Fu, Qiaobin Li, Zi Xie, Gaogang Li, Xiaoming |
| Affiliation | Peking University, China Michigan State University, United States North Carolina State University, United States Nanjing University, China Boston University, United States ICT, CAS, China |
| Issue Date | 2016 |
| Publisher | 42nd International Conference on Very Large Data Bases, VLDB 2016 |
| Citation | 42nd International Conference on Very Large Data Bases, VLDB 2016.2016,9(5),408-419. |
| Abstract | Set queries are fundamental operations in computer systemsand applications. This paper addresses the fundamentalproblem of designing a probabilistic data structure that canquickly process set queries using a small amount of memory.We propose a Shifting Bloom Filter (ShBF) framework forrepresenting and querying sets. We demonstrate the effectivenessof ShBF using three types of popular set queries:membership, association, and multiplicity queries. The keynovelty of ShBF is on encoding the auxiliary informationof a set element in a location offset. In contrast, prior BFbased set data structures allocate additional memory to storeauxiliary information. We conducted experiments usingreal-world network traces, and results show that ShBF significantlyadvances the state-of-the-art on all three types ofset queries. ? 2016 VLDB Endowment 2150-8097/16/01. |
| URI | http://hdl.handle.net/20.500.11897/449606 |
| Indexed | EI |
| Appears in Collections: | 待认领 |
