PEL: Position-Enhanced Length Filter for Set Similarity Joins 89-94

Willi Mann, Nikolaus Augsten

Research output: Chapter in Book/Report/Conference proceeding/Legal commentaryConference contributionResearchpeer-review


Set similarity joins compute all pairs of similar sets from two collections of sets. Set similarity joins are typically implemented in a filter-verify framework: a filter generates candidate pairs, possibly including false positives, which must be verified to produce the final join result. Good filters produce a small number of false positives, while they reduce the time they spend on hopeless candidates. The best known algorithms generate candidates using the so-called prefix filter in conjunction with length- and position-based filters.

In this paper we show that the potential of length and position have only partially been leveraged. We propose a new filter, the position-enhanced length filter, which exploits the matching position to incrementally tighten the length filter; our filter identifies hopeless candidates and avoids processing them. The filter is very efficient, requires no change in the data structures of most prefix filter algorithms, and is particularly effective for foreign joins, i.e., joins between two different collections of sets.
Translated title of the contributionPEL: Position-Enhanced Length Filter for Set Similarity Joins 89-94
Original languageEnglish
Title of host publicationProceedings of the 26th GI-Workshop Grundlagen von Datenbanken
Publication statusPublished - 2014

Fields of Science and Technology Classification 2012

  • 102 Computer Sciences

Cite this