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

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

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


python sql database data-mining kdtree
person Cerin    schedule 31.03.2011    source источник
comment
какое решение вы в итоге использовали?   -  person werber bang    schedule 11.04.2020

Ответы (2)


arrow_upward
4
arrow_downward

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

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

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

person samplebias    schedule 31.03.2011

arrow_upward
0
arrow_downward

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

person Greg Bowyer    schedule 31.03.2011
comment
Я не уверен, что вы имеете в виду. Согласно документам, эти типы индексов предназначены для полнотекстового поиска. Я не понимаю, как они применимы к проблеме K-ближайших соседей. - person Cerin; 31.03.2011
comment
Индексы GIN представляют собой индексы Gist, предназначенные для использования в качестве общей структуры индексов, один человек поместил в них kd-дерево (cs.purdue.edu/spgist/papers/icde06.pdf). - person Greg Bowyer; 25.05.2011