stringtranslate.com

iDistancia

En el reconocimiento de patrones , la iDistance es una técnica de indexación y procesamiento de consultas para consultas de k vecinos más cercanos en datos puntuales en espacios métricos multidimensionales . La consulta kNN es uno de los problemas más difíciles en datos multidimensionales, especialmente cuando la dimensionalidad de los datos es alta . La iDistance está diseñada para procesar consultas kNN en espacios de alta dimensión de manera eficiente y es especialmente buena para distribuciones de datos sesgadas , que generalmente ocurren en conjuntos de datos de la vida real. La iDistance se puede aumentar con modelos de aprendizaje automático para aprender las distribuciones de datos para buscar y almacenar datos multidimensionales. [1]

Indexación

iDistancia
iDistancia

La construcción del índice iDistance tiene dos pasos:

  1. Se eligen varios puntos de referencia en el espacio de datos. Existen varias formas de elegir puntos de referencia. La forma más eficiente es utilizar los centros de los clústeres como puntos de referencia. Los puntos de datos se dividen en celdas de Voronoi en función de los puntos de referencia elegidos correctamente.
  2. Se calcula la distancia entre un punto de datos y su punto de referencia más cercano. Esta distancia más un valor de escala se denomina iDistance del punto . De esta manera, los puntos en un espacio multidimensional se asignan a valores unidimensionales y luego se puede adoptar un árbol B + para indexar los puntos utilizando iDistance como clave .

La figura de la derecha muestra un ejemplo en el que se eligen tres puntos de referencia (O 1 , O 2 , O 3 ). Luego, los puntos de datos se asignan a un espacio unidimensional y se indexan en un árbol B + . Se han propuesto varias extensiones para realizar la selección de puntos de referencia para un rendimiento de consulta eficaz, incluido el empleo de aprendizaje automático para aprender la identificación de puntos de referencia.

Procesamiento de consultas

Para procesar una consulta kNN, la consulta se asigna a una serie de consultas de rango unidimensionales, que se pueden procesar de manera eficiente en un árbol B + . En la figura anterior, la consulta Q se asigna a un valor en el árbol B + , mientras que la "esfera" de búsqueda kNN se asigna a un rango en el árbol B + . La esfera de búsqueda se expande gradualmente hasta que se encuentran las k NN. Esto corresponde a búsquedas de rango que se expanden gradualmente en el árbol B + .

La técnica iDistance puede considerarse como una forma de acelerar el escaneo secuencial. En lugar de escanear registros desde el principio hasta el final del archivo de datos, iDistance inicia el escaneo desde los puntos en los que se pueden obtener los vecinos más cercanos con una probabilidad muy alta.

Aplicaciones

La iDistance se ha utilizado en muchas aplicaciones, entre ellas:

Antecedentes históricos

La iDistance fue propuesta por primera vez por Cui Yu, Beng Chin Ooi, Kian-Lee Tan y HV Jagadish en 2001. [7] Más tarde, junto con Rui Zhang, mejoraron la técnica y realizaron un estudio más exhaustivo sobre ella en 2005. [8]

Referencias

  1. ^ Angjela Davitkova, Evica Milchevski, Sebastian Michel, The ML-Index: Un índice aprendido multidimensional para consultas de puntos, rangos y vecinos más cercanos, Actas de la 23.ª Conferencia internacional sobre la extensión de la tecnología de bases de datos, Copenhague, Dinamarca, 407-410, 2020.
  2. ^ Junqi Zhang, Xiangdong Zhou, Wei Wang, Baile Shi, Jian Pei, Uso de índices de alta dimensión para respaldar la recuperación de imágenes interactivas basada en retroalimentación de relevancia, Actas de la 32.ª Conferencia internacional sobre bases de datos muy grandes, Seúl, Corea, 1211-1214, 2006.
  3. ^ Heng Tao Shen, Beng Chin Ooi, Xiaofang Zhou, Hacia una indexación efectiva para bases de datos de secuencias de vídeo muy grandes, Actas de la Conferencia internacional ACM SIGMOD sobre gestión de datos, Baltimore, Maryland, Estados Unidos, 730-741, 2005.
  4. ^ Christos Doulkeridis, Akrivi Vlachou, Yannis Kotidis, Michalis Vazirgiannis, Búsqueda de similitud punto a punto en espacios métricos, Actas de la 33ª Conferencia internacional sobre bases de datos muy grandes, Viena, Austria, 986-997, 2007.
  5. ^ Sergio Ilarri, Eduardo Mena, Arantza Illarramendi, Consultas dependientes de la ubicación en contextos móviles: procesamiento distribuido utilizando agentes móviles, IEEE Transactions on Mobile Computing, Volumen 5, Número 8, agosto de 2006 Página(s): 1029 - 1043.
  6. ^ Yang Song, Yu Gu, Rui Zhang, Ge Yu, ProMIPS: Búsqueda eficiente de producto interno máximo aproximado de c de alta dimensión con un índice ligero, 37.a Conferencia internacional IEEE sobre ingeniería de datos, Chania, Grecia, 1619-1630, 2021.
  7. ^ Cui Yu, Beng Chin Ooi, Kian-Lee Tan y HV Jagadish Indexación de la distancia: un método eficiente para el procesamiento de KNN, Actas de la 27ª Conferencia Internacional sobre Bases de Datos Muy Grandes, Roma, Italia, 421-430, 2001.
  8. ^ HV Jagadish, Beng Chin Ooi, Kian-Lee Tan, Cui Yu y Rui Zhang iDistance: un método de indexación basado en árboles B+ adaptativo para la búsqueda del vecino más cercano, ACM Transactions on Data Base Systems (ACM TODS), 30, 2, 364-397, junio de 2005.

Enlaces externos