Advanced search
Start date

Exact search operation for reverse nearest k-neighbors in metric spaces

Grant number: 07/02158-0
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.

Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
OLIVEIRA, Willian Dener de. Operação de busca exata aos K-vizinhos mais próximos reversos em espaços métricos. 2010. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação São Carlos.

Please report errors in scientific publications list by writing to: