Подтвердить что ты не робот

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

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

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

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Извините, но вам нужно либо выполнить поиск грубой силы, либо лучше проанализировать вашу проблему и придумать более разумное решение.

Ответ 2

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

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

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

Ответ 3

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

https://github.com/davidmoten/rtree

Вы можете проверить это!