@savinov_ao

Поиск ближайших точек в многомерном пространстве?

Задача заключается в следующем: есть n-мерное пространство (n где-то в районе от 11 до 31), в нём есть k точек (порядка 100.000), точки редко добавляются, редко удалятся. Нужно отвечать на запросы вида «найти все точки на декартовом расстоянии меньшем чем L от заданной точки P(x1,x2,...,xn)». Многие рекомендуют PostgresSQL в качестве СУБД, использовать индексы SP_GiSP (написанные талантливыми людьми из МГУ), но я нигде не нашёл конкретных примеров реализации такой задачи. В стандартном постгресе я не нашёл встроенного типа, который можно использовать как хранилище точки многомерного пространства. Тип cube, на сколько я понял, нужно доставлять как расширение (пока не получилось) и совсем не факт, что индексы SP_GiSP и GiSP вообще умеют его поддерживать. С постгресом встретился абсолютно в первый раз, по сравнению с mysql кажется дремучим лесом. Кто-нибудь может помочь конкретным советом? Я на верном пути, тип cube подойдёт под мою задачу? Может есть какие-то готовые солюшены, примеры реализации?..
  • Вопрос задан
  • 3892 просмотра
Пригласить эксперта
Ответы на вопрос 5
@gleb_kudr
Все зависит от того, как часто вам нужно оперировать с данными.

Навскидку:

1. Если данные редко меняются, но часто запрашиваются — лучше сделать индекс по расстоянию между ребрами.
Это n*(n-1)/2 записей (количество ребер графа с данным числом нод), то есть около 5 млрд записей. Вполне вменяемое число.

2. Если данные не только редко меняются, но и редко запрашиваются, вполне возможно не делать индекса вовсе и считать все на лету, отбрасывая левые результаты. Нужна мощная машина + оптимизации для скорости (и это кстати отлично параллелится на GPU). Зато в этом случае все можно держать в памяти и БД вовсе не понадобится.
Ответ написан
@savinov_ao Автор вопроса
Как самое универсальное решение, в котором скорее всего уже реализованы нужные мне вещи. Есть отдельные готовые демоны, выполняющие мою задачу? Писать самому k-d tree и фильтрацию по расстоянию я честно сказать не горю желанием…
Ответ написан
Комментировать
smagen
@smagen
Руководитель разработки Postgres Professional
1) Правильно пишется SP-GiST и GiST.
2) cube поддерживает GiST индексы
www.postgresql.org/docs/9.2/static/cube.html
но поиск по расстоянию не поддерживает (можно делать поиск на вхождение в прямоугольную область, а потом доп. фильтрацию). Реализовать не проблема, никому не было достаточно сильно это нужно. SP-GiST для cube тоже пока не реализовали.
3) В целом, если есть опыт программирование на C и желание разобраться, то всё можно сделать.
Ответ написан
Комментировать
@mtyurin
avito
FUNCTION 8 надо для gist для cube дописать. пример можете посмотреть в extension btree_gist
Ответ написан
Комментировать
AnnInDark
@AnnInDark
Очень запоздало могу предложить топорное и математическое решение: дабы не нагружать базу излишними типами и дополнениями, пишите в базу прям координаты и считайте их.
Например сделайте таблицу «пространство» в которой ид точки и 2я колонка — массив ее координат.

Например для «пространство3»
1 {1,2,6}
2 {5,0,8}


ну а расстояние считать математикой через ф-цию)
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы