当前位置: > 学院通知 > 学术报告 >
大数据集合查询问题研究--北京大学计算机系网络所杨仝报告会
时间:2016-05-06 点击:
报告题目:大数据集合查询问题研究
时间:2016330日周三14:30
地点:主楼四区305
杨仝,2010-2013,就读于清华大学计算机计算机网络专业。2013-2014年到中科院计算所客座访问。2015年进入北京大学信息学院计算机系网络所,研究方向为网络与大数据。发表多篇著名国际会议论文,包括SIGCOMMVLDBICNPICDCS等。
Abstract: Set queries are fundamental operations in computer systems and applications. 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 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.
该论文研究大数据处理中最基础的大集合查询问题,主要包括集合包含、多集合、元素出现次数三个关键问题。该论文未发表之前的网络版已经被哈佛大学计算机副系主任引用。