Ricerca di set con sottoinsiemi specifici

Question

Sono uno studente laureato in fisica e sto lavorando alla scrittura di un codice per ordinare diverse centinaia di gigabyte di dati e restituire parti di tali dati quando lo chiedo. Ecco il trucco, non conosco un buon metodo per ordinare e cercare dati di questo tipo.

I miei dati sono essenzialmente costituiti da un gran numero di serie di numeri. Questi insiemi possono contenere ovunque da 1 a n numeri (sebbene nel 99,9% degli insiemi, n sia inferiore a 15) e ci sono circa 1,5 ~ 2 miliardi di questi insiemi (purtroppo questa dimensione impedisce una ricerca di forza bruta).

Devo essere in grado di specificare un set con k elementi e avere ogni set con k + 1 elementi o più che contenga il sottoinsieme specificato restituito a me.

Esempio semplice:
Supponiamo che io abbia i seguenti set per i miei dati:
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
(5,8,11)

Se dovessi dare la richiesta (1,3) avrei i set: (1,2,3), (1,2,3,4,5) e (1,3,8,9).
La richiesta (11) restituirebbe il set: (5,8,11).
La richiesta (1,2,3) restituirebbe i set: (1,2,3) e (1,2,3,4,5)
La richiesta (50) non restituirebbe alcun set:

Ormai lo schema dovrebbe essere chiaro. La differenza principale tra questo esempio e i miei dati è che gli insiemi con i miei dati sono più grandi, i numeri utilizzati per ogni elemento degli insiemi vanno da 0 a 16383 (14 bit) e ci sono molti molti altri insiemi.

Se è importante sto scrivendo questo programma in C ++ anche se conosco anche java, c, alcuni assembly, alcuni fortran e alcuni perl.

Qualcuno ha qualche indizio su come farlo?

modifica:
Per rispondere a un paio di domande e aggiungere alcuni punti:

1.) I dati non cambiano. È stato tutto preso in una lunga serie di corse (ciascuna suddivisa in 2 file di concerti).

2.) Per quanto riguarda lo spazio di archiviazione. I dati grezzi occupano circa 250 gigabyte. Stimo che dopo aver elaborato e rimosso molti metadati estranei a cui non mi interessa, potrei buttarlo giù da 36 a 48 gigabyte a seconda di quanti metadati decido di conservare (senza indici). Inoltre, se nella mia elaborazione iniziale dei dati trovo abbastanza insiemi uguali, potrei essere in grado di comprimere ulteriormente i dati aggiungendo contatori per gli eventi di ripetizione anziché semplicemente ripetere gli eventi più e più volte.

3.) Ogni numero all'interno di un set elaborato in realtà contiene almeno due numeri 14 bit per i dati stessi (energia rilevata) e 7 bit per i metadati (numero del rivelatore). Quindi avrò bisogno di almeno 3 byte per numero.

4.) Il mio " sebbene nel 99,9% dei set, n sia inferiore a 15 " il commento è stato fuorviante. In una prima occhiata attraverso alcuni dei blocchi di dati trovo che ho set che contengono fino a 22 numeri, ma la mediana è di 5 numeri per set e la media è di 6 numeri per set.

5.) Mentre mi piace l'idea di costruire un indice di puntatori in file, sono un po 'diffidente perché per le richieste che coinvolgono più di un numero mi rimane il compito semi lento (almeno penso che sia lento) di trovare l'insieme di tutti i puntatori comuni agli elenchi, ovvero trovare il sottoinsieme comune più grande per un determinato numero di insiemi.

6.) In termini di risorse disponibili, posso raccogliere circa 300 GB di spazio dopo che ho i dati grezzi sul sistema (il resto della mia quota su quel sistema). Il sistema è un server a doppio processore con 2 opteron quad core e 16 gigabyte di RAM.

7.) Sì, può verificarsi 0, è un artefatto del sistema di acquisizione dati quando lo fa ma può verificarsi.

Answer 1

Di recente ho scoperto metodi che utilizzano le curve di riempimento dello spazio per mappare i dati multidimensionali in un'unica dimensione. Si può quindi indicizzare i dati in base al suo indice 1D. Le query di intervallo possono essere facilmente eseguite trovando i segmenti della curva che intersecano la casella che rappresenta la curva e quindi recuperando quei segmenti.

Credo che questo metodo sia di gran lunga superiore alla creazione degli indici folli come suggerito perché dopo averlo guardato, l'indice sarebbe grande quanto i dati che desideravo archiviare, a malapena una buona cosa. Una spiegazione un po 'più dettagliata di ciò è disponibile all'indirizzo:

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

