Пространственный индекс для гео-координат?
Какая структура данных могла использоваться для эффективного ближайшего соседнего поиска в большом наборе гео-координат? С "регулярными" пространственными индексными структурами как R-деревья, которые принимают плоские координаты, я вижу, две проблемы (Там другие, которых я пропустил?):
- Циклический возврат в полюсах и Демаркационной линии времени
- Искажение расстояний около полюсов
Как эти факторы могут допускаться? Я предполагаю, что второй мог компенсированный путем преобразования координат. R-дерево может быть изменено для принятия циклического возврата? Или там специализированы геопространственные индексные структуры?
2 ответа
Взгляните на Geohash .
Кроме того, для компенсации зацикливания просто используйте не одно, а три ортогональных R-дерева, чтобы не существовало такой точки на поверхности земли, что все три дерева имели бы обход в этой точке. Тогда две точки являются близкими, если они близки хотя бы по одному из этих деревьев.
Не могли бы вы использовать алгоритм хеширования с учетом местоположения (LSH) в трех измерениях? Это быстро даст вам приблизительную соседнюю группу, которую вы затем сможете проверить, вычислив расстояния большого круга.
Вот статья , описывающая алгоритм для эффективного LSH на поверхности единичной d -мерной гиперсферы. Предположительно это работает для d = 3.