File SortedIntersection.h

↰ Parent directory (ADS/set)

The intersection of two sorted sets, the core of the resolution of a query of several words by an inverted index (chapter 6 of the notes): A of n items and B of m items, strictly increasing, :math:` m leq n ` (the roles are swapped otherwise).

Definition (ADS/set/SortedIntersection.h)

Detailed Description

  • intersectMerge() is the scan of the two lists of Fact 6.1, at most n + m comparisons, :math:` O( ( n + m ) / B ) ` I/Os whatever B, optimal when m and n are close; it is the procedure of section 8.3 of the book that setIntersection() of File SortedListSet.h applies to its lists.

  • intersectBinarySearch() searches each item of B in A, :math:` O( m log n ) ` comparisons (Fact 6.2), better when :math:` m = o( n / log n ) `.

  • intersectMutualPartition() is the algorithm of Baeza-Yates (Algorithm 6.1): the median of the shorter list searched in the longer one splits both, and the two halves recur, the roles swapped when the part of the longer one is the shorter, :math:` O( m ( 1 + log( n / m ) ) ) ` (Fact 6.3), which is optimal, since :math:` log_2 binom{n}{m} ` comparisons are needed to tell the subsets of A of m items apart.

  • intersectDoubling() searches each item of B from the place of the previous one by galloping, the places 1 , 2 , 4 , … ahead and then a binary search within the last gap (Algorithm 6.2, the exponential search of Bentley and Yao; gallopSearch() of File BinarySearch.h is the same search from the start of a vector, and the merges of File RunSorts.h gallop in the same way), :math:` sum_j ( 1 + log Delta_j ) = O( m ( 1 + log( n / m ) ) ) ` comparisons with no recursion (Fact 6.4).

  • intersectTwoLevel() is the two-level storage of Fact 6.5: the first item of each block of L items of A in an array A’ of n / L items, merged with B to find the block where each item of B may be, and each block met merged with its items of B, :math:` O( n / L + m L ) ` time; on the disk [see File TwoLevelMemory.h] intersectTwoLevelExternal() takes :math:` O( n / L B + m L / B + m ) ` I/Os, each block of A met costing at most :math:` lceil L / B rceil + 1 ` reads, against the :math:` lceil n / B rceil + lceil m / B rceil ` of intersectMergeExternal().

  • PermutedBuckets is the random permutation and splitting of Fact 6.6 (the lookup of Sanders and Transier): the values of the universe :math:` [ 0 , 2^w ) ` permuted by :math:` pi( x ) = ( a x + c ) bmod 2^w , a odd so that :math: pi ` is invertible, and a list of n items split by the top :math:` ell = lceil log_2( n / L ) rceil ` bits of the images into buckets of L items on average, the images sorted and addressed by a table of offsets; each image of the shorter list is looked for in the bucket of the longer one named by its own top bits, so that a bucket of A is never looked at unless B has items in it: :math:` O( m + min{ n , m L } ) ` expected time, and the lists need not be sorted beforehand, only their images are.

Compared with the literature: the experiments of Sanders and Transier, and of Barbay et al., find the lookup best up to lists of similar length, the two-level skipping better than the mutual partition for all but the most unequal lists, whose recursion costs more than its bound says; the adaptive algorithms of Demaine, López-Ortiz and Munro and of Barbay and Kenyon extend the galloping to k lists, and Ding and König replace the buckets by word-sized bitmaps.

The contracts [see File Contract.h]: A and B strictly increasing, audits; L >= 1; the result is the intersection, strictly increasing, a postcondition checked as an audit against intersectMerge(); 1 <= w <= 63, a odd, the values below 2^w, and two PermutedBuckets intersected with the same permutation; the files of the external versions share a memory of at least 4 B. The functions are defined in SortedIntersection.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 6

  1. Baeza-Yates, A fast set intersection algorithm for sorted sequences, Proceedings of the 15th Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science 3109, 400-408, 2004, doi:10.1007/978-3-540-27801-6_30

    1. Bentley, A. C.-C. Yao, An almost optimal algorithm for unbounded searching, Information Processing Letters 5(3), 82-87, 1976, doi:10.1016/0020-0190(76)90071-5

  1. Sanders, F. Transier, Intersection in integer inverted indices, Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX), 71-83, 2007

  1. Barbay, A. López-Ortiz, T. Lu, A. Salinger, An experimental investigation of set intersection algorithms for text searching, ACM Journal of Experimental Algorithmics 14, 3.7, 2009, doi:10.1145/1498698.1564507

    1. Demaine, A. López-Ortiz, J. I. Munro, Adaptive set intersections, unions, and differences, Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), 743-752, 2000

  1. Ding, A. C. König, Fast set intersection in memory, Proceedings of the VLDB Endowment 4(4), 255-266, 2011, doi:10.14778/1938545.1938550

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions