Optimal aggregation algorithms for middleware

By Ronald Fagin, Amnon Lotem, Moni Naor. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

2,152 citations recorded by the source corpus.

Assume that each object in a database has m grades, or scores, one for each of m attributes. For example, an object can have a color grade, that tells how red it is, and a shape grade, that tells how round it is. For each attribute, there is a sorted list, which lists each object and its grade under that attribute, sorted by grade (highest grade first). There is some monotone aggregation function, or combining rule, such as min or average, that combines the individual grades to obtain an overall grade. To determine objects that have the best overall grades, the naive algorithm must access every object in the database, to find its grade under each attribute. Fagin has given an algorithm (“Fagin's Algorithm”, or FA) that is much more efficient. For some distributions on grades, and for some monotone aggregation functions, FA is optimal in a high-probability sense. We analyze an elegant and remarkably simple algorithm (“the threshold algorithm”, or TA) that is optimal in a much stronger sense than FA. We show that TA is essentially optimal, not just for some monotone aggregation functions, but for all of them, and not just in a high-probability sense, but over every database. Unlike FA, which requires large buffers (whose size may grow unboundedly as the database size grows), TA requires only a small, constant-size buffer. We distinguish two types of access: sorted access (where the middleware system obtains the grade of an object in some sorted list by proceeding through the list sequentially from the top), and random access (where the middleware system requests the grade of object in a list, and obtains it in one step). We consider the scenarios where random access is either impossible, or expensive relative to sorted access, and provide algorithms that are essentially optimal for these cases as well.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e1f3c9b4da3c84ef47d357140e842d44056c8a98

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

RankSQL: query algebra and optimization for relational top-k queries (2005, background): “In middleware settings, various algorithms are proposed for rank aggregation on a set of objects, by merging multiple ranked lists [10, 26, 16, 11], or scheduling random accesses efficiently [2, 4], with the goal of minimizing number of accesses to objects.”
Efficient IR-Style Keyword Search over Relational Databases (2003, methodology): “Finally, Natsev et al. [13] extend the work by Fagin et al. [6] by allowing different objects to appear in the source “lists,” as opposed to assuming that the lists have just attribute values for a common set of objects.”
IR-Tree: An Efficient Index for Geographic Document Search (2011, methodology): “Here, the threshold algorithm and its variants [7], [10] can”
Group Recommendation: Semantics and Efficiency (2009, background): “1 The weighted summation nature of the consensus function is well supported by the family of threshold algorithms ﬁrst proposed in [6].”
Fast shortest path distance estimation in large networks (2009, methodology): “Algorithm To that end, we use ideas similar to the Thresh-old (TA) algorithm, introduced in the seminal work of Fagin et al. [12].”
Ranking queries on uncertain data: a probabilistic threshold approach (2008, methodology): “Some existing methods such as the well known TA algorithm [ 12 ] can retrieve in batch tuples satisfying the predicate in the ranking order.”
Efficient query processing in geographic web search engines (2006, background): “There has been a significant amount of work in the IR and database communities on this issue under various scenarios; see [2, 10, 14, 15, 26, 37].”
BLINKS: ranked keyword searches on graphs (2007, background): “TA has been proven optimal in terms of number of objects visited, assuming the aggregate function that combines the m scores is monotone [9].”
Distributed top-k monitoring (2003, background): “, [7, 16], in contrast to continuous, online monitoring of top-k answers as they change over time.”
Designing Fair Ranking Schemes (2017, methodology): “The primary focus of this work is on efficient query processing, for which methods include threshold-based [31], view-based [32], and indexing-based [33].”
Evaluating top-k queries over Web-accessible databases (2002, methodology): “[7] presented “instance optimal” query processing algorithms over sources that are either of type SR-Source (TA algorithm) or of type S-Source (NRA algorithm).”
Efficient Distributed Skylining for Web Information Systems (2004, background): “Recent research on web-based information systems has focused on employing middleware algorithms, where users had to specify weightings for each aspect of their query and a central compensation function was used to find the best matching objects [7], [1].”
Progressive skyline computation in database systems (2005, methodology): “Their processing method uses the main concept of the threshold algorithm [Fagin et al. 2001] to compute the entire skyline by reading the minimum number of records in each list.”
SAR: A sentiment-aspect-region model for user preference analysis in geo-tagged reviews (2015, background): “Another choice is the threshold algorithm [4] that may save the computation for some POIs.”
Efficient and effective retrieval using selective pruning (2013, background): “[15], which assume lists sorted by score, while we assume docid-based sorting.”
On the Feasibility of Peer-to-Peer Web Indexing and Search (2003, methodology): “To achieve this effect, Fagin’s algorithm (FA) [9] is used in conjunction with a ranking function to generate incremental ranked results.”
LCARS: a location-content-aware recommender system (2013, methodology): “process of producing recommendations, we extend the thresholdbased algorithm [8] that is capable of correctly finding top-k results by examining the minimum number of spatial items.”