1. Dom
  2. Pytanie i odpowiedź
  3. Najszybszy sposób wykonywania operacji testowania podzbioru na dużej kolekcji zestawów o tej samej domenie

Najszybszy sposób wykonywania operacji testowania podzbioru na dużej kolekcji zestawów o tej samej domenie

2010-12-28 10 views
5

Załóżmy, że mamy gdzieś biliony zestawów. Domena każdego z tych zestawów jest taka sama. Jest również skończony i dyskretny. Zatem każdy zestaw może być przechowywany jako pole bitowe (np .: 0000100111 ...) o stosunkowo krótkiej długości (np. 1024). Oznacza to, że bit X w polu bitowym wskazuje, czy element X (z 1024 możliwych pozycji) jest zawarty w podanym zestawie, czy nie.Najszybszy sposób wykonywania operacji testowania podzbioru na dużej kolekcji zestawów o tej samej domenie

Teraz chcę zaprojektować strukturę pamięci masowej i algorytm, aby efektywnie odpowiedzieć na zapytanie: jakie zestawy w składnicy danych ustawiły Y jako podzbiór. Sama wartość Y nie występuje w składnicy danych i jest określona w czasie wykonywania.

Teraz najprostszym sposobem rozwiązania tego problemu będzie I bitfield dla zestawu Y z polami bitowymi każdego zestawu w składnicy danych jeden po drugim, wybierając te, których I wynik pasuje do pola bitowego Y.

Jak mogę to przyspieszyć? Czy istnieje struktura drzewa (indeks) lub jakiś inteligentny algorytm, który pozwoliłby mi na wykonanie tej kwerendy bez konieczności korzystania z każdego pola bitowego zestawu przechowywanego?

Czy istnieją bazy danych, które już obsługują takie operacje w dużych kolekcjach zestawów?

Źródło

2010-12-28 niktech

+0

Jakiego typu bazy danych używasz? Zastrzeżony format? Serwer SQL? –

+0

Wybór DB będzie zależeć od tego, czy efektywnie obsługuje określone operacje na setach humongous. Żaden z SQL DBS nie skaluje się do wymaganego rozmiaru (RDMS DB i tak byłby złym wyborem dla tego problemu). Zatem wybór jest albo wyspecjalizowanym DB, albo DB, który sam będę realizował. – niktech

+0

Czy znalazłeś jakieś rozwiązanie? To dziwne, że nie ma dobrze znanych baz danych do tego zadania. – actual

Odpowiedz

0

Zazwyczaj mówię, że odpowiedź brzmi nie, ponieważ pole bitowe ma bardzo niską liczebność.

Źródło

2010-12-28 00:57:51

0

To byłby odcinek na konwencjonalnym RDBMS w oparciu o wolumen, czy patrzysz na Neo4j, który jest oparty na modelu przechowywania wykresów?

Źródło

2010-12-28 01:03:43 kd7

+1

Czy skutecznie obsługuje pracę z dużymi zestawami?Z mojego rozumowania jest to bardziej przydatne do przechowywania wykresów, a nie zestawów. – niktech

4

Jeśli możesz wstępnie przetworzyć zestawy, relacja podzbioru jest reprezentowana jako DAG (ponieważ opisujesz poset). Jeśli obliczana jest redukcja przechodnia, to myślę, że możesz uniknąć testowania wszystkich zestawów, wykonując tylko DFS zaczynając od największych zestawów i zatrzymując się, gdy Y nie jest już podzbiorem bieżącego zestawu, który jest odwiedzany.

Źródło

2010-12-28 06:29:09 lijie

+0

Czy możesz rozwinąć? Czy w gruncie rzeczy mówisz o budowaniu DAG, jak na poniższym http://en.wikipedia.org/wiki/File:Hypercubeorder_binary.svg, ale tylko z węzłami z kolekcji istniejących zestawów? Jak wybrałbym początkowy węzeł podczas pracy z DFS? – niktech

+2

tak, zasadniczo. istnieje pewna krawędź od zbioru A do zbioru B, jeśli A jest nadzbiorem B. Użycie przejścia przechodniego jest lepsze, ponieważ zmniejsza się liczba krawędzi (więc współczynnik rozgałęzienia również powinien się zmniejszyć, aby zbadać mniej bezużyteczne węzły). Ponieważ wykres jest acykliczny, pojawi się zestaw węzłów, które nie mają żadnych krawędzi, które można do nich wprowadzić, i możesz zacząć od tego miejsca (te reprezentują zestawy, które nie mają żadnych supersetów w twojej kolekcji). Musiałbyś uruchomić DFS na wszystkich tych (lub po prostu zacząć od wirtualnego węzła połączonego z tymi wszystkimi zestawami - bez supersesji). – lijie

+0

Interesujące. Będę pamiętał o tym algorytmie, chociaż nie jest prawdopodobne, że zbiór zbiorów w składnicy danych będzie zawierał wiele relacji podzestawu/supersetu, a zatem skończę z obsługą DFS w wielu początkowych węzłach. – niktech

1

W zależności od liczności zbioru, z którego rysowane są wszystkie zestawy, jedną opcją może być zbudowanie odwróconego odwzorowania indeksu z elementów do zestawów, które je zawierają. Biorąc pod uwagę zestaw Y, można znaleźć wszystkie zestawy, które mają Y jako podzbiór, znajdując wszystkie zestawy, które zawierają każdy element indywidualnie i obliczając ich przecięcie. Jeśli przechowujesz listy w posortowanej kolejności (na przykład numerując wszystkie zestawy w bazie danych z wartościami 0, 1 itd.), Powinieneś być w stanie dość wydajnie obliczyć to skrzyżowanie, zakładając, że nie ma w nim też ani jednego elementu wiele zestawów.

Źródło

2010-12-28 16:39:29 templatetypedef

+0

Dobra uwaga. Liczność zbiorów w magazynie danych wynosi ~ <= 1024. Teraz trudną częścią będzie wydajne robienie tego przecięcia. Wynik przecięcia może być tak duży, jak cały zbiór zestawów lub tak mały jak kilkadziesiąt zestawów. Jakie algorytmy przecięcia poleciłbyś? – niktech

+0

Wiem, że w przypadku, gdy masz dwie posortowane sekwencje i chcesz obliczyć skrzyżowanie, możesz to zrobić, powtarzając następujące czynności: gdy dwie listy nie są puste, spójrz na pierwszą wartość każdej sekwencji. Jeśli nie są takie same, usuń mniejszy z nich. Jeśli są takie same, wykryto wartość w przecięciu. To działa w czasie O (n + m), gdzie n i m są długością dwóch sekwencji. Jeśli uruchomisz tę procedurę na parach sekwencji, to na wynikach itd. Przebiega ona w O (n lg k), gdzie k jest liczbą sekwencji i n maksymalną długością sekwencji. – templatetypedef

0

Szybki rzut oka sprawia, że ​​myślę o BDD - co jest nieco zgodne z ideą rozwiązania DAG. Alternatywnie może to być ZDD.

Źródło

2010-12-28 16:43:27

 Powiązane problemy

  • Brak powiązanych problemów^_^