Antoine Amarilli

Yael Amsterdamer

Tova Milo

Pierre Senellart

Top-k Querying of Unknown Values under Order Constraints

Keywords: 1998 ACM Subject Classification H.2 DATABASE MANAGEMENT Keywords and phrases uncertainty, partial order, unknown values, crowdsourcing, interpolation Digital Object Identifier 10.4230/LIPIcs

published or not. The documents may come

Introduction

Many data analysis tasks involve queries over ordered data, such as maximum and top-k queries, which must often be evaluated in presence of unknown data values. This problem occurs in many real-life scenarios: retrieving or computing exact data values is often expensive, but querying the partially unknown data may still be useful to obtain approximate results, or to decide which data values should be retrieved next. In such contexts, we can often make use of order constraints relating the data values, even when they are unknown: for instance, we know that object A is preferred to object B (though we do not know their exact rating).

This paper thus studies the following general problem. We consider a set of numerical values, some of which are unknown, and we assume a partial order on these values: we may know that x y should hold although the values x or y are unknown. Our goal is to estimate the unknown values, in a principled way, and to evaluate top-k queries, namely find the items with (estimated) highest values.

Without further information, one may assume that every valuation compatible with the order constraints is equally likely, i.e., build a probabilistic model where valuations are Our third main contribution, in Section 5, is the study of tractable cases, following the hardness of the general problem and the high complexity of approximation. We devise a PTIME algorithm to compute expected values and top-k results when the order constraints are tree-shaped or decomposable to trees. This class of constraints is commonly encountered in the context of unknown values (e.g., taxonomies of products are often trees rather than DAGs); yet, to our knowledge, the corresponding polytopes have no equivalents in the context of computational geometry.

Our results also include a review of existing definitions for top-k over uncertain data, which motivates our particular choice of definition (in Section 6). We survey related work in more depth in Section 7 and conclude in Section 8. Full proofs of our results can be found in [START_REF] Amarilli | Top-k querying of unknown values under order constraints (extended version)[END_REF], an extended version of this paper.

Preliminaries and Problem Statement

This section introduces the formal definitions for the problem that we study in this paper.

We model known and unknown item values as variables, and order constraints as equalities and inequalities over them. Then we define the possible valuations for the variables via possible-world semantics, and use this semantics to define a uniform distribution where all worlds are equally likely. The problem of top-k querying over unknown values can then be formally defined with respect to the expected values of variables in the resulting distribution.

Unknown Data Values under Constraints

Our input includes a set X = {x 1 , . . . , x n } of variables with unknown values v(x 1 ), . . . , v(x n ), which we assume3 to be in the range [0, 1]. We consider two kinds of constraints over them: order constraints, written x i x j for x i , x j ∈ X , encoding that v(x i ) v(x j ); exact-value constraints to represent variables with known values, written4 x i = α for 0 α 1 and for

x i ∈ X , encoding that v(x i ) = α.
In what follows, a constraint set with constraints of both types is typically denoted C. We assume that constraints in C are not contradictory (e.g., we forbid x = 0.1, y = 0.2, y z, and z

x), and that they are closed under implication: e.g., if x = α, y = β are given, and α β, then x y is implied and thus should also be in C. We can check in PTIME that C is non-contradictory by simply verifying that it does not entail a false inequality on exact values (e.g., 0.2 0.1 as in our previous example). The closure of C can be found in PTIME as a transitive closure computation [START_REF] Ioannidis | Efficient transitive closure algorithms[END_REF] that also considers exact-value constraints. We denote by X exact the subset of X formed of variables with exact-value constraints.

Example 1. In the product classification example from the Introduction, a variable x i ∈ X would represent the compatibility score of the product to the i-th category. If the score is known, we would encode it as a constraint x i = α. In addition, C would contain the order constraint x i x j whenever category i is a sub-category of j (recall that the score of a sub-category cannot be higher than that of an ancestor category).

Possible World Semantics

The unknown data captured by X and C makes infinitely many valuations of X possible (including the true one). We model these options via possible world semantics: a possible world w for a constraint set C over X = {x 1 , . . . , x n } is a vector of values w = (v 1 , . . . , v n ) ∈ [0, 1] n , corresponding to setting v(x i ) := v i for all i, such that all the constraints of C hold under this valuation. The set of all possible worlds is denoted by pw X (C), or by pw(C) when X is clear from context.

Notice that C can be encoded as a set of linear constraints, i.e., a set of inequalities between linear expressions on X and constants in [0, 1]. Thus, following common practice in linear programming, the feasible region of a set of linear constraints (pw(C) in our setting) can be characterized geometrically as a convex polytope, termed the admissible polytope: writing n := |X |, each linear constraint defines a feasible half-space of R n (e.g., the half-space where x y), and the convex polytope pw(C) is the intersection of all half-spaces. In our setting the polytope pw(C) is bounded within [0, 1] n , and it is non-empty by our assumption that C is not contradictory. With exact-value constraints, or order constraints such as x i x j and x j x i , it may be the case that the dimension of this admissible polytope is less than |X |. Computing this dimension can easily be done in PTIME (see, e.g., [START_REF] Schrijver | The structure of polyhedra[END_REF]).

