Existiert ein universeller Index?

Bei einer Datentabelle, die eine sehr große Anzahl von Zeilen enthält, wobei jede Zeile eine große Anzahl k von Feldern enthält, wobei jedes Feld eine große, aber feste Anzahl von Bits enthält, gibt es eine Anzahl von Methoden zum Aufbau einer "Index" -Struktur dass die folgenden Operationen an der Tabelle und dem Index in O ( k log N ) -Zeit (relativ zu N und k ) ausgeführt werden können:$N$$k$$O(k\log N)$$N$$k$

1. Fügen Sie ein neues Element in die Tabelle ein.

2. Entfernen Sie ein angegebenes Element aus der Tabelle.

3. Erhalten Sie bei einer Reihe von Feldwerten den ersten Datensatz in der Tabelle mit Feldwerten, die größer als die angegebenen Feldwerte sind, wenn die Tabelle in die lexikografische Reihenfolge mit Feld 1 zuerst, Feld 2 zweitens usw. sortiert wird.

Wir möchten diese Konstruktion so verallgemeinern, dass nach Abschluss von Operation 3 alle Die Reihenfolge der k Felder kann angegeben werden, um die Reihenfolge der Datensätze in der Tabelle zu bestimmen.$k!$$k$

Dies kann natürlich durch Konstruieren von k! Indizes, einer für jede Reihenfolge der Felder. Dann brauchen die Operationen Zeit.$O(k!k\log N)$

Wir wollen einen Algorithmus, dessen Operationen viel schneller sind (relativ zu ), vorzugsweise O ( k log k log N ) .$k$$O(k\log k \log N)$

Existiert ein solcher Algorithmus / eine solche Datenstruktur? Es scheint wahrscheinlich, dass jemand es veröffentlicht und implementiert hätte, wenn es existiert hätte, aber ich habe keine Anzeichen dafür gefunden, dass es eines gibt. Umgekehrt kann möglicherweise nachgewiesen werden, dass kein solcher Algorithmus existiert. Aber ich habe keine Anzeichen dafür gefunden, dass ein solcher Beweis existiert.

${\cal F}$$N$$k$$S$$X \in {\cal F}$$S \subseteq X$

$S$$S$$1$$S$$0$$S$$S$

$O(poly(k)N^{0.99})$${\cal F}$$3$$poly(N,k)$ Vorverarbeitungszeit.