4.1 Motivation und Problem

Datenbankanfragen sind geometrische Anfragen (Folien 3–4)

Eine Firmendatenbank speichert Name, Geburtsdatum, Gehalt, Kinderzahl, … der Angestellten. Anfrage:

Finde alle Angestellten, die zwischen 1995 und 2000 geboren sind, 4.000 € bis 5.000 € verdienen und 1–3 Kinder haben.

Trick: Das Geburtsdatum wird zu einer Zahl: $10\,000\cdot\text{Jahr} + 100\cdot\text{Monat} + \text{Tag}$, z.B. 18.08.1998 ↦ 19 980 818. Diese Zahlen sind genauso geordnet wie die Daten.

Damit ist jeder Angestellte ein Punkt im $\mathbb R^3$ (Geburtsdatum, Gehalt, Kinder), und die Anfrage ist ein achsenparalleler Quader. Gesucht sind alle Punkte darin, eine 3d-Bereichsanfrage.

Beispiele in verschiedenen Dimensionen (Folie 5)

$k$	Beispiel
1	alle Schlüssel einer Folge zwischen $a$ und $b$ (vgl. Bereichssuche im Baum in 3.3.1)
2	alle Städte in einem Quadrat mit 100 km Kantenlänge um Konstanz
$\ge3$	alle Objekte einer Szene im Sichtvolumen (viewing frustum) zum Rendern

Problemstellung (Folie 6)

Eingabe	Menge $P=\{p_1,\dots,p_n\}$ von $n$ Punkten im $k$-dimensionalen Raum und ein achsenparalleler Anfragebereich $D$
Ausgabe	alle Punkte in $P\cap D$
Ziel	viele Anfragen mit verschiedenen $D$ auf derselben Menge $P$ möglichst schnell beantworten
Idee	$P$ einmal in einer Datenstruktur speichern, die Bereichsanfragen effizient unterstützt

Man bewertet eine solche Struktur immer nach drei Größen: Speicher, Aufbauzeit (Vorverarbeitung) und Anfragezeit.

4.2 Mehrdimensionale Suche: erste Ansätze

Naiv (Folie 7)

Jeden Punkt einzeln testen, ob er in $D=[x_l,x_r]\times[y_l,y_r]$ liegt.

• Laufzeit $O(n)$ pro Anfrage, egal wie wenige Punkte im Ergebnis sind.
• Ineffizient, wenn das Ergebnis meist nur aus wenigen Punkten besteht.
• Besser wäre ein ausgabesensitiver Algorithmus, dessen Laufzeit von der Zahl $R$ der gefundenen Punkte abhängt.

Gitter / Quadtree (Folie 8)

Ein reguläres Gitter über $P$ legen. Bei einer Anfrage nur die Punkte in Zellen betrachten, die $D$ schneiden.

• Gut, wenn die Punkte gleichmäßig verteilt sind.
• Schlecht, wenn sich die Punkte in einem Bereich ballen: Dann gibt es viele leere Zellen, und wenige Zellen enthalten fast alle Punkte.

Ein Quadtree verfeinert das Gitter adaptiv, ist aber auch nicht balanciert: Seine Tiefe hängt von den Abständen der Punkte ab, nicht von $n$.

BSP-Bäume (Folie 9)

Die Punktmenge rekursiv an beliebigen (Hyper-)Ebenen teilen (Binary Space Partition).

• Ineffizient, weil der Schnitt eines rechteckigen Anfragebereichs mit beliebigen Halbräumen ein beliebiges konvexes Polygon (in $k$d: Polytop) ergibt. Damit rechnet es sich schlecht.
• Effizient, wenn die Ebenen achsenparallel sind. Das führt direkt zu den $k$d-Bäumen.