Example 2. Let X = {x, y, z}. If C = {x y}, the admissible polytope has dimension 3 and is bounded by the planes defined by x = y, x = 0, y = 1, z = 0 and z = 1. If we add to C the constraint y = 0.3, the admissible polytope is a 2-dimensional rectangle bounded by 0 x 0.3 and 0 z 1 on the y = 0.3 plane. We cannot add, for example, the constraint x = 0.5, because C would become contradictory.

Probability Distribution

Having characterized the possible worlds of pw(C), we assume a uniform probability distribution over pw(C), as indicated in the Introduction. This captures the case when all possible worlds are equally likely, and is a natural choice when we have no information about which valuations are more probable.

Since the space of possible worlds is continuous, we formally define this distribution via a probability density function (pdf), as follows. Let X and C define a d-dimensional polytope pw X (C) for some integer d. The d-volume (also called the Lebesgue measure [START_REF] Jones | Lebesgue Integration on Euclidean Space[END_REF] on R d ) is a measure for continuous subsets of d-dimensional space, which coincides with length, area, and volume for dimensions 1, 2, and 3, respectively. We denote by V d (C) the d-volume of the admissible polytope, or simply V (C) when d is the dimension of pw(C). Definition 3. The uniform pdf p maps each possible world w ∈ pw(C) to the constant p(w) := 1 /V (C).

Top-k Queries

We are now ready to formally define the main problem studied in this paper, namely, the evaluation of top-k queries over unknown data values. The queries that we consider retrieve the k items that are estimated to have the highest values, along with their estimated values, with ties broken arbitrarily. We further allow queries to apply a selection operator σ on the items before performing the top-k computation. In our example from the Introduction, this is what allows us to select the top-k categories among only the end categories. We denote the subset of X selected by σ as X σ .

If all item values are known, the semantics of top-k queries is clear. In presence of unknown values, however, the semantics must be redefined to determine how the top-k items and their values are estimated. In this paper, we estimate unknown items by their expected value over all possible worlds, i.e., their expected value according to the uniform pdf p defined above on pw(C). This corresponds to interpolating the unknown values from the known ones, and then querying the result. We use these interpolated values to define the top-k problem as computing the k variables with the highest expected values, but we also study on its own the interpolation problem of computing the expected values.

To summarize, the two formal problems that we study on constraint sets are:

Interpolation. Given a constraint set C over X and variable x ∈ X , the interpolation problem for x is to compute the expected value of x in the uniform distribution over pw X (C). Top-k. Given a constraint set C over X , a selection predicate σ, and an integer k, the top-k computation problem is to compute the ordered list of the k maximal expected values of variables in X σ (or less if |X σ | k), with ties broken arbitrarily.

We review other definitions of top-k on uncertain data in Section 6, where we justify our choice of semantics.

Alternate phrasing.

The Interpolation problem can also be defined geometrically, as the computation of the centroid (or center of mass) of the admissible polytope: the point G such that all vectors relative to G originating at points within the polytope sum to zero. The constraints that we study correspond to a special kind of polytopes, for which we will design a specific algorithm in the next section, and derive an FP #P membership bound which does not hold for general polytopes (as explained in the Introduction). However, the geometric connection will become useful when we study the complexity of our problem in Section 4.1.

An Algorithm for Interpolation and Top-k

Having defined formally the problems that we study, we begin our complexity analysis by designing an algorithm that computes the expected value of variables.

The algorithm enumerates all possible orderings of the variables (to be defined formally below), but it is still nontrivial: we must handle exact-value constraints specifically, and we must compute the probability of each ordering to determine its weight in the overall expected value computation. From the algorithm, we will deduce that our interpolation and top-k problems are in FP #P .

Eliminating ties. To simplify our study, we will eliminate from the start the problem of ties, which will allow us to assume that values in all worlds are totally ordered. We say that a possible world w = (v 1 , . . . , v n ) of C has a tie if v i = v j for some i, j. Note that occasional ties, not enforced by C, have an overall probability of 0: intuitively, if the admissible polytope is d-dimensional, then all the worlds where v i = v j correspond to a (d -1)-dimensional hyperplane bounding or intersecting the polytope. A finite set of such hyperplanes (for every pair of variables) has total d-volume 0. Since our computations (volume, expected value) involve integrating over possible worlds, a set of worlds with total probability 0 does not affect the result.

What is left is to consider ties enforced by C (and thus having probability 1). In such situations, we can rewrite C by merging these variables to obtain an equivalent constraint set where ties have probability 0. Formally:

XX:7 Lemma 4. For any constraint set C, we can construct in PTIME a constraint set C such that the probability that the possible worlds of C have a tie (under the uniform distribution) is zero, and such that any interpolation or top-k computation problem on C can be reduced in PTIME to the same type of problem on C .

Hence, we assume from now on that ties have zero probability in C, so that we can ignore possible worlds with ties without affecting the correctness of our analysis. Note that this implies that all of our results also hold for strict inequality constraints, of the forms x < y and x = y.

Under this assumption, we first study in Section 3.1 the case where C is a total order. We then handle arbitrary C by aggregating over possible variable orderings, in Section 3.2.

Total Orders

In this section we assume C is a total order C n 1 (α, β) defined as

x 0 x 1 • • • x n x n+1
, where x 0 = α and x n+1 = β are variables with exact-value constraints in X exact .

We first consider unfragmented total orders, where x 1 , . . . , x n ∈ X exact . In this case, we can show that the expected value of x i , for 1 i n, corresponds to a linear interpolation of the unknown variables between α and β, namely: i n+1 • (β -α) + α. This can be shown formally via a connection to the expected value of the order statistics of samples from a uniform distribution, which follows a Beta distribution [START_REF] Gentle | Computational Statistics[END_REF]. Now consider the case of fragmented total orders, where C is allowed to contain more exact-value constraints than the ones on α and β. We observe that we can split the total order into fragments: by cutting at each variable that has an exact-value constraint, we obtain sub-sequences of variables which follow an unfragmented total order. We can then compute the expected values of each fragment independently, and compute the total order volume as the product of the fragment volumes. The correctness of this computation follows from a more general result (Lemma 12) stated and proven in Section 5.

Hence, given a constraint set C imposing a (possibly fragmented) total order, the expected value of x i can be computed as follows. If x i ∈ X exact , analysis is trivial. Otherwise, we consider the fragment C q-1 p+1 (v p , v q ) that contains x i ; namely, p is the maximal index such that 0 p < i and x p ∈ X exact , and q is the minimal index such that i < q n + 1 and x q ∈ X exact . The expected value of x i can then be computed within C q-1 p+1 (v p , v q ) using linear interpolation.

The following proposition summarizes our findings:

Proposition 5. Given a constraint set C implying a total order, the expected value of any variable x i ∈ X can be computed in PTIME.

General Constraint Sets

We can now extend the result for total orders to an expression of the expected value for a general constraint set C. We apply the previous process to each possible total ordering of the variables, and aggregate the results. To do this, we define the notion of linear extensions, inspired by partial order theory: Definition 6. Given a constraint set C over X , we say that a constraint set T is a linear extension of C if (i) T is a total order; (ii) the exact-value constraints of T are exactly those

E C [x] ← 0; V (C) ← 0; 3 m ← |X exact |; 4 Write x 0 < • • • < x m-1 the variables of X exact and v 0 < • • • < v m-1 their values; 5 foreach linear extension T of C do 6 Write i 0 < • • • < i m-1 the indices in T of variables x 0 , . . . , x m-1 in X exact ; 7 Write k the index in T of the variable x; 8 Write i j , i j+1 the indices of variables from X exact s.t. i j < k < i j+1 ; 9 E T [x] ← ExpectedValFrag(i j , i j+1 , k, v j , v ) ; // Expected value of x in T 10 V (T ) ← m-2 l=0 VolumeFrag(i l , i l+1 , v l , v l+1 ) ; // Volume of T 11 E C [x] ← E C [x] + V (T ) × E T [x]; // Sum exp. value of x weighted by V (T ) 12 V (C) ← V (C) + V (T );
// Sum of total order volumes

13 return E C [x] V (C) ; 14 Function ExpectedValFrag(p, q, k, α, β)
Input: p < q: indices; k: requested variable index; α < β: exact values at p, q resp. Output: Expected value of variable x k in the fragment C q-1 p+1 (α, β)

15 n ← q -p -1 ; // num. of variables in the fragment which are ∈ X exact

16 return k-p n+1 • (β -α) + α ; // linear interpolation (see Section 3.1)
17 Function VolumeFrag(p, q, α, β) Input: p < q: indices; α < β: exact values at p, q resp. Output: V (C q-1 p+1 (α, β)): volume of the total order fragment between indices p, q 18 n ← q -p -1 ; // num. of variables in the fragment which are ∈ X exact Algorithm 1 presents our general scheme to compute the expected value of a variable x ∈ X under an arbitrary constraint set C, assuming the uniform distribution on pw(C).

The algorithm iterates over each linear extension T of C, and computes the expected value of x in T and the overall probability of T in pw(C). A linear extension is a total order, so x is within a particular fragment of it, namely, between the indices of two consecutive variables with exact-value constraints, i j and i j+1 . The expected value of x in T , denoted by

E T [x]
, is then affected only by the constraints and variables of this fragment, and can be computed using linear interpolation by the function ExpectedValFrag (line 9). Now, the final expected value of x in C is the average of all E T [x] weighted by the probability of each linear extension T , i.e., the volume of pw(T ) divided by the volume of pw(C). Recall that, by Lemma 4, worlds with ties have total volume 0 and do not affect this expected value. We compute the volume of T as the product of volumes of its fragments (line 10). The volume of a fragment, computed by function VolumeFrag, is the volume of Theorem 8. ([42], Theorem 1). Given a set C of order constraints and x ∈ X , determining the expected value of x in pw(C) under the uniform distribution is FP #P -hard.

We now show a new lower bound for top-k queries: interestingly, these queries are FP #P -hard even if they do not have to return the expected values. Recall that σ is the selection operator (see Section 2.4), which we use to compute top-k among a restricted subset of variables. We can show hardness even for top-1 queries, and even when σ only selects two variables: Theorem 9. Given a constraint set C over X , a selection predicate σ, and an integer k, the top-k computation problem over X , C and σ is FP #P -hard even if k is fixed to be 1,

|X σ | is 2,

and the top-k answer does not include the expected value of the variables.

