Ho sviluppato funzionalità simili per un sito web. Nel mio caso avevo meno dimensioni di te, ma avevo 15 milioni di dischi (simili al tuo caso). Avevo bisogno di servire circa 5000 richieste al secondo, il che significava che ogni richiesta ha un budget di circa 10ms su un server 64-core.
Ho provato vari approcci tra cui l'albero k-d e dopo la marcatura di banco ogni approccio si è concluso con quello descritto di seguito, che era ben all'interno del mio budget di 10 ms quando scritto in C # e in esecuzione su .Net 4.0.
L'algoritmo è più facile da disegnare che scrivere, quindi spero che tu possa seguire la mia spiegazione. Prima pensiamoci su 2 dimensioni (è più semplice da visualizzare) quindi estendilo a più dimensioni dopo.
Immagina di avere un set di 10 milioni di punti con le coordinate xey in uno spazio 2D. Passa attraverso tutti i punti e trova i valori minimo e massimo di x e y, e anche il valore di x e y dove metà dei punti sono sopra e metà dei punti sono sotto questo valore. Questo ti dà uno spazio rettangolare diviso in quattro quadranti in cui ogni quadrante contiene lo stesso numero di punti.
Ripeti questo in ciascuno dei quattro quadranti dividendoli in quattro quadranti e ripeti ricorsivamente fino a quando i quadranti contengono un numero di punti simile a N nella tua Top-N. Mentre lo fai assicurati che ogni punto sappia in quale rettangolo si trova e i rettangoli conoscono la struttura di nidificazione dei rettangoli all'interno dei rettangoli.
Costruire questo indice richiede un po 'di tempo, ma è sufficiente ricostruirlo completamente una volta ogni tanto (forse una volta al giorno). Durante il giorno, mentre i dati cambiano, puoi spostare i punti da un rettangolo all'altro. Mentre muovi i punti attorno all'indice diventa sbilanciato e meno efficiente, quindi devi ricostruire da zero ogni tanto.
Quando vuoi trovare i vicini N più vicini, devi solo considerare i rettangoli adiacenti. Diciamo che stai cercando i 10 vicini più vicini, quindi l'indice continuerà a dividere i rettangoli in 4 quadranti finché ogni rettangolo contiene circa 10 punti. Ora i 10 punti più vicini devono essere nello stesso rettangolo o in uno dei rettangoli adiacenti. Puoi trovare i rettangoli adiacenti risalendo l'albero del rettangolo e giù fino ai suoi figli. Se sei a un confine potresti dover salire di alcuni livelli e retrocedere lo stesso numero di livelli, ma puoi precalcolare l'elenco di rettangoli adiacenti per ciascun rettangolo per renderlo più veloce (ma usa più memoria). Nota che la maggior parte dei rettangoli si trova nel mezzo da qualche parte e avrà 8 rettangoli adiacenti. I rettangoli sul bordo dello spazio delle coordinate avranno meno.
Per estendere questo da 2D a 3D, l'intero spazio ora è un cubo invece di un rettangolo e dividi ogni cubo in 8 cubetti più piccoli, ciascuno contenente lo stesso numero di punti invece di dividere i rettangoli in 4 rettangoli più piccoli, e ogni cubo avrà fino a 26 cubi adiacenti.
Questo può essere esteso logicamente a più dimensioni. Nella mia applicazione avevo 4 (latitudine, longitudine e altri 2). Nel tuo caso i numeri diventano piuttosto grandi quindi avrai bisogno di molta memoria! Non ho fatto i calcoli matematici, ma dividere a metà ogni regione a 128 dimensioni su ciascuna dimensione potrebbe risultare in 2 ^ 128 regioni figlio, il che non è chiaramente possibile. Se questo è il caso, penso che dovrai sperimentare variazioni su questo approccio, ma spero che questo ti dia un punto di partenza.
Si noti che questo algoritmo è imperfetto in base alla progettazione. Le imperfezioni non erano importanti per la mia applicazione e la velocità era molto più importante. L'imperfezione deriva dal fatto che i rettangoli sono suddivisi per numero di punti non per dimensione, quindi i rettangoli adiacenti non sono allineati con questo rettangolo. Questo non importa troppo perché devi ancora calcolare la distanza effettiva dal punto di destinazione a tutti i suoi rettangoli adiacenti e prendere la N più vicina, e anche tu sai che anche se il rettangolo adiacente non è esattamente allineato con questo lì non ci sono altri rettangoli più vicini.