BigSet: An Efficient Set Intersection Approach

S.C. Zhang

doi:10.1109/TKDE.2024.3432595

BigSet: An Efficient Set Intersection Approach

2024-12-01

0

PRE

AI

Wenjie Zhang (Wenjie Zhang)

DOI：10.1109/TKDE.2024.3432595

Original

Original request for help

Save

Abstract

En 中文

Set intersection is a fundamental operation in many applications, such as common neighbor computation in graph-based algorithms, set similarity computation, item recommendation, etc. In the literature, many set intersection methods are proposed. We observe that the state-of-the-art algorithm RCode bears several limitations, such as high index time complexity, inefficient for large-sized sets, and not friendly to the generic set intersection. In this paper, we introduce the B ucket S ig nature for Set ( BigSet ), an efficient generic set intersection algorithm. BigSet consists of two phases, namely the preprocessing phase and the query phase. In the preprocessing phase, BigSet partitions the elements of a record into O(2(k)) buckets and uses a bitmap to indicate the status of the buckets where n is the record length and k is the number of bits in the signature. In the query phase, BigSet calculates the results using a candidate generating-and-verification framework. Specifically, a set of candidate elements is identified as those falling in the same buckets. Then, for each bucket, BigSet collects the common elements using a merge-based method. To improve the performance, we introduce two optimizations, including bucket sharing and size-aware signature construction techniques. We conduct experiments on 10 real graph datasets and 5 real generic set datasets to evaluate the performance of our proposals. The experiment results show that BigSet is 20x faster than the leading generic set intersection algorithms. Besides it outperforms the RCode with 5x speedup, and while uses up to 8x less memory.

Keywords:

Electronic mail

Time complexity

Reviews

Optimization

Labeling

Cyberspace

Computer science

Bitmap signature

bitwise operation

generic set intersection

set intersection

BigSet: An Efficient Set Intersection Approach

Abstract

Journal

Organization

Cited Papers