A Shifting Framework for Set Queries

doi:10.1109/TNET.2017.2730227

	A Shifting Framework for Set Queries
	Yang, Tong 1,2; Liu, Alex X.3,4; Shahzad, Muhammad 5; Yang, Dongsheng 1; Fu, Qiaobin 6; Xie, Gaogang 7; Li, Xiaoming 1
	2017-10-01
发表期刊	IEEE-ACM TRANSACTIONS ON NETWORKING
ISSN	1063-6692
卷号	25 期号:5 页码:3116-3131
摘要	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.
关键词	Set queries Bloom filters algorithms
DOI	10.1109/TNET.2017.2730227
收录类别	SCI
语种	英语
资助项目	National Basic Research Program of China[2014CB340400] ; Primary Research & Development Plan of China[2016YFB1000304] ; NSFC[61472009] ; NSFC[61672061] ; Open Project Funding of CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences ; Special Fund for Strategic Pilot Technology, Chinese Academy of Sciences[XDA06010302] ; National Science Foundation[CNS-1318563] ; National Science Foundation[CNS-1524698] ; National Science Foundation[CNS-1421407] ; National Science Foundation[CNS-1616317] ; National Science Foundation[IIP-1632051] ; Shenzhen Research Project[JCYJ20160330095313861] ; National Natural Science Foundation of China[61472184] ; National Natural Science Foundation of China[61321491] ; Jiangsu Innovation and Entrepreneurship (Shuangchuang) Program
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000413332100038
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计	被引频次：27[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/6461
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liu, Alex X.
作者单位	1.Peking Univ, Dept Comp & Sci, Beijing 100871, Peoples R China 2.NUDT, Collaborat Innovat Ctr High Performance Comp, Changsha 410073, Hunan, Peoples R China 3.Michigan State Univ, Dept Comp Sci & Engn, E Lansing, MI 48824 USA 4.Nanjing Univ, State Key Lab Novel Software Technol, Nanjing 210093, Jiangsu, Peoples R China 5.North Carolina State Univ, Dept Comp Sci, Raleigh, NC 27695 USA 6.Boston Univ, Dept Comp Sci & Engn, Boston, MA 02215 USA 7.Chinese Acad Sci, Inst Comp Technol, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Yang, Tong,Liu, Alex X.,Shahzad, Muhammad,et al. A Shifting Framework for Set Queries[J]. IEEE-ACM TRANSACTIONS ON NETWORKING,2017,25(5):3116-3131.
APA	Yang, Tong.,Liu, Alex X..,Shahzad, Muhammad.,Yang, Dongsheng.,Fu, Qiaobin.,...&Li, Xiaoming.(2017).A Shifting Framework for Set Queries.IEEE-ACM TRANSACTIONS ON NETWORKING,25(5),3116-3131.
MLA	Yang, Tong,et al."A Shifting Framework for Set Queries".IEEE-ACM TRANSACTIONS ON NETWORKING 25.5(2017):3116-3131.