Fast evaluation of union-intersection expressions

Details Fast evaluation of union-intersection expressions Fast evaluation of union-intersection expressions

2007-08-23

arxiv.org/abs/0708.3259v1

Computer Science

Data Structures and Algorithms

Scientific paper

We show how to represent sets in a linear space data structure such that expressions involving unions and intersections of sets can be computed in a worst-case efficient way. This problem has applications in e.g. information retrieval and database systems. We mainly consider the RAM model of computation, and sets of machine words, but also state our results in the I/O model. On a RAM with word size $w$, a special case of our result is that the intersection of $m$ (preprocessed) sets, containing $n$ elements in total, can be computed in expected time $O(n (\log w)^2 / w + km)$, where $k$ is the number of elements in the intersection. If the first of the two terms dominates, this is a factor $w^{1-o(1)}$ faster than the standard solution of merging sorted lists. We show a cell probe lower bound of time $\Omega(n/(w m \log m)+ (1-\tfrac{\log k}{w}) k)$, meaning that our upper bound is nearly optimal for small $m$. Our algorithm uses a novel combination of approximate set representations and word-level parallelism.

Affiliated with

Also associated with

No associations

Rating

Fast evaluation of union-intersection expressions 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 evaluation of union-intersection expressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast evaluation of union-intersection expressions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-394828