Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/3045| Índice aproximado probabilístico para la búsqueda por proximidad en memoria secundaria Aproximate probabilistic index for the search of similarity in secondary memory | |
| FERNANDO LUQUE SUAREZ | |
| Edgar Leonel Chávez González | |
| Acceso Abierto | |
| Atribución | |
| Búsqueda en espacios métricos, indexación, identificación del parlante Searching in metric spaces, indexing, speaker identification | |
| La búsqueda en una colección por objetos similares a un objeto consulta, es un problema que se presenta en muchas aplicaciones en diversas áreas de las ciencias de la computación, como reconocimiento de patrones, recuperación multimedia, identificación con biométricos, etc. En este trabajo nos enfocamos en el modelo más general para la solución del problema que se basa en la noción de espacio métrico, donde la única información disponible es la distancia entre cualquier pareja de objetos en la colección. Con el de objetivo de ser eficiente en una búsqueda, se ha propuesta la organización de los objetos en la colección en una estructura llamada índice, para solo revisar una parte de la colección en una consulta. Debido al efecto de la maldición de la dimensión, los índices más rápidos sacrifican algunas respuestas correctas para poder ser eficientes aún cuando la representación de los objetos en la colección se encuentra en altas dimensiones, estos son los llamados índices aproximados para la búsqueda de similitud. Los índices aproximados más eficientes en la literatura se basan en la navegación sobre un grafo que aproxima una triangulación Delaunay, pero son eficientes únicamente en memoria principal. Para memoria secundaria la técnica que ha reportado mejores resultados es la de archivo invertido métrico, pero para tener una alta precisión requiere de revisar un alto porcentaje de la colección, además de tener posfiltrado con una función costosa computacionalmente de calcular. En este trabajo proponemos el uso de un cubrimiento del conjunto para la construcción de un índice métrico. En la fase de indexación la colección es descompuesta en subconjuntos de un tamaño acotado por una constante, tal que la unión de los subconjuntos es la colección. En una búsqueda, solo los subconjuntos relevantes a la consulta son activados y la unión de estos subconjuntos conforman los candidatos. Después, con un proceso simple de posfiltrado logramos filtrar los candidatos a un número considerablemente más pequeño. Mostramos experimentalmente con una colección de un millón de vectores de 128 dimensiones, que la estructura propuesta alcanza una precisión del 99% revisando únicamente el 1% de la colección. Para el problema de identificación del parlante, se requiere conocer su identidad persona utilizando únicamente su voz, se diseñó una solución que permite la indexación, por lo tanto, puede aplicarse en bases de datos grandes. Evaluamos experimentalmente la calidad de la... Searching in a collection for objects similar to a query object is a problem that occurs in many applications in several areas of computer science, such as pattern recognition, multimedia recovery, biometric identification, etc. In this work we focus on the more general model for solving the problem that is based on the notion of metric space, where the only information available is the distance between any pair of objects in the collection. With the aim of being efficient in a search, the organization of the objects in the collection has been proposed in a structure called index, to only review a part of the collection in a query. Due to the effect of the curse of the dimension the faster indices, sacrifice some correct answers to be able to remain efficient even when the representation of the objects in the collection is in high dimensions, these are the so-called approximate indexes. The most efficient approximate indexes in the literature are based on navigation on a graph that approximates a Delaunay triangulation, but are efficient only in main memory. For secondary memory, the technique that has reported the best results is the metric inverted file, but to have a high precision it requires reviewing a high percentage of the collection, in addition to having post-filtering with a computationally expensive function to calculate. In this work we propose the use of a covering of the set for the construction of a metric index. In the indexing phase, the collection is broken down into subsets of a size bounded by a constant, such that the union of the subsets is the collection. In a search, only the subsets relevant to the query are activated and the union of these subsets make up the candidates. Then, with a simple post-filtering process, we managed to filter the candidates to a considerably smaller number. We show experimentally with a collection of one million vectors of 128 dimensions, that the proposed structure reaches an accuracy of 99% by reviewing only 1% of the collection. For the problem of identification of the speaker where a person's voice is used, it is required to know their identity, a solution was designed that allows indexing, therefore, it can be applied in large databases. We experimentally evaluate the quality of identification with a public database formed by extracting audio from a collection of YouTube videos from 1,000 different speakers. With 20 second audio segments, we were able to identify a speaker with 95% accuracy, when... | |
| CICESE | |
| 2019 | |
| Tesis de doctorado | |
| Español | |
| Luque Suárez, F. 2019. Indice aproximado probabilístico para la búsqueda por proximidad en memoria secundaria. Tesis de Doctorado en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 73 pp. | |
| INTELIGENCIA ARTIFICIAL | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| tesis_Luque Suárez Fernando_28_nov_2019.pdf | Versión completa de la tesis | 3.5 MB | Adobe PDF | Visualizar/Abrir |