#

**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 *i*th
list is sorted according to the *it*h 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