Query Minimization under Stochastic Uncertainty

We study problems with stochastic uncertainty information on intervals for which the precise value can be queried by paying a cost. The goal is to devise an adaptive decision tree to find a correct solution to the problem in consideration while minimizing the expected total query cost. We show that, for the sorting problem, such a decision tree can be found in polynomial time. For the problem of finding the data item with minimum value, we have some evidence for hardness. This contradicts intuition, since the minimum problem is easier both in the online setting with adversarial inputs and in the offline verification setting. However, the stochastic assumption can be leveraged to beat both deterministic and randomized approximation lower bounds for the online setting.

The literature describes two kinds of algorithms for this setting. Though the nomenclature varies, we adopt the following one. An adaptive algorithm may decide which queries to perform based on results from previous queries. An oblivious algorithm, however, must choose the whole set of queries to perform in advance; i.e., it must choose a set of queries that certainly allow the problem to be solved without any knowledge of the actual values. 1 Two main approaches have been proposed to analyze both types of algorithms. In the first, an oblivious (adaptive) algorithm is compared to a hypothetical optimal oblivious (adaptive) strategy; this is the approach in [21,33,39,40]. However, for more complex problems, and in particular for adaptive algorithms, it usually becomes more difficult to understand the optimal strategy. A second (more robust) approach is competitive analysis, which is a standardized metric for online optimization [10]. In this setting, both oblivious and adaptive algorithms are compared to an optimum query set, which we define next. For a given realization of the actual values, a set of queries is a feasible query set if, after querying all intervals in that set, one can find a solution of the underlying problem; an optimal query set is a feasible query set of minimum cost. An algorithm (either adaptive or oblivious) is α-query-competitive if its total query cost is at most α times the cost of an optimum query set. This type of analysis is performed in [6,12,19,20,30,31,33,38,45]. For NP-hard problems, since we do not expect to find the "correct" solution in polynomial time, there are two approaches in the literature: either we have an objective function which combines query and solution costs (this is how the scheduling problem is addressed in [16]), or we have a fixed query budget and the objective function is based only on the solution cost (as for the knapsack problem in [25]). Another related problem is that of, given a realization of the precise values, how to compute an optimum query set. This is often called the verification [6,14,17] or offline [31] version of the problem. This may be interesting both for performing experimental evaluation of the algorithms, as for obtaining insight for solving the corresponding oblivious/adaptive problems (as we discuss in Section 3).
Competitive analysis is, however, rather pessimistic. In particular, many problems such as minimum, sorting and spanning tree have a deterministic lower bound of 2 and a randomized lower bound of 1.5 for adaptive algorithms, and a simple 2-competitive deterministic adaptive algorithm, even if queries are allowed to return intervals [20,30,31,38]. For the sorting problem, e.g., Halldórsson and de Lima [31] showed that there is essentially one structure preventing a deterministic adaptive algorithm from having a competitive ratio better than 2.
One natural alternative to competitive analysis is to assume stochastic inputs, i.e., that the precise value in each interval follows a known probability distribution, and we want to build a decision tree specifying a priority ordering for querying the intervals until the correct solution is found, so that the expected total query cost is minimized. 2 In this paper, we study the sorting problem and the problem of identifying the data item with minimum value in this setting. Some literature is devoted to a similar goal of this paper, but we argue that there are some essential differences. One first line of work consists of the stochastic probing problem [1,24,26,27,28,29,44], which is a general stochastic optimization problem with queries. Even though those works presented results for wide classes of constraints (such as matroid and submodular), they differ in two ways from our work. First, they assume that only elements that are queried can be in a solution of the underlying problem, or that the objective function is based on the expectation of the non-queried elements. Second, the objective function is either a combination of the solution and query costs, or there is a fixed budget for performing queries. Since most of these variants are NP-hard [24], some papers [27,44] focused on devising approximation algorithms, while others [24,28] on bounding the ratio between an oblivious algorithm and an optimal adaptive algorithm (the adaptive gap). Another very close work is that of Welz [45,Section 5.3] and Maehara and Yamaguchi [37], who, like us, assume that a solution may contain non-queried items. Welz presented results for the minimum spanning tree and traveling salesman problems, but under strong assumptions on the probability distributions. Maehara and Yamaguchi devised algorithms for a wide class of problems, that also yield improved approximation algorithms for some classical stochastic optimization problems. However, both works focus on obtaining approximate solutions for the underlying problem, while we wish to obtain an exact one, and they only give asymptotic bounds on the number of queries performed, but do not compare this to the expected cost of an optimum query set. To sum up, our work gives a better understanding on how the stochastic assumption differs from the competitive analysis, since other assumptions are preserved and we use the same metric to analyze the algorithms: minimizing query cost while finding the correct solution.
Our results. We prove that, for the sorting problem with stochastic uncertainty, we can construct an adaptive decision tree with minimum expected query cost in polynomial time. We devise a dynamic programming algorithm which runs in time O(n 3 d 2 ) = O(n 5 ), where n is the number of uncertainty intervals and d is the clique number of the interval graph induced by the uncertainty intervals. We then discuss why simpler strategies fail, such as greedy algorithms using only local information, or relying on witness sets, which is a standard technique for solving query-minimization problems with adversarial inputs [12,20]. We also discuss why we believe that the dynamic programming algorithm cannot be improved to o(n 3 ).
Surprisingly, on the other hand, we present evidence that finding an adaptive decision tree with minimum expected query cost for the problem of finding the data item with minimum value is hard, although the adaptive online version (with adversarial inputs) and the offline (verification) version of the problem are rather simple. We prove that the (locally) optimal decision tree conditioned to first querying the leftmost interval can be computed easily, and that, in a (globally) optimal decision tree, the leftmost interval is queried first or last. This also implies that, for any subtree of an optimal decision tree, one branch can be calculated easily. The hard part of the problem occurs when the global optimum does not query the leftmost interval first, and the question becomes how to find the order in which the other intervals are considered in the "hard branch" of the decision tree. We discuss why various heuristics fail in this case. A simple approximation result with factor 1 + 1/d 1 for uniform query costs, where d 1 is the degree of the leftmost interval in the interval graph, follows from the adaptive online version with adversarial inputs [33]. For arbitrary query costs, we show that the stochastic assumption can be used to beat both deterministic and randomized lower bounds for the adaptive online version with adversarial inputs.
Other related work. One interesting related problem was studied by van der Hoog et al. [32]: how to preprocess a set of intervals so that the actual numbers can be sorted efficiently after their precise values are revealed. Ajtai et al. [2] studied an uncertainty variant of the sorting problem in which a comparison between two values may be imprecise, and the goal is to minimize the number of comparisons to sort the values within a given precision. Braverman and Mossel [11] studied the problem of estimating the most probable ordering of a set of values in two models of uncertainty: (1) when comparisons are not reliable, and (2) when a permutation of the original ordering is sampled within a given probability distribution.
Our work falls into the wide area of stochastic optimization [9], and in particular multi-stage stochastic optimization [41]. Problems with uncertainty data described by intervals have also been studied under the framework of robust optimization [4,34,46]. A classical paper on multi-stage robust optimization is [15]. For surveys on robust optimization, see [7,8].
Organization of the paper. Section 2 is devoted to the sorting problem with stochastic uncertainty, and Section 3 to the problem of finding the minimum data item. We conclude the paper with future research questions in Section 4.

Sorting
The problem is to sort n numbers v 1 , . . . , v n ∈ R whose actual values are unknown. We are given n open intervals I 1 , . . . , I n such that v i ∈ I i = (ℓ i , r i ). We can query interval I i by paying a cost w i , and after that we know the value of v i . We want to find a permutation π : [n] → [n] such that v i ≤ v j if π(i) < π(j) by performing a minimum-cost set of queries. We focus on adaptive algorithms, i.e., we can make decisions based on previous queries. We are interested in a stochastic variant of this problem in which v i follows some known probability distribution on I i . The only constraints are that (1) values in different intervals have independent probabilities, (2) for any subinterval (a, b) ⊆ I i , we can calculate Pr[v i ∈ (a, b)] in constant time 3 , and (3) the known information on the probability distribution cannot be used to shorten the endpoints of any uncertainty interval 4 . The goal is to devise a strategy (i.e., a decision tree) to query the intervals so that the expected query cost is minimized. More precisely, this decision tree must tell us which interval to query first and, depending on where its value falls, which interval to query second, and so on, until we have enough information to find the permutation π. Definition 1. Two intervals I i and I j such that r i > ℓ j and r j > ℓ i are dependent. Two intervals that are not dependent are independent.
The following lemma and proposition are proved in [31]. The lemma tells us that we have to remove all dependencies in order to be able to sort the numbers.

Lemma 2 ([31]). The relative order between two intervals can be decided without querying either of them if and only if they are independent.
Proposition 3 ( [31]). Let I i and I j be intervals with actual values v i and v j . If v i ∈ I j (and, in particular, when I i ⊆ I j ), then I j is queried by every feasible query set.
Note that the dependency relation defines an interval graph, where we have a vertex for each interval, and two vertices are adjacent if the corresponding intervals intersect [36]. Prop. 3 implies that we can immediately query any interval containing another interval, hence we may assume a proper interval graph (that is, without nested interval pairs) [42]. We may also assume the graph is connected, since the problem is independent for each component, and that there are no single-point intervals, as they would give a non-proper or disconnected graph.

