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

• Grant number: 07/02158-0
• Support Opportunities: Scholarships in Brazil - Master
• Start date: October 01, 2007
• End date: 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
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

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. Answering exact reverse k-nerarest neighbors queries in metric space. 2010. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.