Proof sketch. To prove hardness in this case, we reduce from interpolation. We show that a top-1 computation oracle can be used as a comparison oracle to compare the expected value of a variable x to any other rational value α, by adding a fresh element x with an exact-value constraint to α and using σ to compute the top-1 among {x, x }. What is more technical is to show that, given such a comparison oracle, we can perform the reduction and determine exactly the expected value v of x (a rational number) using only a polynomial number of comparisons to other rationals. This follows from a bound on the denominator of v, and by applying the rational number identification scheme of [START_REF] Papadimitriou | Efficient search for rationals[END_REF].

In settings where we do not have a selection operator (i.e., X σ = X ), we can similarly show the hardness of top-k (rather than top-1). See [START_REF] Amarilli | Top-k querying of unknown values under order constraints (extended version)[END_REF] for details.

Complexity of Approximate Computation

In light of the previous hardness results, we now review approximation algorithms, again via the geometric characterization of our setting. In Section 5, we will show a novel exact solution in PTIME for specific cases.

The interpolation problem can be shown to admit a fully polynomial-time randomized approximation scheme (FPRAS). This result follows from existing work [START_REF] Bertsimas | Solving convex programs by random walks[END_REF][START_REF] Kannan | Random walks and an O * (n 5 ) volume algorithm for convex bodies[END_REF], using a tractable almost uniform sampling scheme for convex bodies.

Proposition 10. ([31], Algorithm 5.8). Let C be a set of constraints with variable set X and x ∈ X . There is an FPRAS that determines an estimate ÊC [x] of the expected value E C [x] of x in pw(C) under the uniform distribution.

This result is mostly of theoretical interest, as the polynomial is in |X | 7 (see [START_REF] Bertsimas | Solving convex programs by random walks[END_REF], Table 1), but recent improved sampling algorithms [START_REF] Lovász | Hit-and-run from a corner[END_REF] may ultimately yield a practical approximate interpolation technique for general constraint sets (see [START_REF] Ge | A fast and practical method to estimate volumes of convex polytopes[END_REF][START_REF] Lovász | Computational results of an O * (n 4 ) volume algorithm[END_REF]).

For completeness, we mention two natural ways to define randomized approximations for top-k computation:

We can define the approximate top-k as an ordered list of k items whose expected value does not differ by more than some > 0 from that of the item in the actual top-k at the same rank. An FPRAS for this definition of approximate top-k can be obtained from that of Proposition 10. It is highly unlikely that there exists a PTIME algorithm to return the actual top-k with high probability, even without requiring it to return the expected values. Indeed, such an algorithm would be in the BPP (bounded-error probabilistic time) complexity class; yet it follows from Theorem 9 above that deciding whether a set of variables is the top-k is NP-hard, so the existence of the algorithm would entail that NP ⊆ BPP.

Tractable Cases

Given the hardness results in the previous section and the impracticality of approximation, we now study whether exact interpolation and top-k computation can be tractable on restricted classes of constraint sets. We consider tree-shaped constraints (defined formally below) and generalizations thereof: they are relevant for practical applications (e.g., classifying items into tree-or forest-shaped taxonomies), and we will show that our problems are tractable on them. We start by a splitting lemma to decompose constraint sets into "independent" subsets of variables, and then define and study our tractable class.

Splitting Lemma

We will formalize the cases in which the valuations of two variables in X are probabilistically dependent (the variables influence each other), according to C. This, in turn, will enable us to define independent subsets of the variables and thus independent subsets of the constraints over these variables. This abstract result will generalize the notion of fragments from total orders (see Section 3.1) to general constraint sets. In what follows, we use x i ≺ x j to denote the covering relation of the partial order , i.e., x i x j is in C but there exists no

x k / ∈ {x i , x j } such that x i x k and x k x j are in C.
Definition 11. We define the influence relation x ↔ y between variables of X \X exact as the equivalence relation obtained by the symmetric, reflexive, and transitive closure of the ≺ relation on X \X exact .

The uninfluenced classes of X under C is the partition of X \X exact as the subsets X 1 , . . . , X m given by the equivalence classes of the influence relation.

The uninfluence decomposition of C is the collection of constraint sets C 1 , . . . , C m of C where each C i has as variables X i X exact and contains all exact-value constraints of C and all order constraints between variables of X i X exact . We assume w.l.o.g. that m > 0, i.e., there are unknown variables in X \X exact ; otherwise the uninfluence decomposition is meaningless but any analysis is trivial. Intuitively, two unknown variables x, x are in different uninfluenced classes if in every linear extension there is some variable from X exact between them, or if they belong to disconnected (and thus incomparable) parts of the partial order. In particular, uninfluenced classes correspond to the fragments of a total order: this is used in Section 3.1. The uninfluence decomposition captures only constraints between variables that influence each other, and constraints that can bound the range of a variable by making it comparable to variables from X exact . We formally prove the independence of C 1 , . . . , C m via possible-world semantics: every possible world of C can be decomposed to possible worlds of C 1 , . . . , C m , and vice versa. Example 13. Let X be {x, y, y , z, w}, and let C be defined by y = 0.5 and x y y z. The uninfluence classes are X 1 = {x, y}, X 2 = {z}, and X 3 = {w}. The uninfluence decomposition thus consists of C 1 , with variables X 1 {y }, and constraints x y y and y = 0.5; C 2 , with variables X 2 {y }, and constraints y z and y = 0.5; and C 3 , with variables X 3 {y }, and constraint y = 0.5.

