Algorytm szybkiego wyszukiwania znaczników

Problem jest następujący.

• Istnieje zestaw prostych bytów E, z których każdy ma dołączony zestaw znaczników T. Każda jednostka może mieć dowolną liczbę tagów. Całkowita liczba podmiotów wynosi około 100 milionów, a całkowita liczba tagów to około 5000.

Tak więc początkowe dane są mniej więcej takie:

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

Te początkowe dane są dość rzadko aktualizowane.

• Jakoś moja aplikacja generuje logiczne wyrażenie na takich tagach:

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

• Muszę obliczyć liczbę bytów pasujących do danego wyrażenia (uwaga - nie byty, ale tylko liczba). Oczywiście ten może nie być całkowicie dokładny.

To, co mam teraz, to proste wyszukiwanie w tabeli w pamięci, co daje mi 5-10 sekund na wykonanie pojedynczego wątku.

Jestem ciekawy, czy jest jakiś skuteczny sposób na poradzenie sobie z tymi rzeczami? Jakie podejście poleciłbyś? Czy istnieją do tego jakieś popularne algorytmy lub struktury danych?

Aktualizacja

Trochę wyjaśnienia zgodnie z prośbą.

1. Tobiekty są w rzeczywistości stosunkowo krótkimi ciągami stałymi. Ale to tak naprawdę nie ma znaczenia - zawsze możemy przypisać niektóre identyfikatory i operować na liczbach całkowitych.
2. Zdecydowanie możemy je posortować.

Zrobiłbym to w sql posiadający tabelę linków EntityCategorymiędzy eidjednostką cidodwołującą się a kategorią odwołującą się za pomocą self-joins:

    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} ...

Po napisaniu tej odpowiedzi powinienem prawdopodobnie oznaczyć pytanie jako „zbyt ogólne” - od wieków możemy rozmawiać o różnych strategiach, w końcu trzeba będzie przeprowadzić test porównawczy z Twoimi danymi.

Każdy znacznik może być skutecznie reprezentowany przez liczbę całkowitą. Każda jednostka ma zestaw tagów. Ważny jest wybór prawidłowej implementacji zestawu - możliwe są zarówno B-drzewa, jak i posortowane tablice. Z tym zestawem przeprowadzamy tylko testy członkostwa. Ponieważ obie struktury robią to w O (log t) (z t znacznikami na jednostkę), wolałbym tablice ze względu na ich gęstszą reprezentację.

Możemy teraz filtrować wszystkie jednostki w operacji O (n · log t · p) , gdzie p jest średnią długością ścieżki w drzewie decyzji predykatu. To drzewo decyzyjne można zamówić, aby decyzja mogła zostać szybko podjęta. Bez danych statystycznych możliwe jest jedynie wykluczenie typowego podwyrażenia.

Kolejność przeszukiwania jednostek nie jest tak naprawdę ważna. Z drugiej strony może to być korzystne, aby rozwiązać to tak, że podmioty w indeksach 0do iwszystkich mają pewien znacznik, podczas gdy reszta nie. Zmniejsza to n podczas wyszukiwania tego konkretnego znacznika (w drzewie decyzyjnym powinien to być pierwszy test). Można to rozszerzyć na wiele poziomów, ale komplikuje to wszystko i zabiera pamięć O (2 ^k ) z kpoziomy. W przypadku wielu poziomów najpierw należy zdecydować o znacznikach o najwyższym wzmocnieniu, gdzie wzrost to liczba bytów, które nie muszą być sprawdzane, razy prawdopodobieństwo ich odrzucenia. Zysk staje się maksymalny dla szans 50:50 lub gdy 50% bytów ma ten konkretny znacznik. Umożliwiłoby to optymalizację, nawet jeśli wzorce dostępu nie są znane.

Można również utworzyć zestawy, które indeksują byty według każdego użytego znacznika - jeden zestaw ze wszystkimi elementami dla T1, a drugi dla T2. Oczywistą optymalizacją (przestrzeni i czasu) jest zatrzymanie się, gdy zestaw zawiera więcej niż połowę wszystkich elementów, i zapisanie tych elementów, które nie mają tego znacznika - w ten sposób budowanie indeksów dla wszystkich znaczników zajmie mniej niż ½ · n · tmiejsce (z t tagów ogółem). Pamiętaj, że zapisywanie zestawów uzupełniających może utrudnić inne optymalizacje. Ponownie chciałbym (posortować) tablice dla zestawów.

Jeśli reprezentujesz również swoje jednostki za pomocą zakresu liczb całkowitych, możesz skompresować przestrzeń używaną dla zestawów indeksów, przechowując tylko element początkowy i końcowy ciągłego zakresu. Pod względem implementacji byłoby to prawdopodobnie wykonane za pomocą wysokiego bitu wskazującego, czy wpis jest ograniczeniem zakresu, czy zwykłym.

Jeśli teraz mamy zestawy indeksów (a tym samym statystyki dotyczące tagów), możemy zoptymalizować nasze predykaty, aby najpierw przetestować mało prawdopodobne właściwości (strategia niezawodna). Oznacza to, że jeśli T1jest powszechny i T2rzadki, to predykat T1 & T2powinien zostać oceniony poprzez iterację przez wszystkie T2wpisy zestawu indeksów i testowanie każdego elementu T1.

Jeśli zastosujemy posortowane tablice do zaimplementowania zestawów indeksów, wówczas wiele kroków oceny można zaimplementować jako operacje scalania. T1 & T2oznacza, że ​​bierzemy listy T1i T2, przydzielamy tablicę docelową rozmiar większych danych wejściowych i wykonujemy następujący algorytm, aż oba dane wejściowe będą puste: Jeśli T1[0] < T2[0], to T1++(odrzuć głowę). Jeśli T1[0] > T2[0]potem T2++. Jeżeli obie głowice są równe, skopiuj ten numer na do tablicy docelowej, a przyrost wszystkie trzy wskaźniki ( T1, T2, docelowy). Jeśli predykatem jest T1 | T2, to żadne elementy nie są odrzucane, ale mniejszy jest kopiowany. Predykat formy T1 & ¬T2mogą być również realizowane z wykorzystaniem strategii łączenie, ale ¬T1czy T1 | ¬T2nie.

Należy to wziąć pod uwagę przy zamawianiu drzewka decyzyjnego: uzupełnienia powinny wystąpić albo na RHS &, albo na końcu, gdy ustalana jest ostateczna liczba i nie trzeba patrzeć na rzeczywiste elementy.

Bez użycia zestawów indeksów każdy wątek może filtrować swoją część bytów i zwracać liczbę elementów pasujących do predykatu, które można zsumować. W przypadku korzystania z zestawów indeksów każdemu wątkowi przypisano jeden węzeł w drzewie decyzyjnym. Pobiera dwa strumienie wejściowe, które odpowiadają uporządkowanym zestawom, i zwraca połączony strumień. Zauważ, że każdy węzeł w drzewie decyzyjnym ma odpowiadający mu zestaw, który reprezentuje wszystkie byty spełniające to podwyrażenie, i że z powodu uporządkowania zbiorów nie trzeba znać całego zestawu na raz, aby je scalić .

Różne strategie, takie jak scalanie zestawów indeksowanych lub filtrowanie przez listę jednostek, można w pewnym stopniu łączyć. Filtrowanie ma bardzo przewidywalną wydajność. Jeśli zapytanie jest bardzo szczegółowe, więc użycie zestawów indeksów drastycznie zmniejsza przestrzeń wyszukiwania, wówczas operacje scalania mogłyby być lepsze. Należy zauważyć, że połączenie wielu dużych zestawów danych wejściowych może skutkować znacznie gorszą wydajnością niż wyszukiwanie z użyciem siły. Bardzo zoptymalizowany algorytm wybierze odpowiednią strategię na podstawie wielkości wejściowej, struktury zapytań i wskaźników statystycznych.

Nawiasem mówiąc, buforowanie częściowych wyników może być korzystne, jeśli oczekuje się, że podobne zapytania będą uruchamiane w przyszłości, nawet jeśli nie przyspieszą początkowego uruchomienia.