Advanced search
Start date

Genetic algorithms for similarity queries in metric spaces

Full text
Renato Bueno
Total Authors: 1
Document type: Master's Dissertation
Press: São Carlos.
Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
Defense date:
Examining board members:
Caetano Traina Junior; Karin Becker; André Carlos Ponce de Leon Ferreira de Carvalho
Advisor: Caetano Traina Junior

I search process on complex domains for exact answer to a similarity query is an expensive process considering computational resources, such as memory and processing time requirements. However, when comparing multimédia dal,a, the comparison operations usually consider some properties of each daturn element, so exact queries involving this data return results tliat are exact regarding the properties compared, but not necessarily exact regarding the multimedia data itself. For example, searching for similar images regarding their colors return images whose color histogram are the most similar, but the retrieved images can be very different regarding for example the forni of the objects pietured. Therefore, for applications dealing with complex data types, trading exact answering with query time response can be a worth exchange. In this work we developed techniques based 011 genetic algorithms to allow retrieving approximate data indexed in a Metric Access Methods (MAMs) within a limited, user-defined, amount of time. For evaluation purposes, the algorithms were developed regarding the Slim-lrce, but the approximate query techniques developed in this work can be straightforwardly implemented on other MAMs. The algorithms can be used to perform nearest neighbor queries, range queries and some other variations. Svnthetic and real world datasets were used to evaluate the approximate algorithms, achieving good results in a fraetion of the time required to obtain the exact answer. The experimental results show that, allowing the algorithm to run during 50% of the exact query time, the precision of the approximate results is about 90%, and precision of 65% can be obtained consuming just 20% of the same exact query time. (AU)