We next use this independence property to analyse restricted classes of constraint sets.

On large tree-shaped taxonomies (e.g., the Google Product Taxonomy [START_REF]Google Product Taxonomy[END_REF]), in an interactive setting where we may ask user queries (e.g., the one in the Introduction), we can improve running times by asking more queries. Indeed, each answer about a category adds an exact-value constraint, and reduces the size of the constraint sets of the uninfluence decomposition, which decreases the overall running time, thanks to the superadditivity of x → x 3 . We do not study which variables should be queried in order to reduce the running time of the algorithm; see, e.g., [START_REF] Parameswaran | Humanassisted graph search: it's okay to ask questions[END_REF] for tree-partitioning algorithms.

Other Variants

We have defined top-k computation on constraint sets by considering the expected value of each variable under the uniform distribution. Comparing to different definitions of top-k on unknown values that have been studied in previous work, our definition has some important properties [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF]: it provides a ready estimation for unknown values (namely, their expected value) and guarantees an output of size k. Moreover, it satisfies the containment property of [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF], defined in our setting as follows:

Definition 18. A top-k definition satisfies the containment property if for any constraint set C on variables X , for any predicate σ (where we write X σ the selected variables), and for any k < |X σ |, letting S k and S k+1 be the ordered lists of top-k and top-(k + 1) variables, S k is a strict prefix of S k+1 .

The containment property is a natural desideratum: computing the top-k for some k ∈ N should not give different variables or order for the top-k with k < k. Our definition clearly satisfies the containment property (except in the case of ties). By contrast, we will now review prominent definitions of top-k on uncertain data from related work [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF][START_REF] Soliman | Top-k query processing in uncertain databases[END_REF][START_REF] Zhang | Semantics and evaluation of top-k queries in probabilistic databases[END_REF], and show that they do not satisfy the containment property when we apply them to the possible world distributions studied in our setting. We focus on two prominent definitions, U-top-k and global-top-k and call our own definition local-top-k when comparing to them; we also discuss other variants in [START_REF] Amarilli | Top-k querying of unknown values under order constraints (extended version)[END_REF].

U-top-k. The U-top-k variant does not study individual variables but defines the output as the sequence of k variables most likely to be the top-k (in that order), for the uniform distribution on pw(C). We call this alternative definition U-top-k by analogy with [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF][START_REF] Soliman | Top-k query processing in uncertain databases[END_REF]. Interestingly, the U-top-k and local-top-k definitions sometimes disagree in our setting: Lemma 19. There is a constraint set C and selection predicate σ such that local-top-k and U-top-k do not match, even for k = 1 and without returning expected values or probabilities.

We can easily design an algorithm to compute U-top-k in PSPACE and in polynomial time in the number of linear extensions of C: compute the probability of each linear extension as in Algorithm 1, and then sum on linear extensions depending on which top-k sequence they realize (on the variables selected by σ), to obtain the probability of each answer. Hence: Proposition 20. For any constraint set C over X , integer k and selection predicate σ, the U-top-k query for C and σ can be computed in PSPACE and in time O(poly(N )), where N is the number of linear extensions of C. Unlike Theorem 7, however, this does not imply FP #P -membership: when selecting the most probable sequence, the number of candidate sequences may not be polynomial (as k is not fixed). We leave to future work an investigation of the precise complexity of U-top-k.

We show that in our setting U-top-k does not satisfy the containment property of [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF]. [START_REF] Davidson | Using the crowd for top-k and group-by queries[END_REF][START_REF] Faigle | Searching in trees, seriesparallel and interval orders[END_REF][START_REF] Gunopulos | Discovering all most specific sentences[END_REF][START_REF] Parameswaran | Humanassisted graph search: it's okay to ask questions[END_REF]. This relates to many applications, e.g., crowd-assisted graph search [START_REF] Parameswaran | Humanassisted graph search: it's okay to ask questions[END_REF], frequent itemset mining with the crowd [START_REF] Amarilli | On the complexity of mining itemsets from the crowd using taxonomies[END_REF], and knowledge discovery, where the unknown data is queried via oracle calls [START_REF] Gunopulos | Discovering all most specific sentences[END_REF]. These studies are complementary to ours: when the target function can be phrased as a top-k or interpolation problem, if the search is stopped before all values are known, we can use our method to estimate the complete output.

Computational geometry. Our work reformulates the interpolation problem as a centroid computation problem in the polytope of possible worlds defined by the constraint set. This problem has been studied independently by computational geometry work [START_REF] Kannan | Random walks and an O * (n 5 ) volume algorithm for convex bodies[END_REF][START_REF] Maire | An algorithm for the exact computation of the centroid of higher dimensional polyhedra and its application to kernel machines[END_REF][START_REF] Luis | Approximating the centroid is hard[END_REF].

