Recherche d'ensembles comportant des sous-ensembles spécifiques

Question

Je suis un étudiant diplômé en physique et je travaille sur l'écriture de code pour trier plusieurs centaines de giga-octets de données et renvoyer des tranches de ces données lorsque je le demande. Voici le truc, je ne connais aucune bonne méthode pour trier et rechercher des données de ce genre.

Mes données consistent essentiellement en un grand nombre d'ensembles de nombres. Ces ensembles peuvent contenir entre 1 et n nombres (même si dans 99,9% des ensembles, n est inférieur à 15) et il y en a environ 1,5 à 2 milliards (malheureusement, cette taille empêche toute recherche par force brute).

Je dois pouvoir spécifier un ensemble avec k éléments et que chaque ensemble avec k + 1 éléments ou plus contenant le sous-ensemble spécifié me soit renvoyé.

Exemple simple:
Supposons que je dispose des ensembles suivants pour mes données:
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
(5,8,11)

Si je devais donner la demande (1,3), j'aurais les ensembles: (1,2,3), (1,2,3,4,5) et (1,3,8,9).
La requête (11) renverrait l'ensemble: (5,8,11).
La demande (1,2,3) renverrait les ensembles: (1,2,3) et (1,2,3,4,5)
La requête (50) ne renverrait aucun jeu:

À présent, le schéma devrait être clair. La principale différence entre cet exemple et mes données est que les ensembles sans mes données sont plus grands, les nombres utilisés pour chaque élément des ensembles vont de 0 à 16383 (14 bits), et il en existe beaucoup plus.

Si c'est important, j'écris ce programme en C ++, mais je connais aussi java, c, un certain assembly, un autre pour Foran et un peu de Perl.

Quelqu'un at-il des indices sur la manière de retirer ceci?

modifier:
Pour répondre à quelques questions et ajouter quelques points:

1.) Les données ne changent pas. Tout cela a été pris dans une longue série d'essais (chacun divisé en fichiers de 2 gig).

2.) Comme pour l’espace de stockage. Les données brutes prennent environ 250 gigaoctets. J'estime qu'après avoir traité et éliminé de nombreuses métadonnées superflues qui ne m'intéressent pas, je pourrais le réduire à 36-48 gigaoctets, selon le nombre de métadonnées que je décide de conserver (sans index). De plus, si lors du traitement initial des données, je rencontre un nombre suffisant d'ensembles identiques, je pourrais peut-être encore plus compresser les données en ajoutant des compteurs pour les événements répétés, plutôt que de simplement répéter ces événements encore et encore.

3.) Chaque numéro dans un ensemble traité contient en fait au moins deux nombres: 14 bits pour les données elles-mêmes (énergie détectée) et 7 bits pour les métadonnées (numéro de détecteur). J'aurai donc besoin d'au moins trois octets par numéro.

4.) Mon " bien que dans 99,9% des ensembles, n soit inférieur à 15 & "; commentaire était trompeur. Après un coup d’œil préliminaire sur quelques-uns des morceaux de données, je trouve que j’ai des ensembles qui contiennent jusqu’à 22 nombres, mais la médiane est de 5 nombres par ensemble et la moyenne est de 6 nombres par ensemble.

5.) Bien que l’idée de construire un index de pointeurs dans des fichiers me plaise, je suis un peu méfiant, car pour les demandes impliquant plus d’un nombre, il me reste la tâche semi-lente (du moins, je pense qu’elle est lente): trouver l'ensemble de tous les pointeurs communs aux listes, c'est-à-dire trouver le plus grand sous-ensemble commun pour un nombre donné d'ensembles.

6.) En termes de ressources à ma disposition, je peux rassembler environ 300 Go d'espace disque après avoir les données brutes sur le système (le reste de mon quota sur ce système). Le système est un serveur biprocesseur doté de 2 contrôleurs quad core et de 16 Go de RAM.

7.) Oui 0 peut se produire, c’est un artefact du système d’acquisition de données, mais il peut se produire.

Answer 1

J'ai récemment découvert des méthodes qui utilisent des courbes de remplissage d'espace pour mapper les données multidimensionnelles vers une seule dimension. On peut alors indexer les données en fonction de son index 1D. Les requêtes de plage peuvent être facilement effectuées en recherchant les segments de la courbe qui intersectent la case qui représente la courbe, puis en récupérant ces segments.

Je pense que cette méthode est de loin supérieure à la création des index insensés suggérés, car après les avoir examinés, l’indice serait aussi volumineux que les données que je souhaitais stocker, ce qui n’est guère une bonne chose. Vous trouverez une explication un peu plus détaillée à l’adresse suivante:

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

