efficient algorithm to intersect m ordered sets in memory?

Question

Suppose we have m ordered sets and we want to find their intersection.

Which data structures should we use for the ordered sets and which algorithm would be the most efficient?

same question: Algorithm for N-way merge

It appears that the literature is huge. Thus a better question is this: Which good implementations are there?

Answer 1

You can create binary tree with link to parent node and implement classic algorithm of intersection/union:

1. Set iterA to left-most (smallest) node of the tree (i.e. descend over left-most branches to leaf).
2. Set iterB to first (smallest) node of the ordered set (if it is implemented with ordered array or to the left-most node if as tree).
3. Branch by comparison of items pointed by iterA and iterB
   • If lower: yield item of union and advance iterA
   • If equals: yield item of union and item of intersection and advance both iterA and itemB
   • If greater: yield item of union and advance iterB
4. Repeat until one of iterator is unable to advance
5. Rest of items accessible from other iterator yield as union items

Advance of binary tree iterator by:

• If current node have right child descend to it and descend to the left-most child of it while possible. Yield that item.
• If node have parent ascend over it and repeat that while we ascending from right child. Yield that item.
• Otherwise: all items of tree is yielded already (end of collection).

Update: If you know that your ordered set (walked by iterB) is much smaller than the tree you can use a bit more sophisticated algorithm for intersection:

1. Initially set iterB to beginning of ordered set (lower value).
2. Set iterA to the node which is minimum upper bound of value iterB.
3. Branch by comparison of items pointed by iterA and iterB
   • If equals: yield item of intersection.
4. Advance itemB to the next value.
5. Advance iterA to the minimum upper bound of value at itemB starting from current itemA.
6. Repeat until itemB pass all items of ordered set.

Where advance to the minimum upper bound from specific node is:

• If value of current node less than target
  • Find upper bound on right child by walking right-children of each node
  • If even right-most node of that branch is lower than target: ascend to parent while moving from right child and restart from that node.
  • Else from node where we found upper bound
  • Find first left-most children value of which is less than target
    • If not found: left-most leaf of that branch is minimum upper bound
    • Else restart from that node (more precisely will be to use sub-algorithm which walk over left-most and right-most nodes narrowing borders).

The main idea of searching bound is narrowing upper and minimum bound ("-" is ignored nodes, "..." is new search range):

for B < X < A
    U
   / \-
  L
-/ \...

for A < X < B
  L
-/ \
    U
.../ \-