Encontrar conjuntos que têm subconjuntos específicos

Question

Eu sou um estudante de pós-graduação de física e eu estou trabalhando em escrever algum código para ordenar várias centenas de gigabytes de dados e fatias de retorno de que os dados quando eu pedir para ela. Aqui está o truque, eu não conheço nenhum bom método para classificação e pesquisa de dados desse tipo.

Os meus dados consiste essencialmente de um grande número de conjuntos de números. Estes conjuntos podem conter de 1 a n números dentro deles (embora em 99,9% dos conjuntos, n é inferior a 15) e há cerca de 1,5 ~ 2 bilhões desses conjuntos (Infelizmente, este tamanho impede uma busca força bruta).

Eu preciso ser capaz de especificar um conjunto com k elementos e tem todo o conjunto com + 1 k elementos ou mais que contém o subconjunto específico voltou para mim.

Exemplo Simples:
Suponha que eu tenho os seguintes conjuntos para os meus dados:
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
(5,8,11)

Se eu fosse dar a solicitação (1,3) eu teria os conjuntos: (1,2,3), (1,2,3,4,5), e (1,3,8,9).
O pedido (11) deve retornar o conjunto:. (5,8,11)
O pedido (1,2,3) iria devolver os conjuntos: (1,2,3) e (1,2,3,4,5)
O pedido (50) voltaria há conjuntos:

Até agora o padrão deve ser clara. A principal diferença entre este exemplo e os dados é que os conjuntos withn os dados são maiores, os números usados ??para cada elemento de um dos conjuntos de correr de 0 a 16383 (14 bits), e existem muitas muitos mais conjuntos.

Se é importante que eu estou escrevendo este programa em C ++ embora eu também sei java, c, alguns montagem, alguns fortran, e alguns perl.

Alguém tem alguma pista de como fazer isso?

edit:
Para responder a algumas perguntas e adicionar alguns pontos:

1.) Os dados não muda. Foi tudo tomado em uma longa série de corridas (cada um dividido em 2 arquivos GIG).

2.) Quanto espaço de armazenamento. Os dados brutos ocupa aproximadamente 250 gigabytes. Estimo que após o processamento e tirando um monte de metadados estranho que eu não estou interessado em que eu poderia bater que para baixo para em qualquer lugar de 36 a 48 gigabytes, dependendo de quanto metadados eu decidir manter (sem índices). Além disso, se no meu processamento inicial dos dados que eu encontro conjuntos suficientes que são os mesmos que eu poderia ser capaz de comress os dados ainda mais pela adição de contadores para eventos de repetição ao invés de simplesmente repetir os eventos e outra vez.

3.) Cada número dentro de um conjunto processado realmente contém pelo menos dois números de 14 bits para o próprio (energia detectada dados) e 7 bits para metadados (número detector). Então eu vou precisar de pelo menos três bytes por número.

4). Meu "embora em 99,9% dos conjuntos, n é inferior a 15" comentário foi enganosa. Em um olhar preliminar através de alguns dos pedaços dos dados que eu acho que eu tenho conjuntos que contêm até 22 números, mas a média é de 5 números por conjunto ea média é de 6 números por set.

5.) Enquanto eu gosto da idéia de construir um índice de ponteiros em arquivos estou um pouco desconfiado, porque as solicitações que envolvem mais de um número eu fiquei com a tarefa semi lenta (pelo menos eu acho que é lento) de encontrar o conjunto de todos os ponteiros comum nas listas, ou seja, encontrar o maior subconjunto comum para um determinado número de conjuntos.

6.) Em termos de recursos disponíveis para mim, eu posso reunir cerca de 300 GB de espaço depois de eu ter os dados brutos sobre o sistema (O restante da minha cota nesse sistema). O sistema é um servidor de processador duplo com 2 quad core AMD Opteron e 16 gigabytes de RAM.

7). Sim 0 pode ocorrer, é um artefato do sistema de aquisição de dados quando isso acontece, mas pode ocorrer.

Answer 1

Eu descobri recentemente métodos que usam curvas de preenchimento do espaço para mapear os dados multi-dimensionais para baixo a uma única dimensão. Pode-se então indexar os dados com base em seu índice 1D. consulta de intervalo pode ser facilmente realizado por encontrar os segmentos da curva que cruzam a caixa que representa a curva e, em seguida, recuperar esses segmentos.

Eu acredito que este método é muito superior ao fazer os índices insanas como sugerido porque depois de olhar para ele, o índice seria tão grande quanto os dados que eu queria store, dificilmente uma coisa boa. Uma explicação um pouco mais detalhada deste pode ser encontrado em:

