Improving Search Using Indexing: A Study with Temporal CSPs

1 Introduction

Many problems in a variety of application domains can be modeled and solved as constraint satisfaction prob­ lems (CSPs). A binary CSP is defined by:

• a set of n variables v 1o ··· , v"
• for each variable v; a domain D; of m; values: { Un, ... ,uim;}
• for each pair of variables { v;, v1}, i,tcj, a binary constraint CiJ, which is a subset of D;xD1.

An assignment { v; ~ u;a,, v 1 ~ u Ja 1 } is consistent if ( u u . ) E C.. The goal is to find one or all solutions, ta;' JOj lj i.e., n-tuples ( u 1 " 1 , ·· , U;a, , .. , u Ja 1 , ·. , U 11 a.,) such that for each{ij"} i,tci {v . ~u v . ~u . }isconsistent. JU j · · ,

' ' J' l W; ' ) Several systematic search heuristics that aim to minimize the number of consistency checks have been pro­ posed. Based on the general idea of backtracking, these methods try to improve the backward step, e.g. back­ jumping, or the forward step, e.g. for~ard check~ng [Haralick and Elliot, 1980]. Hybrid algonthms combine different types of backward and forward steps [Prosser, 1993] . The aforementioned search methods apply ex­ haustive search in the variable domains while assigning or pruning values. When the number of potential values for a variable is small (i .e. less than 100) linear scan suffices; for large domains, however, the overhead can be significant due to repetition of s~an . . ..

In this paper we study how Indexing may be utilized by CSP algorithms to direct search and avoid linear scan of domains. As an application, we deal with CSPs, where the values are temporal intervals and the constraints are disjunctions of temporal relations as defined in [Allen, 1983]. Such problems may occur in planning or temporal databases. A previous work that uses indexing in tempo­ ral databases is [Dean, 1989]. In contrast to our method, where intervals are indexed according to their position in space, that method directs search using a conceptu~l hi­ erarchical structure, the discrimination tree. Algonthms that combine CSP search and indexing to facilitate re­ trieval of structural queries in large spatial databases were presented in [Papadias et al., 1998] .. He:e, we e~­ tend this work by investigating the applicatiOn of di­ rected search in temporal databases and study the per­ formance gain of directed search under various problem conditions using different CSP algorithms.

The rest of the paper is organized as follows. Section 2 introduces data structures and search methods for tempo­ ral intervals. Section 3 shows how conventional methods for solving CSPs can be modified to accelerate searc.h using indexing. Section 4 experimentally compares di­ rected search algorithms with methods that do not use indexing. Finally, Section 5 concludes the paper with directions for future work.

2 Temporal CSPs

The class of problems that we deal with in this paper includes CSPs where domain values are well defined intervals in discrete time, and each binary constraint CiJ is a disjunction of the permissible set of Allen's [1983] temporal relations between v; and v 1 . Notice that the c.ur­ rent issue is different from traditional temporal reasomng problems (e.g. [van Beek, 1992]) where the ain: is to identify a consistent scenario for a set of continuous variables, given information about their relationships. Here, we search into domains of intervals for variable assignments that satisfy the given constraints.

This temporal CSP can be solved by employing tradi­ tional search techniques. Each time a variable is visited, its whole domain has to be scanned in order to identify consistent assignments. When the variable domains are small , classic CSP algorithms behave well, but as t~e domain size increases, linear scan for consistent values IS expensive. .

CSP algorithms can avoid linear scans by employmg interval-based data structures that index the variable do­ mains . The search for solutions can be directed upon satisfaction of the temporal constraints, using the data structure to minimize the number of consistency checks. Since search through the domains is repeated a large number of times, directed search has a significant effect on performance.

For the indexing of variable domains we use R-trees [Guttman, 1984], a data structure aimed at indexing multidimensional rectangles in spatio-temporal data­ bases . The data rectangles are stored into leaf nodes; each intermediate node contains a pointer to a lower level node and the minimum bounding rectangle of the rectangles in this node. We chose R-trees beca~se they are becoming a standard in both research and mdust~y (e .g., Illustra, Informix) due to their efficie~cy, dynam1c nature and relatively simple implementatiOn. Alterna­ tively, any interval-based data structure, such as interval trees and segment trees [Preparata and Shamos, 1985], can be employed.