An optimal algorithm
We describe a dynamic programming algorithm to solve the sorting problem with stochastic uncertainty. Since we have a proper interval graph, we assume intervals are in the natural total order, with ℓ 1 < · · · < ℓ n and r 1 < · · · < r n . We also pre-compute the regions S 1 , . . . , S t defined by the intervals, where t ≤ 2n − 1. A region is the interval between two consecutive points in the set n i=1 {ℓ i , r i }; we assume that the regions are ordered. We write S x = (a x , b x ) with a x < b x , and we denote by I x (y, z) = {i : S x ⊆ I i ⊆ (a y , b z )} the indices of the intervals totally contained in (a y , b z ) that contain S x . For simplicity we assume that, for any interval I i and any region S x , 0; this is natural for continuous probability distributions, and for discrete distributions we may slightly perturb the distribution support so that this is cascading area (a) cascading area enforced (we give more detail in Section 2.4). Since the dependency graph is a connected proper interval graph, we can also assume that each interval contains at least two regions. Before explaining the recurrence, we first examine how Prop. 3 reduces the space of feasible query sets with an example. In Figure 1(a), suppose we first decide to query I 3 and its value falls in region S 5 . Due to Prop. 3, all intervals that contain S 5 , namely I 2 and I 4 , have to be queried as well. In Figure 1(b), we assume that v 2 falls in S 3 and v 4 falls in S 6 . This forces us to query I 1 but also implies that I 5 can be left unqueried. Therefore, each time we approach a subproblem by first querying an interval I i whose value falls in region S x , we are forced to query all other intervals that contain S x , and so on in a cascading fashion, until we end up with subproblems that are independent of current queried values. To find the best strategy, we must pick a first interval to query, and then recursively calculate the cost of the best strategy, depending on the region in which its value falls. Here, the proper interval graph can be leveraged by having the cascading procedure follow the natural order of the intervals.
We solve the problem by computing three tables. The first table, M , is indexed by two regions y, z ∈ {1, . . . , t}, and M [y, z] is the minimum expected query cost for the subinstance defined by the intervals totally contained in (a y , b z ). Thus, the expected query cost of an optimum decision tree for the whole problem is M [1, t]. To compute M [y, z], we suppose the first interval in (a y , b z ) that is queried by the optimum decision tree is I i . Then, for each region S x ⊆ I i , when v i ∈ S x , we are forced to query every interval I j with j ∈ I x (y, z) and this cascades, forcing other intervals to be queried depending on where v j falls. So we assume that, for all j ∈ I x (y, z), v j falls in the area defined by regions z ′ , z ′ + 1, . . . , y ′ − 1, y ′ , with z ′ ≤ x ≤ y ′ , and that this area is minimal (i.e., some point is in S z ′ , and some point is in S y ′ ). We call this interval (a z ′ , b y ′ ) the cascading area of I i in I x (y, z). In Figure 1(b), we have i = 3, x = 5, z ′ = 3 and y ′ = 6. As the dependency graph is a proper interval graph, the remaining intervals (which do not contain S x ) are split in two independent parts, and we compute the resulting expected query cost using two tables, L and R, which we describe next. So the recurrence for M [y, z] is where p(y, z, i, x, z ′ , y ′ ) is the probability that (a z ′ , b y ′ ) is the cascading area of I i in I x (y, z). We omit how to calculate this probability. The definitions of L and R are symmetric, so we focus on L. For region indices y, z, let I j ′ be the leftmost interval totally contained in (a y , b z ). Now, L[y, z ′ , j] is the minimum expected query cost of solving the subproblem consisting of intervals I j ′ , I j ′ +1 , . . . , I j−1 , assuming that a previously queried point lies in the region S z ′ . We ensure that z ′ is the leftmost region in (a y , b z ) that contains a queried point, so that we query all intervals that contain some point. For example, in Figure 1(b), after querying I 2 , I 3 and I 4 , the left subproblem has z ′ = 3 and j = 2. It holds that L can be calculated in the following way. If no interval before I j contains S z ′ , then the cascading is finished and we can refer to table M for regions y, y + 1, . . . , z ′ − 1. Otherwise I j−1 must contain S z ′ , we query it, and either v j−1 falls to the right of a z ′ and we proceed to the next interval, or v j−1 falls in a region S k with k < z ′ , and we proceed to the next interval with the leftmost queried point now being in S k . Thus, we have We illustrate this in Figure 2. In Figure 2(a), the subproblem contains I j−1 , I j−2 , . . ., and the leftmost queried point is in S z ′ . Since S z ′ ⊆ I j−1 , we query I j−1 and assume v j−1 falls in a region S k . In Figure 2(b), we have that k ≥ z ′ , so we recurse on L[y, z ′ , j − 1]; this will recurse on M [y, z ′ − 1] in its turn, since S z ′ ⊆ I j−2 . In Figure 2(c), we have that k < z ′ , so we recurse on L[y, k, j − 1], which in its turn will have to query I j−2 .
Analogously for table R, let I j ′ be the rightmost interval totally contained in (a z , b y ). We want to find the best strategy for intervals I j+1 , . . . , I j ′ , assuming that the rightmost queried point is contained in S y ′ . Thus, we have Observe that the definition of table L only depends on which is the leftmost region in the cascading area (and, symmetrically, R only depends on the rightmost region). Therefore, we can simplify the recurrence for table M to if (a y , b z ) contains less than 2 intervals min Ii⊆(ay,bz) Sx⊆Ii where p L (y, z, i, x, z ′ ) is the probability that S z ′ is the leftmost region in the cascading area of I i in I x (y, z), and p R (y, z, i, x, y ′ ) is the probability that S y ′ is the rightmost region. We explain how to calculate these probabilities in Section 2.3. At this point it is not hard to see that the next theorem follows by a standard optimal substructure argument. We present a proof for the sake of completion. Proof. We prove that, for any 1 ≤ y ≤ z ≤ t, the value M [y, z] is the expected query cost of a best decision tree for the subproblem defined by the intervals totally contained in (a y , b z ). The proof is by induction on the number of intervals totally contained in (a y , b z ). If it contains less than two intervals, then no query has to be done to solve this subproblem and the claim follows, so let us assume it contains at least two intervals.
Let us define more precisely how the decision tree for a subproblem is structured. Let I be a collection of intervals and queried points, with at least two dependent elements, and let T (I) be a best decision tree for solving the subproblem defined by I. The root of the tree indicates which interval I i to query first. Then, for each region S x contained in I i , the tree has a branch which is the decision tree for the remaining intervals, conditioned to the fact that v i ∈ S x ; we can write this subtree as T (( is the same, since v x will be dependent to the same intervals, and the dependencies between other intervals do not change. The expected cost of the decision tree encoded by T (I) is then The leaves of the tree will correspond to collections of independent intervals, and will have query cost zero.
If a subtree T (I) contains a queried value v x and a non-queried interval I j with v x ∈ I j , then Prop. 3 says that any feasible query set for I must query I j . This implies that I j is queried in the path between the root and any leaf of the tree. Thus, it is easy to see that there is a decision tree for this subproblem with the same cost in which the first query is I j . If more than one interval contains a queried value v x , then we can query them before other intervals, and in any order, so we can actually query all of them at the same time, and have a root with branches for each combination of regions in which the values fall.
The algorithm starts by querying an interval I i and, depending on the region S x in which v i falls, queries all intervals that contain S x . Since we have a proper interval graph, the remaining intervals are divided into two independent suproblems. Also, if the minimal area containing the regions in which the values fall is the same, then the cost of the subtree is the same, since the same intervals will contain a point queried at this time; this implies that each cascading area is a single disjoint event. Given a cascading area (a z ′ , b y ′ ), the remaining problem consists of finding the best decision tree for two subproblems: one considering that the intervals to the left of S x have not been queried and that the leftmost queried point is in S z ′ , and another that the intervals to the right of S x have not been queried and that the rightmost queried point is in S y ′ . This is precisely the definition of tables L and R; thus, if the recurrences for tables L and R are correct, then the theorem follows by an optimal substructure argument.
So let us prove that the recurrence for table L[y, z ′ , j] is correct; the proof for table R is analogous. Let us recall the definition: L[y, z ′ , j] is the minimum expected cost of solving the subinstance of (a y , b z ) (for some z ≥ z ′ ) consisting of intervals I j ′ , I j ′ +1 , . . . , I j−1 , where I j ′ is the leftmost interval totally contained in (a y , b z ), assuming that the leftmost queried point is contained in then all intervals in I j , I j+1 , . . . have a value to the right of a z ′ , and thus any feasible query set to the intervals totally contained in (a y , b z ′ −1 ) is feasible to complement the current decision tree. Thus, by an optimal substructure argument, Prop. 3 implies that I j−1 must be queried in any feasible query set of the subproblem, and thus can be the first interval queried in this subproblem. When querying I j−1 , we ensure that the leftmost region with a queried point is updated correctly, so the last term in the recurrence for L[y, z ′ , j] is correct by an optimal substructure argument.
The recurrences can be implemented in a bottom-up fashion in time O(n 5 ): if we precompute the value of p L (y, z, i, x, z ′ ) and p R (y, z, i, x, y ′ ), then each entry of M is computed in time O(n 3 ), and each entry of L and R can be computed in linear time. It is possible to precompute p L and p R in time O(n 3 ), which we discuss in Section 2.3. A more careful analysis shows that the time consumption of the whole algorithm is O(n 3 d 2 ), where d is the clique number of the interval graph. First, we show that each entry of M can be computed in time O(nd 2 ). Note that, in a proper interval graph, an interval contains at most 2d − 1 regions, so we have at most 2d − 1 choices of S x for each I i . It holds that I x (y, z) contains at most d intervals, since every such interval contains S x . Moreover, for a given choice of S x , note that z ′ cannot go further left than the leftmost region of the leftmost interval that contains S x , and since z ′ ≤ x we have at most 2d − 1 choices of z ′ ; an analogous argument applies to y ′ . Now we argue that we only need to compute L[y, z ′ , j] if S z ′ ⊆ I j : the leftmost queried point cannot be to the right of I j , since we assume I j was already queried, and cannot be to the left of I j , since we assume I j is the leftmost queried interval. Moreover, it is clear that each entry of L can be computed in time O(d). Analogous arguments apply to table R. Finally, in Section 2.3 we also refine the analysis to argue that the probabilities can be precomputed in time O(n 2 d).
We now argue that an actual optimal decision tree can be constructed using polynomial time and space, if we represent it by a directed acyclic graph (DAG). First, we augment table M with an entry for the interval that is queried first in each subproblem, so we can track what is the best option. Then, we create one node in the DAG for each entry in tables M, L, R. Each node will then have a polynomial number of children: for table M , we have a child for each choice of x, z ′ , y ′ and, for tables L and R, we have a child for each choice of k. Note that the same entry of the table is used by overlapping subproblems, so we can do the same for the nodes in the DAG. It is not hard to see that this construction can be done using at most as much time as for computing the original tables.
It seems difficult to improve this dynamic programming algorithm to something better than O(n 3 · poly(d)). Note that the main information that the decision tree encodes is which interval should be queried first in a given independent subproblem (and there are Ω(n 2 ) such subproblems). We could hope to find an optimal substructure that would not need to test every interval as a first query, and that this information could somehow be inferred from smaller subproblems. However, consider I 1 = (0, 100), I 2 = (6, 105), and I 3 = (95, 198), with uniform query costs and uniform probability distributions. The optimum solution for the first two intervals is to first query I 1 , but the optimum solution for the whole instance is to start with I 2 . Thus, even though I 2 is a suboptimal first query for the smaller subproblem, it is the optimal first query for the whole instance. This example could be adapted to a larger instance with more than d intervals, so that we need at least a linear pass in n to identify the best first query.

Simpler strategies that fail
It may seem that our dynamic programming strategy above is overly complex, and that a simpler algorithm may suffice to solve the problem. Below, we show sub-optimality of two such strategies.
We begin by showing that any greedy strategy that only takes into consideration local information (such as degree in the dependency graph or overlap area) fails. Consider a 5-path with intervals I 1 , . . . , I 5 , where interval I i has non-empty intersection with intervals I i−1 (if i > 1) and I i+1 (if i < 5). Let each interval have query cost 1 and an overlap of 1/3 with each of its neighbors, and the exact value be uniformly distributed in each interval. It can be shown by direct calculation that if we query I 2 (or, equivalently, I 4 ) first, then we have an expected query cost of at most 29/9 = 3.22, while querying I 3 first yields an expected query cost of at least 11/3 = 3.66. However, a greedy strategy that only takes into consideration local information cannot distinguish between I 2 and I 3 .
One technique that has been frequently applied in the literature of uncertainty problems with query minimization is the use of witness sets. A set of intervals W is a witness if a correct solution for the underlying problem cannot be computed unless at least one interval in W is queried, even if all other intervals not in W are queried. Witness sets are broadly adopted because they simplify the design of querycompetitive adaptive algorithms. If, at every step, an algorithm queries disjoint witness sets of size at most α, then this algorithm is α-query-competitive. This concept was proposed in [12]. For the sorting problem, by Lemma 2, any pair of dependent intervals constitute a witness set. However, we cannot take advantage of witness sets for the stochastic version of the problem, even for uniform query costs and uniform probability distributions, and even if we take advantage of the proper interval order. Consider the following intervals: (0, 100), (95, 105), (98,198). The witness set consisting of the first two intervals may lead us to think that either of them is a good choice as the first query. However, the unique optimum solution first queries the third interval. (The costs are 843/400 = 2.1075 if we first query the first interval, 277/125 = 2.216 if we first query the second interval, and 4182/2000 = 2.0915 if we first query the third interval.)

Computing the probability of a cascading area
Let us discuss how to calculate p L (y, z, i, x, z ′ ), which is the probability that, given that v i ∈ S x , it holds that v k > a z ′ for each k ∈ I x (y, z), and some j ∈ I x (y, z) has v j ∈ S z ′ . (The arguments are symmetric for p R (y, z, i, x, y ′ ), so we omit them.) Note that, considering the definition of table M , we can assume that Pr[v i ∈ S x ] > 0; otherwise we don't need to compute p L (y, z, i, x, z ′ ). We will also assume that z ′ = x, and the remaining case can be computed similarly.
Let us fix the values y, z, x, and denote I = I x (y, z), denote the similar probability defined for the set of intervals Note that all divisions in the equation are defined, because we assumed that Pr[v i ∈ S x ] > 0 and z ′ < x.
Since q L (z ′ ) does not depend on i, for each fixed x, y, z, it can be computed in linear time, so all q L (z ′ ) can be computed for all x, y, z in time O(n 5 ). Given this precomputation, all values p L (z ′ , i) for all y, z, i, x, z ′ can be precomputed in O(n 5 ) time.
We can further improve the runtime to O(n 4 ) as follows. Here, we fix z ′ and y, z, and compute q L (z ′ ) for various values of x, so let us now denote q L (x) = q L (z ′ ). Recall that q L (x) = j∈Ix(y,z) Pr[v j > a z ′ ], and note that each factor in this product is non-zero due to assumption (3) at the beginning of Section 2. We compute q L (x) sequentially from x = z ′ to x = x * , where x * is the rightmost region such that there is an interval that contains both S z ′ and S x * . Given q L (x) for some x, q L (x+1) is computed by removing from the product intervals in I x (y, z) \ I x+1 (y, z) and including intervals in I x+1 (y, z) \ I x (y, z). The remainder of the product is reused. Observe that, during this computation, each interval that contains a region in (a z ′ , b x * ) is included in (and removed from) the product exactly once. Therefore, the computation corresponding to fixed values of y, z, z ′ can be done in time proportional to the number of regions x between z ′ and x * plus the number of intervals that contain some region in (a z ′ , b x * ), that is, in O(n) time. Thus, the computation of the whole table takes O(n 4 ) time.
Finally, the preprocessing time can be further reduced (still having constant time computation of p L (· · · ) after preprocessing), by decomposing the table for q into two parts, based on the following observation. The first table is indexed by y, x, z ′ , while the second one by z, x, z ′ . Consider the value q L (y, z, x, z ′ ). This is a product of probabilities ranging over intervals I x (y, z). The observation is that where J x (z, t) is the set of intervals that contain both S x and S z and do not end at b z . Thus, x, z ′ ) if the denominator is non-zero, and otherwise q L (y, z, x, z ′ ) = q L (y, t, x, z ′ ), where q ′ L is defined similarly as q L , except it ranges over J x (z, t). The subtables q L and q ′ L can be computed in O(n 3 ) time using the observations in the previous paragraph.
To refine the analysis, recall that each interval in a proper interval graph contains at most 2d − 1 regions. Since we only consider pairs z ′ , x such that there is an interval that contains both S z ′ and S x , we have at most 2d − 1 choices of x for each choice of z ′ . Thus, we only need time O(d) to compute q L (y, z, z ′ ) for all values of x and fixed y, z, z ′ , and the whole preprocessing can be done in time O(n 2 d).

Allowing arbitrary probabilities on interval endpoints
In this section we discuss how to remove the assumption that 1. If there is some interval I j with ℓ j = b x but no interval j ′ with r j ′ = b x , then we can simply move the probability Pr Note that we did not need to query I j if originally v i = b x ; we could simply make π(i) < π(j). On the other hand, all intervals that originally contained b x will contain b x − ε, so they will be queried if originally v i = b x .

We can do a symmetric operation if there is some interval
3. If there is an interval I j with ℓ j = b x and an interval I j ′ with r j ′ = b x , then we can "shift" the whole ray (b x , +∞) to the right by 2ε, for some ε > 0. More formally, any interval I k with ℓ k ≥ b x will have a new left endpoint ℓ ′ k = ℓ k + 2ε; any interval I k with r k > b x will have a new right endpoint r ′ k = r k + 2ε; for any α > b x , we will move the probability we did not need to query I j or I j ′ if originally v i = b x (we could simply make π(j ′ ) < π(i) < π(j)), and all intervals that originally contained b x will also contain b x + ε (so they will be queried if originally Note that the last transformation creates new regions, but the total number of regions will be at most twice the original, so the time consumption does not increase asymptotically. Moreover, the algorithm can be modified to allow closed and half-open intervals, and thus discrete distributions with finite support. We only need to be careful when v i = b x for some queried interval I i and some region S x : we do not need to query all intervals that contain S x , but only intervals I j with b x ∈ (ℓ j , r j ).

Finding the Minimum
We also consider the problem of finding the minimum (or, equivalently, the maximum) of n unknown values v 1 , . . . , v n . Note that we do not need to know the precise minimum value, but just the data item that contains it; therefore, in some cases it is not necessary to query the corresponding interval. We assume that all intervals are open 5 , and that they are sorted by the left endpoint, i.e., ℓ 1 ≤ ℓ 2 ≤ · · · ≤ ℓ n . Regarding the probability distributions, we also assume constraints (1)-(3) described at the beginning of Section 2. Let I = {I 1 , . . . , I n }.
We begin by discussing some assumptions we can make. First, we can assume that the interval graph is a clique: with two independent intervals, we can remove the one on the right. (However, we cannot assume a proper interval graph, as we did for sorting: the argument that one of the nested intervals has to be queried no longer holds, since here we are only interested in finding the minimum rather than the total order.) The last assumption is that I 1 does not contain another interval; it is based on the following proposition and implies that r 1 = min i r i . Note that it also implies that ℓ 1 < ℓ 2 , . . . , ℓ n . Proposition 5. If I 1 contains some I j , then I 1 is queried in every feasible query set.
Proof. Suppose by contradiction that there is a feasible query set Q that does not contain I 1 . Since ℓ 1 = min i ℓ i , we must have Q = I \ {I 1 } and v i > r 1 for every I i ∈ Q, otherwise we cannot decide if v 1 is the minimum. However, assuming both v j > r 1 and I j ⊆ I 1 is a contradiction.
It is also useful to understand how to find an optimum query set, i.e., to solve the verification problem assuming we know v 1 , . . . , v n . Lemma 6. The optimum query set either (a) queries interval I i with minimum v i and each interval I j with ℓ j < v i ; or (b) queries all intervals except for I 1 , if v 1 is the minimum, v j > r 1 for all j > 1, and this is better than option (a).
Option (b) can be better not only due to a particular non-uniform query cost configuration, but also with uniform query costs, when v 1 ∈ I 2 , . . . , I n . Note also that I 1 is always queried in option (a).
Proof. First let us consider the case when v 1 is the minimum. If v j < r 1 for some j > 1, then I 1 has to be queried even if all other intervals have already been queried, due to Prop. 5. Thus, the only situation in which I 1 may not be queried is when v j > r 1 for all j > 1, and in this case clearly we have to query all other intervals, since otherwise we cannot decide who is the minimum. Now we prove that, if v i is the minimum with i = 1, then I i must be queried. Since v i is the minimum, all other values fall to the right of ℓ i . In particular, v 1 ∈ I i , since I 1 has minimum r 1 . Thus, even if all other intervals have already been queried, I i must be queried due to Prop. 5.
It remains to prove that, for any i ≥ 1, if v i is minimum and I i is queried, then all intervals with ℓ j < v i must also be queried; we actually prove that I 1 , . . . , I j must be queried, by induction on j. The base case is j = 1, and if i = 1 the claim follows from Prop. 5, since v i < r 1 and ℓ 1 < ℓ i . So assume j > 1; note that ℓ j−1 ≤ ℓ j < v i thus, by induction hypothesis, I 1 , . . . , I j−1 must be queried. Since v i is the minimum, v k ≥ v i > ℓ j , for k = 1, . . . , j − 1. Therefore, after I 1 , . . . , I j−1 are queried, I j is the leftmost interval, and must be queried due to Prop. 5, since it contains v i .
We first discuss what happens if the first interval we query is I 1 . In Figure 3(a), we suppose that v 1 ∈ S 3 . This makes I 2 become the leftmost interval, so it must be queried, since it contains v 1 . At this point we also know that we do not need to query I 4 , since v 1 < ℓ 4 . After querying I 2 , we have two possibilities. In Figure 3(b), we suppose that v 2 ∈ S 2 , so we already know that v 2 is the minimum and no other queries are necessary. In Figure 3(c), we suppose that v 2 ∈ S 6 , so we still need to query I 3 to decide if v 1 or v 3 is the minimum. Note that, once I 1 has been queried, we do not have to guess which interval to query next, since any interval that becomes the leftmost interval will either contain v 1 or will be to the right of v 1 . Since this is an easy case of the problem, we formalize how to solve it. The following claim is clear: if we have already queried I 1 , . . . , I i−1 and v 1 , . . . , v i−1 > ℓ i , then we have to query I i . (This relies on I i having minimum ℓ i among I i , . . . , I n .) If we decide to first query I 1 , then we are discarding option (b) in the offline solution, so all intervals containing the minimum value must be queried. The expected query cost is then n i=1 w i · Pr[I i must be queried]. Given an interval I i , it will not need to be queried if there is some I j with v j < ℓ i , thus the former probability is the probability that no value lies to the left of I i . Since the probability distribution is independent for each interval, the expected query cost will be This can be computed in O(n 2 ) time. Now let us consider what happens if an optimum decision tree does not start by querying I 1 , but by querying some I k with k > 1. When we query I k , we have two cases: (1) if v k falls in I 1 , then we have to query I 1 and proceed as discussed above, querying I 2 if v 1 > ℓ 2 , then querying I 3 if v 1 , v 2 > ℓ 3 and so on; (2) if v k / ∈ I 1 , then v k falls to the right of ℓ i , for all i = k, so essentially the problem consists of finding the optimum decision tree for the remaining intervals, and this value will be independent of v k . Therefore, the cost of querying I k first is Thus, we can see that a decision tree can be specified simply by a permutation of the intervals, since the last term in the last equation is fixed. More precisely, let a(1), . . . , a(n) be a permutation of the intervals, where a(k) = i means that I i is the k-th interval in the permutation. We have two types of subtrees. Given a subset X k = {a(k), . . . , a(n)} that contains 1, letT k be the tree obtained by first querying I 1 , then querying the next leftmost interval in X k if it contains v 1 and so on. The second type of subtree T k is defined by a suffix a(k), . . . , a(n) of the permutation. If a(k) = 1, then T k is a decision tree with a root querying I a(k) and two branches. One branch, with probability Pr[v a(k) ∈ I 1 ], consists ofT k+1 ; the other branch, with probability Pr[v a(k) / ∈ I 1 ], consists of T k+1 . If a(k) = 1, then T k =T k , unless k = n, in which case T n will be empty: I 1 does not need to be queried, because all other intervals have already been queried and their values fall to the right of I 1 . We have that cost(T k ) if a(k) = 1 and k = n cost(T k ), if a(k) = 1 and k < n w a(k) + Pr[v a(k) ∈ I 1 ] · cost(T k+1 |v a(k) ∈ I 1 ) + Pr[v a(k) / ∈ I 1 ] · cost(T k+1 ), otherwise.
Note that in the last case we need to condition cost(T k+1 ) to the fact that v a(k) ∈ I 1 . We have that It holds that, if I 1 is not the last interval in a decision tree permutation, then it is always better to move I 1 one step towards the beginning of the permutation. This fact is formalized in the following lemma.
Lemma 7. Given a decision tree permutation I k I 1 I k ′ · · · of a subset S, with |S| ≥ 3 and I 1 ∈ S, it costs at least as much as the cost of I 1 I k I k ′ · · · .
Proof. Let 1[A] be the indicator variable of the event A, i.e., 1[A] = 1 if A is true, and zero otherwise. The cost of where the first equality holds since the probability distributions are independent, so Pr[v j > ℓ i |v k ∈ I 1 ] = Pr[v j > ℓ i ] unless j = k. The second equality holds since ℓ i < r 1 for all i, so Pr[v k > ℓ 1 |v k / ∈ I 1 ] = 1. The third equality holds since Pr[v k / ∈ I 1 ] + Pr[v k ∈ I i ] = 1 and by Bayes' theorem. On the other hand, if we swap I k and I 1 , then the cost is since j<k Pr[v j > ℓ k ] ≤ 1, and the last value is precisely the cost of the former permutation. This lemma implies, by induction, that the optimum decision tree either first queries I 1 , or has I 1 at the end of the permutation. If I 1 is the last interval in the permutation, then it does not have to be queried if all other values fall to its right. Thus it may be that, in expectation, having I 1 as the last interval is optimal.
We do not know, however, how to efficiently find the best permutation ending in I 1 . Simply considering which interval begins or ends first, or ordering by Pr[v i ∈ I 1 ] is not enough. To see this, consider the following two instances with uniform costs and uniform probabilities. In the first, I 1 = (0, 100), I 2 = (5, 305) and I 3 = (6, 220); the best permutation is I 2 , I 3 , I 1 and has cost 2.594689. If we just extend I 2 a bit to the right, making I 2 = (5, 405), then the best permutation is I 3 , I 2 , I 1 , whose cost is 2.550467.
If there was a way to determine the relative order in the best permutation between two intervals I j , I k = I 1 , simply by comparing some value not depending on the order of the remaining intervals (for example, by comparing the cost of I j I k I 1 · · · and I k I j I 1 · · · ), then we could find the best permutation easily. Unfortunately, the ordering of the permutations is not always consistent, i.e., given a permutation, consider what happens if we swap I j and I k : it is not always best to have I j before I k , or I k before I j . Consider intervals I 1 = (0, 1000), I 2 = (3, 94439), I 3 = (8, 6924), and I 4 = (9, 2493), with uniform query cost and uniform probability distributions. The best permutation is I 4 , I 3 , I 2 , I 1 , and the costs of the permutations ending in I 1 are as follows. Note that it is sometimes better that I 2 comes before I 3 , and sometimes the opposite. This issue also seems to preclude greedy and dynamic programming algorithms from succeeding. It seems that it is not possible to find an optimal substructure, since the ordering is not always consistent among subproblems and the whole problem. We have implemented various heuristics and performed experiments on random instances, and could always find instances in which the optimum was missed, even for uniform query costs and uniform probabilities.
Another reason to expect hardness is that the following similar problem is NP-hard [24]. Given stochastic uncertainty intervals I 1 , . . . , I n , costs w 1 , . . . , w n , and a query budget C, find a set S ⊆ {1, . . . , n} with w(S) ≤ C that minimizes E[min i∈S v i ].
Note that the decision version of our problem (whether there is a decision tree with expected cost ≤ α) is in NP as we can represent a decision tree using linear space (by a permutation of the intervals) and compute its cost in polynomial time.

Approximation Algorithms
Good approximation algorithms have been proposed for the adaptive online version with adversarial inputs [33]. If query costs are uniform, then first querying I 1 costs at most opt + 1, which yields a factor 1 + 1/d 1 , where d 1 is the degree of I 1 in the interval graph. For arbitrary costs, there is a randomized 1.5-approximation algorithm using weighted probabilities in the two strategies stated in Lemma 6. Those results apply to the stochastic version of the problem simply by linearity of expectation.
Theorem 8. The stochastic minimum problem with uncertainty admits a (1 + 1/d 1 )-approximation for uniform query costs, and a randomized 1.5-approximation for arbitrary costs.
Proof. For any path between the root and a leaf in the decision tree, the result holds in the worst case, so it holds in expectation.
Those results have matching lower bounds for the adaptive online setting with adversarial inputs, and for arbitrary query costs there is a deterministic lower bound of 2. We show that the stochastic assumption can be used to beat those lower bounds for arbitrary costs. First, the randomized 1.5-approximation algorithm can be derandomized, simply by choosing which strategy has smaller expected query cost: either first querying I 1 , or first querying all other intervals and if necessary querying I 1 . We know how to calculate both expected query costs in time O(n 2 ); the latter is i>1 Theorem 9. There is a deterministic 1.5-approximation algorithm for the stochastic minimum problem with uncertainty with arbitrary query costs.
Proof. Let V be the set of realizations of the values, and assume V is finite. (Otherwise finiteness can be attained by grouping realizations into equivalence classes based on the partition into regions.) For each V ∈ V, let C 1 (V ) be the random variable denoting the cost of first querying I 1 , then querying I 2 if v 1 ∈ I 2 , and so on, and let w(R) = i>1 w i . We partition V in sets V 1 and V R , where V ∈ V 1 if opt(V ) = C 1 (V ), and V ∈ V R if opt(V ) = w(R); note that Lemma 6 guarantees that this is indeed a partition.
. If opt * is the expected query cost of the best permutation for the stochastic problem, then where the inequality holds by bounding opt * via a "fractional" decision tree.
Now consider the solution for the stochastic problem obtained by the algorithm. Let ALG 1 be the cost of first querying I 1 , and let ALG R be the cost of first querying all other intervals. Then where the second inequality holds because Pr[V ∈ V 1 ] = 1 − ρ and C 1 (V ) ≥ w 1 for any V . On the other hand, The expected query cost of the algorithm is where the second and third inequalities hold by the properties of the geometric mean.
Ahead in Theorem 11 we propose a more refined algorithm, that we analyze according to the expected approximation ratio. In the proof above, instead, we bounded the ratio of the expected query cost and the expected optimum query cost (the latter corresponding to the fractional decision tree we use as lower bound). Since there is no fixed relation between E[A]/E[B] and E[A/B] for random variables A, B, we cannot compare the results of Theorems 9 and 11. To circumvent that, we prove the following proposition. The example used in the proof was proposed for a similar result in [5], regarding the ratio of the expected query cost and the expected optimum query cost.
Proof. Consider three intervals I 1 , I 2 , I 3 , with ℓ 1 < ℓ 2 < ℓ 3 < r 1 < r 2 , r 3 . Let the query costs be w 1 = w 3 = k and w 2 = 1, with k = (1 − 2ε)/ε 2 ; note that k > 0. Let the probability distributions be the following: The algorithm will either query I 1 and cascade, with expected query cost (the algorithm queries I 1 , then , or query {I 2 , I 3 }, and then I 1 if necessary, with expected query cost Since the first option is slightly better, the algorithm will choose that strategy. Thus, the expected approximation ratio is Next we describe a more refined deterministic algorithm, which attains expected approximation ratio at most 1.4507; a pseudocode is given in Algorithm 1. The idea is, in some sense, to try to decide between first querying I 1 or I \ {I 1 } (as the algorithm above), but in a more cautious way, taking into consideration the relationship between the query costs and the probability distributions. The algorithm has six parameters µ 1 , µ R , ρ 1 , ρ R , φ 1 , φ j ≥ 1, which are described in the analysis and are functions of the input.
Let R = I \ {I 1 }. For a set G ⊆ R, let w(G) = i∈G w i . We say that a set G ⊆ R hits I 1 if, for some interval I i ∈ G, it holds that v i ∈ I 1 ; note that Pr[G hits . First, we try to find a set G ⊆ R such that w(G) ≤ α · w(R) and Pr[G hits I 1 ] ≥ α · Pr[R hits I 1 ], for some α ∈ [1/4, 3/4]. If we manage to find such G, then we use the parameters µ 1 , µ R , defined later in the analysis, to decide between two strategies. If µ 1 ≤ µ R , then we query I 1 and cascade. Otherwise, we first query G, and if it hits I 1 then we query I 1 and cascade. If G does not hit I 1 , then we query the remaining of R, and query I 1 if necessary. The high-level reason why it is better to query G before querying all of R is the following: if R hits I 1 , then there is a good probability (at least 1/4) that G also hits I 1 , but the cost of G is bounded by 3/4 times the cost of R. Now we describe how to find G. If some interval I j ∈ R has cost at least 3w(R)/4 and the probability that R \ {I j } hits I 1 is at least Pr[R hits I 1 ]/4, then we clearly can take G = R \ {I j }. If every interval in R has cost less than 3w(R)/4, then there is a set G ′ ⊆ R with w(R)/2 ≤ w(G ′ ) ≤ 3w(R)/4 (it can be computed greedily). In this case, let β = w(G ′ )/w(R); if G ′ hits I 1 with probability at least β · Pr[R hits I 1 ], then we can take G = G ′ and α = β. Otherwise, the complement R \ G ′ has cost (1 − β) · w(R) and probability of hitting So we let G = R \ G ′ and α = 1 − β. Note that β ∈ [1/2, 3/4] and (1 − β) ∈ [1/4, 1/2], so α ∈ [1/4, 3/4]. If we do not manage to find the set G, then note that there is an interval I j with w j ≥ 3w(R)/4, but the probability of R \ {I j } hitting I 1 is less than Pr[R hits I 1 ]/4. We have two strategies, depending on whether w 1 ≤ 3w(R)/4: 1. If w 1 ≤ 3w(R)/4, then we make a deterministic choice between querying I 1 and cascading, or querying R and then I 1 if necessary. That choice is made with the parameters ρ 1 , ρ R , which are defined later in the analysis. In this case, we show that there is a high chance that I j is part of every feasible query set, and it comprises most of the cost of the instance, so the expected query cost is not far from the expected optimum.
Input: (I 1 , . . . , I n , w, Pr) We now analyze the expected approximation factor of this algorithm.
Theorem 11. Algorithm 1 has expected approximation factor at most 1.4507 for the stochastic minimum problem with uncertainty with arbitrary query costs.
Proof. Throughout the proof, we denote by C 1 the random variable consisting of the cost of querying I 1 and cascading. Let k be the maximum index such that w 1 +. . . w k ≤ w(R), and let p 1 = Pr[v 1 > ℓ k+1 ] = Pr[v 1 ∈ I k+1 ] (cf. Prop. 5). (Note that k < n because w 1 > 0.) Note that p 1 = Pr[C 1 > w(R)|R does not hit I 1 ]: this is because, if we assume that all the values in R are to the right of r 1 , then every interval I i ∈ R with v 1 ∈ I i must be queried. We also point out that p 1 is independent from the choices of the values of the intervals in R. To simplify notation, let p R = Pr[R hits I 1 ].
First, consider the case that the algorithm queries I 1 and cascades. If R hits I 1 , which happens with probability p R , then the optimal strategy is to query I 1 and cascade, as discussed in Section 3, so we are optimal. Otherwise, the optimum cost is min(w(R), C 1 ), while the algorithm pays C 1 . In this case, the approximation ratio is 1 if C 1 ≤ w(R) (which happens with probability 1 − p 1 ); otherwise (with probability p 1 ), the ratio is at most (w 1 + w(R))/w(R) = 1 + w 1 /w(R). Thus, the expected approximation ratio is at most Next, suppose we first query G. Recall that, with probability p R , R hits I 1 and it is optimal to query I 1 and cascade. Let γ = Pr[G hits I 1 |R hits I 1 ]. If G hits I 1 , then an upper bound on the query cost of the algorithm is w(G) + C 1 , while the optimum is C 1 . Since C 1 ≥ w 1 , the approximation ratio in this case is (C 1 +w(G))/C 1 ≤ 1+w(G)/w 1 ≤ 1+αw(R)/w 1 . Otherwise, in the worst case the algorithm pays w(R)+w 1 , while again, the optimum is at least w 1 , so the approximation ratio is at most (w 1 +w(R))/w 1 = 1+w(R)/w 1 . Thus, the expected approximation ratio conditioned to R hitting I 1 is at most where the first inequality holds because 1 ≥ γ ≥ α (hence γ(α − 1) ≤ α(α − 1)), and the last inequality holds because the maximum for α 2 + 1 − α in the interval [1/4, 3/4] is 13/16. If R does not hit I 1 , which happens with probability 1 − p R , the optimum cost is min(C 1 , w(R)), while the algorithm pays w(R). Conditioned to this event, the expected approximation ratio is at most Altogether, the expected approximation ratio when the algorithm first queries G is at most where we denote z = w(R)/w 1 . By definition, the expected approximation ratio of the algorithm is at most min(µ 1 , µ R ). Our goal now is to show that this minimum is upper-bounded by the claimed approximation factor.
First, consider the case when 0 < z ≤ 1; then, both µ 1 and µ R are increasing in p 1 , so we may let p 1 = 1. Then the functions to bound are f 1 (z, p R ) = 1 + (1 − p R )/z and f 2 (z, p R ) = 1 + (13/16) · p R · z. If p R ∈ {0, 1}, then min(f 1 , f 2 ) = 1, so assume p R ∈ (0, 1). In this case, for every fixed p R , it holds that f 1 is a decreasing function of z, while f 2 is an increasing function of z. Thus, for every p R , the z that maximizes min(f 1 , f 2 ) is given by f 1 (z, p R ) = f 2 (z, p R ), that is, z = 16 (1−pR) 13pR . Plugging that value of z back into f 2 , we obtain 1 + 13 16 (p R − p R 2 ), which is maximized at p R = 1/2, giving us the bound 1 + √ 13/8 < 1.4507. Now assume z > 1. Note that we may assume z < 16/3, as otherwise µ 1 ≤ 1 + 3/16. Under such assumption, the coefficient of 1 − p R in (2) is negative, which means that for every fixed p 1 and z, µ 1 is a decreasing function of p R , while µ R is an increasing function of p R . Thus, for each z and p 1 , min(µ 1 , µ R ) is maximized when µ 1 = µ R . Solving the last equation for p R (ignoring the restriction p R ∈ (0, 1)), we get The common value of µ 1 and µ R for such p R , plugging the expression above in (1) where the first inequality holds by letting p 1 = 1, which we can do since z < 16/3 implies that the left hand side is an increasing function of p 1 . The second inequality is obtained by minimizing the denominator by setting its derivative to 0: 13/16 − 1/z 2 = 0, z = 16/13. Concluding, we see that the expected approximation ratio in Case 1 is always bounded by 1 + √ 13/8 < 1.4507. Case 2, G = ∅, w 1 ≤ 3w(R)/4. In this case we make a deterministic choice between two options: either query I 1 and cascade, or query R and then query I 1 only when R hits I 1 . The choice is based on estimates ρ 1 , ρ R of the expected approximation ratio we get in either option.
First, consider the case when we query I 1 and cascade. With probability p R , the optimum is to query I 1 and cascade as discussed in Section 3. Assuming R does not hit I 1 , with probability 1−p 1 again the optimum is to query I 1 and cascade. In the remaining case, we have approximation ratio at most (w 1 + w(R))/w(R), as the optimum only queries R. Putting these cases together, we get approximation ratio at most Next, let us estimate the approximation ratio when we choose to first query R. We divide in several cases to organize the argument.
1. With probability 1 − p R , R does not hit I 1 . Conditioned on this event, with probability p 1 , the optimum queries R only, otherwise the optimum costs C 1 ≥ w 1 . Thus, we have approximation ratio at most 2. With probability p R , R hits I 1 , so the optimum is to query I 1 and cascade, and the algorithm will query all the intervals. Remember that R contains an element I j with w j ≥ 3w(R)/4, but Let p ′ 1 = Pr[v 1 ∈ I j ]. Again, note that p ′ 1 is independent from the choices in R. Conditioned on the event when R hits I 1 , we have the following cases.
(a) With probability p ′ 1 , we have that v 1 ∈ I j . Conditioned to this event, we have two subcases. i. Since we are conditioned to R hitting I 1 , by Equation (4) we have probability at least 3/4 that R \ {I j } does not hit I 1 but v j ∈ I 1 . Therefore, querying I j must be part of any feasible query set, since v 1 ∈ I j and every interval I j ′ ∈ R \ {I j } has v j ′ > r 1 (including those with j ′ < j). So we have approximation ratio at most ii. With probability at most 1/4, we use the bound of (w 1 + w(R))/w 1 .
Thus we have that the ratio conditioned to R hitting I 1 is at most We then claim that p ′ 1 ≥ p 1 . Suppose by contradiction that p ′ 1 < p 1 , then we have that j > k + 1. By the definition of k, it holds that a contradiction since we assume that w 1 ≤ 3w(R)/4. Thus, since 1 w1+3w(R)/4 ≤ 1 w1 , the approximation ratio conditioned to R hitting I 1 is at most Summing up, the expected approximation ratio assuming that we first query R is at most Note that p 1 < 1, due to our assumption on p R . Plugging back into (3), we get where A = z 2 − z + 1 ≥ 1, and B = 1 + z 2 /4 + 3z 2 /(12z + 16) − z > 0 (for all z ≥ 1). Note also that A > B holds for all z ≥ 1. We can rule out z > 11/5, as follows. Assuming z > 11/5, our bound on p R implies p R < 0.392. Let us set p R = 0.392 in the first parentheses in (7). Then we obtain a decreasing function of p R , since 1 − A/B < 0, which is maximized for p R = 0, giving us the following function of z: 1 + z−0.608 z 2 −z+1 . The latter is easily checked to be less than 1.44 for all z > 11/5. Thus, we assume that z ∈ [4/3, 11/5]. It can be checked that the value of B in this interval is bounded by 0.353. We replace B = 0.353 and p R = 1 in the denominator of (6), to get the function We optimize this for p R . If z ≤ 2, the optimum is p R = 1 − z/2, giving us the function 1 + z 2 /4 A−0.353 , while for z > 2, the optimal value is p R = 0, giving us the function 1 + z−1 A−0.353 . Both functions can rather easily be checked to be bounded by 1.41, for z ∈ [4/3, 11/5].
Case 3, G = ∅, w 1 > 3w(R)/4. To simplify notation, let us write First let us consider the case that R ′ hits I 1 , so the optimum strategy is to query I 1 and cascade. If I j is not queried, then the approximation ratio is at most If I j is queried in the cascading, then it must be part of every feasible query set, so the approximation ratio is at most w(R ′ ) + w 1 + w j w 1 + w j ≤ 7 6 .
Now let us assume that R ′ does not hit I 1 . Let p ′ 1 = Pr[v 1 ∈ I j ] and p j = Pr[v j ∈ I 1 ]; note that those are independent events.
First, consider the situation in which the algorithm queries I 1 before I j . With probability p ′ 1 , the algorithm also queries I j ; if v j ∈ I 1 (which happens with probability p j ), then both I 1 and I j need to be queried to decide which is the minimum, otherwise the optimum strategy is to query R only, as C 1 ≥ w 1 +w j but w(R) = w j + w(R ′ ) ≤ w j + w 1 /3. With probability 1 − p ′ 1 , the algorithm does not query I j , and the optimum strategy is to query I 1 and cascade if v j ∈ I 1 or C 1 ≤ w(R). Thus, the approximation ratio is at most w(R ′ ) w 1 + (1 − p j ) · w(R ′ ) + w 1 min(w 1 , w(R)) =: φ 1 , where z = w(R)/w 1 . Now consider the case when the algorithm queries I j before I 1 . With probability p j , the optimum strategy is to query I 1 and cascade, and the algorithm queries all intervals; also, if v 1 ∈ I j , then C 1 ≥ w 1 + w j . With probability 1 − p j , the algorithm does not query I 1 ; if v 1 ∈ I j , then the optimum is to query R only, as w(R ′ ) ≤ w 1 /3 (as discussed in the previous paragraph), otherwise the optimum is the minimum between querying I 1 and cascading or querying R only. Therefore, the approximation ratio is at most w(R) min(w 1 , w(R)) =: φ j . (9) which is maximized when p ′ 1 = 4 − 2 42/13 and the maximum is 17 − 2 182/3 < 1.4223. Case 3.2, w 1 > w(R). Note that z ∈ (0, 1), where z = w(R)/w 1 . Recalling that w(R ′ ) ≤ w(R)/4 and w(R ′ ) ≤ w j /3, we have w(R ′ ) < w 1 /4, w(R ′ ) < (w 1 + w j )/7, and (w(R ′ ) + w 1 )/ min(w 1 , w(R)) = (w(R ′ ) + w 1 )/w(R) ≤ 1/z + 1/4. In this case, Equation (8) is at most which is a function of z that is non-increasing for any fixed value of p ′ 1 , p j , since p j ≤ 1. On its turn, Equation (9) is at most (using w(R)/ min(w 1 , w(R)) = 1) If p j = 0 then this is optimal, and when p ′ 1 = 1 it can be bounded by 8/7. Otherwise we have a function of z that is increasing for any fixed value of p ′ 1 , p j , since p ′ 1 ∈ [0, 1) and p j ∈ (0, 1]. Since one function is non-increasing and the other is increasing, their minimum is maximized when they are equal, which happens when and Equation (13) then becomes (4 − 3z(1 − p ′ 1 ))(p ′ 1 + 7z(1 − p ′ 1 )) 28(1 − z(1 − z)(1 − p ′ 1 )) + 1 =:φ(p ′ 1 , z).
Note that the denominator of the first summand inφ(p ′ 1 , z) is minimized w.r.t. z at z = 1/2, hence is at most 21 + 7p ′ 1 , and the numerator is non-negative for z ∈ (0, 1). Taking factors 3(1 − p ′ 1 ) and 7(1 − p ′ 1 ) out of the first and second brackets (resp.) of the numerator and denoting a = For fixed p ′ 1 , the right-hand side of this inequality is a parabola with negative coefficient of z 2 , hence it is maximized when z = (a − b)/2, implying .
The approximation factor can be improved slightly by choosing a different parameter δ ∈ (0, 1/3] such that α ∈ [δ, 1 − δ]. Note that it does not work for δ ∈ (1/3, 1/2), since in this case we cannot build G ′ with w(R)/2 ≤ w(G ′ ) ≤ (1−δ)·w(R) simply by assuming that every interval in R has cost less than (1−δ)·w(R). Using the analysis of Case 1, this implies that a lower bound on the approximation that can be achieved by this strategy is 1 + √ 7/6 > 1.4409, even if not restricted by Cases 2 and 3.

Further Questions
It would be interesting to find out whether it is possible to implement our dynamic programming algorithm for the sorting problem more efficiently, e.g., in O(n 4 ) time. We could also try to extend our approach for sorting so as to handle a dynamic setting, e.g. as in [13], where some intervals can be inserted/deleted from the initial set; updating the dynamic program should be faster than building it again from scratch.
The main question that we leave open regards the complexity of finding the best decision tree for the minimum problem. It has proved non-trivial to obtain either a negative or positive result. It could also be promising to look for better approximation algorithms for particular cases, e.g. if query costs and probability distributions are uniform.
If it is NP-hard to find the best decision tree for the minimum problem, then the same applies to the stochastic versions of the problem of finding the k-th smallest value (the generalized median problem) [22,33] and the minimum spanning tree problem with uncertainty on edge weights [17,20,38]. This holds because the minimum problem is a particular case of both: for the k-th smallest value problem it is the case with k = 1; for the minimum spaning tree problem, if we have two vertices connected by multiple edges, then we want to identify the edge of minimum weight. It would be interesting to find out whether it is possible to devise polynomial-time algorithms for those problems with better approximation guarantees than the respective best results for the adaptive online problem with adversarial inputs, as we did for the minimum problem. We believe those problems would require different techniques to the ones we developed here, as they are more intricate.


extfieldsofstudy:
Computer Science
Mathematics

text:
Enhash: A Fast Streaming Algorithm For Concept Drift Detection

We propose Enhash, a fast ensemble learner that detects \textit{concept drift} in a data stream. A stream may consist of abrupt, gradual, virtual, or recurring events, or a mixture of various types of drift. Enhash employs projection hash to insert an incoming sample. We show empirically that the proposed method has competitive performance to existing ensemble learners in much lesser time. Also, Enhash has moderate resource requirements. Experiments relevant to performance comparison were performed on 6 artificial and 4 real data sets consisting of various types of drifts.

Introduction
A data stream environment is often characterized by large volumes of data that flow rapidly and continuously. They are processed in an online fashion to accommodate data that cannot reside in main memory. A streaming data environment is commonly used for tasks such as making recommendations for users on streaming platforms [29], and real-time analysis inside IoT devices [1]. In such a stream, the underlying data distribution may change, and this phenomenon is referred to as concept drift. Formally, the posterior probability of a sample's class changes with time. Consequently, the method must also be able to adapt to the new distribution. To adapt to a new concept, the method may require supplemental or replacement learning. Tuning a model with new information is termed as supplemental learning. Replacement learning refers to the case when the model's old information becomes irrelevant, and is replaced by new information. A shift in the likelihood of observing a data point x within a particular class when class boundaries are altered, is called real concept drift. Concept drift without an overlap of true class boundaries, or an incomplete representation of the actual environment, is referred to as virtual concept drift. In virtual concept drift, one requires supplemental learning, while real concept drift requires replacement learning [13]. The other common way to categorize concept drift is determined by the speed with which changes occur [2]. Hence, drift may be incremental, abrupt or gradual. A reoccurring drift is one that emerges repeatedly. Thus, in order to handle concept drift, a model must be adaptive to non-stationary environments.
Several methods have been recently proposed to handle concept drift in a streaming environment. The most popular of these are ensemble learners [25,11,30,5,14,31,19,18]. As the data stream evolves, an ensemble method selectively retains a few learners to maintain prior knowledge while discarding and adding new learners to learn new knowledge. Thus, an ensemble method is quite flexible, and maintains the stability-plasticity balance [20] i.e. retaining the previous knowledge (stability) and learning new concepts (plasticity).
In this paper, we propose Enhash, an ensemble learner that employs projection hash [15] to handle concept drift. For incoming samples, it generates a hash code such that similar samples tend to hash into the same bucket. A gradual forgetting factor weights the contents of a bucket. Thus, the contents of a bucket are relevant as long as the incoming stream belongs to the concept represented by them.
The rest of the paper is organized as follows. Section 2 discusses the basic principle of some relevant ensemble learners. Section 3 elaborates the proposed ensemble learner. Section 4 highlights the performance metrics used to evaluate the performances of several ensemble learners on artificial and real data sets with varying concept drift. Section 5 discusses the impact of tuning of parameters on the performance of Enhash. Section 6 compares the performances of discussed ensemble learners. Section 7 compares the performance of Enhash with its two different variants and highlights the importance of design choice. Section 8 concludes the aspects of the proposed method.

Related Work
In this section, we discuss some of the widely used ensemble learners for drift detection.
Learn++ [25] is an Adaboost [12,28,27] inspired algorithm, that generates an ensemble of weak classifiers, each trained on a different distribution of training samples. The multiple classifier outputs are combined using weighted majority voting. For incremental learning, Learn++ updates the distribution for subsequent classifiers such that instances from new classes are given more weights.
While Learn++ is suitable for incremental learning, Learn ++ .NSE [11] employs a passive drift detection mechanism to handle non-stationary environments. If the data from a new concept arrives and is misclassified by the existing set of classifiers, then a new classifier is added to handle this misclassification. Learn ++ .NSE is an ensemble-based algorithm that uses weighted majority voting, where the weights are dynamically adjusted based on classifiers' performance.
Accuracy-Weighted Ensemble [31] is an ensemble of weighted classifiers where the weight of a classifier is inversely proportional to its expected error.
Additive Expert Ensemble [18] uses a weighted vote of experts to handle concept drift. The weights of the experts that misclassify a sample are decreased by a multiplicative constant β ∈ [0, 1]. In case the overall prediction is incorrect, new experts are added as well.
Dynamic Weighted Majority (DWM) [19] dynamically adds and removes classifiers to cope with concept drift.
Online bagging and boosting [23] ensemble classifiers are used in combination with different algorithms such as ADaptive WINdowing (ADWIN) [4] for concept drift detection. ADWIN dynamically updates the window by growing it when there is no apparent change, and shrinking it when the data evolves. In general, bagging is more robust to noise than boosting [10,24]. Henceforth, we discuss methods based on online bagging, that approximates batch-bagging by training every base model with K copies of a training sample, where K ∼ Poisson(1). We refer to the combination of online bagging classifiers with ADWIN as Online Bagging-ADWIN.
Leveraging bagging [5] exploits the performance of bagging by increasing randomization. Resampling with replacement is employed in online bagging using Poisson (1). Leveraging bagging increases the weights of this resampling by using a larger value of λ to compute the Poisson distribution. It also increases randomization at the output by using output codes.
Online SMOTE Bagging [30] oversamples a minor class by using SMOTE [9] at each bagging iteration to handle class imbalance. SMOTE generates synthetic examples by interpolating minor class examples.
Adaptive Random Forest, ARF [14] is an adaptation of Random Forest [7] for evolving data streams. It trains a background tree when there is a warning, and replaces the primary model if drift occurs.

The Proposed Method
Several recent methods employ hashing for online learning and outlier detection [26,16]. We propose Enhash, an ensemble learner, that employs hashing for concept drift detection. Let x t ∈ R d represent a sample from a data stream S at time step t and let y ∈ {1, 2, ..., C} represent its corresponding concept, where C is the total number of concepts. Further, let us assume a family of hash functions H such that ∀h l ∈ H, it maps x t to an integer value. The hash code h l (x t ) is assigned to x t by hash function h l . A bucket is a set of samples with the same hash code; both these terms are used interchangeably. The total number of samples in bucket h l (x t ) is denoted by N h l (xt) . Further assume that N samples have been seen and hashed from the stream so far. Amongst N , N c samples belong to the concept class c such that c=C c=1 N c = N . Based on the evidence from the data stream seen so far, the probability of bucket h l (x t+1 ) is given by and prior for class c is given by p(c) = N c /N . Assuming, (N h l (xt+1) ) c represents the samples of concept c in bucket h l (x t+1 ). Hence, the likelihood of x t+1 belonging to concept c in bucket h l (x t+1 ) is given by The probability of x t+1 belonging to class c is given by Equation (3) is simply the normalization of counts in bucket h l (x t+1 ).
To predict the concept class of x t+1 , an ensemble of L such hash functions can be employed and the weight for each concept class is computed aŝ and the concept class is predicted aŝ y = arg max c∈{1,..,C}p c To accommodate an incoming sample of class c, the bucket is updated as Enhash utilizes a simple strategy as described above to build an ensemble learner for concept drift detection. In Enhash, the projection hash family is selected as a base learner. Here, a hash function involves the dot product of hyperplane w (l) and sample x t . It is defined as where, bin-width is quantization width, w (l) j and bias (l) can be sampled from any desired distribution. In our implementation, w Effectively, each h l (7) divides the space into equally spaced unbounded regions of size bin-width (earlier referred to as bucket). Equation (3) computes the probability of each concept class in a region. An ensemble of hash functions makes all the regions bounded. The weight of a concept class in the bounded region is computed using (4). An absolute value of concept class is assigned to each region in (5). Figure 1a shows the arrangement of randomly generated hyperplanes. The solid line in Figure 1b shows the inferred decision boundary (learned distribution) after an absolute assignment of concept class to every bounded region. The dashed line in Figure 1b depicts the true decision boundary (true distribution).
Assuming at time step t, Figure 1b shows the current stage of learner. At step t+1, a new sample x t+1 arrives (gray sample in Figure 1c). After updating the bucket (6), the learned distribution shifts and moves towards the true distribution. Hence, Enhash accommodates virtual drift present in the data stream. Figure 1d depicts the real drift when the true distribution evolves. This requires forgetting some of the previously learned information. Suppose that sample x t+∆t hashes to bucket h l (x t+∆t ) at time say, t + ∆t. Assume that previously, x t from a different concept, was hashed to this bucket. In order to accommodate forgetting, Enhash employs a decay factor multiplier to p(c|h l (x t+∆t )) (4) while weighting a bounded region.p where λ is the decay rate. The update rule for the bucket (5) is also changed to reflect the new concept class as follows Setting λ = 0 will reduce these equations to the base case.
In order to break ties in p(c|h l (x t )), the class weight in the region is also weighted by the distance of the sample x t from the mean of class samples in bucket and remaining ties are broken arbitrarily.

Implementation Details
Algorithm 1 gives Enhash's pseudo-code. We refer to an instance of the ensemble as an estimator. The parameter bin-width determines the granularity of the buckets, and λ represents the rate of decay that accounts for gradual forgetting [17]. Every estimator l generates a hash code for incoming stream samples and hashes them into bucket b (l) . The hash code for a sample x is compute using (7). The timestamp when a sample of class y was last hashed into a bucket is an infinitely indexable 2D-array. An infinitely indexable ND-array is a data structure that has N dimensions and can store values at any arbitrary combinations of indexes in those dimensions. In practice, an infinitely indexable ND-array can be created using maps or dictionaries. The recent access time of the hash code b (l) can be retrieved by selecting the maximum value in tstamp (l) [b (l) ]. The count of samples in bucket b (l) is stored in another infinitely indexable 2D-array counts (l) at an index counts (l) [b (l) ]. The information required to break the ties during prediction is stored in sCounts (l) and sAcc (l) . The variable sCounts (l) , an infinitely indexable 2D-array, keeps track of the number of samples from every class y falling into the bucket b (l) . sAcc (l) , an infinitely indexable 3D-array, stores the class-wise vector sum of all the samples falling into the bucket b (l) . The last dimension in this array belongs to the features in the dataset. Enhash has two phases. In the first one, Enhash predicts the class of a new sample. Assuming that sample x falls into bucket b (l) , its distance from all the cluster centers in the bucket is computed (steps 18 and 19). The variable cweights accumulates the prediction for a sample x via each estimator. This variable is also an infinitely indexable array so that it can accommodate unseen class labels. To get the prediction for sample x from an estimator l, a decayed value of count (weighted by distance) is computed (step 21). The decay factor 2 −λ∆t1 , depends upon the decay parameter λ and the difference of the current time and the last access time of bucket b (l) . The decay factor determines whether the previous value in counts (l) [b (l) ] is relevant or not, and hence, introducing the forgetting effect in the algorithm. In effect, if the difference in the time is large, then decay is almost zero, and this emulates local replacement in the bucket b (l) [8]. On the other hand, λ reduces the effect of samples (possibly, of the same concept) hashing into a bucket. The higher is the value of λ, then more is the rate of decay. Collectively, λ, and time difference play an important role in drift detection. The log-transformed value of the prediction is added to cweights. A pseudo-count of 1 is added during log-transformation to handle 0 or near-zero values in prediction. After accumulating predictions from every estimator, a class with maximum weight is designated as the class of sample x (step 30).
In the second phase, the information is updated in the variables to accommodate recent changes in the concept. Assume that a recent sample belongs to class y.
is set to the current timestamp. Further, to update the effective count in bucket for class y in counts (l) [b (l) ][y], the present value is decayed by the difference of the current time and the last seen time of sample from class y and then incremented by 1 (steps [24][25]. This introduces the forgetting phenomenon during updates and also handles spurious changes. For example, if a bucket was accustomed to seeing samples from a particular class and the sudden arrival of a sample from another class that had not been seen by the bucket for a long time, it would not alter the bucket's prediction abruptly. However, after seeing a few samples from the new class, the bucket's confidence will grow gradually towards the recent trends. The value in In essence, samples with a similar concept are most likely to have the same hash code and hence, share the bucket. For an evolving stream, thus, different buckets are populated. The weight associated with the bucket is gradually incremented when samples of the same concept arrive. The contents of a bucket are more relevant when the concept reoccurs in the near future than in a faraway future. Formally, the temporal nature of the posterior distribution of a sample x belonging to a class y is modeled as the Bayes posterior probability P (y|x) = P (y)P (x|y)/P (x). Let n and n y denote the count of total samples and samples of a class y, respectively. In the proposed method, for a given estimator l, P (y) = n y /n, P (x|y) = counts

Time Complexity Analysis
There are three important steps in Algorithm 1, namely, the computation of hash function (step 17), prediction of class (steps [18][19][20][21][22], and update of model parameters counts (l) ← infinitely indexable 2D-array 8: tstamp (l) ← infinitely indexable 2D-array 9: sCounts (l) ← infinitely indexable 2D-array 10: sAcc (l) ← infinitely indexable 3D-array 11: Run: (x, y) ← next(S) 14: t ← t + 1 15: cweights ← array initialized with 0s 16: for l ∈ {1, ..., L} do 17: b (l) = generate hash code using (7) for estimator l 18: (steps [23][24][25][26][27][28]. In Enhash, the hash function computation is the dot product of a sample with weight parameters (7). Let the time required to compute the hash function be given by ψ(d) = O(d). The prediction of a sample's class involves the computation of distances from cluster centers in the bucket (10). Assuming that, Enhash has observed C concept classes so far; then, the time required for prediction is given by The update of the model involves updating the timestamp of the bucket, the effective count of the concept class in the bucket, the total samples hashed into the bucket, and accumulation of samples. Effective counts are also normalized in the update step which depends upon C. Say, the time required to update model parameter is given by ζ(d, C) = O(d + C). Thus, an estimator takes time of order . These steps are repeated by all L estimators, and hence, the total time complexity of Enhash, for an arbitrary data set and hyper-parameters settings, is given by O(L * d * C).
Thus, for a fixed setting of hyper-parameter L, the time complexity of Enhash to process a newly arrived sample for an arbitrary data set is given by O(d * C). However, it can be argued that for a fixed data set, the dimension of data d and number of concept classes C are fixed. Hence, Enhash will effectively take only a constant time, O(1), in the processing of a new sample.

Experimental Setup
Enhash's performance on concept drift detection was compared with some of the widely used ensemble learners. These include Learn++ [25], Learn ++ .NSE [11], Accuracy-Weighted Ensemble (AWE) [31], Additive Expert Ensemble (AEE) [18], DWM [19], Online Bagging-ADWIN (OB) [4,23], Leveraging Bagging [5], Online SMOTE Bagging (OSMOTEB) [30], and ARF [14]. The implementation of these methods is available in scikit-multiflow python package [22]. A fixed value of estimators was used for all the methods. For methods such as Accuracy-Weighted Ensemble, Learn ++ .NSE, Learn++, Leveraging Bagging, and Online Bagging-ADWIN, the maximum size of window was set min(5000, 0.1 * n), where n is the total number of samples. For the rest of the parameters, the default value was used for all the methods.

Evaluation metrics for performance comparison
We evaluated all the experiments in terms of time, memory consumption, and classifiers' performance. The memory consumption is measured in terms of RAM-hours [6]. Every GB of RAM employed for an hour defines one RAM-hour. The performance of a classifier is measured in terms of accuracy/error, Kappa M, and Kappa Temporal [3]. Kappa M, and Kappa Temporal handle imbalanced data streams, and data streams that have temporal dependencies, respectively. We evaluated the classifiers' performance using the Interleaved Test-Train strategy [21]. This strategy is commonly employed for incremental learning since every sample is used as a test and a training point as it arrives.

Tuning of parameters for Enhash
The hyperparameters that govern the performance of Enhash constitute L (number of estimators), and bin-width (quantization parameter). Even though the decay rate λ is also one of the hyperparameters, its value does not require much tuning, and usually, λ = 0.015 is preferred [26]. However, making λ = 0 is equivalent to removing the forgetting phenomenon and hence, worsens the performance (discussed further in Section 7).

Constraints to tune L
In Figure 2, it is shown empirically that with an increase in the value of L, the performance of Enhash eventually saturates. The time taken by Enhash also increases with L. This may be attributed to the fact that for every sample arriving at time t, the insertion involves calculating the hash code of the sample for every estimator l. It should be emphasized that, as shown empirically in Figure 2, only a few estimators are needed to achieve optimum performance. Further, the increase in time due to an increase in L can be reduced through a parallel implementation of Enhash. In that case, evaluation of a hash code for a sample for each l can be done independently of others. Consequently, a moderate value of L = 10 is used to perform all the experiments.

Constraints to tune bin-width
The parameter bin-width divides the space into equally spaced unbounded regions of size bin-width. The smaller is the value of bin-width, the more granular is the division of space. In other words, for smaller values of bin-width, the possible values of different hash codes (or buckets) increase rapidly. In the worst case, every sample may fall into a different bucket. Thus, the overall cost to store the contents of all buckets for every estimator grows exponentially. Figure 3 shows empirically the effect of bin-width on memory consumption. The figure highlights that for small values of bin-width, the overall memory requirement is extremely high. Also, the prediction of the concept for the sample may be arbitrary for extremely small values of bin-width since there is no neighborhood information in the bucket. As a result, for every new sample, a new concept may be falsely predicted. On the other extreme, for large values of bin-width, samples from different classes may lead to frequent collision. As a result of this, the concept of an arriving sample may not be predicted correctly due to confusion in the bucket. Thus, in general, an intermediate range of values for bin-width ∈ {0.01, 0.1} is more suitable for all data sets.   Table 2 Error (in %) is reported to compare the performance of Enhash with other methods. For a given data set, the method with the least error is in boldface. Due to implementation constraint, Learn ++ .NSE could not run for the outdoorStream data set.

Experimental Results
For all methods, the number of estimators is considered as 10. In addition for Enhash, bin-width was set to {0.1, 0.01} and λ was set to 0.015. Tables 2, 3, and 4 compare the performance of the methods in terms of error, KappaM, and KappaT respectively using Interleaved Test-Train strategy. For these measures, the performance of the proposed method was superior to Accuracy-Weighted Ensemble (AWE), and Additive Expert Ensemble (AEE) on 8 data sets, DWM, Learn ++ .NSE, Online SMOTE Bagging (OSMOTEB), and Online Bagging-ADWIN (OB) on 7 data sets, Learn++,  Table 4 KappaT is reported to compare the performances of the methods. The highest value of KappaT in each row is highlighted.
and Leveraging Bagging (LB) on 6 data sets, and ARF on 5 data sets. The performance of Enhash supersedes all other methods for 4 data sets -mixedDrift, mov-ingSquares, interchangingRBF, and outdoorStream. Other evaluation criteria are speed (Table 5) and RAM-hours (Table 6). Table 5 reports the overall time (in hrs) taken by each method for a given data set. For a majority of the data sets, Enhash takes the least time. For instance, it took only 0.339 hrs for the mixedDrift data set, followed by Learn ++ .NSE, which took 0.627 hrs. Notably, OSMOTEB took more than 185 hrs.
In terms of speed, DWM, Learn ++ .NSE, and Learn++ are comparable to Enhash. In terms of accuracy, however, Enhash supersedes the individual methods on the majority of the data sets. Our findings were consistent across all commonly used evaluation metrics namely error, KappaM, and KappaT. For instance, DWM requires 0.038 hrs on the interchangingRBF data set as compared to 0.132 hrs needed by Enhash. However, the error of Enhash is 2.72%, while DWM has an error of 7.02%.
The overall closest competitors of Enhash in terms of evaluation measures error, KappaM, and KappaT are ARF, LB, and OB. Enhash's speed and RAM-hours' requirement are almost insignificant when compared with other methods. For instance,  In summary, DWM has relatively poor performance in detecting virtual drifts but fairs well in abrupt and incremental drifts. Learn++ is exceptionally well in detecting virtual drift but severely under-performs in abrupt and incremental drifts. LB and ARF suffer in detecting incremental drifts. However, LB and ARF have an overall satisfactory performance. Enhash performs relatively well on all data sets. Enhash has a superior performance on a data set consisting of three different kinds of drifts, namely incremental, virtual, and abrupt drifts. Although Enhash falls short in detecting abrupt drifts, but the performance gap is not very significant.  Table 7 Ablation study of Enhash. The performance of Enhash is compared with its two different variants-1. Enhash with λ = 0 (referred to as Enhash-lambda0), and 2. Enhash when ties in concept class assignments are not broken by considering the distance of an incoming sample from the mean of classes in the bucket (referred to as Enhash-noWeights).

Ablation study
Enhash is built by modifying (5) and (6). The two major changes in Enhash from these are the inclusion of a forgetting factor and a heuristic for tie braking mechanism to reduce the false positives. In this section, we assess the impact of these changes, which make Enhash suitable for the concept drift detection. Table 7 compares the performances of Enhash with its two variants -Enhash-lambda0 and Enhash-noWeights. Enhash-lambda0 refers to the variant when λ = 0 or equivalently, the forgetting phenomenon is not accounted. Enhash-noWeights refers to the variant of Enhash when ties in the assignment of concept class are broken randomly. In other words, the distance (10) of an incoming sample from the mean of the classes in the bucket is not used to determine the class in case of ties. The values of the other hyperparameters are the same as that in Section 6. Table 7 shows that the performance of Enhash is much superior to its both variants for the majority of the data sets. The sub-optimal results of Enhash-noWeights may be attributed to the fact that when the same count of samples from different classes is present in the same bucket, the class for an incoming sample gets assigned randomly.

Conclusions
We conclude that Enhash supersedes other methods in terms of speed since the algorithm effectively requires only O(1) running time for each sample on a given estimator. In addition, the performance of Enhash in terms of error, KappaM, and KappaT is better or comparable to others for majority data sets. These data sets constitute abrupt, gradual, virtual, and reoccurring drift phenomena. The closest competitor of Enhash in terms of performance is the Adaptive Random Forest. Notably, Enhash requires, on an average 10 times lesser RAM-hours than that of Adaptive Random Forest.

Funding
Not applicable

Competing interests
The authors declare that they have no known competing interests.

Availability of data and material
The data sets are available on https://github.com/vlosing/driftDatasets.

Author's contributions
Aashi Jindal: Design of this study, Methodology, Software. Prashant Gupta: Design of this study, Methodology, Software, Investigation. Jayadeva: Conceptualization of this study, Design. Debarka Sengupta: Conceptualization of this study, Design.


The Architecture of Memory for Core Processors

The effectiveness and storage capacity of single-bit cache memory have been investigated. Write driver circuit, random access memory cell, and current mode detector make up the single-bit cache. Using various strategies, such as power-saving components like current mode sensing amplifiers and static random access memory cells, memory systems with just one bit of cache can use less power. To save power, substitute a forced stack and a current mode detecting amplifier for a single-bit cache.

Introduction
As transistors get smaller, large integrated circuits can have more circuits and function better. Transistors in most integrated circuits are connected by wiring [1][2][3][4]. The wiring within a semiconductor is referred to as the "global interconnect on-chip." Other global linkages, including those connecting cache memory to CPUs, are emerging alongside breakthroughs in submicron VLSI technology. How long it takes to make depends on how many connections a chip has globally [5][6][7]. Transceivers and signalling protocols enable faster message transmission. The recordings of sense amplifiers used as connection receivers allowed for this discovery. A combination of the SRAMC and sense amplifier has also been suggested [8][9][10].

Power reduction techniques
The requirements of a circuit are met while using less electricity [11].

Sleep transistor technique
State-destructive operations can harm PMOS and NMOS sleep transistors connected to the supply voltage or ground. The same technology is known by the names VDD and gated-ground [12]. Sleep semiconductor technology lowers the power used during sleep by separating logical networks from sleep transistors (see Figure 1). Figure 2 illustrates the forced stack. Costs can be further decreased by stacking transistors. By turning off lots of transistors at once, stacking the semiconductor device lowers the subthreshold leakage current [13]. ____________________

Dual sleep technique
Every component in the circuit is either NMOS or NMOS-like (NM0 and NM1). On the other hand, the header and footer employ NMOS and PMOS transistors, respectively. The two options are "on" and "off" [14]. These two devices operate normally when not used, as seen in Figure 3.   Figure 5 shows the write driver for this application. The bit line's high pre-load level is below the writing margin of the SRAMC when the WDC is turned on. With the aid of a WDC, the necessary voltage may be calculated. When WE are set to 1, all data received from an input line is sent to that line's bit lines. The word "Write Enable" is highlighted at the very top of the code. Finally, access transistors provide the data to the proper memory cell. Before the WDC, each computer bit cell was required to have a particular value [17,18].

Conventional SRAM
The shifting of the 6T SRAMC is shown in Figure 6. Due to how much data they can store, "static RAM cells" are also known as SRAMCs. Six NM8/NM9 NMOS transistors and six CMOS inverters serve as access transistors for the SRAMC (PM6, PM7, NM6, and NM7). The cross-coupled inverters for each bit are constructed using transistors and SRAMC. The only possible values in the cell [19,20] are 0 or 1. In a bi-stable latching circuit, two inverters control six SRAMC transistors.

CTDSA
The sensing amplifier plays a key role in the cache memory's construction. Only one of the two-bit lines is wired to the power source during reading. A current sense amplifier comprises various parts that talk to one another [21][22][23].

Analysis of Result
In this section, the output of each circuit is described and rated. Figure 8 displays the SAEN, WL, and CMSA open and reading data. This sensing amplifier can read only the bit lines of SRAM cells. The bit lines provide data to V3 and V4.  Less power is needed as the resistance rises. A circuit's resistance impacts its size, functionality, and speed. In essence, it makes the spread of authority more challenging. To cut down on power usage when using a forced stack technique, CMSA uses the SRAM strategy shown in Table 3.

Conclusion
Researchers examined single-bit cache memory to determine its effectiveness. Single-bit cache memory comprises a write driver circuit, a static random access memory cell, and a current mode detection amplifier. Single-bit cache memories can consume less power using sleep transistors, forced stacks, and dual sleep on components like current-mode sensors and static random-access memories. In this study, it was discovered that SRAM cells consumed less power than single-bit caches.