Есть ли разработанные алгоритмы быстрого нечеткого поиска?

[AHOHbIMHO]

Проблема примерно следующая.

В базе есть N векторов размерности M. Задана метрика для измерения расстояния между векторами.
Ищется в этой базе вектор, ниболее близкий по расстоянию к произвольно заданному вектору. Интересует алгоритм индексации и поиска со следующими требованиями:
1. количество операций при поиске не больше чем O(ln(N));
2. количество операций при индексации не больше чем O(N*ln(N));
3. объем данных индексации не больше чем O(N*ln(N));

[Егор]

Для размерности 1 решение очевидно: отсортировать, а потом использовать бинарный поиск.

Другой крайний случай: координаты могут принимать только значения 0 и 1, а расстояние между векторами вычисляется по Хеммингу (количество различных битов). Интересно, есть ли решение для этого частного случая.

[VLarin]

А чем Вас не устраивают бинарные деревья? Поиск - O(lnN) (правда в худшем случае, если дерево несбалансировано, то ето O(N)). Инициализация дерева - O(N*lnN). С объемом памяти - тут нужно еще подумать:), зависит от реализации.

Обычные бинарные деревья - это поиск при размерности 1. Для N-мерного поиска - здесь есть такая тема как Alternative Digital Tree. Их обычно используют при создании конечно-элементных сеток, как в двухмере, так и в 3D.
Суть их сводится к тому, что дерево организуется по подуровням, каждый подуровень отвечает за свою размерность. К примеру, в нулевом подуровне сравнение ведется по X, в 1 - по Y, во втором - по Z, уровень - 3 сравнение снова по X.
В общем - Level % N -> дает порядковый номер размерности, по которой идет сравнение.

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

[reader_st]

Уважаемые Егор и AHOHbIMHO я никогда не работал с указанные вещами, но подразумеваю, что указанные алгоритмы уже запрограммированы, например, в MatLab. На сайте exponenta.ru если я не ошибаюсь есть даже отдельный раздел посвященный указанной тематике.

[незваный гость]

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

Вообще, ключевы слова: spatio-temporal, spatial, temporal, spatiotemporal, database, index.

[AHOHbIMHO]

Спасибо большое за наводки . Радует, что в принципе есть такие алгоритмы. Вобщем немало разработок. Нет у кого-нибудь из специалистов желания работать в этом направлении? Мы ищем специалиста по поисковым алгоритмам, сами все специализируемся оброботкой звука. Конечно мы в состоянии по вашим наводким изучить разработки, токо загружены сильно. Я бы поместил тут объявление, только не нашел соответствующего раздела. А вот если ссылку дам, то сотрут ведь сообщение. Извините, если сообщение не соотвтеутсвует тематике раздела.

[Vassil]

По линку
http://www.gams.com/modlib/libhtml/csp.htm
встретил следующую
Reference:
Meneses, C N, Lu, Z, Oliveira, C A S, and Pardalos, P M, Optimal Solutions for the Closest-String Problem via Integer Programming. INFORMS Journal on Computing 16, 4 (2004), 419-429.

Но Ваши требования очень сильны. Не знаю подход через целочисленного программирования удовлетворяет ли их.

[AHOHbIMHO]

Так. Если требования слишком сильные, то попробуем смягчить.

В базе есть N векторов евклидового пространства размерности M.
Ищется в этой базе вектор, который не дальше чем d по расстоянию к произвольно заданному вектору. Интересует алгоритм индексации и поиска со следующими требованиями:
1. количество операций при поиске не больше чем O(ln(N));
2. вероятность нахождения вектора, если такой существует - 95%


Интересут так же такой частный случай, когда известно, что вектора в базе статистически равномерно распределены (белый шум) в еденичном кубе или шаре.

Мне кажется, в таком частном случае задача решаема. И может быть возможно свести общую задачу к указанному частному случаю. Анализируем распредение векторов в базе, придумываем статистическую модель с несколькими параметрами (скажем смесь гауссовых распределений), подбираем параметры максимизацией ожидания.

Вот по этому поводу

Gaussian Mixture Models (GMM) and Expectation-Maximization (EM)
http://www.cse.psu.edu/~cg586/cse586GMM ... n%20GMM%22

Expectation-Maximization Theory
http://www.phptr.com/articles/article.a ... Num=5&rl=1

Adaptive Dimension Reduction in Text Clustering Using ADR-Expectation Maximization Algorithm
http://www.ee.iitb.ac.in/uma/~saket/dat ... n%20GMM%22

и прочее

Зная статистическую модель и параметры модели, делаем соответственно отображение векторов, так чтобы статистически равномерно лежали в еденичном кубе или шаре, ну и область пространства (шар радиуса d), где вектора ищутся.

Вот такие у меня соображения.

[AHOHbIMHO]

Классификация и экспериментальное исследование современных алгоритмов нечеткого словарного поиска

Бойцов Леонид Моисеевич
Яndex
[e-mail]
(2004)

http://www.impb.ru/~rcdl2004/cgi/get_pa ... cgi?pid=27

Аннотация
Цель данной работы заключается в
классификации и экспериментальном
сравнении существующих алгоритмов
нечеткого словарного поиска.
Нами были реализованы и протестированы
алгоритм последовательного перебора,
модификации n-граммный алгоритмов, trie-
деревья, метрические деревья, kd-деревья, а
также менее распространенные сигнатур–
ные алгоритмы.
В отличие от большинства других работ мы
тестируем не только скорость поиска в
индексе, загруженном в память, но и
скорость чисто дискового поиска, когда
индекс считывается непосредственно с
диска.

********************************************************************
Similarity Search in High Dimensions via Hashing

Aristides Gionis, Piotr Indyk, Rajeev Motwani

(1999)

http://citeseer.ist.psu.edu/rd/80602428 ... larity.pdf

Тут хеш-функции строятся так, что чем меньше расстояние между двумя
векторами, тем больше вероятность того, что значения хеш-функций на
этих векторах совпадают.