Inserimento di elementi nel grafico con un algoritmo streaming / online

Un buon punto di partenza potrebbe essere una versione semplificata di iDistance . L'algoritmo completo funziona definendo nodi cluster (centrali), che vengono utilizzati per ridurre le dimensioni multiple a uno. Questo scalare monodimensionale viene utilizzato per cercare un albero B +. Ci sono altri algoritmi come questo, ma fondamentalmente usano lo stesso approccio. ( Indicizzazione di dati ad alta dimensione per Ricerca di similarità in-memory efficiente fornisce una buona panoramica di diversi algoritmi e delle loro prestazioni.)

Tuttavia, se permettiamo alcune approssimazioni e scartando i nodi, allora potrebbe essere sufficiente avere solo un albero di nodi cluster, forse alcuni strati profondi. Cerca quell'albero per il nodo del cluster più vicino, quindi cerca i 5 punti più vicini collegati a quel nodo. Tutti i calcoli della forza bruta della distanza tra i punti nello spazio N-dimensionale. O comunque vuoi ottimizzarlo.

Considera il seguente algoritmo in pseudo codice:

Cluster clusters[200];

FillRandom(clusters);

for (i = 0; i < 10000; ++i)
    Vector v = randomVector();

    cluster = clusters.findNearestCluster(v); // brute force search on distance squared

    PointArray points[] = cluster.sortPointsOnDistanceSquared(v);

    selectFirstFive(points);

Implementato in Java, 100 dimensioni, ciascuna dimensione compresa tra 0.0 e 10.0, viene eseguita in 5-8 secondi, su un Intel i7, di seconda generazione. Il che significa, ben al di sotto della velocità del flusso di 1000 / s. C'è molto spazio per l'ottimizzazione. (Condividerei il codice, ma in realtà non aggiungerà nulla.)

C'è più che abbastanza tempo per fare qualcosa sul ribilanciamento dell'albero del cluster. I cluster che si trovano nel bel mezzo del nulla e non ricevono colpi possono essere rimossi. I cluster che hanno troppi hit potrebbero essere divisi o altrimenti ridotti. Ci dovrebbe essere un raggio associato, alcuni test di sovrapposizione, ecc.

In questo codice di esempio, questi erano alcuni dei tempi:

Minimum: 0, Maximum: 1067, #Clusters_having_points: 96, Average: 104, Time: 7498ms
Minimum: 0, Maximum: 1095, #Clusters_having_points: 97, Average: 103, Time: 7241ms
Minimum: 0, Maximum: 1010, #Clusters_having_points: 99, Average: 101, Time: 6465ms
Minimum: 0, Maximum:  832, #Clusters_having_points: 99, Average: 101, Time: 5688ms

Con Min / Max / Avg i punti min / max / avg per nodo cluster. È programmato in pochissimo tempo e facile da giocare, per avere un'idea di come i dati si gestiscono da soli.

Per come la vedo io, molti algoritmi offrono precisione e conservano tutti i loro dati. Hanno trascorso il loro tempo sulla riduzione del punto N-dimensionale su una dimensione. Hanno bisogno di quella dimensione, di utilizzare tutti i tipi di strutture di dati di bilanciamento, in modo che possano setacciare migliaia di miliardi di dati. Lasciando andare quell'esattezza (e la storia), si libera tempo per usare metodi più banali per bilanciare l'albero di ricerca. "Troppi punti per questo ammasso? Getti via metà, finchè possiamo trovare 5 punti che sono (quasi) il più vicino possibile a qualsiasi altro che troveremmo." È un po 'grezzo, ma tu hai l'idea, spero.

È lo stesso principio usato nei giochi. Se non puoi fare la cosa vera, fingilo. Va bene finché sembra buono.

Se ciò non è soddisfacente, però, si può andare per gli algoritmi più esatti che sono noti. La ricerca di alcuni di essi, come menzionato nell'articolo che ho collegato, porterà facilmente a materiale di lettura interessante, compresi gli algoritmi.

Per quanto ne so, il miglior software per fare questo tipo di elaborazione è Apache Mahout . Esistono algoritmi più efficienti di una ricerca lineare, ma generalmente solo per le dimensioni inferiori. Fortunatamente (anche se non per il tuo portafoglio), è altamente parallelizzabile, quindi puoi sempre gettare più hardware sul problema.

Per migliorare la latenza su uno streaming live, potresti prendere in considerazione la preelaborazione di alcuni dati storici per avere un'idea di una distanza tipica tra i nodi più vicini, quindi utilizzare tale distanza come euristica. Invece dei cinque assoluti più vicini, puoi scegliere i primi cinque che sono all'interno, diciamo, 5 volte della distanza tipica. Puoi aumentare o diminuire quel margine quando la potenza di elaborazione lo consente.

Un'altra euristica potenzialmente utile è che una volta identificato un punto relativamente vicino, i vicini più vicini identificati in precedenza sono buoni candidati per il tuo nuovo punto, e puoi diramarti da lì, piuttosto che scegliere i candidati a caso.

Ad esempio, se il 95% dei vicini più vicini ha una distanza pari o inferiore a 10, eseguire prima una ricerca lineare per trovare un punto entro 50, quindi osservare i vicini più prossimi di quel punto, quindi il più vicino dei vicini del vicino, e così via.