Algorithmen zur Analyse von Suchanfragen in Systemen mit invertierter Dateiorganisation

In einem invertierten Dateisystem hat eine Abfrage die Form eines booleschen Ausdrucks von Indextoren. Als Antwort auf eine Abfrage greift das System auf die invertierten Listen zu, die den Indextoren entsprechen, fügt sie zusammen und wählt aus der zusammengeführten Liste jene Datensätze aus, die die Suchlogik erfüllen. In diesem Papier wird das Problem der Bestimmung eines booleschen Ausdrucks betrachtet, der zu der minimalen Gesamtmergezeit unter allen booleschen Ausdrücken führt, die äquivalent zu dem im Abfrage gegebenen Ausdruck sind. Dieses Problem ist identisch mit der Suche nach einem optimalen Merge-Baum unter allen Bäumen, die die Wahrheitsfunktion realisieren, die durch den booleschen Ausdruck in der Abfrage bestimmt wird. Es werden mehrere Algorithmen beschrieben, die optimale Merge-Bäume generieren, wenn die Größen der Überlappungen zwischen unterschiedlichen Listen im Vergleich zur Länge der Listen klein sind.