Computational geometry mostly studies arbitrary convex polytopes (corresponding to polytopes defined by arbitrary linear constraint sets), and often considers the task of volume computation, which is related to the problem of computing the centroid [START_REF] Luis | Approximating the centroid is hard[END_REF]. In this context, it is known that computing the exact volume of a polytope is not in FP #P because the output is generally not of polynomial size [START_REF] Lawrence | Polytope volume computation[END_REF]. Nevertheless, several (generally exponential) methods for exact volume computation [START_REF] Büeler | Exact volume computation for polytopes: a practical study[END_REF] have been developed. The problem of approximation has also been studied, both theoretically and practically [START_REF] Cousins | A practical volume algorithm[END_REF][START_REF] Loera | Software for exact integration of polynomials over polyhedra[END_REF][START_REF] Ge | A fast and practical method to estimate volumes of convex polytopes[END_REF][START_REF] Kannan | Random walks and an O * (n 5 ) volume algorithm for convex bodies[END_REF][START_REF] Lovász | Computational results of an O * (n 4 ) volume algorithm[END_REF][START_REF] Simonovits | How to compute the volume in high dimension? Mathematical programming[END_REF]. Our problem of centroid computation is studied in [START_REF] Maire | An algorithm for the exact computation of the centroid of higher dimensional polyhedra and its application to kernel machines[END_REF], whose algorithm is based on the idea of computing the volume of a polytope by computing the lower-dimensional volume of its facets. This is different from our algorithm, which divides the polytope along linear extensions into subpolytopes, for which we apply a specific volume and centroid computation method. Some works in computational geometry specifically study order polytopes, i.e., the polytopes defined by constraint sets with only order constraints and no exact-value constraints. For such polytopes, volume computation is known to be FP #P -complete [START_REF] Brightwell | Counting linear extensions[END_REF], leading to a FP #P -hardness result for centroid computation [START_REF] Luis | Approximating the centroid is hard[END_REF]. However, these results do not apply to exact-value constraints, i.e., when order polytopes can only express order relations, between variables which are in [0, 1]. Exact-value constraints are both highly relevant in practice (to represent numerical bounds, or known information, e.g., for crowdsourcing), allow for more general polytopes, and complicate the design of Algorithm 1, which must perform volume computation and interpolation in each fragmented linear order.

Furthermore, to our knowledge, computational geometry works do not study the top-k problem, or polytopes that correspond to tree-shaped constraint sets, since these have no clear geometric interpretation.

Tree-shaped partial orders. Our analysis of tractable schemes for tree-shaped partial orders is reminiscent of the well-known tractability of probabilistic inference in tree-shaped graphical models [START_REF] Bishop | Graphical models[END_REF], and of the tractability of probabilistic query evaluation on trees [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF] and treelike instances [START_REF] Amarilli | Provenance circuits for trees and treelike instances[END_REF]. However, we study continuous distributions on numerical values, and the influence between variables when we interpolate does not simply follow the tree structure; so our results do not seem to follow from these settings.

Conclusion

In this paper, we have studied the problems of top-k computation and interpolation for data with unknown values and order constraints. We have provided foundational solutions, including a general computation scheme, complexity bounds, and analysis of tractable cases. One natural direction for future work is to study whether our tractable cases (tree-shaped orders, sampling) can be covered by more efficient PTIME algorithms, or whether more general tractable cases can be identified: for instance, a natural direction to study would be partial orders with a bounded-treewidth Hasse diagram, following recent tractability results for the related problem of linear extension counting [START_REF] Kangas | Counting linear extensions of sparse posets[END_REF]. Another question is to extend our scheme to request additional values from the crowd, as in [START_REF] Amarilli | On the complexity of mining itemsets from the crowd using taxonomies[END_REF][START_REF] Ciceri | Crowdsourcing for top-k query processing over uncertain data[END_REF], and reduce the expected error on the interpolated values or top-k query, relative to a user goal. In such a setting, how should we choose which values to retrieve, and could we update incrementally the results of interpolation when we receive new exact-value constraints? Finally, it would be interesting to study whether our results generalize to different prior distributions on the polytope.

  of [α, β] n divided by num. of total orders of C; and (iii) C ⊆ T , namely every constraint x y in C also holds 5 in T .

Lemma 12 .

 12 Let C 1 , . . . , C m be the uninfluence decomposition of C. There exists a bijective correspondence between pw(C) and pw(C 1 ) × • • • × pw(C m ).

XX:8 Top-k Querying of Unknown Values under Order Constraints Algorithm 1:

  Compute the expected value of a variableInput: Constraint set C on variables X with n := |X | where ties have probability 0 and where value range [0, 1] is enforced by constraints; variable x ∈ X Output: Expected value of x 1 if x is in X exact , i.e., has an exact-value constraint in C to some v then return v; 2

#P is the class of counting problems that return the number of solutions of NP problems. FP #P is the class of function problems that can be computed in PTIME using a #P oracle.

Our results extend to other bounded, continuous ranges, because we can rescale them to fall in [0, 1].

The number α is written as a rational number, represented by its numerator and denominator.

The linear extensions of C in this sense are thus exactly the linear extensions of the partial order on X imposed by C: this partial order is indeed antisymmetric because C has no ties.

Acknowledgements

This work is partially supported by the European Research Council under the FP7, ERC grant MoDaS, agreement 291071, by a grant from the Blavatnik Interdisciplinary Cyber Research Center, by the Israel Science Foundation (grant No. 1157/16), and by the Télécom ParisTech Research Chair on Big Data and Market Insights.

XX:9

