Optimal Aggregation Algorithms for Middleware

Details Optimal Aggregation Algorithms for Middleware Optimal Aggregation Algorithms for Middleware

2002-04-22

arxiv.org/abs/cs/0204046v1

Computer Science

Databases

41 pages. Preliminary version appeared in ACM PODS 2001, pp. 102-113

Scientific paper

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 k objects according to a monotone aggregation function t, while minimizing access to the lists. The problem arises in several contexts. In particular Fagin (JCSS 1999) considered it for the purpose of aggregating information in a multimedia database system. We are interested in instance optimality, i.e. that our algorithm will be as good as any other (correct) algorithm on any instance. We provide and analyze several instance optimal algorithms for the task, with various access costs and models.

Affiliated with

Also associated with

No associations

Rating

Optimal Aggregation Algorithms for Middleware does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Aggregation Algorithms for Middleware, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Aggregation Algorithms for Middleware will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-402953