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

Question

[savinov_ao]

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

Comments

[dbmaster]

Зачем вам СУБД (транзакции, атомарность, клиент/сервер,...)?

Answer 1

[gleb_kudr]

Все зависит от того, как часто вам нужно оперировать с данными.

Навскидку:

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

2. Если данные не только редко меняются, но и редко запрашиваются, вполне возможно не делать индекса вовсе и считать все на лету, отбрасывая левые результаты. Нужна мощная машина + оптимизации для скорости (и это кстати отлично параллелится на GPU). Зато в этом случае все можно держать в памяти и БД вовсе не понадобится.

Comments

[gleb_kudr]

И вообще, я бы лично в потроха БД в данном случае не лез и использовал ее бы только для хранения и простых выборок, так как задача тяжелая, а оптимизировать скорость SQL это та еще задачка.

Answer 2

[savinov_ao]

Как самое универсальное решение, в котором скорее всего уже реализованы нужные мне вещи. Есть отдельные готовые демоны, выполняющие мою задачу? Писать самому k-d tree и фильтрацию по расстоянию я честно сказать не горю желанием…

Answer 3

[Александр Коротков]

1) Правильно пишется SP-GiST и GiST.
2) cube поддерживает GiST индексы
www.postgresql.org/docs/9.2/static/cube.html
но поиск по расстоянию не поддерживает (можно делать поиск на вхождение в прямоугольную область, а потом доп. фильтрацию). Реализовать не проблема, никому не было достаточно сильно это нужно. SP-GiST для cube тоже пока не реализовали.
3) В целом, если есть опыт программирование на C и желание разобраться, то всё можно сделать.

Answer 4

[Михаил]

FUNCTION 8 надо для gist для cube дописать. пример можете посмотреть в extension btree_gist

Answer 5

[AnnInDark]

Очень запоздало могу предложить топорное и математическое решение: дабы не нагружать базу излишними типами и дополнениями, пишите в базу прям координаты и считайте их.
Например сделайте таблицу «пространство» в которой ид точки и 2я колонка — массив ее координат.

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

ну а расстояние считать математикой через ф-цию)