Optimal Aggregation Algorithms for Middleware

Ron Fagin, Amnon Lotem, Moni Naor

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 f…