[α, β] n , i.e., all assignments to the n variables of the fragment in [α, β], divided by the number of orderings of these variables, to obtain the volume of one specific order (line [START_REF] Detwiler | Integrating and ranking uncertain scientific data[END_REF].

The complexity of Algorithm 1 is polynomial in the number of linear extensions of C, as we can enumerate them in constant amortized time [START_REF] Pruesse | Generating linear extensions fast[END_REF]. However, in the general case, there may be up to |X |! linear extensions. To obtain an upper bound in the general case, we note that we can rescale all constraints so that all numbers are integers, and then nondeterministically sum over the linear extensions. This yields our FP #P upper bound: Theorem 7. Given a constraint set C over X and x ∈ X (resp., and a selection predicate σ, and an integer k), determining the expected value of x in pw(C) under the uniform distribution (resp., the top-k computation problem over X , C, and σ) is in FP #P .

The FP #P membership for interpolation does not extend to centroid computation in general convex polytopes, which is not in FP #P [START_REF] Lawrence | Polytope volume computation[END_REF][START_REF] Luis | Approximating the centroid is hard[END_REF]. Our algorithm thus relies on the fact that the polytope pw(C) is of a specific form, defined with order and exact-value constraints. The same upper bound for the top-k problem immediately follows. We will show in Section 4 that this FP #P upper bound is tight.

We also provide a complete example to illustrate the constructions of this section.

x y = γ y z Full Example. We exemplify our scheme on variables X = {x, y, y , z} and on the constraint set C generated by the order constraints x y, y z, x y , y z and the exact-value constraint y = γ for some fixed 0 < γ < 1. Remember that we necessarily have 0 x and z 1 as well. The constraints of C are closed under implication, so they also include x z. The figure shows the Hasse diagram of the partial order defined by C on X . Note that ties have a probability of zero in pw(C).

The two linear extensions of C are T 1 : x y y z and T 2 : x y y z. Now, T 1 is a fragmented total order, and we have pw(T 1 ) = pw {x,y} (C ) × {γ} × [γ, 1] where C is defined on variables {x, y} by 0 x y γ. We can compute the volume of pw(T 1 ) as

. Let us compute the expected value of y for C. In T 1 its expected value is

The overall expected value of y is the average of these expected values weighted by total order probabilities (volumes fractions), namely E C [y] = α1µ1+α2µ2 α1+α2 .

Hardness and Approximations

We next show that the intractability of Algorithm 1 in Section 3 is probably unavoidable. We first show matching lower bounds for interpolation and top-k in Section 4.1. We then turn in Section 4.2 to the problem of approximating expected values.

Hardness of Exact Computation

We now analyze the complexity of computing an exact solution to our two main problems. We show below a new result for the hardness of top-k. But first, we state the lower bound for the interpolation problem, which is obtained via the geometric characterization of the problem. In previous work, centroid computation is proven to be hard for order polytopes, namely, polytopes without exact-value constraints, which are a particular case of our setting:

Tree-Shaped Constraints

We define the first restricted class of constraints that we consider: tree-shaped constraints.

Recall that a Hasse diagram is a representation of a partial order as a directed acyclic graph, whose nodes correspond to X and where there is an edge (x, y) if x ≺ y. An example of such a diagram is the one used in Section 3.2.

Definition 14. A constraint set C over X is tree-shaped if the probability of ties is zero, the Hasse diagram of the partial order induced on X by C is a directed tree, the root has exactly one child, and exactly the root and leaves are in X exact . Thus, C imposes a global minimal value, and maximal values at each leaf, and no other exact-value constraint.

We call C reverse-tree-shaped if the reverse of the Hasse diagram (obtained by reversing the direction of the edges) is tree-shaped.

Tree-shaped constraints are often encountered in practice, in particular in the context of product taxonomies. Indeed, while our example from Figure 1 is a DAG, many real-life taxonomies are trees: in particular, the Google Product Taxonomy [START_REF]Google Product Taxonomy[END_REF] and ACM CCS [2].

We now show that for a tree-shaped constraint set C, unlike the general case, we can tractably compute exact expressions of the expected values of variables. In the next two results, we assume arithmetic operations on rationals to have unit cost, e.g., they are performed up to a fixed numerical precision. Otherwise, the complexities remain polynomial but the degrees may be larger. We first show: Theorem 15. For any tree-shaped constraint set C over X , we can compute its volume

Proof sketch. We process the tree bottom-up, propagating a piecewise-polynomial function expressing the volume of the subpolytope on the subtree rooted at each node as a function of the value of the parent node: we compute it using Lemma 12 from the child nodes.

This result can be applied to prove the tractability of computing the marginal distribution of any variable x ∈ X \X exact in a tree-shaped constraint set, which is defined as the pdf p x (v) := V d-1 (C ∪ {x = v})/V d (C), where d is the dimension of pw(C): Theorem 16. For any tree-shaped constraint set C on variable set X , for any variable x ∈ X \X exact , the marginal distribution for x is piecewise polynomial and can be computed

Proof sketch. We proceed similarly to the proof of Theorem 15 but with two functions: one for x and its descendants, and one for all other nodes. The additional |X exact | factor is because the second function depends on how the value given to x compares to the leaves.

We last deduce that our results for tree-shaped constraints extend to a more general tractable case: constraint sets C whose uninfluence decomposition C 1 , . . . , C m is such that every C i is (reverse-)tree-shaped. By Lemma 12, each C i (and its variables) can be considered independently, and reverse-tree-shaped trees can be easily transformed into tree-shaped ones. Our previous algorithms thus apply to this general case, by executing them on each constraint set of the uninfluence decomposition that is relevant to the task (namely, containing the variable x to interpolate, or top-k candidates from the selected variables X σ ): Corollary 17. Given any constraint set C and its uninfluence decomposition C 1 , . . . , C m , assuming that each C i is a (reverse-)tree-shaped constraint set, we can solve the interpolation problem in time O(max i |X i |

3 ) and the top-k problem in PTIME.

Lemma 21. There is a constraint set C without ties such that U-top-k does not satisfy the containment property for the uniform distribution on pw(C).

Global-top-k. We now study the global-top-k definition [START_REF] Zhang | Semantics and evaluation of top-k queries in probabilistic databases[END_REF], and show that it does not respect the containment property either, even though it is defined on individual variables: Definition 22. The global-top-k query, for a constraint set C, selection predicate σ, and integer k, returns the k variables that have the highest probability in the uniform distribution on pw(C) to be among the variables with the k highest values, sorted by decreasing probability.

Lemma 23. There is a constraint set C without ties such that global-top-k does not satisfy the containment property for the uniform distribution on pw(C).

Related Work

We extend the discussion about related work from the Introduction.

Ranking queries over uncertain databases.

A vast body of work has focused on providing semantics and evaluation methods for order queries over uncertain databases, including top-k and ranking queries (e.g., [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF][START_REF] Detwiler | Integrating and ranking uncertain scientific data[END_REF][START_REF] Haghani | Evaluating top-k queries over incomplete data streams[END_REF][START_REF] Hua | Ranking queries on uncertain data[END_REF][START_REF] Jestes | Semantics of ranking queries for probabilistic data[END_REF][START_REF] Li | A unified approach to ranking in probabilistic databases[END_REF][START_REF] Re | Efficient top-k query evaluation on probabilistic data[END_REF][START_REF] Soliman | Supporting ranking queries on uncertain and incomplete data[END_REF][START_REF] Wang | On pruning for top-k ranking in uncertain databases[END_REF][START_REF] Yi | Efficient processing of top-k queries in uncertain databases[END_REF]). Such works consider two main uncertainty types: tuple-level uncertainty, where the existence of tuples (i.e., variables) is uncertain, and hence affects the query results [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF][START_REF] Detwiler | Integrating and ranking uncertain scientific data[END_REF][START_REF] Hua | Ranking queries on uncertain data[END_REF][START_REF] Jestes | Semantics of ranking queries for probabilistic data[END_REF][START_REF] Li | A unified approach to ranking in probabilistic databases[END_REF][START_REF] Re | Efficient top-k query evaluation on probabilistic data[END_REF][START_REF] Wang | On pruning for top-k ranking in uncertain databases[END_REF][START_REF] Yi | Efficient processing of top-k queries in uncertain databases[END_REF]; and attribute-level uncertainty, more relevant to our problem, where the data tuples are known but some of their values are unknown or uncertain [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF][START_REF] Haghani | Evaluating top-k queries over incomplete data streams[END_REF][START_REF] Jestes | Semantics of ranking queries for probabilistic data[END_REF][START_REF] Soliman | Supporting ranking queries on uncertain and incomplete data[END_REF]. Top-k queries over uncertain data following [START_REF] Soliman | Supporting ranking queries on uncertain and incomplete data[END_REF] was recently applied to crowdsourcing applications in [START_REF] Ciceri | Crowdsourcing for top-k query processing over uncertain data[END_REF]. These studies are relevant to our work as they identify multiple possible semantics for order queries in presence of uncertainty, and specify desired properties for such semantics [START_REF] Cormode | Semantics of ranking queries for probabilistic data and expected ranks[END_REF][START_REF] Jestes | Semantics of ranking queries for probabilistic data[END_REF]; our definition of top-k satisfies the desiderata that are relevant to attribute-level uncertainty [START_REF] Jestes | Semantics of ranking queries for probabilistic data[END_REF]. We depart from this existing work in two main respects. First, existing work assumes that each variable is given with an independent function that describes its probability distribution. We do not assume this, and instead derive expressions for the expected values of variables in a principled way from a uniform prior on the possible worlds. Our work is thus well-suited to the many situations where probability distributions on variables are not known, or where they are not independent (e.g., when order constraints are imposed on them). For this reason, the problems that we consider are generally computationally harder. For instance, [START_REF] Soliman | Supporting ranking queries on uncertain and incomplete data[END_REF] is perhaps the closest to our work, since they consider the total orders compatible with given partial order constraints. However, they assume independent marginal distributions, so they can evaluate top-k queries by only considering k-sized prefixes of the linear extensions; in our setting even computing the top-1 element is hard (Theorem 9).

The second key difference is that other works do not try to estimate the top-k values, because they assume that the marginal distribution is given: they only focus on ranks. In our context, we need to compute missing values, and need to account, e.g., for exact-value constraints and their effect on the probability of possible worlds and on expected values (Section 3).

We also mention our previous work [START_REF] Amarilli | Uncertainty in crowd data sourcing under structural constraints[END_REF] which considers the estimation of uncertain values (expectation and variance), but only in a total order, and did not consider complexity issues. Partial order search. Another relevant research topic, partial order search, considers queries over elements in a partially ordered set to find a subset of elements with a certain property [3,