iDistance
В распознавании образов — iDistance это метод индексации и обработки запросов для запросов k-ближайших соседей к точечным данным в многомерных метрических пространствах . Запрос kNN — одна из самых сложных проблем с многомерными данными, особенно когда размерность данных высока . iDistance предназначен для эффективной обработки запросов kNN в многомерных пространствах и особенно хорош для асимметричных распределений данных , которые обычно возникают в реальных наборах данных. iDistance можно дополнить моделями машинного обучения, чтобы изучить распределение данных для поиска и хранения многомерных данных. [1]
Индексация [ править ]
Построение индекса iDistance состоит из двух этапов:
- Выбирается ряд опорных точек в пространстве данных. Существуют различные способы выбора ориентиров. Использование центров кластеров в качестве ориентиров — наиболее эффективный способ. Короче говоря, точки данных разделены на ячейки Вороного на основе хорошо выбранных контрольных точек.
- Рассчитывается расстояние между точкой данных и ближайшей контрольной точкой. точки Это расстояние плюс значение масштабирования называется iDistance . Таким образом, точки в многомерном пространстве сопоставляются с одномерными значениями, а затем B + -tree можно использовать для индексации точек, используя iDistance в качестве ключа .
На рисунке справа показан пример, в котором три опорные точки (O 1 , O 2 , O 3 выбраны ). Затем точки данных сопоставляются с одномерным пространством и индексируются в B. + -дерево. Были предложены различные расширения для выбора контрольных точек для эффективного выполнения запросов, включая использование машинного обучения для обучения идентификации контрольных точек.
Обработка запросов [ править ]
Для обработки запроса kNN запрос сопоставляется с рядом запросов одномерного диапазона, которые можно эффективно обрабатывать на B. + -дерево. На рисунке выше запрос Q сопоставлен со значением в B. + -дерево, в то время как "сфера" поиска kNN отображается в диапазон в B + -дерево. Сфера поиска постепенно расширяется, пока не будут найдены k NN. Это соответствует постепенному расширению диапазона поиска в B. + -дерево.
Технику iDistance можно рассматривать как способ ускорения последовательного сканирования. Вместо сканирования записей от начала до конца файла данных iDistance начинает сканирование с мест, где ближайшие соседи могут быть получены заранее с очень высокой вероятностью.
Приложения [ править ]
iDistance использовался во многих приложениях, включая
- Получение изображения [2]
- Индексирование видео [3]
- Поиск по сходству в P2P-системах [4]
- Мобильные вычисления [5]
- Рекомендательная система [6]
Историческая справка [ править ]
iDistance впервые предложили Цуй Ю, Бенг Чин Оой, Киан-Ли Тан и Х.В. Джагадиш в 2001 году. [7] Позже вместе с Руй Чжаном они усовершенствовали методику и провели ее более полное исследование в 2005 году. [8]
Ссылки [ править ]
- ^ Анжела Давиткова, Эвика Милчевски, Себастьян Мишель, ML-индекс: многомерный изученный индекс для запросов к точкам, диапазонам и ближайшим соседям, Материалы 23-й Международной конференции по расширению технологии баз данных, Копенгаген, Дания, 407-410, 2020.
- ^ Цзюньци Чжан, Сяндун Чжоу, Вэй Ван, Бэйл Ши, Цзянь Пей, Использование многомерных индексов для поддержки поиска интерактивных изображений на основе обратной связи по релевантности, Материалы 32-й Международной конференции по очень большим базам данных, Сеул, Корея, 1211-1214, 2006 г. .
- ^ Хэн Тао Шен, Бенг Чин Оой, Сяофан Чжоу, На пути к эффективному индексированию для очень большой базы данных видеопоследовательностей, Материалы Международной конференции ACM SIGMOD по управлению данными, Балтимор, Мэриленд, США, 730-741, 2005.
- ^ Христос Дулкеридис, Акриви Влаху, Яннис Котидис, Михалис Вазиргианнис, Одноранговый поиск по сходству в метрических пространствах, Материалы 33-й Международной конференции по очень большим базам данных, Вена, Австрия, 986-997, 2007.
- ^ Серджио Иларри, Эдуардо Мена, Аранца Илларраменди, Запросы, зависящие от местоположения, в мобильных контекстах: распределенная обработка с использованием мобильных агентов, Транзакции IEEE на мобильных вычислениях, том 5, выпуск 8, август 2006 г. Страницы: 1029–1043.
- ^ Ян Сонг, Ю Гу, Руй Чжан, Ге Ю, ProMIPS: эффективный многомерный c-приблизительный поиск максимального внутреннего продукта с облегченным индексом, 37-я Международная конференция IEEE по инженерии данных, Ханья, Греция, 1619-1630, 2021.
- ^ Цуй Ю, Бенг Чин Оой, Киан-Ли Тан и Х.В. Джагадиш Индексирование расстояния: эффективный метод обработки KNN , Материалы 27-й Международной конференции по очень большим базам данных, Рим, Италия, 421-430, 2001.
- ^ Х. В. Джагадиш, Бенг Чин Оой, Киан-Ли Тан, Цуй Ю и Руй Чжан iDistance: адаптивный метод индексации на основе B +-дерева для поиска ближайших соседей , Транзакции ACM в системах баз данных (ACM TODS), 30, 2, 364- 397, июнь 2005 г.