• 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
Doctoral Thesis
Full name
Mônica Ribeiro Porto Ferreira
Knowledge Area
Date of Defense
São Carlos, 2012
Pimentel, Maria da Graça Campos (President)
Aniorte, Philippe
Chbeir, Richard
Manolopoulos, Ioannis
Moro, Mirella Moura
Silva, Altigran Soares da
Title in English
Optimizing similarity queries in metric spaces meeting user's expectation
Keywords in English
Metric spaces
Similarity algebra
Similarity queries
Similarity query optimization
User's expectation
Abstract in English
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
Title in Portuguese
Otimização de operações de busca por similaridade em espaços métricos
Keywords in Portuguese
Álgebra por similaridade
Consultas por similaridade
Espaços métricos
Expectativa do usuário
Otimização de consultas por similaridade
Abstract in Portuguese
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
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
WARNING: The material described below relates to works resulting from this thesis or dissertation. The contents of these works are the author's responsibility.
  • 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.
All rights of the thesis/dissertation are from the authors
Centro de Informática de São Carlos
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.