Fast Set Intersection in Memory

Details Fast Set Intersection in Memory Fast Set Intersection in Memory

2011-03-12

arxiv.org/abs/1103.2409v1

Proceedings of the VLDB Endowment (PVLDB), Vol. 4, No. 4, pp. 255-266 (2011)

Computer Science

Databases

VLDB2011

Scientific paper

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 O(n/sqrt(w)+kr), 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 in terms of execution time for both synthetic and real data sets and workloads.

Affiliated with

Also associated with

No associations

Rating

Fast Set Intersection in Memory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Set Intersection in Memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Set Intersection in Memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-278598