Please use this identifier to cite or link to this item: http://localhost/handle/Hannan/224300
Title: A Shifting Framework for Set Queries
Authors: Tong Yang;Alex X. Liu;Muhammad Shahzad;Dongsheng Yang;Qiaobin Fu;Gaogang Xie;Xiaoming Li
Year: 2017
Publisher: IEEE
Abstract: Set queries are fundamental operations in computer networks. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a shifting bloom filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF-based set data structures allocate additional memory to store auxiliary information. We further extend our shifting framework from BF-based data structures to sketch-based data structures, which are widely used to store multiplicities of items. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.
URI: http://localhost/handle/Hannan/224300
volume: 25
issue: 5
More Information: 3116,
3131
Appears in Collections:2017

Files in This Item:
File SizeFormat 
8012437.pdf2.48 MBAdobe PDF
Title: A Shifting Framework for Set Queries
Authors: Tong Yang;Alex X. Liu;Muhammad Shahzad;Dongsheng Yang;Qiaobin Fu;Gaogang Xie;Xiaoming Li
Year: 2017
Publisher: IEEE
Abstract: Set queries are fundamental operations in computer networks. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a shifting bloom filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF-based set data structures allocate additional memory to store auxiliary information. We further extend our shifting framework from BF-based data structures to sketch-based data structures, which are widely used to store multiplicities of items. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.
URI: http://localhost/handle/Hannan/224300
volume: 25
issue: 5
More Information: 3116,
3131
Appears in Collections:2017

Files in This Item:
File SizeFormat 
8012437.pdf2.48 MBAdobe PDF
Title: A Shifting Framework for Set Queries
Authors: Tong Yang;Alex X. Liu;Muhammad Shahzad;Dongsheng Yang;Qiaobin Fu;Gaogang Xie;Xiaoming Li
Year: 2017
Publisher: IEEE
Abstract: Set queries are fundamental operations in computer networks. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a shifting bloom filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF-based set data structures allocate additional memory to store auxiliary information. We further extend our shifting framework from BF-based data structures to sketch-based data structures, which are widely used to store multiplicities of items. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.
URI: http://localhost/handle/Hannan/224300
volume: 25
issue: 5
More Information: 3116,
3131
Appears in Collections:2017

Files in This Item:
File SizeFormat 
8012437.pdf2.48 MBAdobe PDF