• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tesis Doctoral
DOI
10.11606/T.55.2012.tde-24012013-091242
Documento
Autor
Nombre completo
Mônica Ribeiro Porto Ferreira
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2012
Director
Tribunal
Pimentel, Maria da Graça Campos (Presidente)
Aniorte, Philippe
Chbeir, Richard
Manolopoulos, Ioannis
Moro, Mirella Moura
Silva, Altigran Soares da
Título en inglés
Optimizing similarity queries in metric spaces meeting user's expectation
Palabras clave en inglés
Metric spaces
Similarity algebra
Similarity queries
Similarity query optimization
User's expectation
Resumen en inglés
The complexity of data stored in large databases has increased at very fast paces. Hence, operations more elaborated than traditional queries are essential in order to extract all required information from the database. Therefore, the interest of the database community in similarity search has increased significantly. Two of the well-known types of similarity search are the Range ('R IND. q') and the k-Nearest Neighbor ('kNN IND. q') queries, which, as any of the traditional ones, can be sped up by indexing structures of the Database Management System (DBMS). Another way of speeding up queries is to perform query optimization. In this process, metrics about data are collected and employed to adjust the parameters of the search algorithms in each query execution. However, although the integration of similarity search into DBMS has begun to be deeply studied more recently, the query optimization has been developed and employed just to answer traditional queries. The execution of similarity queries, even using efficient indexing structures, tends to present higher computational cost than the execution of traditional ones. Two strategies can be applied to speed up the execution of any query, and thus they are worth to employ to answer also similarity queries. The first strategy is query rewriting based on algebraic properties and cost functions. The second technique is when external query factors are applied, such as employing the semantic expected by the user, to prune the answer space. This thesis aims at contributing to the development of novel techniques to improve the similarity-based query optimization processing, exploiting both algebraic properties and semantic restrictions as query refinements
Título en portugués
Otimização de operações de busca por similaridade em espaços métricos
Palabras clave en portugués
Álgebra por similaridade
Consultas por similaridade
Espaços métricos
Expectativa do usuário
Otimização de consultas por similaridade
Resumen en portugués
A complexidade dos dados armazenados em grandes bases de dados tem aumentado sempre, criando a necessidade de novas operações de consulta. Uma classe de operações de crescente interesse são as consultas por similaridade, das quais as mais conhecidas são as consultas por abrangência ('R IND. q') e por k-vizinhos mais próximos ('kNN IND. q'). Qualquer consulta e agilizada pelas estruturas de indexação dos Sistemas de Gerenciamento de Bases de Dados (SGBDs). Outro modo de agilizar as operações de busca e a manutenção de métricas sobre os dados, que são utilizadas para ajustar parâmetros dos algoritmos de busca em cada consulta, num processo conhecido como otimização de consultas. Como as buscas por similaridade começaram a ser estudadas seriamente para integração em SGBDs muito mais recentemente do que as buscas tradicionais, a otimização de consultas, por enquanto, e um recurso que tem sido utilizado para responder apenas a consultas tradicionais. Mesmo utilizando as melhores estruturas existentes, a execução de consultas por similaridade tende a ser mais custosa do que as operações tradicionais. Assim, duas estratégias podem ser utilizadas para agilizar a execução de qualquer consulta e, assim, podem ser empregadas também para responder às consultas por similaridade. A primeira estratégia e a reescrita de consultas baseada em propriedades algébricas e em funções de custo. A segunda técnica faz uso de fatores externos à consulta, tais como a semântica esperada pelo usuário, para restringir o espaço das respostas. Esta tese pretende contribuir para o desenvolvimento de técnicas que melhorem o processo de otimização de consultas por similaridade, explorando propriedades algebricas e restrições semânticas como refinamento de consultas
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2013-01-29
 
ADVERTENCIA: El material descrito abajo se refiere a los trabajos derivados de esta tesis o disertación. El contenido de estos documentos es responsabilidad del autor de la tesis o disertación.
  • FERREIRA, Monica R. P., et al. Adding Knowledge Extracted by Association Rules into Similarity Queries. JOURNAL OF INFORMATION AND DATA MANAGEMEN [online], 2010, vol. 1, n. 3, p. 391-406. [cited ]. Available from : <http://seer.lcc.ufmg.br/index.php/jidm/article/view/64>
  • FERREIRA, Monica R. P., et al. Algebraic Properties to Optimize kNN Queries. JOURNAL OF INFORMATION AND DATA MANAGEMENT [online], 2011, vol. 2, n. 3, p. 385-400. [cited ]. Available from : <http://seer.lcc.ufmg.br/index.php/jidm/article/view/143>
  • FERREIRA, Monica R. P., et al. Identifying Algebraic Properties to Support Optimization of Unary Similarity Queries. In Proceedings of the 3rd Alberto Mendelzon International Workshop on Foundations of Dat [online], 3, Arequipa, Peru, 2009. Arequipa, Peru : CEUR-WS.org, 2009. vol. 450, p. 1-10. [cited ]. Available from : <http://ceur-ws.org/Vol-450/paper6.pdf>
  • FERREIRA, Monica R. P., et al. Integrating user preference to similarity queries over medical images datasets [doi:10.1109/CBMS.2010.6042693]. In 2010 IEEE 23rd International Symposium on Computer-Based Medical Systems (CBMS) [online], 23, Bentley, Australia, 2010. Bentley, Australia : IEEE, 2010. p. 486-491. ISBN 978-1-4244-9167-4.
  • RIBEIRO, Marcela X., et al. Data pre-processing: a new algorithm for feature selection and data discretization [doi:10.1145/1456223.1456277]. In Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology - CSTST '08 [online], 5, Cergy-Pontoise, France, 2008. New York, New York, USA : ACM Press, 2008. p. 252-257. ISBN 9781605580463.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2020. Todos los derechos reservados.