Хорошо объясненные алгоритмы индексации и поиска в метрических пространствах

Question

Мне нужно реализовать поиск метрического пространства в Postgres (*) (PL или PL / Python). Поэтому я ищу хорошие источники (или документы) с очень четким и четким объяснением механизма, лежащего в основе этих идей, таким образом, чтобы я мог реализовать его сам.

Я бы предпочел ясность, а не эффективность.

(*) Необходимость в этом описана лучше здесь .

Answer 1

Специально для географических данных, сначала посмотрите PostGIS , чтобы узнать, нужно ли вам что-либо реализовывать. Если вы это сделаете, начните с работ, перечисленных в записи Википедии на GiST .

Глядя на вашу ссылку, кажется, что ваше метрическое пространство - это строки с некоторым расстоянием редактирования в качестве метрики. Хороший, но устаревший обзор некоторых решений дает Наварро, Баеза-Йейтс, Сутинен и Тарио, Бюллетень IEEE Data Engineering, 2001 ; соответствующие документы о Citeseer также могут быть полезны. Хеширование с учетом локальных особенностей - это более новая методика, которая может быть полезна, но многие статьи тяжелы по математике.

Answer 2

Вы можете попробовать http://sisap.org, где перечислены многие современные метрические индексы, включая BK-деревья. Вы можете найти код в C, чтобы попробовать разные варианты.

Answer 3

BK-Trees полезны для индексации и поиска всего, что соответствует неравенству треугольника, включая метрические пространства. Канонический пример - поиск строк на заданном расстоянии редактирования от цели. Я написал статью об этом здесь .

К сожалению, в Postgres нет встроенной поддержки для этого. Вы можете реализовать это самостоятельно, используя GIST , но, очевидно, это будет много работы. Я не могу придумать способ реализовать его без написания собственных индексов, кроме хранения дерева в таблице, что, очевидно, не будет очень эффективным.

Answer 4

Некоторые методы, которые включают космический поиск, могут помочь вам: восхождение на холм, обучение нейронной сети, генетический алгоритм и рой частиц.

Вам также нужно будет определить метрику расстояния по вашему метрическому пространству. Вы сделали это? (И из любопытства, что это, если вы сделали это)