Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных деревьями и графами. В качестве меры сходства использовано расстояние редактирования. Рассмотрено выполнение запросов точного поиска по сходству. В основном представлены алгоритмы на основе стратегии фильтрации и уточнения, использующие обратное индексирование. Кроме того, рассмотрены алгоритмы точного вычисления расстояния редактирования графов и его нижних и верхних границ.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Приведены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных деревьями и графами. В качестве меры сходства использовано расстояние редактирования. Рассмотрено выполнение запросов точного поиска по сходству. В основном представлены алгоритмы на основе стратегии фильтрации и уточнения, использующие обратное индексирование. Кроме того, рассмотрены алгоритмы точного вычисления расстояния редактирования графов и его нижних и верхних границ.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Приведены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены индексные структуры на основе локально-чувствительного хэширования и их модификации. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Обсуждена их взаимосвязь и некоторые теоретические аспекты.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены структуры как для точного, так и для более быстрого, но приближенного поиска. Приведены главным образом индексные структуры на основании разбиения на области (в том числе иерархические) и графов соседства. Обсуждено также ускорение поиска по сходству с использованием преобразования исходных данных. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Проведено сравнение подходов к ускорению поиска по сходству в индексных структурах рассмотренных типов, а также на основе сохраняющего сходство хэширования.

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

Рассмотрен класс таких индексных структур для быстрого поиска по сходству, при конструировании и применении которых используется только информация о значениях или ранге некоторых расстояний/сходств между объектами. Обсужден поиск как по метрическим расстояниям (для последних выполняется неравенство треугольника и другие метрические аксиомы), так и по неметрическим. Приведены структуры, которые возвращают объекты базы, являющиеся точным ответом на поисковый запрос, а также структуры для приближенного поиска по сходству (они не гарантируют точность, но обычно возвращают близкие к точным результаты и работают быстрее структур для точного поиска). Изложены общие принципы конструирования и применения некоторых индексных структур, а также рассмотрены идеи, лежащие в основе конкретных алгоритмов, как известных, так и предложенных в последнее время.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных бинарными векторами (с компонентами 0 или 1). Рассмотрены структуры как для точного, так и для приближенного поиска по расстоянию Хэмминга и другим мерам сходства. Приведены, главным образом, индексные структуры на основе хэш-таблиц, сохраняющего сходство хэширования, а также древовидных структур, графов соседства и нейросетевой распределенной автоассоциативной памяти. Изложены идеи известных и предложенных в последнее время алгоритмов.

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

Предложено преобразование входных вещественных векторов в выходные бинарные векторы путем проецирования бинарной случайной матрицей с элементами {0, 1} и порогового преобразования. Исследована скорость сходимости распределения компонентов векторов до бинаризации к гауссовому, а также ошибка оценки угла между входными векторами по бинаризованным выходным векторам. Показано, что при выборе параметров проецирования, для которых достигается близость распределения к гауссовому, экспериментальная и аналитическая ошибки близки.

Исследована оценка угла, скалярного произведения и евклидова расстояния вещественных векторов по бинарным векторам с регулируемой разреженностью. Преобразование проведено проецированием с применением бинарной случайной матрицы с элементами {0,1} и выходного порогового преобразования. Дан сравнительный анализ ошибки оценки мер сходства входных векторов по ряду мер сходства выходных бинарных векторов на основе скалярного произведения.

Предложено использование бинарной случайной матрицы с элементами {0,1} для проецирования входных векторов, имеющих формат с плавающей запятой, в выходные векторы того же формата, но сокращенной размерности. Проанализирована точность оценки скалярного произведения, евклидова расстояния, нормы входных векторов по выходным. Аналитически и экспериментально показано, что ошибка оценки для предложенной случайной проекции меньше, чем для тернарной случайной матрицы.

We investigate the properties of randomized binary vector representations with adjustable sparseness formed from the input vectors by projecting them using a random matrix with ternary elements {-1, 0, +1}. We analyze the accuracy of estimating the measures of similarity-difference of the source vectors having a floating-point format by the output binary vectors. Those vector representations can be used for an efficient processing of large volumes of input multidimensional vectors in applications related to search, classification, associative memory, etc.

An approach is proposed to the stable solution of discrete ill-posed problems, based on a combination of random projection of the initial ill-conditioned matrix with ill-defined numerical rank and pseudo-inversion of the resultant matrix. To select the dimension of the projection matrix, we propose to use selection criteria for the model and regularization parameter. The results of experimental studies on the well-known examples of discrete ill-posed problems are given. The solution error is close to the Tikhonov regularization error; however, reducing the matrix dimension due to the projection reduces the computational costs, especially at high noise levels.

Розглянуто підхід до підвищення інтелектуальності інформаційних технологій і систем на основі моделювання мислення людини - міркувань по прецедентах і аналогіях і використання "знань здорового глузду". Для реалізації запропоновано використовувати методи нейросітьового розподіленого представлення інформації.

Розроблено й експериментально досліджено бінарні розподілені представлення векторних даних (числових, текстових та зображень) у задачах класифікації. Проведено порівнювальний аналіз результатів для різних методів і задач із штучними та природними даними.

Досліджено та порівняно час пошуку бінарних векторів за схожістю в асоціативній пам'яті для нейросіткового та традиційного підходів. Показано, що для ентропії сигнального простору порядку сотень та кількості запам'ятованих векторів, яка набагато перевищує ентропію, нейросітковий підхід перевершує традиційний навіть у разі реалізації на послідовному комп'ютері.

Розглянуто характеристики грубого кодування за допомогою випадково розподілених гіперпрямокутних рецептивних полів для схеми випадкових підпросторів RSC. Одержано розподіли ймовірностей рецептивних полів, вирази для щільності розподілу у різних точках вхідного простору, характеристики перекриття кодів та ін. Результати теоретичного аналізу підтверджено експериментами на кодах великої розмірності.

Розглянуто моделі першої стадії міркувань за аналогією: пошук у пам'яті аналогів деякої ситуації. Ситуації та аналоги ієрархічно структуровані та можуть включати відношення вищих порядків, що ускладнює пошук за умов використання традиційних підходів. Наведено схеми розподіленого представлення аналогів у вигляді багатовимірних бінарних векторів. Показано, що ступінь схожості ситуацій можна відобразити за допомогою величини скалярного добутку векторів, які їх представляють. Це створює підгрунтя для моделювання процесів пошуку аналогів людьми та більш ефективного пошуку у базах знань.