Figure l illustrates how a !-dimensional R-t~ee can b_e used for interval storage and retrieval, assummg maxi­ mum tree node capacity equal to 3. The data intervals (a to k) are stored in the leaf nodes. Artificial intervals in the higher tree nodes are formulated by grouping inter­ vals from the level below (e.g., a,b and fare grouped in A). The end points of an intermediate node i?terval ar_e the leftmost and rightmost end points of the mtervals 1t indexes. The R-tree for a static set of intervals can be built in a bottom-up fashion after sorting them with re­ spect to one end-point, e.g. in this example the left one

(R-tree packing). Thus, the R-tree construction for n in­ tervals costs O(nlogn) .

R-trees are very efficient in answering range intersec­ tion queries, i.e., find all intervals that intersect (share a common point with) a query interval. In addition, ~he hierarchical nature of R-tree facilitates general selectiOn queries, i.e., retrieval of intervals that satisfy any tempo­ ral condition with respect to a query interval. As an ex­ ample, consider the query: "find all intervals that start immediately after interval b" applied to the R-tree of Figure l. Retrieval starts from the root of the tree: due to the relative positions of b and 2, there can be no mterval indexed by the root entry 2 that starts immediately after b. Thus the sub-tree under 2 is pruned. On the other hand, entry 1 can contain qualifying intervals an? is re­ cursively searched. Both entries A and B may pom~ to _a query answer and they are followed; th~ only sol~tlon IS interval c. Typically, the .retrieval cost IS proportional to the number of solutions; when this is small , worst case performance is logarithmic to the number of stored inter­ vals .

Let q=[q.left,q.right] be a query interval; Table l shows, for each temporal relation, the bounding co~di­ tions that an intermediate-level interval I should sat1sfy in order to potentially point to a query answer x. This is the criterion of following an R-tree node during retrieval. In the previous example (b meets x) the intermediate nodes to be searched should satisfy /.left ~ b. right and 1. right > b. right. Intermediate interval 2 is pruned . be­ cause it violates 2.left ~ b. right. When the query IS a disjunction of temporal relations, the disjunction of ~he bounding conditions is applied during searc~. For ~n­ stance if the search predicate is starts v dunng v fzn­ ishes, 'the bounding conditions for an intermediate level entry I are /.leftS: q.left and /. right~ q.right. Although for the examples throughout the paper we use the tree of Figure 1, for our implementation we assume that each variable domain is different and indexed by a separate R­ tree. The next section describes algorithms that use these indexes to prune the search space (the methods can be easily applied when some domains/trees are common).

3. Directed Search for Temporal CSPs

Classic local consistency methods, like arc and path consistency, perform well for small domains because in this case there is a high probability that a v~lue will be pruned. However, for large variable domains and dense constraint graphs usually they do not pay-off. Therefore, we do not consider conventional local consistency meth­ ods for pre-processing, but apply the temporal network maintenance algorithm from [Allen, 1983] prior to search in order to infer undefined constraints and refine the ex­ i~ting ones. This is equivalent to a path consistency algo­ nthm that does not check value consistency, but con­ straint graph consistency, and its complexity is, there­ fore, independent from the domain sizes. For instance, consider a constraint graph of three variables, where C12 =meets, C23 =during, and C/3 is undefined. The implied constraint C13 is then overlap v starts v during. If C13 was defined, then the updated constraint is C13 1\ {overlap v starts v during} . Notice that this reasoning method detects inconsistency prior to search, e.g. when c/3 1\ {overlap v starts v during)= 0 .

Efficiency of CSP search depends on the order by which variables are instantiated [Dechter and Meiri , 1994]. The usual rule for static variable ordering (SVO) schemes is to "place the most constrained variable first". A simple way to apply this rule is to sort the variables in d~crea.s ing order of their degree in the constraint graph. Smce m our problem the constraint edges do not have the same tightness, we follow another method: instead of "adding I" for each edge that goes out from a variable, we add a weight that represents the tightness of the con­ straint edge. For a temporal relation r, weight(r) is the inverse of the probability 1 P(r) that r will be satisfied between two arbitrary intervals. In typical cases, the re­ lation with the largest weight is equal, and the relations with the smallest, before and after. If a constraint is a disjunction of primitive relations, the weight is the in­ verse sum of the relation weights that participate in the disjunction, e.g.,

