Datenstruktur, die effiziente tagbasierte Suchvorgänge ermöglicht

Ich suche eine hocheffiziente Datenstruktur zur Speicherung von Daten ähnlich der folgenden.

ID Tags Order1 Order2 
--------------------------
1 1,2 1 1
2 2,5 2 3
3 1,7 4 7
4 6 3 0

Ich muss in der Lage sein, diese Struktur so abzufragen, dass ich eine Liste aller IDs bekomme, die einen Ausdruck von Tags enthalten - unterstützende ANDund ORund NOTOperationen. Z.B. ((1 oder 2) und nicht 7)

Ich muss auch in der Lage sein, die Reihenfolge der Ergebnisse (Reihenfolge1 oder Reihenfolge2) anzugeben und die maximalen Zeilen anzugeben, die mit einem optionalen Versatz zurückgegeben werden. Die Leistung für den Abruf der ersten 30-100 Ergebnisse ist der Schlüssel.

Schließlich brauche ich eine kostengünstige Möglichkeit, um nach "Tag-Beziehungen" zu suchen. Ich möchte beispielsweise wissen, welche Tags sich auf Tags (1 ODER 2) beziehen und in welcher Häufigkeit. Dies bedeutet, welche Tags im selben Satz wie 1 ODER 2 ... nach Häufigkeit geordnet erscheinen.

Gibt es eine Vorstellung davon, welche Datenstruktur (oder welcher Satz von Strukturen) für diese Art von Arbeit hocheffizient wäre?

(Ich möchte dies als Proof of Concept für die Neugestaltung der markierten Seiten der SE-Site-Familie verwenden.)

Dies ist nicht gerade eine Antwort auf eine effiziente Datenstruktur, sondern eine Ausarbeitung der Kommentare von @bbejot und @Kaveh, die ein handwedelndes Argument dafür liefern, warum wir angesichts der aktuellen Frage nicht etwas erwarten sollten, das viel besser funktioniert als das Durchsuchen der ganze Datenbank. Das Argument basiert auf einer Reduktion von SAT, der exponentiellen Zeithypothese und viel Handwinken.

Angenommen, wir haben bis zu verschiedene Tags, dann können wir uns vorstellen , dass jede ID einem Bitvektor der Länge wobei wenn wir das te Tag haben, und sonst. Da es keine wirklichen Einschränkungen für das Aussehen der Datenbank gibt, kann ich davon ausgehen, dass sie die IDs bis wobei der ten ID ein binärer Tag-Vektor von . Die Auftragsfelder können beliebig sein, da sie das Problem nur erschweren. Nun, wenn wir eine willkürliche Abfrage von , und$n$$x$$|x| = n$$x_j = 1$$j$$x_j = 0$$1$$2^n$$k$$k$$AND$$OR$$NOT$s dann stellt dies nur eine SAT-Frage zu Variablen. Nach der exponentiellen Zeithypothese können wir nicht erwarten, dass dies viel schneller als ... oder mit anderen Worten, wir können nicht erwarten, dass dies viel schneller ist als das Durchsuchen der gesamten Datenbank.$n$$2^n$

Wir sollten keine effiziente Suche in der Länge der Abfrage erwarten (durch Reduktion auf SAT). Wir sollten auch nicht viel besseres erwarten, als alle Elemente in der Datenbank anhand der exponentiellen Zeithypothese zu betrachten.

Um auf eine effiziente Datenstruktur für diese Frage zu hoffen, müssen wir einige ernsthafte Annahmen über die Struktur der Datenbank treffen, die in dieser Frage nicht getroffen werden. Wenn wir beispielsweise eine spezielle Struktur für die Abfragen annehmen (z. B. CNF), können wir auf etwas Effizienteres hoffen. Eine alternative Annahme betrifft die Struktur der Datenbank. Wir könnten wahrscheinlich annehmen, dass bei Tags nur ein kleiner Teil der Tags auf einer bestimmten ID vorhanden ist (sagen wir logarithmisch einige s). Dies ist angesichts der Anwendung von getaggten Fragen keine unangemessene Annahme (was nützen Tags, wenn fast jedes einzelne Tag für eine Frage verwendet wird).$n$$1$

Dies ist eine ziemlich einfache Antwort, aber ich denke effektiv:

Ein suggestiver Typ für Ihre Datenstruktur: Map Tag ([Id],[Id])Hier werden die beiden ID- Listen nach Reihenfolge1 bzw. Reihenfolge2 sortiert. Das Verwalten und Generieren dieser Struktur ist mit Kosten verbunden, aber Abfragen für ein einzelnes Tag sollten in der Anzahl der Tags . Das Speichern der Länge der Listen mit den Listen würde bei der Abfrageoptimierung helfen, und viel besser als eine tatsächliche Liste wäre ein fauler Bitvektor, der die Negation ebenfalls extrem billig machen würde.$O(log (n))$

Wenn Sie eine andere Karte des Typs Map Id (Set Tag)einwerfen, sollte die Erzeugung der zugehörigen Frequenzen bei einer Liste von Ids in der Größe der Liste und der Größe der Sätze von Tags sein.$O(n * log (m))$