A Fast Set Intersection Algorithm for Sorted Sequences Export

@incollection{citeulike:4195948, abstract = {This paper introduces a simple intersection algorithm for two sorted sequences that is fast on average. It is related to the multiple searching problem and to merging. We present the worst and average case analysis, showing that in the former, the complexity nicely adapts to the smallest list size. In the later case, it performs less comparisons than the total number of elements on both inputs when n = α m ( α > 1). Finally, we show its application to fast query processing in Web search engines, where large intersections, or differences, must be performed fast. Keywords: Set operations, merging, multiple search, Web search engines, inverted indices.}, author = {Baeza-Yates, Ricardo}, citeulike-article-id = {4195948}, citeulike-linkout-0 = {http://www.springerlink.com/content/yth9h90y94n10l7e}, journal = {Combinatorial Pattern Matching}, keywords = {algorithms, interest-sharing, thesis}, pages = {400--408}, posted-at = {2009-03-19 18:55:23}, priority = {0}, title = {A Fast Set Intersection Algorithm for Sorted Sequences}, url = {http://www.springerlink.com/content/yth9h90y94n10l7e}, year = {2004} }

TY - CHAP ID - citeulike:4195948 L3 - citeulike-article-id:4195948 N2 - This paper introduces a simple intersection algorithm for two sorted sequences that is fast on average. It is related to the multiple searching problem and to merging. We present the worst and average case analysis, showing that in the former, the complexity nicely adapts to the smallest list size. In the later case, it performs less comparisons than the total number of elements on both inputs when n = α m ( α > 1). Finally, we show its application to fast query processing in Web search engines, where large intersections, or differences, must be performed fast. Keywords: Set operations, merging, multiple search, Web search engines, inverted indices. JF - Combinatorial Pattern Matching EP - 408 TI - A Fast Set Intersection Algorithm for Sorted Sequences SP - 400 KW - algorithms KW - interest-sharing KW - thesis AU - Baeza-Yates, Ricardo PY - 2004/// UR - http://www.springerlink.com/content/yth9h90y94n10l7e ER -