| Título: |
Diseño de un índice para colecciones de nubes de puntos en una rejilla Design of an index for collections of point clouds in a mesh |
| Autores: | MIGUEL RAMIREZ CHACON |
| Fecha: | 2017 |
| Publicador: | CICESE |
| Fuente: |
 |
| Tipo: | info:eu-repo/semantics/masterThesis |
| Tema: |
info:eu-repo/classification/Autor/nubes de puntos, búsqueda de proximidad, índices, búsqueda aproximada de vecinos más cercanos info:eu-repo/classification/Autor/point clouds, similarity search, index, approximate nearest neighbor search info:eu-repo/classification/cti/1 info:eu-repo/classification/cti/12 info:eu-repo/classification/cti/1203 info:eu-repo/classification/cti/120315 |
| Descripción: |
En los últimos años se ha incrementado significativamente el tamaño de las bases de datos de contenido multimedia y existe cada vez más interés en mantener nuevas bases de datos. Ante este incremento, es de suma importancia diseñar estructuras de datos y algoritmos (llamados índices) que permitan realizar consultas de proximidad de manera eficiente. Aunque un gran número de objetos multimedia pueden ser representados como nubes de puntos (imágenes, audio, información de sistemas geográficos, puntos y polígonos en sistemas CAD, series de tiempo, etc.), pocos trabajos han abordado el diseño de índices para objetos multimedia que utilizan esta representación. El objetivo de este trabajo es diseñar una estructura de datos que permita realizar búsquedas de proximidad de objetos multimedia representados mediante nubes de puntos, en bases de datos de gran tamaño en tiempo sublineal y que estas estructuras de datos sean robustas ante inserciones y borrados. Para esto, se proponen estructuras de datos basadas en dos esquemas de solución: índices para nubes de puntos basados en índices invertidos y basados en índices métricos. Se realizaron pruebas experimentales en bases de datos de gran tamaño, incluyendo una base de datos sintéticos de 10 millones de nubes de puntos (1000 puntos por cada nube) y la base de datos MIR Flickr-1M, la cual contiene 1 millón de imágenes de alta calidad. El desempeño de los índices propuestos fue evaluado en función de su tiempo promedio de consulta, tiempo de construcción, exhaustividad@k, memoria de almacenamiento utilizada y desempeño ante inserciones/borrados. Los resultados obtenidos indican que los índices para nubes de puntos propuestos basados en índices invertidos, tienen un desempeño superior en tiempo promedio de consulta respecto al índice para nubes de puntos utilizado en la literatura, logrando en algunas pruebas experimentales, una mejora de tres órdenes de magnitud en tiempo promedio de consulta en la base de datos de imágenes MIR Flickr-1M y 𝑒𝑥ℎ𝑎𝑢𝑠𝑡𝑖𝑣𝑖𝑑𝑎𝑑@1 ≥ 0.989 bajo el efecto de inserciones y borrados para todos los índices propuestos In recent years there has been a significant increase in the size of multimedia databases, and new databases of large size are created continuously. It is, therefore, of utmost importance the design of indexes and algorithms allowing efficient similarity queries. Although a large number of multimedia objects can be represented as a point cloud (images, audio, information of geographic systems, points and polygons in CAD systems, time series, etc.), just a few works have addressed the design of indexes for multimedia objects using this representation. The objective of this work is to design data structures and algorithms, with sublinear performance, for similarity search of multimedia objects represented by point clouds in large databases, robust to insertions and deletions. To this end, we propose data structures based on two solution schemes: indexes for point clouds based on inverted indexes and based on metric indexes. Experimental tests were performed on large databases, including a synthetic database of 10 million point clouds (1000 points per cloud) and the Flickr-1M MIR database, which contains 1 million high-resolution images. The performance of the proposed indexes was evaluated according to: Average query time, construction time, recall@k, storage memory used and performance under insertions and deletions. The obtained results shows that the indexes proposed for point clouds based on inverted indexes, have a superior performance in average query time compared with the actual index for point clouds used in the literature. In some tests we obtained an improvement of three orders of magnitude on average query time in the image database MIR Flickr-1M and recall@1≥0.989 under the effect of insertions and deletions for all proposed indexes. |
| Idioma: | spa |
1 | 6 |
2 | 7 |
3 | 8 |
4 | 9 |
5 | 10 |