Multi-Index-Hashing für die Informationsbeschaffung

Wir beschreiben eine Technik zum Aufbau von Hash-Indizes für ein großes Wörterbuch von Zeichenfolgen. Diese Technik ermöglicht eine robuste Retrieval von Zeichenfolgen aus dem Wörterbuch, selbst wenn das Abfrageformat eine signifikante Anzahl von Fehlern aufweist. Diese Technik steht in engem Zusammenhang mit dem klassischen Turan-Problem für Hypergraphen. Wir schlagen eine allgemeine Methode zur Konstruktion von Multi-Indizes vor, indem wir bestimmte Turan-Hypergraphen verallgemeinern. Außerdem entwickeln wir eine begleitende Theorie zur Analyse solcher Hashing-Schemata. Die resultierenden Algorithmen wurden implementiert und können auf eine Vielzahl von Erkennungs- und Retrievalproblemen angewendet werden.