Ranking objects according to di erent criteria is a central issue in many data-intensive applications. Yet, no existing solution deals with the case of partially speci ed score aggregation functions (e.g., a weighted sum with no precisely known weight values). We address multi-source top-k queries with constraints (rather than precise values) on the weights. Our solution is instance optimal and provides increased exibility with negligible overhead wrt classical top-k queries.
a h j d f b e i c g R1 9 8 8 7 7 6 6 5 4 4
i a g j c h f d e b R2 10 9 8 8 7 6 5 5 5 4
c f e i d a b g h j
R3 9 8 7 7 6 5 5 5 4 3
Example 1. Consider the scenario depicted in Figure 1, where ten restaurants, a; : : : ; j, are ordered by d = 3 rankings. Assume that the overall score is a weighted sum of the local scores, i.e., f (o) = Pd i=1 wi o[i], where o[i] is the score assigned by Ri to object o (e.g., c[2] = 7), and that the k = 2 best restaurants are sought. In particular, using the weight vector W1 = (1=3; 1=3; 1=3), the top-2 restaurants are a and i, with f (a) 7:67 and f (i) 7:33. A di erent choice of weights, say W2 = (0:2; 0:3; 0:5), results in i and c being the top-2 restaurants.
Choosing precise weights in the scoring function is admittedly di cult, and might be the result of learning from users, e.g., via crowdsourcing [4]. A more Copyright c 2019 for the individual papers by the papers authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. SEBD 2019, June 16-19, 2019, Castiglione della Pescaia, Italy. viable alternative is to specify weights only partially through a set of constraints. With reference to Example 1, instead of having xed weights, it might be interesting to \explore" all the alternatives arising when weights vary around W2, by, say, 0:1. Then, only a, c, f, and i can be the possible (top-2) answers.
We study the problem of answering multi-source top-k queries with partially speci ed weights. This leads to a family F of scoring functions for ranking objects. Existing solutions to the problem with a single scoring function are Fagin's algorithm (FA) [6] and the threshold algorithm (TA) [7]. The latter was shown to perform better and to achieve optimal I/O performance. Our proposal, FSA, solves the general case and reduces to TA for classical top-k queries (i.e, when F = ff g) and is instance optimal for any F . When no constraints are present, FSA behaves like FA and returns the so-called k-skyband [9], the case k = 1 being the skyline of the dataset [1].
This paper summarizes the main contributions presented in [3], namely 1) a provably correct and instance optimal algorithm, FSA, for answering multi-source top-k queries, 2) several optimization opportunities for improving the execution time of FSA, 3) experimental evidence that FSA enjoys the exibility of partially speci ed weights while incurring little overhead wrt top-k queries.
Consider a dataset D = fo1; : : : ; oN g where each object o 2 D has d 2 partial scores, (o[1]; : : : ; o[d]). For any scoring function f and dataset D, a top-k query on D using f returns a set of k objects with the highest scores according to f (ties arbitrarily broken). Given objects o and o0, if o[i] o0[i] holds for all i = 1; : : : ; d, at least once strictly, then o dominates o0, written o o0. Notice that o o0 implies f (o) f (o0) 8f 2 M (M being the set of all monotone scoring functions). The skyline of D is the set of undominated objects in D:
Sky(D) = fo 2 D j @o0 2 D: o0 og;
but can also be viewed as the set of objects that can be top-1 [8], i.e.:
(
The k-skyband of D, written Skyk(D), is the set of all objects in D that are dominated by less than k objects [9], and thus includes all possible top-k sets.
As a generalization of dominance for a family F of monotone scoring functions ([2]), we say that object o F -dominates object o0, o 6= o0, denoted by o F o0, i 8f 2 F : f (o) f (o0) and 9f 2 F : f (o) > f (o0).
We de ne the non-dominated restricted skyband of D wrt F , denoted ndk(D; F ), as the set of objects in D that are F -dominated by less than k objects: F o ^ : : : ^ ok
F og
(
Clearly, ndk(D; F ) Skyk(D). When F reduces to a single function f , then
ndk(D; ff g) includes all possible top-k results for f (whereas, in case of ties,
top-k queries may nondeterministically discard tuples). From (
Fagin's algorithm FA was the rst to address multi-source top-k queries for arbitrary scoring functions. It consists of three phases: 1) sorted accesses are executed; 2) random accesses are executed on all objects met in phase 1; 3) scores of all fetched objects are computed using a scoring function f and the top-k result determined. The stopping condition for phase 1 is to have seen at least k objects on all the d rankings. With the scenario depicted in Figure 1, FA would stop at depth 7 (after 7 sorted accesses per ranking), after seeing a and f on all rankings. The FA algorithm can be adapted to compute Skyk(D), since it stops phase 1 independently of f . Therefore, the set S of objects seen when the algorithm stops includes the top-k objects according to any possible monotonic scoring function (and, thus, Skyk(D), which, in turn, includes ndk(D; F )).
The TA algorithm uses a threshold value f ( ) computed by applying the speci c scoring function f to the tuple of last scores seen by sorted access on each ranking, which we here call the threshold point. A further di erence with respect to FA is that random accesses are not delayed to a separate phase: after performing d sorted accesses (one per ranking), all the necessary random accesses are executed. The algorithm stops when at least k seen objects have a global score no worse than f ( ). Thus, for each object o in the result, f (o) f ( ) holds. In Figure 1, with k = 2 and weights W2 = (0:2; 0:3; 0:5) TA would stop at depth 4, where f ( ) = 7:3, since f (i) = 7:5 and f (c) = 7:4.
Being tailored to a speci c f , the stopping criterion of TA is (much) more e cient than the one used by FA, but now, when TA stops, S is only guaranteed to contain the top-k objects according to f , but not necessarily according to other scoring functions.
Let us say that o weakly F -dominates o0, o 6= o0 i 8f 2 F : f (o) f (o0). Then, we can unify FA and TA according to the following observation. Observation 1 FA stops executing sorted accesses when k seen objects o1; : : : ; ok weakly M-dominate . TA stops when k seen objects weakly ff g-dominate .
Our proposal, FSA, applies the notion of F -dominance wrt , which includes (M-)dominance and ff g-dominance as special cases. The extraction performed by FSA stops as soon as k objects are seen that F -dominate , as all unseen objects are also necessarily F -dominated by these k objects. Notice that FSA uses F -dominance rather than weak F -dominance for not discarding ties from ndk(D; F ). The pseudocode of FSA is presented in Figure 1.
Note that the descent performed by FSA alternates a single sorted access on the i-th ranking with d 1 random accesses on the other rankings. This di ers from the strategy adopted by TA, which, at each depth, rst performs d sorted accesses (one per ranking), thereby retrieving up to d unseen objects, and then completes the scores for these objects with up to d (d 1) random accesses. However, both algorithms stop at the same depth. Also note that FA performs all random accesses at the end; however, such an approach would not be possible for TA or FSA, since ff g-dominance and F -dominance generally require knowing all the scores of the objects being compared.
Algorithm 1: FSA algorithmic pattern for computing ndk.
Input: Rankings R1; : : : ; Rd for D, family of scoring functions F, integer k > 0.
Output: ndk(D; F). 1. let S := ; // Seen objects 2. do 3. for i in 1 : : : d 4. let ho; i := sortedAccess(Ri) // Do a sorted access in each ranking Ri 5. [i] := // Update score for threshold 6. if o 2= S then // Object o is new 7. o[i] := // Save score for o 8. for j in 1 : : : d // Extract all other scores for o via random access 9. if j 6= i then o[j] := randomAccess(Rj; o) 10. if @o1; : : : ; ok 2 S: o1 F o ^ : : : ^ ok F o then handle(o) 11. while @o1; : : : ; ok 2 S: o1 F ^ : : : ^ ok F // Stop if k objects F 12. clean() // Remove from S all objects F-dominated by k others 13. return S
Let I = hD; F ; ki indicate an instance of the problem of computing ndk(D; F ) wrt a set of monotone scoring functions F and let I indicate the class of all such problems. An algorithm A is correct (for the computation of ndk) if, for each instance I = hD; F ; ki 2 I, A returns ndk(D; F ).
Performance in top-k contexts is commonly characterized by the number of objects accessed by sorted access by an algorithm A on an instance I, which we indicate as sumDepths(A; I). Algorithm A is instance optimal if there exist constants c1 and c2 such that sumDepths(A; I) c1 sumDepths(A0; I) + c2 for every correct algorithm A0 and instance I 2 I.
4
We now discuss e cient implementations of FSA and focus on the case in which each scoring function is of the form f (o) = Pid=1 wigi(o[i]), where the wi's are weights subject to a set C of linear constraints and the gi's are monotone. This form includes, e.g., weighted linear sums and weighted Lp norms. The constraints may be of several kinds (see [5] for an overview), such as 1. weak rankings : w1 w2 : : : wd (relative importance of attributes); 2. ratio bounds : wi(1 ") wi wi(1 + "), 1 i d (spread around a weight).
Without loss of generality, we consider the space of normalized weight vectors W [0; 1]d, such that, for each W = (w1; : : : ; wd) 2 W, we have Pid=1 wi = 1; W(C) denotes the subset of W of weight vectors satisfying constraints C.
F -dominance test. There are two main approaches to e ciently check F dominance [2]. One approach requires solving a linear programming problem encoding the notion of F -dominance. This may be expensive, since every F dominance test requires solving a di erent LP problem. A better approach, which we choose for FSA, is based on the F -dominance region of an object o, i.e., the set of all points that o F -dominates. Such a region needs to be computed only once for all the tests in which o is the candidate F -dominant object. Testing membership to the F -dominance region is done by i) computing the vertices of the convex polytope W(C), and ii) checking the following inequalities: d X wi(`)gi(o[i]) i=1
d
X wi(`)gi(o0[i]);
i=1
` 2 f1; : : : ; qg;
(
Memoization of the vertex scores. We call the lhs of (
Sorting. In FSA, we keep the seen objects topologically sorted wrt the F dominance relation, so that, in a sequence o1; : : : ; on, no object oi can be F dominated by an object oj if j > i. We do so by sorting according to weights in the centroid of W(C). Then, when checking whether an object o should be added to the set S of seen objects (line 10 of Algorithm 1), we only look for k objects F -dominating o among those preceding o in the topological sort.
Pruning. In FSA, object removal can occur within either handle or clean. With lazy pruning, we do not remove objects in handle and wait to do it when clean is called. With eager pruning, when an object o is inserted in S, handle also removes all objects in S that are F -dominated by o and were already F dominated by k 1 other objects; clean does nothing.
Vertex lists. We observe that is F -dominated by an object o i all vertex
scores of o are no less than the corresponding vertex scores of , and at least
one is greater. We then maintain, for each vertex W (`), a list V` of seen
objects whose vertex score is still lower than 's vertex score v`( ). An object o is
added to V` within the call to handle(o) and, in V`, the objects are kept sorted
by vertex score. Additionally, for each object o, we maintain a mask of q bits
B1(o); : : : ; Bq(o) such that B`(o) = 1 i v`(o) v`( ), plus one extra bit B>(o)
that is set to 1 i at least one inequality holds strictly. Analogously, we also
maintain a list V> of those objects o such that B>(o) = 0. In this way, when checking
which objects F -dominate , it su ces to consider, for each ` 2 f1; : : : ; qg, only
the objects in V` [ V> and only if v`( ) has changed since the last check.
Example 2. Consider again the scenario of Example 1, with k = 2 and weight
vector (0:2; 0:3; 0:5) 0:1 on each weight. The vertices of W(C) are W (
In this section we evaluate the performance of our implementations of FSA. In particular, we quantify the overhead incurred by the increased exibility of FSA when compared to the computation of plain k-skybands and top-k queries. For our experiments, we consider three kinds of data distribution (anticorrelated, uniform, and real)1 and scoring functions taken from weighted L1 norms with ratio bounds constraints applied on the weights (1=d(1 ") wi 1=d(1 + ")). We report on both e ectiveness and e ciency in di erent scenarios varying by number of rankings d, spread ", and k, with defaults 4, 20%, and 10, resp.
In order to evaluate the e ectiveness of our approach, we compare it to kskybands, which also retrieve non(-F )-dominated objects but in a way that is agnostic with respect to the set of scoring functions F . The introduction of F drastically helps to reduce the result set. Figure 2 shows this e ect for NBA. In Figure 2a, we vary the spread parameter " used in ratio bounds constraints and keep default values for all other parameters. As can be seen, the result sets returned by ndk and Skyk coincide (985 objects) only when the spread is so high 1 NBA: 190862 tuples reporting measures of basketball players' performance, available at www.quantifan.com; ANT and UNI have 100K tuples. that each weight can vary in the entire [0; 1] interval (\full"). For all other values of ", the result set of ndk is much smaller (from 71 objects when " = 50%, to only 12 for " = 1%). Note that, when " = 0% (\none"), all weights equal 1=d exactly and, thus, there is only one scoring function in F ; in that case, the cardinality of the result set is exactly k = 10. Figure 2b also reports the cardinality of the result sets, but for di erent values of k (defaults otherwise). The result set returned by Skyk is always almost two orders of magnitude larger than that of ndk, the ratio becoming larger as k increases (from 157=2 when k = 1 to 6076=191 when k = 100). Finally, Figure 2c shows this when the number of rankings d varies (defaults otherwise). As d increases, the ratio between the cardinalities of the results increases (from 89=15 when d = 2 to 27403=63 when d = 8). Similar trends can be observed for the UNI and ANT datasets (omitted in the interest of space). Overall, this shows that, thanks to F , ndk is able to keep the result set within a reasonable cardinality, even for larger or more challenging problem instances, while the cardinality of Skyk soon diverges.
⨯⨯⨯⨯⨯⨯⨯⨯◇ ◇ ◇ ◇ ◇ ◇ ◇
% %ε (% % %) % (a) Spread " varies.
◇ ◇ ⨯ ◇ ⨯⨯ ⨯⨯⨯ ⨯⨯ ◇ ◇ ◇ ◇ ◇ ◇ ◇ ⨯
⨯⨯ ⨯ ◇ ◇ ◇
◇ ◇ ⨯ ⨯ ⨯ ◇ (b) k varies. (c) Number of rankings d varies.
Fig. 2: Cardinality of results for the NBA dataset. Varying parameter: " in (a), k in (b), d in (c).
We consider two variants of the FSA pattern: VEL+ and VEE+, using lazy and, resp., eager pruning, and test them in terms of execution time.
E ect of number of rankings d. Both variants exhibit sub-second execution times in default conditions. The \vertex lists" optimization grants savings of up to one order of magnitude, especially for more complex problem instances. Indeed, for d > 4 the number q of vertices increases dramatically, from q = 6 with d = 4 to q = 70 with d = 8. Yet, our optimization allows skipping many (already veri ed) vertex score comparisons between objects and the threshold point, thus leading to a linear behavior as d varies.
E ect of k and spread ". Figure 3 shows execution times as k and " vary in all datasets. Clearly, in all scenarios, the problem becomes more challenging as k increases and as " increases, since, in both cases, more objects need to be extracted and compared. VEL+ and VEE+ show similar performance, with VEE+ slightly prevailing on more challenging instances (e.g., when k = 100 or " =\full"). In such cases, many objects are kept by a lazy strategy and thus the call to the clean procedure weighs more heavily than the eager pruning of objects. In the other cases, the extra cost of pruning objects early is balanced with () )( ◇△ ◇△ ◇△ ◇△ ◇△ )( )( (a) UNI: k varies.
(b) ANT: k varies.
(c) NBA: k varies.
◇△ ◇△% ◇△%ε ◇(△% ◇△% ◇△%)◇△% ◇△ ◇△% ◇△%ε ◇△(% ◇△% ◇△%) ◇△% ◇△ ◇△% ◇△%ε ◇△(% ◇△% ◇△%) ◇△% (d) UNI: spread " varies. (e) ANT: spread " varies. (f) NBA: spread " varies. Fig. 3: CPU times for computing ndk. Datasets: UNI in (a),(d); ANT in (b),(e); NBA in (c),(f). ◇△ ◇△ ◇△ ◇△ ◇△ ◇△ ◇△ ◇△ ◇△ ◇△ the reduced cost of calling clean. We also observe that, in most scenarios, VEE+ and VEL+ incur sub-second execution times, and only exceed 2s when " =\full" (a case in which the result coincides with the k-skyband) in the ANT dataset. We have presented a framework for multi-source top-k queries de ned by scoring functions with partially speci ed weights. This provides the exibility required in many application scenarios (e.g., online services, crowdsourcing, etc.). Our solution, FSA, is a provably instance optimal algorithmic pattern that encompasses both top-k queries (attaining comparable performance) and k-skyband queries.