Optimal Aggregation Algorithms for Middleware
Ron Fagin Amnon Lotem
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,
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,
Back to On-Line Publications