Wie können wir Daten effizient aus großen Dateien abrufen, wenn Abfragen unvollständig sind? Diese Forschungsarbeit untersucht Dateidesigns, die für den Abruf aus einer Datei mit k-Buchstaben-Wörtern geeignet sind, wenn Abfragen nur teilweise angegeben sind. Die Autoren stellen eine neuartige Klasse von Partial-Match-File-Designs (PMF-Designs) vor, die auf Hash-Codierung und Trie-Suchalgorithmen basieren. Diese Designs bieten eine gute Worst-Case-Performance, wobei Obergrenzen für die Performance festgelegt und Beispiele für Dateien vorgestellt werden, die diese Grenzen erreichen. Die Implementierung dieser Dateidesigns sowie zugehöriger Abrufalgorithmen wird ebenfalls berücksichtigt. Die Speicheranforderungen sind so optimiert, dass sie im Wesentlichen dem Bedarf der Datensätze selbst entsprechen. Diese PMF-Designs bieten eine effiziente Lösung für den Partial-Match-Abruf und gleichen den Speicherbedarf mit der Abrufleistung aus. Die Techniken sind für Datenbankmanagementsysteme und Informationsabrufanwendungen von großer Bedeutung.
Diese in ACM Transactions on Database Systems veröffentlichte Arbeit über Hashing- und Trie-Algorithmen steht im Einklang mit dem Fokus der Zeitschrift auf innovative Techniken für Datenbankmanagement und Informationsabruf. Die Erforschung von Partial-Match-File-Designs und ihrer Performance trägt direkt zum Bereich der Datenbankoptimierung bei.