Similarity search with set intersection as a distance measure

Abstract

This thesis deals with a fundamental algorithmic problem. Given a database of sets and a query set, we want to determine a set from the database that has a maximal intersection with the query set. It is allowed to preprocess the database so that queries can be answered efficiently.

We solve the approximate version of this problem. We investigate two randomized input models which are derived from real inputs. We present a deterministic algorithm for each of them. Under the assumption that the database and the query set follow one of these models, the corresponding algorithm determines with high probability a set from the database that has no maximal intersection with the query set, but an intersection that achieves a large proportion of the maximal size. Depending on the model, the query time is either quasi-linear in the sum of the database size and the number of different elements from all sets, or it is polylogarithmic in the database size. Thus, both algorithms are significantly faster than a naive algorithm intersecting the query set with each single database set.

Die vorliegende Arbeit beschäftigt sich mit einem elementaren Problem aus dem Gebiet der Algorithmentheorie. Gegeben sei eine Datenbank von Mengen und eine Anfragemenge. Das Ziel ist, möglichst effizient eine Menge der Datenbank zu bestimmen, die einen Schnitt maximaler Größe mit der Anfragemenge besitzt. Dabei ist es erlaubt, die Datenbank vorzuverarbeiten.

Wir präsentieren Lösungen für die Approximationsvariante dieses Problems. Wir untersuchen zwei aus der Praxis hergeleitete Eingabemodelle und stellen für jedes Modell einen deterministischen Algorithmus vor. Verhalten sich die Datenbank und die Anfragemenge gemäß einem dieser Modelle, dann bestimmt der entsprechende Algorithmus mit hoher Wahrscheinlichkeit eine Menge der Datenbank, deren Schnittgröße mit der Anfragemenge zwar nicht maximal ist, jedoch einen hohen Anteil der maximalen Größe erreicht. Die Anfragezeit ist je nach Modell entweder quasilinear in der Summe der Datenbankgröße und der Anzahl der verschiedenen Elemente aller Mengen, oder polylogarithmisch in der Datenbankgröße. Somit sind beide Algorithmen deutlich schneller als ein naiver Algorithmus, der die Größe des Schnittes zwischen der Anfragemenge und jeder einzelnen Menge der Datenbank bestimmt.