A Fast Set Intersection Algorithm for Sorted Sequences.
R. Baeza-Yates.
Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004, Seite 400-408. (2004)

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.

Dokument

http://www.springerlink.com/index/YTH9H90Y94N10L7E.pdf

Suchen auf

Diese Publikation wurde noch nicht bewertet.

Bewertungsverteilung

Durchschnittliche Benutzerbewertung0,0 von 5.0 auf Grundlage von 0 Rezensionen

Bitte melden Sie sich an um selbst Rezensionen oder Kommentare zu erstellen.

@inproceedings{conf/cpm/Baeza-Yates04,
  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 = 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.},
  added-at = {2006-06-13T09:56:10.000+0200},
  author = {Baeza-Yates, Ricardo A.},
  biburl = {https://puma.uni-kassel.de/bibtex/2ac1a8233f1ea5edb39d834f943390cfc/jaeschke},
  booktitle = {Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004},
  description = {dblp},
  editor = {Sahinalp, Suleyman Cenk and Muthukrishnan, S. and Dogrusoz, Ugur},
  interhash = {a71b1a4a88d4228da47271d744a1a97b},
  intrahash = {ac1a8233f1ea5edb39d834f943390cfc},
  keywords = {set fast intersection algorithm merge},
  pages = {400-408},
  timestamp = {2011-07-28T16:18:55.000+0200},
  title = {A Fast Set Intersection Algorithm for Sorted Sequences.},
  url = {http://www.springerlink.com/index/YTH9H90Y94N10L7E.pdf},
  year = 2004
}

%0 Conference Paper
%1 conf/cpm/Baeza-Yates04
%A Baeza-Yates, Ricardo A.
%B Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004
%D 2004
%E Sahinalp, Suleyman Cenk
%E Muthukrishnan, S.
%E Dogrusoz, Ugur
%K set fast intersection algorithm merge
%P 400-408
%T A Fast Set Intersection Algorithm for Sorted Sequences.
%U http://www.springerlink.com/index/YTH9H90Y94N10L7E.pdf
%X 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.

PUMA

A Fast Set Intersection Algorithm for Sorted Sequences.
R. Baeza-Yates.
Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004, Seite 400-408. (2004)

Tags

Nutzer

Kommentare und Rezensionen

Zitieren Sie diese Publikation

PUMA

A Fast Set Intersection Algorithm for Sorted Sequences.R. Baeza-Yates. Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004, Seite 400-408. (2004)

Tags

Nutzer

Kommentare und Rezensionen

Zitieren Sie diese Publikation

A Fast Set Intersection Algorithm for Sorted Sequences.
R. Baeza-Yates.
Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM 2004, Seite 400-408. (2004)