Gesellschaft für Informatik e.V.

Lecture Notes in Informatics


Datenbanksysteme für Business, Technologie und Web (BTW) 2013 - Workshopband P-216, 227-236 (2013).

Gesellschaft für Informatik, Bonn
2013


Copyright © Gesellschaft für Informatik, Bonn

Contents

Optimierung der Exact-Match Anfrage eines Lokal Sensitiven Hashverfahrens

Sarah Heckel

Abstract


Hochdimensionale Indexverfahren sind wichtig um einen schnellen Zugriff auf Multimediadaten zu gewährleisten. Eine Klasse dieser Verfahren ist das Lokal Sensitive Hashen (LSH). Beim LSH können sehr unterschiedlich ausgelastet Bereiche entstehen. Um die Exakt-Match-Anfrage beim Permutationsansatz, einer Variante des LSHs, effizient bearbeiten zu können, ist eine gleichmäßige Raumaufteilung von Vorteil. Dazu ist die Wahl der Protoypen von großer Bedeutung. Im Folgenden wird ein mathematisches Optimierungsproblem aufgestellt, welches die Prototypen bestimmt. Die Idee dabei ist Kugeln mit minimalem gleichem Radius um die Prototypen zu legen, sodass jeder Datenpunkt in mindestens einer Kugel enthalten ist. Werden optimierte Prototypen für die permutationsbasierte Variante des LSHs gewählt, so ist die Abweichung der Raumaufteilung gegenüber der Aufteilung bei zufällig gewählten Prototypen stabiler.


Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-610-7


Last changed 12.03.2014 15:16:28