Fast Set Intersection in Memory
Fast Set Intersection in Memory
复制标题
DOI：
10.14778/1938545.1938550
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
Bolin Ding;A. König
中科院分区：
文献类型：
--
作者：
Bolin Ding;A. König
集合交集是信息检索和数据库系统中的一项基本操作。本文引入线性空间数据结构来表示集合，使得集合的交点可以用最坏情况有效的方法计算。一般来说，给定k个（预处理）集合，总共有n个元素，我们将展示如何在预期时间内计算它们的交集[公式]，其中r是交集大小，w是机器字中的位数。此外，我们介绍了该算法的一个非常简单的版本，它具有较弱的渐近保证，但在实践中表现得更好；对于合成数据集和真实数据集以及工作负载，这两种算法都优于最先进的技术。
Set intersection is a fundamental operation in information retrieval and database systems. This paper introduces linear space data structures to represent sets such that their intersection can be computed in a worst-case efficient way. In general, given k (preprocessed) sets, with totally n elements, we will show how to compute their intersection in expected time [EQUATION], where r is the intersection size and w is the number of bits in a machine-word. In addition, we introduce a very simple version of this algorithm that has weaker asymptotic guarantees but performs even better in practice; both algorithms outperform the state of the art techniques for both synthetic and real data sets and workloads.