Реализация R-Tree Java

Question

Последние несколько дней я искал стабильную реализацию R-Tree с поддержкой неограниченных измерений (20 или около того было бы достаточно). Я только нашел это http://sourceforge.net/projects/jsi/, но они поддерживают только 2 измерения.

Другим вариантом будет многомерная реализация дерева интервалов.

Может быть, я совершенно не прав в идее использования R-Tree или Intervall-Tree для моей Проблемы, поэтому я кратко излагаю Проблему, чтобы вы могли отправить мне свои мысли по этому поводу.

Проблема, которую мне нужно решить, это какой-то поиск ближайшего соседа. У меня есть набор антенн и комнат и для каждой антенны интервал целых чисел. Например. антенна 1, мин -92, макс -85. Фактически это может быть представлено как комната -> набор антенн -> интервал для антенны. Идея заключалась в том, что каждая комната располагается в R-дереве по размеру антенн и в каждом измерении по интервалу.

Если я получу запрос с N-антеннами и значениями для каждой антенны, я тогда смогу просто представить информацию как точку запроса в комнате и получить комнаты, «ближайшие» к этой точке.

Надеюсь, у вас есть идея проблемы и моя идея.

Answer 1

Имейте в виду, что R-деревья могут сильно ухудшаться, когда у вас есть дискретные данные.Первое, что вам действительно нужно выяснить, - это соответствующее представление данных, а затем проверьте, работают ли ваши запросы на подмножестве данных.

R-Trees только сделает ваши запросы быстрее .Если они не работают в первую очередь, это не поможет. Вы должны сначала проверить свой подход, не используя R-Trees. Если вы не получили большой объем данных (скажем, 100 000 объектов), линейное сканирование в памяти может легко превзойти R-Tree, особенно когдавам нужен какой-то слой адаптера, потому что он плохо интегрирован с вашим кодом.

Очевидный подход здесь состоит в том, чтобы просто использовать ограничивающие прямоугольники и линейно сканировать их.Если они работают, вы можете сохранить MBR в R-Tree, чтобы получить некоторые улучшения производительности. Но если он не работает с линейным сканированием, он также не будет работать с R-деревом (он не будет работать быстрее.)

Answer 2

Мне не совсем ясно, в чем именно заключается ваша проблема, но R-дерево или интервальное дерево не будет работать в 20 измерениях. Это не огромное количество измерений, но оно достаточно велико, чтобы проклятие размерности начало проявляться.

Чтобы понять, что я имею в виду, подумайте о том, чтобы просто попытаться посмотреть на всех соседей коробки, в том числе на углах и краях. С 20 размерами у вас будет 3 ²⁰ - 1 или 3 486 784 400 соседних ящиков. (Вы получаете это, понимая, что вдоль каждой оси сосед может быть равен -1 единице, 0 единице или +1 единице, но (0,0,0) не является соседом, поскольку он представляет исходную ячейку.)

Извините, но вам либо нужно принять перебор, либо лучше проанализировать свою проблему и найти более умное решение.

Answer 3

Я нашел эту реализацию R * -Tree в Java, которая, кажется, предлагает множество функций:

https://github.com/davidmoten/rtree

Возможно, вы захотите проверить это!

Answer 4

Вы можете использовать функцию индексирования в Обобщенном дереве поиска PostgreSQL.

GiST Quick demo

Answer 5

Еще одна хорошая реализация в Java - это ELKI: https://elki -project.github.io / .