Struttura DB per il rilevamento della somiglianza

5

Il problema che voglio risolvere è il seguente:

Dato un insieme di utenti, ciascuno con una serie di interessi che possono specificare autonomamente, trovare tutte le coppie di utenti che condividono gli stessi interessi con una soglia di somiglianza (ad esempio il 50% di interessi simili). Inoltre alcune categorie di interessi dovrebbero avere un peso maggiore di altre (cioè essere più importanti verso la soglia).

Attualmente, posso solo pensare a modelli relazionali per risolvere questo problema, ma ci si sente in errore e qualcosa che richiederà troppo tempo per essere elaborato una volta che ci sono almeno 100 utenti. Con la mia attuale conoscenza dei DB basati su documenti (ad es. Mongo) ritengo che non siano un'opzione, poiché dovremmo sempre ricorrere ai documenti di riferimento incrociato (?). Dovrei fare più letture su DB basati su grafici? Qualsiasi suggerimento è benvenuto.

Sto cercando una soluzione equilibrata in termini di complessità e prestazioni. Non sto cercando qualcosa che funzioni con milioni di utenti se questo significa che devo leggere un sacco di documenti di ricerca, ma un approccio che supporterà poche migliaia di utenti sarà sufficiente.

    
posta latusaki 28.02.2017 - 10:19
fonte

3 risposte

2

Il tuo problema è una ricerca multidimensionale, quindi hai bisogno di un sistema che sia capace di tale.

Puoi convertire i tuoi interessi in una sequenza di funzioni e utilizzare l'opzione Locality Sensitive Hashing per ridurre il set di dati su cui eseguire una ricerca più precisa.

Un'altra alternativa sarebbe usare R-Trees .

    
risposta data 28.02.2017 - 16:12
fonte
2

Ho trovato Introduzione al recupero informazioni per essere molto leggibile e informativo. Vi sono dettagli tecnici e lunghi elenchi di "ulteriori letture", ma il testo stesso non si impantana nei minimi dettagli.

Il capitolo 14 sulla classificazione dello spazio vettoriale si applicherebbe a questa situazione. Tratta ogni interesse come una dimensione in uno spazio multidimensionale. Normalizza i valori (in senso matematico, non quello DB) e pesi in modo appropriato. Quindi calcola una distanza N-dimensionale tra gli utenti in questo spazio. Quelli con una distanza minore sono più simili.

Poiché si tratta essenzialmente di una serie di calcoli, qualsiasi DBMS dovrebbe essere in grado di eseguirlo. Tuttavia, potrebbe essere più economico trasferire i dati a un server delle applicazioni e comunque utilizzare i relativi cicli della CPU.

Il numero di calcoli aumenta come il quadrato della base di utenti, comunque. Potresti non essere in grado di farlo scalare come desideri.

Il libro copre anche vari algoritmi di clustering vicini più vicini. Ci sono euristiche per tagliare il numero totale di confronti al costo di una certa precisione. Questo può essere un compromesso accettabile in questo scenario.

    
risposta data 15.03.2017 - 23:15
fonte
1

Fondamentalmente hai un grafico bipartito composto da persone e interessi (corrispondenti a hub e raggi).

L'algoritmo SALSA ti fornirà l'elenco delle persone che corrispondono meglio (classificate) per una persona (alla query tempo).

    
risposta data 15.03.2017 - 23:37
fonte

Leggi altre domande sui tag