The weight of a variable is then the sum of the weights of all constraint edges adjacent to it. SVO will instantiate the "heaviest" variable first and the one with the smallest weight last. Whenever dynamic variable ordering (DVO)

1 The probabilities of temporal relations can be estimated either by sampling the input data, or by using probabilistic estimation for­ mulae given the distribution of interval positions and sizes.

is employed, the above method is used to find the vari­ able with the largest weight and place it first. The order ?f subsequent variables is dynamically changed accord­ mg to their domain sizes during search.

3.1 Directed Search Backtracking

Integration of directed search into backtracking (BT) is r~ther simple. Whenever a variable v 1 is visited, its con­ Sistent values are retrieved from the corresponding R­ tree R 1 by applying the instantiations of the previous vanables v;, i<j, as query intervals, and the constraints ~ii as retrieval conditions. During retrieval, the conjunc­ tiOn of bounding conditions, defined by each v;, direct the search at intermediate R-tree levels. At the leaf level, the entries that satisfy the constraint CiJ with each vari­ able v;, are retrieved as consistent values for v ·.

To clarify the retrieval procedure, consider the fol­ lowing example. Let the query overlap(v1,v3) 1\ over­ lapped by (v2,v3) and the instantiations v1 f- J, v2 f- h in Figure 1 (i.e., v3 should overlap f to the right and h to the left). In order to retrieve all consistent values for v3, first the bounding conditions (BC) according to v 1 and v2 are calculated using Table 1; BC13 = {!.left <fright and /.right> fright} and BC23 = {!.left < h. left and /.right> h. left}. The conjunction of the above constraints results in the bounding conditions {/.left <fright and / .right> h. left}, used to guide R-tree search. Retrieval starts from the root, where entry 2 is pruned as it does not satisfy 2.left <fright. Similarly, entry A violates A. right> h.left and the sub-tree below is pruned. Only intervals under entry B can satisfy both C13 and C23 . Finally, d and e constitute the consistent assignments for v3· Notice that the whole process costs 4 consistency checks at the in­ termediate levels and 6 at the leaf level (each interval under B is tested against both v1 and v2), whereas a linear scan would cost 14 consistency checks.

The above method can be applied with alternative forms of backtracking (e.g., backjumping, dynamic backtracking) using information about nogoods. In the next subsection we illustrate how forward checking can employ the index to prune the domains of future vari­ ables.

3.2 Directed Search Forward Checking

After a variable instantiation, forward checking (FC) marks in the domains of all future variables the values that are consistent with the current variable (check­ forward). When a subsequent variable is to be instanti­ ated only the marked values will be considered. This marking mechanism can be thought of as a linear index in the variable domain that points to the consistent val­ ues. Assume that an intermediate variable v; is being in­ stantiated. The domain of each future variable v 1 (i<j) has already been pruned by the instantiation of variables be­ fore v;. As the linear indexes of some variables may still be large, check-forward during instantiation of v; can be rather costly. For these variables we apply directed search using the R-tree and filter the results using the linear index. Filtering with respect to the linear index is needed, because directed search is performed on the whole domain (i .e. , an interval which satisfies the current constraint with v; may have been pruned out by a previ­ ous instantiation). The issue to be investigated is when to apply directed search instead of linear scan.

A good heuristic is to employ directed search at a fu­ ture variable only when the number of remaining consis­ tent values is large, and the search constraint is tight, so the search would benefit from the R-tree. For example, let c /3 =before and c23 =equal. After VI is instantiated, directed search is applied to prune the domains of v2 and v3 . When v2 is given a value it is worth applying directed search again while checking forward for consistent val­ ues of v3 , because the domain of v3 is still large and C23 is a tight constraint. The results of directed search that do not satisfy before with respect to the value of vI are filtered out. Now let C13 =equal and C23 =before. After vi is given a value, the domain of v3 is expected to be­ come very small; thus, during instantiation of v2> linear scan of D 3 is cheaper than using the tree.

