Struktura danych, która umożliwia wydajne wyszukiwanie w oparciu o znaczniki

Szukam wysoce wydajnej struktury danych do przechowywania danych podobnych do poniższych.

Identyfikatory Zamówienie 1 Zamówienie 2 
--------------------------
1 1,2 1 1
2 2,5 2 3
3 1,7 4 7
4 6 3 0

Muszę być w stanie kwerendy tej struktury w taki sposób, że daje mi listę wszystkich identyfikatorów zawierających wyraz tagów - wspieranie ANDi ORi NOToperacje. Na przykład. ((1 lub 2) i nie 7)

Potrzebuję też być w stanie określić kolejność wyników (Order1 lub Order2) i być w stanie określić maksymalną liczbę wierszy zwracanych z opcjonalnym przesunięciem. Kluczowe znaczenie ma wydajność przy pobieraniu pierwszych 30–100 wyników.

Na koniec potrzebuję taniego sposobu na wyszukanie „relacji znaczników”, na przykład chcę wiedzieć, które znaczniki „odnoszą się” do znaczników (1 LUB 2) i na jakiej częstotliwości. Oznacza, które tagi pojawiają się w tym samym zestawie co 1 LUB 2 ... uporządkowane według częstotliwości.

Masz pojęcie o tym, która struktura danych (lub zestaw struktur) byłaby wysoce wydajna dla tego rodzaju pracy?

(Chciałbym użyć tego jako dowodu koncepcji przeprojektowania otagowanych stron rodziny witryn SE)

ds.data-structures application-of-theory db.databases

— Sam Saffron
źródło

Tylko komentarz (może trywialny). Dlaczego nie polegasz na systemie zarządzania relacyjnymi bazami danych? Możesz zdefiniować tabelę za pomocą par <id, tag> i dodać indeks do kolumny tagu. Następnie możesz użyć standardowych zapytań SQL do wyodrębnienia danych. RDBMS skutecznie wykona „brudną” pracę związaną z optymalizacją zapytań i sortowaniem danych wyjściowych.

— Marzio De Biasi

@Vor, wyrażenia są niezwykle nieefektywne na dużą skalę, łączenie się staje się koszmarnymi zapytaniami.

— Sam Saffron

@Sam: ok. Twoje zadanie jest dość powszechne, więc pomyślałem, że dobry RDBMS (z narzędziem do eksploracji danych) może to zrobić. Oddaję głos ekspertowi od struktury danych. :-)

— Marzio De Biasi

Uważam, że zezwolenie na wszystkie kombinacje AND, OR, NOT utrudni utworzenie struktury danych, która nie zawiera wszystkich elementów (być może może być ograniczona do 3-CNF?). Jeśli takie ograniczenie nie istnieje, być może po prostu przejrzyj rekordy (w określonej kolejności), aż znajdziesz 30–100 spełniających wymagania dotyczące tagu. Chociaż generalnie zgadzam się z sugestią Vora, aby użyć bazy danych do wykonania ciężkiego podnoszenia.

— bbejot

Nie jestem ekspertem, ale myślę, że jeśli nie nałożysz żadnych ograniczeń na sposób, w jaki możesz pytać o tagi, będzie to trudne. Ograniczenie ich do CNF (jak sugeruje bbejot) jest jednym sposobem, innym jest ograniczenie liczby różnych znaczników, o które zapytanie może zapytać małą liczbą (powiedzmy 6).

— Kaveh

Odpowiedzi:

To nie jest dokładnie odpowiedź na efektywną strukturę danych, ale raczej rozwinięcie komentarzy @bbejot i @Kaveh, podających wymachujący ręką argument, dlaczego biorąc pod uwagę bieżące pytanie, nie powinniśmy oczekiwać czegoś, co będzie o wiele lepsze niż wyszukiwanie cała baza danych. Argument opiera się na redukcji z SAT, hipotezie o wykładniczym czasie i wielu machaniu ręką.

Załóżmy, że mamy do różnych znaczników, wtedy możemy myśleć o każdym identyfikatorze jako związanym z bitvektorem o długości gdzie jeśli mamy -ty znacznik, a przeciwnym razie. Ponieważ nie ma rzeczywistych ograniczeń dotyczących wyglądu bazy danych, mogę założyć, że ma ona identyfikatory od do przy czym -ty identyfikator ma powiązany wektor znaczników $n$ $x$ $|x| = n$ $x_j = 1$ $j$ $x_j = 0$ $1$ $2^n$ $k$ $k$ napisane binarnie. Pola zamówienia mogą być dowolne, ponieważ tylko utrudniają problem. Otóż, jeśli otrzymamy arbitralne zapytanie , i to po prostu zadajemy pytanie SAT dotyczące zmiennych. Zgodnie z hipotezą wykładniczą dotyczącą czasu, nie możemy oczekiwać, że będzie to znacznie szybsze niż ... lub innymi słowy, nie możemy oczekiwać, że będzie to znacznie szybsze niż przeszukiwanie całej bazy danych. $AND$ $OR$ $NOT$ $n$ $2^n$

Nie należy oczekiwać wydajnego wyszukiwania w długości zapytania (poprzez redukcję do SAT). Nie powinniśmy również oczekiwać dużo lepszego niż przeglądanie wszystkich pozycji w bazie danych według wykładniczej hipotezy czasowej.

$n$ $1$

— Artem Kaznatcheev
źródło

Dobra obserwacja. Każde pytanie ma maksymalnie 5 tagów, więc zapytanie dotyczące tagów jest równoważne 5-CNF.

— Kaveh

Dziękuję Ci! tak, możemy założyć, że 5-CNF dalej, zachowanie tagowania nie jest przypadkowe. Zasadniczo ludzie będą oznaczać rzeczy najczęściej używanymi tagami, więc pozwoli to na kilka innych skrótów.

— Sam Saffron,

@Kaveh, zakończyliśmy tworzenie struktury pamięci. Istnieje kilka nietrywialnych skrótów, sortowanie jest wąskim gardłem, używanie sortowania sterty lub zmodyfikowane szybkie sortowanie pozwala na skuteczne wybranie najwyższego N bez konieczności wykonywania pełnego sortowania. sortowanie przed obliczeniem pozwala na efektywniejsze wybieranie osi przestawnych i unikanie sortowania, gdy potrzebne jest pełne skanowanie. wielowątkowość przyspiesza wybór. wiele pracy można odroczyć w tle, zanim użytkownicy wejdą w interakcje ze strukturami. zadziwiająco nasze struktury w pamięci wynoszą średnio 0 ms dla wyszukiwania w zestawie danych przepełnienia stosu.

— Sam Saffron

@SamSaffron - Gdzie jest post MSO opisujący tę funkcję? Mamy tutaj raport o błędzie .

— Kevin Vermeer

To dość prosta odpowiedź, ale uważam, że jest skuteczna:

Map Tag ([Id],[Id]) $O(log (n))$

Map Id (Set Tag)Id $O(n * log (m))$

— sclv
źródło

Zazwyczaj zgadzam się, że niektóre bardzo proste struktury, takie jak mapa buforowana wiele razy, mogą być najlepszym sposobem na przejście tutaj. pamięć jest tania, a utrzymywanie wielu pamięci podręcznych nie jest zbyt trudne

— Sam Saffron