Implementazione R-Tree Java

Question

Stavo cercando gli ultimi giorni per un'implementazione stabile di R-Tree con supporto di dimensioni illimitate (20 circa sarebbero sufficienti). Ho trovato solo questo http://sourceforge.net/projects/jsi/ ma supportano solo 2 dimensioni.

Un'altra opzione sarebbe un'implementazione multidimensionale di un albero ad intervalli.

Forse ho completamente torto con l'idea di usare un R-Tree o Intervall-Tree per il mio problema, quindi in breve dichiaro che il problema è che puoi inviarmi i tuoi pensieri a riguardo.

Il problema che devo risolvere è una sorta di ricerca per il vicinato più vicino. Ho un set di antenne e stanze e per ogni antenna un intervallo di numeri interi. Per esempio. antenna 1, min -92, max -85. Infatti potrebbe essere rappresentato come room -> set di antenne -> intervallo per antenna. L'idea era che ogni stanza si estendesse su una casella nell'albero R oltre la dimensione delle antenne e in ogni dimensione dell'intervallo.

Se ottengo una query con N-Antenne e valori per ciascuna antenna, posso quindi rappresentare l'informazione come punto interrogativo nella stanza e recuperare le stanze "più vicine" al punto.

Spero che tu abbia un'idea del problema e della mia idea.

Answer 1

Non sono del tutto chiaro su quale sia il tuo problema esatto, ma un albero R o un albero ad intervalli non funzionerebbero bene in 20 dimensioni. Non è un numero enorme di dimensioni, ma è abbastanza grande da far apparire la maledizione della dimensionalità.

Per vedere cosa intendo, si consideri solo cercando di guardare tutti i vicini di una scatola, compresi quelli fuori dagli angoli e dai bordi. Con 20 dimensioni, avrai 3 - 1 o 3,486,784,400 caselle adiacenti. (Si ottiene realizzando che lungo ciascun asse un vicino può essere -1 unità, 0 unità o +1 unità, ma (0,0,0) non è un vicino perché rappresenta la scatola originale)

Mi dispiace, ma devi o accettare la ricerca di forza bruta, oppure analizzare meglio il tuo problema e trovare una soluzione più intelligente.

Answer 2

Si noti che gli R-Trees possono degradarsi male quando si dispone di dati discreti. La prima cosa che devi veramente scoprire è una rappresentazione dei dati appropriata, quindi verificare se le tue query funzionano su un sottoinsieme di dati.

R-Trees farà solo le vostre domande più veloce. Se non funzionano in primo luogo, non sarà di aiuto. Dovresti testare il tuo approccio senza usare prima R-Trees. A meno che non si raggiunga una grande quantità di dati (ad esempio, 100.000 oggetti), una scansione lineare in memoria può facilmente sovraperformare un R-Tree, in particolare quando è necessario un adattatore di livello perché non è ben integrato con il codice.

L'approccio ovvio qui è quello di utilizzare rettangoli di delimitazione e scansionare linearmente su di essi. Se funzionano, è possibile quindi archiviare gli MBR in un R-Tree per ottenere alcuni miglioramenti delle prestazioni. Ma se non funziona con una scansione lineare, non funzionerà neanche con un R-Tree (non funzionerà più velocemente)

Answer 3

Ho trovato questa implementazione R * -Tree in Java che sembra di offrire molte caratteristiche:

https://github.com/davidmoten/rtree

si potrebbe desiderare di check it out!

Answer 4

Un'altra buona implementazione in Java è ELKI: https://elki-project.github.io/.