Algorithmus für die schnelle Tag-Suche

Das Problem ist folgendes.

• Es gibt eine Reihe von einfachen Entitäten E, an die jeweils eine Reihe von Tags T angehängt ist. Jede Entität kann eine beliebige Anzahl von Tags haben. Die Gesamtzahl der Entitäten liegt bei fast 100 Millionen, und die Gesamtzahl der Tags liegt bei etwa 5000.

Die anfänglichen Daten sind also ungefähr so:

E1 - T1, T2, T3, ... Tn
E2 - T1, T5, T100, ... Tk
..
Ez - T10, T12, ... Tl

Diese Anfangsdaten werden ziemlich selten aktualisiert.

• Irgendwie generiert meine App einen logischen Ausdruck für Tags wie dieses:

  T1 & T2 & T3 | (T5 &! T6)

• Ich muss eine Anzahl von Entitäten berechnen, die mit dem angegebenen Ausdruck übereinstimmen (Anmerkung - nicht die Entitäten, sondern nur die Anzahl). Dieser könnte natürlich nicht ganz genau sein.

Was ich jetzt habe, ist eine einfache In-Memory-Tabellensuche, die mir eine Ausführungszeit von 5-10 Sekunden für einen einzelnen Thread gibt.

Ich bin neugierig, gibt es eine effiziente Möglichkeit, mit diesen Dingen umzugehen? Welchen Ansatz würden Sie empfehlen? Gibt es dafür einige gebräuchliche Algorithmen oder Datenstrukturen?

Aktualisieren

Ein bisschen Klarstellung, wie gewünscht.

1. TObjekte sind eigentlich relativ kurze konstante Zeichenfolgen. Aber es spielt eigentlich keine Rolle - wir können immer einige IDs zuweisen und Ganzzahlen verarbeiten.
2. Wir können sie definitiv sortieren.

Ich würde dies in SQL mit einer Verknüpfungstabelle EntityCategoryzwischen eidreferenzierender Entität und cidreferenzierender Kategorie unter Verwendung von Self-Joins tun :

    select count(ec1.eid)
    from EntityCategory ec1 
    left join EntityCategory ec2 on ec1.eid=ec2.eid 
    left join EntityCategory ec3 on ec1.eid=ec3.eid 
    ...
    where 
      ec1.cid={categoryId1} and 
      ec2.cid={categoryId2} and
      ec3.cid={categoryId3} ...

Nachdem ich diese Antwort geschrieben habe, sollte ich die Frage wahrscheinlich als "zu umfassend" kennzeichnen - wir können seit Ewigkeiten über verschiedene Strategien sprechen, am Ende muss ein Benchmark mit Ihren Daten durchgeführt werden.

Jedes Tag kann effizient durch eine ganze Zahl dargestellt werden. Jede Entität verfügt über eine Reihe von Tags. Die Wahl der richtigen Mengenimplementierung ist wichtig - sowohl B-Bäume als auch sortierte Arrays sind möglich. Mit diesem Set werden nur Mitgliedschaftstests durchgeführt. Da beide Strukturen dies in O (log t) (mit t Tags pro Entität) tun , würde ich Arrays aufgrund ihrer dichteren Darstellung vorziehen.

Wir können jetzt alle Entitäten in einer O (n · log t · p) -Operation filtern , wobei p die durchschnittliche Pfadlänge im Prädikatentscheidungsbaum ist. Dieser Entscheidungsbaum kann bestellt werden, damit eine Entscheidung schnell getroffen werden kann. Ohne statistische Daten ist es nur möglich, häufige Unterausdrücke herauszurechnen.

Die Reihenfolge, in der die Entitäten durchsucht werden, ist nicht wirklich wichtig. Auf der anderen Seite kann es vorteilhaft sein, es so zu sortieren, dass die Entities bei Indizes 0für ialle ein bestimmtes Tag haben, während der Rest nicht. Dies reduziert das n bei der Suche nach diesem bestimmten Tag (im Entscheidungsbaum sollte dies der erste Test sein). Dies kann auf mehrere Ebenen erweitert werden, erschwert jedoch die Dinge und benötigt O (2 ^k ) Speicher mit kEbenen. Bei mehreren Ebenen sollten die Tags mit der höchsten Verstärkung zuerst bestimmt werden, wobei die Verstärkung die Anzahl der Entitäten ist, die nicht nachgeschlagen werden müssen, multipliziert mit der Wahrscheinlichkeit, dass sie verworfen werden. Der Gewinn wird maximal für 50:50 Chancen oder wenn 50% der Entitäten dieses spezifische Tag haben. Auf diese Weise können Sie auch dann optimieren, wenn die Zugriffsmuster nicht bekannt sind.

