next up previous contents
Next: Probleme in der Praxis Up: Effizienz der Dublettenkontrolle Previous: Effizienz der Dublettenkontrolle

Legende Aufwand und Rechenzeit mit Index

Anfrage:
Die an die Datenbanken gestellte Anfrage.
Anzahl Treffer:
Die Summe der Treffer von allen Datenbanken insgesamt.

Vergleiche:
Jeder Datensatz wird mit jedem verglichen. Der Aufwand wächst quadratisch mit der Anzahl der Datensätze: (n2 - n) / 2. Dies ist der ungünstigste Fall (worst case).

Vergleiche ZACK Index:
Diese Spalte gibt die Anzahl der notwendigen Vergleiche mit einem Index im System ZACK an.

In Prozent:
Gibt an, wie effektiv die Nutzung eines Indexes im Unterschied zum Verfahren jeden Datensatz mit jedem zu vergleichen ist.

Vergleiche pro Treffer:
Gibt an, wieviele Vergleiche durchschnittlich pro Datensatz mit einem Index notwendig sind.

Zeit in Sekunden:
Gibt die Rechenzeit [*] in ZACK für die Dublettenkontrolle mit Index an.

Es hat sich gezeigt, daß man mit einem Index die Anzahl der notwendigen Vergleiche deutlich reduzieren kann. Bei der Suche im Attribut Titel reduziert sich der Aufwand für die Vergleiche um rund 90%, bei der Suche mit dem Attribut Autor immerhin noch um 1/3.

Bei der Autorensuche haben die Treffer fast alle denselben Autor. Deshalb wird die Vorauswahl von ähnlichen Datensätzen schwieriger und komplexer. Im ungünstigsten Fall sind die Cluster so groß wie die Anzahl der Datensätze, und der Aufwand mit einem Index ist genauso groß wie bei einem Vergleich ``jeder Datensatz mit jedem'' (O2). Bei großen Datenmengen (>100) gibt es mehr potentielle Dubletten und die Größe der Cluster wächst. Die Anzahl der notwendigen Vergleiche wird um so geringer, je besser die Cluster der minimal ähnlichen Datensätze gebildet werden. Dabei ist entscheidend, daß die Cluster möglichst klein bleiben (Anzahl < 5), da innerhalb eines Clusters alle Datensätze miteinander verglichen werden.

Für den Aufbau des temporären Indexes wird Rechenzeit benötigt. Der Aufwand dafür wächst linear mit der Anzahl der Datensätze. Mit einem Index kann man nur gleiche Attribute vergleichen. Sobald Tippfehler auftauchen, ist ein Vergleich nicht mehr möglich.


next up previous contents
Next: Probleme in der Praxis Up: Effizienz der Dublettenkontrolle Previous: Effizienz der Dublettenkontrolle

Copyright (c) 1999 Wolfram Schneider , 4-July-1999
URL: https://wolfram.schneider.org/lv/diplom/