This mechanism is called a double index, in the sense that we keep both the whole domain R-tree and the linear index of consistent values and use either both, or only the linear index. Directed search is applied when the ex­ pected number of values that satisfy the search condi­ tions is smaller than the number of values in the linear index . The number of retrieved values is estimated using the temporal relation probabilities . For instance, if CiJ = overlap , P(overlap) = 0.02 and ID 1 1= 1000, then 20 inter­ vals in the domain of v 1 are expected to be consistent with the value of a previous variable v;. If while instanti­ ating v;, the remaining consistent values of v 1 from for­ mer checks is smaller than 20, linear scan at checkJorward(v;,v 1 ) will be preferred to directed search.

Alternatively, versions of the variable R-trees could be maintained at each instantiation level, where only con­ sistent values would remain in the data structure, and search could be performed at each check-forward. We do not use this method because dynamic operations on data structures (i .e. insertion, deletion, construction) are usu­ ally expensive.

4 Experiments

In this section we compare the performance of directed BT (dirBT) and directed FC (dirFC) with plain versions of the algorithms based on linear scan. FC and dirFC use the fail first (FF) DVO heuristic [Haralick and Elliot, 1980] . BT and dirBT apply the SVO heuristic described in Section 3, because, as suggested in [Bacchus and van Run, 1995], BT with DVO does at least as much work as FC with DVO, thus it is just a FC-DVO algorithm with redundant checks .

The problems were randomly generated by modifying the parameters <n,m,p ~>P2> (see [Dechter and Meiri , 1994 ]), where n is the number of variables, m the cardi­ nality of the domains, pI the probability that a random pair of variables is constrained (constraint network den­ sity), and p2 the probability that a random assignment for a constrained pair is inconsistent (constraint tightness) . The centers of the intervals in the variable domains are uniformly distributed and their sizes take values with an average 1.5% of the workspace. The intervals in each domain are indexed by R-trees with node capacity equal to 20.

In order to identify the hard region of the problems we use the constrainedness measure [Gent et a/. , 1996]:

The hard region for an ensemble of problems is when K"" 1, whereas problems with K<< 1 and K>> 1 are easy and soluble and easy and insoluble, respectively. The denominator of eq. (1) denotes the size of the problem and Sol denotes the number of solutions in a random problem of the class. If the binary constraints are inde­ pendent, Sol can be estimated by:

where P( C; 1 ), as described in the previous section, is the probability that two intervals from D; and D 1 satisfy CiJ. The first product in (2) corresponds to the total number of n-tuples of intervals, while the second one to the probability that a tuple constitutes a solution. For acyclic networks the constraints are independent and (2) will give a good estimation of the problem solutions. When cycles exist the constraints are no longer independent, but applying (2) for the minimum spanning tree of the graph (w.r.t. the constraint tightness) will give an over­ estimation of the expected solutions .

We first tested the performance improvement achieved by the path consistency (PC) method of Section 3 for acyclic networks (pi = (n-1)/(n(n-1)/2) = 2/n), by run­ ning experiments for n=10 and m=1000, and several val­ ues of p2 around the hard region . For each value of p2 we solved an ensemble of 100 problems and measured the average cost for finding one solution. Usually, random CSPs are generated with every constraint having exactly the same tightness. Because this cannot be done for the current problem, we chose disjunctions of temporal rela­ tions which may be different for each constraint, but have average tightness within ±10- 4 of the target value p2. The hard region (K = 1) is when p2""0.99953. This large value of p2 is due to the large domain size and the spar­ seness of the graph. In general, problems with sparse graphs are easy [Dechter and Pearl, 1987] and the few existing constraints must be very tight in order to gener­ ate a small number of solutions.

Figure 2 shows the cost (in terms of consistency checks 2 ) of directed search BT and FC, with and without PC. The dotted vertical lines include the phase transition, i.e. the first ensemble that included an insoluble problem (left line) and the last ensemble that included a soluble one (right line). As expected, the performance gain of PC is significant since the inferred constraints drastically prune the search space. In the sequel we use PC for both directed search and plain versions of the algorithms. The nearest point to 50% solubility (crossover point) was at p2 = 0.99925 (K = 0.93748), where 54% of the problems were soluble.

