Recupero e indicizzazione dei dati

Question

Recupero e indicizzazione dei dati

#1 da (3 voti)
#2 da (3 voti)

1

Ho circa 800.000 file di dati memorizzati nella memoria condivisa di boost dal database. I dati sono nella forma:

Id        Color        Length          Size

1        1                 2            4
2        3                 4            5
3        2                 2            0
4        1                 2            4......and so on

I colori possono essere il valore compreso tra 1 e 12, la lunghezza 1-4 e la dimensione 1-5. L'Id, Lunghezza, Colore, Dimensione sono memorizzati in un vettore separato di 800.000 dimensioni nella memoria condivisa. Quindi c'è il vettore Id per Id, Color vector for Color e così via.

Voglio filtrare i dati prima di eseguire alcuni calcoli. Quindi desidero i dati per i quali Colore è 1 e lunghezza è 2 e Dimensione 4 i.e riga 1 e 4 nel caso precedente. C'è un modo efficace per filtrare i dati senza utilizzare per il ciclo e passare attraverso tutte le 800.000 immagini e controllando la condizione?

In questo momento sto solo usando l'istruzione mysql per ottenere gli ID dei dati che soddisfano la condizione.

"select Id from features_table where Color=1 and Length=2 and Size =4"

Ma c'è un modo più veloce per farlo? O dovrei attenermi a questo metodo? Sto cercando un metodo più veloce, quindi non sono sicuro che il recupero degli ID dal database aumenterà il tempo di esecuzione dell'algoritmo.

Quali sono le altre opzioni che posso prendere in considerazione in questo caso? Ho letto di Hash table, B-Tree, Binary Search tree e sono confuso, che è adatto per questo caso. Kd-tree sarà utile in questo caso? Perché molte immagini possono avere la stessa combinazione di colori, lunghezza e dimensioni. Non sono sicuro che kd-tree sia la cosa giusta da fare. Ho letto di FLANN in opencv usato per kd-tree. C'è qualche esempio o risorse che potrebbero essere utili in questo caso? O ci sono delle librerie c ++ integrate?

c++ data-structures indexing

posta user1583647 11.02.2014 - 10:18

fonte

2 risposte

Leggi altre domande sui tag c++ data-structures indexing

Chiama il database ogni volta o crea un oggetto in memoria e, in caso affermativo, come e quanto spesso aggiornare? Dovrei usare git per i file di progetto, oltre alla sorgente effettiva? [duplicare]

score 3 · Answer 1

Ci sono molti dati duplicati lì, poiché il numero di possibili combinazioni di colori, lunghezza e dimensioni è troppo piccolo rispetto al numero di righe.

Un'alternativa migliore è l'archiviazione di un set di indici di riga per ogni possibile tupla:

struct Rows
{
    std::tuple<Color, Length, Size> properties;
    std::vector<int> rowids;
} ;

In questo modo, le query sono semplici.

Se il numero di possibili tuple è abbastanza alto, vale la pena di impostare indici sotto forma di hash set di righe, un hash per proprietà: std::map<Color, Rows *> e così via.

score 3 · Answer 2

Hai esattamente 240 valori unici per colore, lunghezza e dimensioni. Se l'ID è strettamente crescente come nel tuo esempio, non è necessario memorizzarlo e i dati potrebbero essere comodamente imballati in un singolo breve int. Una serie di 800.000 cortometraggi richiederà 1,6 MB di memoria e potrebbe essere sottoposta a ricerca bruta in meno di 1 millisecondo. Ti serve più veloce di questo?

Se l'ID deve essere memorizzato, sono necessari 27 bit, ma un breve e un int possono essere più convenienti. Ancora solo 4,8 MB di memoria, ancora molto veloce da cercare.

Se conosci in anticipo le ricerche che desideri effettuare, puoi creare indici per rendere le ricerche ancora più rapide. È possibile utilizzare i 240 valori univoci come chiave e l'id come dati, con circa 3333 ID in ciascun bucket.

Tabella hash: sì. Quanto sopra potrebbe essere implementato con una multimap non ordinata, come quella nella libreria standard. Tuttavia, una soluzione personalizzata potrebbe essere più veloce.

Gli alberi B e la ricerca binaria sono dati ordinati. Non hai indicato questo come requisito.

Gli alberi Kd sono dati ordinati multidimensionali, eccellenti per le ricerche dei vicini più vicini. Ancora una volta, non sembra corrispondere alle tue esigenze.