http://www.ddj.com/184410998
e
http://www.dcs.bbk.ac.uk/~jkl/ publications.html

Answer 2

Seu problema é o mesmo que o enfrentado pelos motores de busca. "Eu tenho documentos bajillion. Eu preciso aqueles que contêm este conjunto de palavras." Você apenas tem (muito convenientemente), inteiros, em vez de palavras, e documentos smallish. A solução é uma índice invertido . Introduction to Information Retrieval por Manning et ai é (em que apontam) disponível gratuitamente on-line, é muito legível, e vou entrar em muitos detalhes sobre como fazer isso.

Você vai ter que pagar um preço no espaço em disco, mas pode ser paralelizado, e deve ser mais do que rápido o suficiente para atender às suas necessidades de tempo, uma vez que o índice é construído.

Answer 3

Assumindo uma distribuição aleatória de 0-16383, com uma consistente 15 elementos por set, e dois bilhões de conjuntos, cada elemento iria aparecer em aproximadamente 1.8M sets. Já considerou (e você tem a capacidade para) a construção de uma 16384x ~ 1.8M (entradas 30B, 4 bytes cada) tabela de pesquisa? Diante de tal tabela, você pode consultar quais conjuntos contêm (1) e (17) e (5555) e, em seguida, encontrar as interseções desses três listas ~ 1.8M-elemento.

Answer 4

Meu palpite é a seguinte.

Suponha que cada conjunto tem um nome ou ID ou o endereço (um número de 4 bytes vai fazer se houver apenas 2 bilhões deles).

Agora percorrer todos os conjuntos de uma vez, e criar os arquivos de saída a seguir:

• Um arquivo que contém os IDs de todos os conjuntos que contêm '1'
• Um arquivo que contém os IDs de todos os conjuntos que contêm '2'
• Um arquivo que contém os IDs de todos os conjuntos que contêm '3'
• ... etc ...

Se existem 16 entradas por jogo, em seguida, em média, cada um destes 2 ^ 16 arquivos irão conter os IDs de 2 ^ 20 conjuntos; com cada ID sendo 4 bytes, isso exigiria 2 ^ 38 bytes (256 GB) de armazenamento.

Você vai fazer o acima uma vez, antes de processar os pedidos.

Quando você receber pedidos, usar esses arquivos como segue:

• olhar para um par de números na solicitação
• Abrir-se um par dos arquivos de índice correspondentes
• Obter a lista de todos os conjuntos que existem em ambos os arquivos (há apenas um milhão de IDs em cada arquivo, de modo que este should't ser difícil)
• Veja qual destas alguns conjuntos satisfazer o restante do pedido

Meu palpite é que se você fizer o acima, criar os índices será (muito) lento e solicitações de manipulação será (muito) rápida.

Answer 5

Faça 16383 arquivos de índice, um para cada valor de pesquisa possível. Para cada valor no conjunto de entrada, escrever a posição do arquivo do começo do set no ficheiro de índice correspondente. É importante que cada um dos arquivos de índice contém o mesmo número para o mesmo conjunto. Agora, cada arquivo de índice será composto de índices ascendentes no arquivo mestre.

Para pesquisar, comece a ler os arquivos de índice correspondentes a cada valor de pesquisa. Se você ler um índice que seja mais baixa do que o índice de ler de outro arquivo, descartá-lo e ler outra. Quando você obter o mesmo índice de todos os arquivos, que é um jogo - obter o conjunto do arquivo mestre, e ler um novo índice de cada um dos arquivos de índice. Quando chegar ao final de qualquer um dos arquivos de índice, você está feito.

Se os seus valores estão uniformemente distribuídas, cada arquivo de índice conterá 1/16383 dos conjuntos de entrada. Se o seu conjunto de pesquisa média consiste de 6 valores, você estará fazendo um passe linear ao longo de 6/16383 de sua entrada original. Ainda é uma solução de O (n), mas o seu n é um pouco menor agora.

P.S. É zero um valor de resultado impossível, ou você realmente tem 1638 4 possibilidades?

Answer 6

defensor jogando apenas do diabo por uma abordagem que inclui bruta lookup vigor + índice:

1. Criar um índice com o mínimo, máximo e não de elementos de conjuntos.
2. Em seguida, aplique a força bruta, exceto os grupos onde max min (conjunto que está sendo pesquisado)
3. Na força bruta também excluir conjuntos de todo elemento de contagem é menor que a do conjunto que está sendo procurado.

95% de suas pesquisas seria realmente força bruta de um subconjunto muito menor. Apenas um pensamento.