PUMA publications for /author/Ricardo%20Baeza-Yates/set%20algorithm%20mergehttps://puma.uni-kassel.de/author/Ricardo%20Baeza-Yates/set%20algorithm%20mergePUMA RSS feed for /author/Ricardo%20Baeza-Yates/set%20algorithm%20merge2024-03-29T16:07:21+01:00A Fast Set Intersection Algorithm for Sorted Sequences.https://puma.uni-kassel.de/bibtex/2ac1a8233f1ea5edb39d834f943390cfc/jaeschkejaeschke2006-06-13T09:56:10+02:00algorithm intersection fast set merge <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Ricardo A. Baeza-Yates" itemprop="url" href="/author/Ricardo%20A.%20Baeza-Yates"><span itemprop="name">R. Baeza-Yates</span></a></span>. </span><span itemtype="http://schema.org/Book" itemscope="itemscope" itemprop="isPartOf"><em><span itemprop="name">Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004</span>, </em></span><em>Seite <span itemprop="pagination">400-408</span>. </em>(<em><span>2004<meta content="2004" itemprop="datePublished"/></span></em>)Tue Jun 13 09:56:10 CEST 2006Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004400-408A Fast Set Intersection Algorithm for Sorted Sequences.2004algorithm intersection fast set merge 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 = agr m (agr > 1). Finally, we show its application to fast query processing in Web search engines, where large intersections, or differences, must be performed fast.dblp