Embedding k-Nearest Neighbor Queries into Relational Database Management Systems

  • Gabriel V. De Pierro University of São Paulo
  • Mônica R. P. Ferreira University of São Paulo
  • Lucio F. D. Santos University of São Paulo
  • Willian D. Oliveira University of São Paulo
  • Agma J. M. Traina University of São Paulo
  • Caetano Traina Jr. University of São Paulo
Keywords: k-Nearest neighbors, Relational model, Similarity algebra, Similarity search

Abstract

The ability to use, in a single query, both similarity and traditional select operators inside a Relational Database Management System (RDBMS) has proven to be a valuable tool, which provides a strong capability for better contextualizing queries involving complex data. However, the integration of both query operator classes is still in its early stages, as most works on similarity queries focus on the data structures and operations required to execute just the similarity retrieval operation, but few of them target problems on the integration itself. Among them, the k-Nearest Neighbor (k-NN) comparison operator gives ground to conflicting interpretations when composed with others. In this article we present a novel approach to remove dubiety when similarity-selections based on k-NN are embedded into a RDBMS, formalize the possible interpretations, and show how to resolve implementation issues that occur when executing them on database relations that include attributes queried by similarity. We also implemented a prototype for a RDBMS that also supports queries employing k-NN predicates and evaluated the proposed interpretations, measuring the performance of their respective operators, as well as the semantic implications. The proposed solution is versatile, being able to handle queries combining similarity-based and traditional predicates.

Published
2014-09-28
Section
SBBD Articles