Optimal Aggregation Algorithms for Middleware

 Ron Fagin        Amnon Lotem         Moni Naor

Abstract:

Let D be a database of N objects where each object has m fields. The objects are given in m sorted lists (where the ith list is sorted according to the ith field). Our goal is to find the top  object according to a monotone aggregation function, such as min or average, while minimizing access to the lists. The problem arises in several contexts. In particular Fagin (JCSS 1999) considered it for the purpose of a middleware aggregating information in a multimedia database system.

In this work we design algorithms that are instance optimal, i.e. our algorithm should be be as good (or not much worse) as any other (correct) algorithm on every instance.  We analyze a remarkably simple algorithm (``the threshold algorithm'', or TA) and show that TA is essentially optimal, not just for some monotone aggregation functions, but for all of them, and over every database. We also consider the scenario where random access cost is expensive relative to sorted access and provide algorithms that are instance optimal for this case as well.
 

Paper: Postscript , gzipped Postscript. PDF . Slides: ppt .
 

Related On-Line Papers:
  • Cynthia Dwork, Ravi Kumar, and Moni Naor, D. Sivakumar, Rank aggregation methods for the Web, WWW10, 2001 .

    • Abstract, HTML
     

    Back to On-Line Publications

    Back Home