Answer 2

Il tuo problema è uguale a quello affrontato dai motori di ricerca. " Ho un bajillion di documenti. Ho bisogno di quelli che contengono questo insieme di parole. & Quot; Hai solo (molto convenientemente) numeri interi anziché parole e documenti di piccole dimensioni. La soluzione è un indice invertito . Introduzione al recupero delle informazioni di Manning et al is (at quel link) disponibile gratuitamente online, è molto leggibile e fornirà molti dettagli su come farlo.

Dovrai pagare un prezzo nello spazio su disco, ma può essere parallelizzato e dovrebbe essere più che abbastanza veloce da soddisfare i tuoi requisiti di tempistica, una volta costruito l'indice.

Answer 3

Supponendo una distribuzione casuale di 0-16383, con 15 elementi coerenti per set e due miliardi di set, ogni elemento apparirebbe in circa 1,8 milioni di set. Hai preso in considerazione (e hai la capacità di) costruire una tabella di ricerca 16384x ~ 1.8M (30B voci, 4 byte ciascuna)? Data una tabella di questo tipo, è possibile eseguire una query su quali set contengono (1) e (17) e (5555) e quindi trovare le intersezioni di questi tre elenchi di elementi ~ 1,8 M.

Answer 4

La mia ipotesi è la seguente.

Supponi che ogni set abbia un nome, un ID o un indirizzo (un numero di 4 byte lo farà se ce ne sono solo 2 miliardi).

Ora cammina attraverso tutti i set una volta e crea i seguenti file di output:

• Un file che contiene gli ID di tutti i set che contengono '1'
• Un file che contiene gli ID di tutti i set che contengono '2'
• Un file che contiene gli ID di tutti i set che contengono '3'
• ... ecc ...

Se ci sono 16 voci per set, in media ciascuno di questi 2 ^ 16 file conterrà gli ID di 2 ^ 20 set; con ogni ID di 4 byte, ciò richiederebbe 2 ^ 38 byte (256 GB) di spazio di archiviazione.

Farai quanto sopra una volta, prima di elaborare le richieste.

Quando ricevi richieste, usa questi file come segue:

• Guarda un paio di numeri nella richiesta
• Apri un paio dei file indice corrispondenti
• Ottieni l'elenco di tutti i set che esistono in entrambi questi file (c'è solo un milione di ID in ciascun file, quindi non dovrebbe essere difficile)
• Scopri quale di questi pochi set soddisfa il resto della richiesta

La mia ipotesi è che se si esegue quanto sopra, la creazione degli indici sarà (molto) lenta e la gestione delle richieste sarà (molto) rapida.

Answer 5

Crea 16383 file indice, uno per ogni possibile valore di ricerca. Per ogni valore nel set di input, scrivere la posizione del file di inizio del set nel file indice corrispondente. È importante che ciascuno dei file di indice contenga lo stesso numero per lo stesso set. Ora ogni file indice sarà composto da indici ascendenti nel file principale.

Per cercare, inizia a leggere i file indice corrispondenti a ciascun valore di ricerca. Se leggi un indice inferiore all'indice che leggi da un altro file, scartalo e leggine un altro. Quando ottieni lo stesso indice da tutti i file, questa è una corrispondenza: ottieni il set dal file principale e leggi un nuovo indice da ciascuno dei file di indice. Una volta raggiunta la fine di uno qualsiasi dei file indice, il gioco è fatto.

Se i valori sono distribuiti uniformemente, ogni file indice conterrà 1/16383 dei set di input. Se il set di ricerca medio è composto da 6 valori, eseguirai un passaggio lineare su 6/16383 dell'input originale. È ancora una soluzione O (n), ma ora la tua n è un po 'più piccola.

P.S. Lo zero è un valore di risultato impossibile o hai davvero 1638 4 possibilità?

Answer 6

Semplicemente giocando l'avvocato del diavolo per un approccio che include la forza bruta + la ricerca dell'indice:

1. Crea un indice con gli elementi min, max e no degli insiemi.
2. Quindi applica la forza bruta esclusi i set in cui max < max (set in fase di ricerca) e min > min (set da cercare)
3. In forza bruta anche escludere i set di elementi interi è inferiore a quello del set cercato.

Il 95% delle tue ricerche sarebbe davvero brutale forzando un sottoinsieme molto più piccolo. Solo un pensiero.