• 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
 
 
Thèse de Doctorat
DOI
10.11606/T.55.2012.tde-24012013-091242
Document
Auteur
Nom complet
Mônica Ribeiro Porto Ferreira
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2012
Directeur
Jury
Pimentel, Maria da Graça Campos (Président)
Aniorte, Philippe
Chbeir, Richard
Manolopoulos, Ioannis
Moro, Mirella Moura
Silva, Altigran Soares da
Titre en anglais
Optimizing similarity queries in metric spaces meeting user's expectation
Mots-clés en anglais
Metric spaces
Similarity algebra
Similarity queries
Similarity query optimization
User's expectation
Resumé en anglais
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
Titre en portugais
Otimização de operações de busca por similaridade em espaços métricos
Mots-clés en portugais
Álgebra por similaridade
Consultas por similaridade
Espaços métricos
Expectativa do usuário
Otimização de consultas por similaridade
Resumé en portugais
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
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2013-01-29
 
AVERTISSEMENT: Le matériau se réfère à des documents provenant de cette thèse ou mémoire. Le contenu de ces documents est la responsabilité de l'auteur de la thèse ou mémoire.
  • 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.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2020. Tous droits réservés.