Grafos

Estructuras de Datos II

Universidad Nacional de San Agustín

Docente: M.Sc. Carlo Corrales Delgado

Resumen
 Buscar elementos en un conjunto que son

cercanos a una consulta (query) bajo un
criterio de similaridad.
 Estamos interesados en casos donde el
criterio de similaridad define un espacio
métrico en vez de un espacio vectorial.
 Las mismas ideas han sido reinventadasvarias veces y diferentes presentaciones
han sido dadas para diferentes enfoques.

Resumen
 Se muestra una vista unificada de todas la

propuestas conocidas de organizar
espacios métricos.
 Se presentan resultados de la dificultad
del problema de búsqueda y propuestas
para organizar los espacios métricos.

Introducción
 Datos numéricos y alfabéticos →

búsquedas exactas, clavescomparables.
Existe un orden lineal total en claves.
 No es posible ya estructurar la
información en claves y registros. Nace la
búsqueda por similaridad o proximidad.
 Similaridad está modelada con una
función de distancia (desigualdad
triangular). El conjunto de objetos es
llamado espacio métrico.

Introducción
 El problema aparece en distintas áreas

(estadística, geometríacomputacional,
inteligencia artificial, bases de datos,
biología computacional reconocimiento de
patrones, minería de datos)
 Se ha intentado considerarlo como un
caso especial de los espacios vectoriales,
pero no se puede extender a los espacios
métricos generales donde solo se conoce
la distancia entre los objetos.

Introducción
 Es más dificil calcular la distancia. La

meta esreducir el nro de evaluaciones de
distancias.
 En espacios vectoriales se usan índices
para reducir las E∕S.
 Los algoritmos de indexación existentes
para búsquedas por proximidad consisten
en construir un conjunto de clases
equivalentes, obviando algunas clases y
buscando exhaustivamente en el resto.

Introducción
 Técnicas basadas en relaciones de

equivalencia:
 Pivoting

Particiones Voronoi

 Nos enfocamos en el nro de evaluaciones

de distancias necesarias para ejecutar
consultas de rango.
 Veremos:

 Estado del arte: búsqueda en espacios métricos
 Resultados en el problema de búsqueda y

modelo unificado

Aplicaciones motivadoras
 Consultas por contenido en Bases de datos








estructuradas: grid files (hiperrectángulos de k-dim,con consultas de subrectángulos).
Consultas por contenido en Objetos multimedia:
reconocimiento facial impresión de huellas digitales,
reconocimiento de voz, BD multimedia.
Recuperación de texto (no estructurado): buscados
por conceptos semánticos. Misspelling.
Biología computacional: secuencias ADN y proteínas
Reconocimiento de patrones y aproximación de
funciones: funciones de redesneurales y fuzzy.
Compresión de audio y video

Aplicaciones motivadoras
 Consultas por contenido en Bases de

datos estructuradas:

 Clásica aproximación: la clave es fija y completa.

Posible tipos de búsquedas son puntuales o clave,
por rango y por proximidad.
 Una solución a la consulta por rango es el
GridFile. El dominio es visto como un hiperrectángulo de k-dim, donde cadadimensión tiene
un orden.
 Cada registro en la BD es considerado como un
punto dentro del hiper-rectángulo. Una consulta
especifica un subrectángulo (un rango en cada
dim) y todos los puntos dentro son recuperados.

Aplicaciones motivadoras
 Consultas por contenido en Objetos

multimedia:

 Nuevos tipos de datos, como imágenes, audio y

video, no pueden ser consultados en el sentidoclásico. Ni ordenados ni comparados.
 La probabilidad que dos diferentes imágenes
sea igual pixel a pixel es ínfima a menos que
sean copias digitales de una misma fuente.
 Similaridad: reconocimiento de caras, huellas
digitales, reconocimiento de voz, etc.
 Ej. Halla una imagen de un león en una sabana.

Aplicaciones motivadoras
 Consultas por contenido en Objetos

multimedia:...