Sie können auch Mengen erstellen, die die Entitäten nach jedem verwendeten Tag indizieren - eine Menge mit allen Entitäten für T1, die nächste für T2. Eine naheliegende (räumliche und zeitliche) Optimierung besteht darin, zu stoppen, wenn eine Menge mehr als die Hälfte aller Elemente enthält, und die Elemente zu speichern, die dieses Tag nicht haben. Auf diese Weise dauert das Erstellen von Indizes für alle Tags weniger als ½ · n · tLeerzeichen (mit insgesamt t Tags). Beachten Sie, dass das Speichern von Ergänzungssätzen andere Optimierungen erschweren kann. Auch hier würde ich Arrays für die Sets (sortieren).

Wenn Sie Ihre Entitäten auch durch einen ganzzahligen Bereich darstellen, können Sie den für die Indexmengen verwendeten Platz komprimieren, indem Sie nur das Start- und Endelement eines fortlaufenden Bereichs speichern. In Bezug auf die Implementierung würde dies wahrscheinlich mit einem hohen Bit erfolgen, um anzuzeigen, ob es sich bei einem Eintrag um einen bereichsgebundenen oder einen regulären Eintrag handelt.

Wenn wir jetzt Indexmengen (und damit Statistiken zu den Tags) haben, können wir unsere Prädikate so optimieren, dass unwahrscheinliche Eigenschaften zuerst getestet werden (Fail-Fast-Strategie). Dies bedeutet, dass das Prädikat ausgewertet werden sollte, indem alle Indexsatzeinträge durchlaufen und jedes Element auf überprüft wird , wenn dies T1häufig und T2selten vorkommt .T1 & T2T2T1

Wenn wir sortierte Arrays verwenden, um die Indexmengen zu implementieren, können viele Bewertungsschritte als Zusammenführungsoperationen implementiert werden. T1 & T2bedeutet, dass wir die T1und T2-Listen nehmen, einem Ziel-Array die Größe der größeren Eingaben zuweisen und den folgenden Algorithmus ausführen, bis beide Eingaben leer sind: Wenn T1[0] < T2[0], dann T1++(den Kopf verwerfen). Wenn T1[0] > T2[0]dann T2++. Wenn beide Köpfe gleich sind, dann kopiert werden, diese Zahl über an die Zielanordnung und inkrementieren alle drei Zeiger ( T1, T2, Ziel). Wenn das Prädikat ist T1 | T2, werden keine Elemente verworfen, sondern das kleinere kopiert. Ein Prädikat der Form T1 & ¬T2kann auch eine Verschmelzung Strategie implementiert werden, aber ¬T1oder T1 | ¬T2nicht.

Dies sollte bei der Bestellung des Prädikat-Entscheidungsbaums berücksichtigt werden: Komplemente sollten entweder auf der rechten Seite eines &oder am Ende auftreten, wenn die endgültige Zählung ermittelt wird und die tatsächlichen Elemente nicht überprüft werden müssen.

Ohne Verwendung von Indexsätzen kann jeder Thread durch seinen Teil der Entitäten filtern und die Anzahl der Elemente zurückgeben, die mit dem Prädikat übereinstimmen, das summiert werden kann. Wenn Indexmengen verwendet werden, wird jedem Thread ein Knoten im Entscheidungsbaum zugewiesen. Es werden zwei Eingabestreams benötigt, die den geordneten Mengen entsprechen, und ein zusammengeführter Stream wird zurückgegeben. Beachten Sie, dass jeder Knoten im Entscheidungsbaum eine entsprechende Menge hat, die alle Entitäten darstellt, die diesen Unterausdruck erfüllen, und dass es aufgrund der Reihenfolge der Mengen nicht erforderlich ist, die gesamte Menge auf einmal zu kennen, um sie zusammenzuführen .

Verschiedene Strategien wie das Zusammenführen indizierter Mengen oder das Filtern durch eine Liste von Entitäten können zu einem bestimmten Grad kombiniert werden. Das Filtern hat eine sehr vorhersehbare Leistung. Wenn eine Abfrage sehr spezifisch ist, sodass die Verwendung von Indexmengen den Suchbereich drastisch verringert, sind Zusammenführungsvorgänge möglicherweise besser. Es ist wichtig zu beachten, dass das Zusammenführen vieler großer Eingabesätze zu einer wesentlich schlechteren Leistung führen kann als die Brute-Force-Suche. Ein sehr optimierter Algorithmus wählt eine geeignete Strategie basierend auf der Eingabegröße, der Abfragestruktur und den statistischen Indikatoren.

Abgesehen davon kann das Zwischenspeichern von Teilergebnissen von Vorteil sein, wenn erwartet wird, dass ähnliche Abfragen in Zukunft ausgeführt werden, auch wenn sie den ersten Durchlauf nicht beschleunigen.