Processing top-k join queries

Minji Wu, Laure Berti-Équille, Amélie Marian, Cecilia M. Procopiuc, Divesh Srivastava

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

We consider the problem of efficiently finding the top-k answers for join queries over web-accessible databases. Classical algorithms for finding top-k answers use branch-and-bound techniques to avoid computing scores of all candidates in identifying the top-k answers. To be able to apply such techniques, it is critical to efficiently compute (lower and upper) bounds and expected scores of candidate answers in an incremental fashion during the evaluation. In this paper, we describe novel techniques for these problems. The first contribution of this paper is a method to efficiently compute bounds for the score of a query result when tuples in tables from the "FROM" clause are discovered incrementally, through either sorted or random access. Our second contribution is an algorithm that, given a set of partially evaluated candidate answers, determines a good order in which to access the tables to minimize wasted efforts in the computation of top-k answers. We evaluate our algorithms on a variety of queries and data sets and demonstrate the significant benefits they provide.

Original languageEnglish (US)
Pages (from-to)860-870
Number of pages11
JournalProceedings of the VLDB Endowment
Volume3
Issue number1
DOIs
StatePublished - Sep 2010

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Processing top-k join queries'. Together they form a unique fingerprint.

Cite this