The second set of experiments compares the cost of di­ rected versus undirected search for tree (p1 = 2/n) and clique (p1 = 1) graphs. The experimental settings are the same as in the previous experiments (n=lO and m=lOOO; each ensemble contains 100 problems for each value of p2 around the hard region) . Figure 3 illustrates the cost for tree graphs. The directed search versions outperform the original algorithms by more than one order of mag­ nitude. Tree constraint graphs can alternatively be solved by the application of arc consistency prior to search, which would lead to backtrack-free search [Dechter and Pearl, 1987]. This method is also expected to profit from indexing.

2 We consider as consistency checks the comparisons that take place at all levels of the R-trees.

For cliques, the hard region cannot be estimated using ( 1 ), due to the dependency of the constraints. In order to identify it, we experimented with various values of p2· The diagram of Figure 4 illustrates the behavior of algo­ rithms for a wide scope of tightness values. Notice that the hard region corresponds to a larger range of p2 than in the case of tree graphs . While the cost difference be­ tween directed and regular versions of the algorithms is again about an order of magnitude for large p2, their per­ formance converges as the constraints become loose. When p2 < 0.7 most of the constraints contain relations before or after. On the average, each such constraint prunes out around 50% of the values in a domain, and directed search is only about twice as fast as linear scan.

As a general conclusion, the performance gain of di­ rected search in comparison to linear scan grows with the constraint tightness p2· dirFC is, as expected, more effi­ cient than dirBT due to its relevance with FC which in most cases outperforms BT. In the sequel we focus on the performance gain of dirFC with respect to FC for various problem settings.

The next experiment compares FC and dirFC for n=10, clique topology, and various values of m and p2· Figure 5 shows how many times dirFC is faster than FC (average of 50 instances per experimental setting). The gray hori­ zontal lines present the phase transition for each m, and the symbol on the line indicates the position of the crossover point. With the exception of m=100-200 and very small tightness values (p2<0.65), dirFC outperforms FC several times . For small domains the constraints should be very tight in order for the intermediate R-tree node comparisons to pay-off. However, directed search is intended for large domains (e.g., in spatia-temporal databases the cardinality often exceeds 10 5 ), and in such cases the performance gain is significant. For this ex­ periment, we limited m to 2000, so that FC could termi­ nate in reasonable time.

In order to test the implication of the number of vari­ ables, we fixed m=lOOO, p2 to be around the crossover point, the graph topology to clique, and generated 100 random problems for several values of n. Table 2 pres­ ents, for each ensemble, the value of p2, the percentage of soluble problems, and the mean consistency checks of FC and dirFC. The last row of the table shows how many times dirFC was faster than FC. As the number of vari­ ables increases, the value of p2 at the crossover point decreases. As a result, the costs of dirFC and FC con­ verge due to the relaxation of constraints which deterio­ rates R-tree search, making it comparable to linear scan.

5 Discussion

This paper studies a specific CSP problem, where vari­ able domains are large collections of well defined inter­ vals and constraints are temporal relations. We show how systematic CSP algorithms can take advantage of indexing to accelerate search. Although we experimented with two representative algorithms, chronological back­ tracking and forward checking, directed search can be applied with a variety of algorithms and heuristics (e.g. arc consistency). In ty~ical database applications, where m is in the order of 10 or above and n<10, the perform­ ance gain of directed search is large.

Application of data structures is not limited to the temporal CSP discussed here. Any problem, where vari­ ables have large domains and the nature of constraints facilitates directed search, can benefit from it. This par­ ticularly applies for spatial and multimedia databases where several types of content-based queries can be modeled as CSPs (e.g., find all triplets (v1>v2.v3) of ob­ jects such that v2 is inside v1, and v1 is northeast of v3) . An alternative approach that solves the above problem by hierarchically applying CSP algorithms at each R-tree level is described in [Papadias et al., 1999].

Acknowledgement

This work was supported by grant HKUST 6151/98E from Hong Kong RGC and grant DAG97 /98.EG02.