Answer 2

Votre problème est le même que celui rencontré par les moteurs de recherche. & J'ai; un bajillion de documents. J'ai besoin de ceux qui contiennent cet ensemble de mots. & Quot; Vous avez juste (très commodément), des nombres entiers au lieu de mots et de petits documents. La solution est un index inversé . Introduction à la recherche d'informations par Manning et al is (at Ce lien), disponible gratuitement en ligne, est très lisible et vous expliquera comment le faire.

Vous allez devoir payer un prix sur l’espace disque, mais il peut être parallélisé et devrait être suffisamment rapide pour répondre à vos besoins en termes de temps, une fois que l’indice est construit.

Answer 3

En supposant une distribution aléatoire de 0-16383, avec une cohérence de 15 éléments par ensemble et deux milliards d'ensembles, chaque élément apparaîtrait dans environ 1,8 million d'ensembles. Avez-vous envisagé (et avez-vous la capacité de) de construire une table de correspondance 16384x ~ 1.8M (30B entrées, 4 octets chacune)? Avec une telle table, vous pouvez rechercher quels ensembles contiennent (1) et (17) et (5555), puis rechercher les intersections de ces trois listes de ~ 1,8 M éléments.

Answer 4

Mon hypothèse est la suivante.

Supposons que chaque ensemble ait un nom, un identifiant ou une adresse (un nombre de 4 octets suffira s'il n'y en a que 2 milliards).

Parcourez tous les ensembles une fois et créez les fichiers de sortie suivants:

• Un fichier contenant les identifiants de tous les ensembles contenant '1'
• Un fichier contenant les identifiants de tous les ensembles contenant "2"
• Un fichier contenant les identifiants de tous les ensembles contenant '3'
• ... etc ...

S'il y a 16 entrées par série, chacun de ces 2 ^ 16 fichiers contiendra en moyenne les identifiants de 2 ^ 20 séries; avec chaque identifiant étant de 4 octets, cela nécessiterait 2 ^ 38 octets (256 Go) de stockage.

Vous ferez une fois ce qui précède avant de traiter les demandes.

Lorsque vous recevez des demandes, utilisez ces fichiers comme suit:

• Regardez quelques chiffres dans la demande
• Ouvrez quelques fichiers d'index correspondants
• Obtenez la liste de tous les ensembles présents dans ces deux fichiers (il n'y a qu'un million d'identifiants dans chaque fichier, cela ne devrait donc pas être difficile)
• Voir lequel de ces quelques jeux satisfait le reste de la demande

Je suppose que si vous procédez comme indiqué ci-dessus, la création des index sera (très) lente et le traitement des demandes sera (très) rapide.

Answer 5

Créez 16383 fichiers d’index, un pour chaque valeur de recherche possible. Pour chaque valeur de votre jeu d'entrées, écrivez la position du début du jeu dans le fichier d'index correspondant. Il est important que chacun des fichiers d'index contienne le même numéro pour le même ensemble. Désormais, chaque fichier d’index sera constitué d’index ascendants dans le fichier maître.

Pour effectuer une recherche, commencez à lire les fichiers d’index correspondant à chaque valeur de recherche. Si vous lisez un index inférieur à celui que vous avez lu à partir d'un autre fichier, supprimez-le et lisez-en un autre. Lorsque vous obtenez le même index de tous les fichiers, vous obtenez une correspondance: obtenez l'ensemble à partir du fichier maître et lisez un nouvel index à partir de chacun des fichiers d'index. Une fois que vous avez atteint la fin d’un des fichiers d’index, vous avez terminé.

Si vos valeurs sont réparties uniformément, chaque fichier d'index contiendra 1/16383 des jeux d'entrées. Si votre ensemble de recherche moyen comprend 6 valeurs, vous effectuerez un passage linéaire au-dessus de 6/16383 de votre entrée d'origine. C'est toujours une solution O (n), mais votre n est un peu plus petit maintenant.

P.S. La valeur zéro est-elle impossible, ou avez-vous vraiment 1638 4 possibilités?

Answer 6

Je me fais l'avocat du diable pour une approche qui inclut la recherche force brute + index:

1. Créez un index avec les éléments min, max et no.
2. Appliquez ensuite la force brute en excluant les ensembles où max < max (ensemble en cours de recherche) et min > min (ensemble en cours de recherche)
3. En force brute, excluez également les ensembles. Le nombre total d'éléments est inférieur à celui de l'ensemble recherché.

95% de vos recherches seraient vraiment brutales forçant un très petit sous-ensemble. Juste une pensée.