中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
A Shifting Framework for Set Queries

文献类型：期刊论文

作者Yang, Tong2,3; Liu, Alex X.4,5; Shahzad, Muhammad6; Yang, Dongsheng2; Fu, Qiaobin7; Xie, Gaogang1; Li, Xiaoming2
刊名IEEE-ACM TRANSACTIONS ON NETWORKING
出版日期2017-10-01
卷号25期号:5页码:3116-3131
关键词Set queries Bloom filters algorithms
ISSN号1063-6692
DOI10.1109/TNET.2017.2730227
英文摘要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.
资助项目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记录号WOS:000413332100038
出版者IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
源URL[http://119.78.100.204/handle/2XEOYT63/6460]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Liu, Alex X.
作者单位1.Chinese Acad Sci, Inst Comp Technol, Beijing 100080, Peoples R China
2.Peking Univ, Dept Comp & Sci, Beijing 100871, Peoples R China
3.NUDT, Collaborat Innovat Ctr High Performance Comp, Changsha 410073, Hunan, Peoples R China
4.Michigan State Univ, Dept Comp Sci & Engn, E Lansing, MI 48824 USA
5.Nanjing Univ, State Key Lab Novel Software Technol, Nanjing 210093, Jiangsu, Peoples R China
6.North Carolina State Univ, Dept Comp Sci, Raleigh, NC 27695 USA
7.Boston Univ, Dept Comp Sci & Engn, Boston, MA 02215 USA
推荐引用方式
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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。