Реализация KD-дерева в SQL

Question

Кто-нибудь знает о KD-дереве или подобном пространственном индексе, реализованном в SQL?Я собирался написать свой собственный, используя Python и Django ORM, но я бы хотел не изобретать колесо заново.

У меня есть таблица, содержащая миллионы строк, в каждой строке по 128 столбцов, представляющих данные объектов изображения.Учитывая произвольный длинный список изображений с 128 элементами, я хочу использовать KD-Tree, чтобы найти N наиболее похожих изображений в базе данных.Я нашел много реализаций KD-Tree, но все они, похоже, загружаются только в локальной памяти и не масштабируются и не взаимодействуют с базами данных.

Answer 1

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

Возможно, вы захотите найти существующую систему поиска сходства изображений, в которую вы можете отобразить свои данные. Вот тот, который называется Lire , который извлекает элементы из изображений и индексирует их с помощью Lucene.

Если ваша работа в большей степени ориентирована на исследования, вы, возможно, захотите прочитать показатели метрического пространства и приблизительный поиск k-ближайших соседей.

Answer 2

Я могу быть немного здесь, но вам лучше всего использовать индексы Gist / Gin внутри Postgresql