|Support type:||Scholarships in Brazil - Master|
|Effective date (Start):||October 01, 2007|
|Effective date (End):||November 30, 2008|
|Field of knowledge:||Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques|
|Principal Investigator:||Caetano Traina Junior|
|Grantee:||Willian Dener de Oliveira|
|Home Institution:||Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil|
Data stored in large databases present an ever increasing complexity, pressing for the development of new classes of query operators. One such class, which is having an increasing interest, is the so-called Similarity Queries, where the most common are the similarity range queries (Rq) and the k-nearest neighbor queries (kNNq). A k-nearest neighbor query aims at retrieving the k stored elements nearer (or more similar) to a given reference element. Another important similarity query is the reverse k-nearest neighbor one (RkNNq), useful for both queries posed directly by the analyst and queries that are part of more complex analysis processes. The objective of a reverse k-nearest neighbor queries is obtaining the stored elements that has the query reference element as one of their k-nearest neighbors. As the RkNNq operation is a rather expensive operation, from the computational standpoint, most existing solutions only solve the query when applied over Euclidean multidimensional spaces (as these spaces also define cardinal and topological operations besides the Euclidean distance between pairs of elements) or retrieve only approximate answers, where false negatives can occur.Several applications, like the analysis of scientific, medical, engineering or financial data, require efficient and exact answers for the RkNNq queries over data which is frequently represented in metric spaces, that is where no other property besides the similarity measure exists. Therefore, for applications handling metrical data, the assumption of Euclidean metric or even multidimensional data cannot be used.This master-degree project aims at developing a new technique to retrieve the exact answer for a reverse k-nearest neighbor query posed over data represented in a metric space, based on metric access methods that allow pruning sub-spaces from the search space, and lead to efficient query execution.