Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В распознавания образов , то iDistance является способ обработки индексации и запросов для K-ближайшего соседа запросов на точечных данных в многомерных метрических пространств . Запрос kNN - одна из самых сложных проблем для многомерных данных, особенно когда размерность данных высока . IDistance разработан для эффективной обработки запросов kNN в многомерных пространствах и особенно хорош для искаженных распределений данных , которые обычно возникают в реальных наборах данных.

Индексирование [ править ]

iDistance

Построение индекса iDistance состоит из двух этапов:

  1. Выбирается ряд ориентиров в пространстве данных. Есть разные способы выбора опорных точек. Использование центров кластеров в качестве ориентиров - наиболее эффективный способ.
  2. Рассчитывается расстояние между точкой данных и ближайшей к ней контрольной точкой. Это расстояние плюс значение масштабирования называется iDistance точки . Таким образом, точки в многомерном пространстве сопоставляются с одномерными значениями, и затем может быть принято B + -дерево для индексации точек с использованием iDistance в качестве ключа .

На рисунке справа показан пример выбора трех опорных точек (O 1 , O 2 , O 3 ). Затем точки данных отображаются в одномерное пространство и индексируются в B + -дереве.

Обработка запросов [ править ]

Чтобы обработать запрос kNN, этот запрос отображается на ряд запросов одномерного диапазона, которые могут быть эффективно обработаны на B + -дереве. На приведенном выше рисунке запрос Q отображается на значение в B + -дереве, в то время как поисковая «сфера» kNN отображается в диапазон в B + -дереве. Сфера поиска постепенно расширяется, пока не будут найдены k NN. Это соответствует постепенно расширяющемуся диапазону поиска в B + -дереве.

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

Приложения [ править ]

IDistance использовался во многих приложениях, включая

Историческая справка [ править ]

IDistance впервые была предложена Цуй Ю, Бенг Чин Оои, Киан-Ли Тан и Х.В. Джагадишем в 2001 году. [5] Позже, вместе с Руи Чжаном, они усовершенствовали эту технику и провели более всестороннее исследование в 2005 году [6]. ]

Ссылки [ править ]

  1. ^ Цзюньци Чжан, Сяндун Чжоу, Вэй Ван, Байле Ши, Цзянь Пей, Использование высокоразмерных индексов для поддержки поиска интерактивных изображений на основе релевантной обратной связи, Материалы 32-й Международной конференции по очень большим базам данных, Сеул, Корея, 1211-1214, 2006 .
  2. ^ Хэн Тао Шен, Бэн Чин Оой, Сяофан Чжоу, На пути к эффективному индексированию для очень большой базы данных видеопоследовательностей, Труды Международной конференции ACM SIGMOD по управлению данными, Балтимор, Мэриленд, США, 730-741, 2005.
  3. ^ Христос Доулкеридис, Акриви Влаху, Яннис Котидис, Михалис Вазиргианнис, Одноранговый поиск подобия в метрических пространствах, Труды 33-й Международной конференции по очень большим базам данных, Вена, Австрия, 986-997, 2007.
  4. ^ Серхио Иларри, Эдуардо Мена, Аранца Илларраменди, Зависимые от местоположения запросы в мобильных контекстах: распределенная обработка с использованием мобильных агентов, IEEE Transactions on Mobile Computing, Volume 5, Issue 8, Aug. 2006 Page (s): 1029-1043.
  5. ^ Цуй Ю, Бенг Чин Оои, Киан-Ли Тан и Х.В. Джагадиш Индексирование расстояния: эффективный метод обработки KNN , Труды 27-й Международной конференции по очень большим базам данных, Рим, Италия, 421-430, 2001.
  6. ^ HV Jagadish, Beng Chin Ooi, Kian-Lee Tan, Cui Yu и Rui Zhang iDistance: Адаптивный метод индексации на основе B + -дерева для поиска ближайшего соседа , транзакции ACM в системах баз данных (ACM TODS), 30, 2, 364- 397, июнь 2005 г.

Внешние ссылки [ править ]