A New Method to Index and Query Sets

1 Introduction

The problem of how to effectively index and query sets occurs in various computer applications:

Researchers in object oriented databases have among others stressed the need for richer data types, in particular set-valued attributes such as for example the set of keywords in a document, the set of classes a student is enrolled in, etc. Typi­ cal queries to such an enriched database require to determine all supersets or subsets of a given query. For example, given a set of classes C, to find all stu­ dents taking at least these classes the supersets of C need to be determined. Or as another example, given that a student has passed some basic courses C, which advanced courses become possible? The answer is found by retrieving all advanced courses whose prerequisite course set is a subset of C.

Machine learning is highly concerned with the utility problem, i.e., the problem of learning new knowledge in such a way that the learning costs do not exceed the savings in the system's performance that are achieved through learning. A key factor in a good learning algorithm is to effectively match sets of attributes against each other, for example in the form of preconditions of large sets of production rules. In order to decide which rules apply to a particular situation, all precondition sets have to be determined that are subsets of the query set describing the situation.

Artificial intelligence planning is concerned with the problem of constructing a sequence of ac­ tions that achieves a set of goals given a particular initial state in which the plan is scheduled for ex­ ecution. Even in its simplest form, the problem is known to be PSPACE-complete [Bylander, 1991], i.e., planning algorithms are worst-case exponen­ tial and techniques to effectively prune the search space are mandatory. Since millions of goal sets are constructed when searching larger state spaces for a plan, it is important to know in advance when a goal set can never be satisfied. This is the case when at least one subset of the current goal set has previously been shown to be unsatisfiable.

Modal logics are often formalized using la­ beled tableau methods, where one is sometimes confronted with infinite branches in the tableau. To guarantee termination, one needs to identify potential periodic chains of labels [Gore, 1997].

In its abstract form, these and other applications have to deal with the following problem: Given a set of sets S stored in some data structure and a query set q, does there exist a set s E S such that q 2 s (or sometimes q ~ s depending on the application). Though this seems to be a trivial problem to handle, its difficulty comes from the dimensions in which it occurs: S will quite often contain millions of sets and some applications re­ quire to handle a huge sequence of queries Qi over a dynamically changing S .

2 The UBTree Algorithm

The key to a fast set query answering algorithm lies in an appropriate data structure to index a large number of sets of varying cardinality.

2.1 The UBTree Data structure

A node (see Figure 1) N in UBTree consists of three components:

• N.e : the element it represents
• N.T : the sons, a set of other tree nodes
• N.EoP : the End-of-Path marker.

The UBTree is now simply represented by a set T of such nodes and can be seen as a forest. Note that we are speaking about sets of tree nodes, i.e., nei­ ther the number of trees nor the number of sons any node can have is limited. That is where the UBTree got its name from: Unlimited Branching Tree.

Based on this data structure, the following func­ tions. will be defined below:

• insert( sets, tree T) inserts a sets into the tree T.
• lookup_first(set q, tree T) tells us whether any subset s ~ q is stored in T.
• lookup..subs(set q, tree T) determines all sub­ sets for a given query set q from T.
• lookup..sups(set q, tree T) determines all supersets for a given query set q from T.

The only assumption on which our algorithm relies is the existence of a total ordering over all elements that can possibly occur in the sets.

2.2 The insert Function

To insert a sets into a forest T, the insert function (Figure 2) creates a path starting in T correspond­ ing to that set. In principle, this path is just a se­ ries of connected tree nodes corresponding to the ordered elements of s.

Definition 1 Let s = { e0 , . . . , en-1} be an or­ dered set, T be a forest.

A path <P(s) in T corresponding to sis a non-empty tuple of tree nodes No, ... , Nn- 1 such that

When the insert function is called, T is initial­ ized with the root nodes of the forest . The func­ tion then tries to look up the elements of s one af­ ter the other (remember that the sets get ordered before they are inserted) and, doing this, follows paths that have been created by other, previously inserted sets. If there is no corresponding node for some element e; in the set T of nodes (implying that no set starting with { e0 , ... , e;} has been in­ serted before), it creates a new path at that point, i.e., a new son is added to the current node N. Fi­ nally, the last node (the one that represents en-1) is marked as the end of a path. Note that we as­ sume s to be non-empty, i.e., n > 0, otherwise there would be no element en_1 and, consequently, no node N to represent it. 1

Figure 3 shows how a forest T with two trees evolves when the 4 (already ordered) sets s0 = {eo,e1,e2,e3}, s1 = {eo, e1,e3}, s2 = {eo,e1,e2}, and s3 = { e2 , e3 } are inserted one after the other.

2.3 The lookup Functions

We now show how the set of sets S stored in a forest T can be used to answer questions about the query set q.

Let us begin with the lookup_first function, which decides if there is any set s E S in T with s ~ q. The function simply tries to reach a node N in the tree that is marked as the end of a path, using the elements in q as "money" to pay its travel costs. This is to say, given a set of tree nodes T and a set q = {eo, ... ,en-d, it finds all nodes NET corresponding to an element ei E q. If any such N is marked as the end of a path, lookup_first suc­ ceeds in finding a subset to the query set. Oth­ erwise, the ongoing search is a recursive instance with the set of sons, N.T, and the remaining el­ ements { ei+ 1, . . . , en-1} as parameters. 2 See Fig­ ure 4 for a formal description of the lookupJirst function.

1 We make this assumption just for simplification, the UBTree algorithm can easily be extended to deal with possibly empty sets.

M :=all nodes NET that match an element e; E q while M is non-empty do choose a node N E M if N is the end of a path then succeed endif I· else: call search on next tree and remaining elements ·I lookupJirst(N.T, { ei+l , . .. , en-d) end while I· all elements have failed ·I fail

The function is initially called on the (previously ordered) query set q and the forest T. It is impor­ tant to notice and crucial to the performance of UBTree that , in using the "money" method, large fractions of the search space can be excluded: for a query set q = { q0 , .. . , qn_1} of length n, 2n pos­ sible subsets need to be considered. Half of them (those that contain q0 ) lie in the tree rooted in the node corresponding to q0 . If there is no such node, the search space is immediately reduced to 2n- 1 .

Note that the function is non-deterministic with respect to which matching node N E M is chosen first. A possible heuristic could store in each node the distance to the next end-of-path node. The node with the least distance could then be tried first. This distance information can also be used, and in fact is used in our implementation to cut unnecessary branches out of the search tree. If the distance stored in a search node N is greater than the number of elements we have left at that stage of search, we can back up (i.e., fail) right away. In this case the query set does not contain enough elements to reach an end-of-path marker.

The lookup...subs function, as given in Figure 5, works in a very similar way. Instead of termi­ nating after identifying one end-of-path marker, i.e., the first matching subset, it has to work its way through all nodes it can reach. Again, the function uses the "money" method, i.e., passes only those nodes for which it has matching elements in the query. Every time it finds a node that is the end of a path, it adds the path ending in this node to a global answer set Q. The function is initially called with the ordered query set q and the for­ est T as parameters, the answer set is initialized with the empty set Q := 0. Upon termination of lookup...subs, Q contains all sets s E S with s ~ q.

2 No nodes representing any of the elements in {eo, . .. , ei} can exist in a subtree starting in e; due to the total ordering of the elements.

M := all nodes N E T that match an element e; E q for all nodes N E M do if N is the end of a path then Q := Q U { the set on the path toN } endif lookup.subs(N.T, { ei+l, .. . , en-d) endfor

Finally, we show how to retrieve all supersets s E S, s 2 q from T. This can be done by finding all paths in T that comprise the path corresponding to q as a (possibly disconnected) subpath. The lookup...sups algorithm is shown in Figure 6. Again, the answer set is initialized with Q := 0 and the function is called with the ordered query set q and the forest T as input parameters.

M :=all nodes NET matching e withe< eo call lookup.sups(q, N.T) on all nodes N E M if a node N E T corresponds to eo then if {e1, . .. ,en-d i= 0 then lookup.sups({e1 , .. . ,en-d, N.T) else P := all end-of-path nodes N' in the tree under N Q := Q U {sIs is represented by a node N' E P} endif endif

At each stage of the search, lookup ...sups does the following: First, it searches all trees that start with an element preceding the first element in the query set; these are trees that can possibly contain nodes for the whole set. If there is a node N E T that di­ rectly corresponds to the first element in the (pos­ sibly already reduced) query set, the query set gets further reduced by this element. Now the function only needs to find matching nodes for the remain­ ing elements. If there are no such elements left, the search has succeeded, i.e., every end-of-path node that can be reached from N will yield a superset to the query. Otherwise, search needs to be continued with the reduced query set and the appropriate set of nodes.

3 Theoretical Properties of UBTree

We state the soundness and completeness of the lookup_first function in the following theorem.

Theorem 1 Let T be a forest UBTree that has been constructed by iteratively inserting all sets s E S. The lookupJirst function, as defined in Section 2, succeeds on a query set q and T if and only if there exists a set s E S with s ~ q.

A similar theorem stating the soundness and completeness of the lookup...subs and lookup...sups functions can be proven.

To analyze the runtime behavior of the lookup...subs and lookup_first functions, let us re­ examine the algorithm in Figure 5 from a differ­ ent perspective. At each stage, the function tries to find a node N in T that matches the first el­ ement e0 of q. If this node is found, there is a new recursive instance, with N.T and q \{eo} as parameters; afterwards, the function works on T and q \ { e0 }. If on the other hand, no node in T matches e0 , the function simply skips eo and con­ tinues with q \ { e0 }. From these observations, we get the following recursive formula for the num­ ber of search nodes that are visited by lookup...subs (which is an upper limit to the number of nodes visited by lookup_first):

Here, pN denotes the probability that the node N matching e0 is in T, and E(i), consequently, de­ notes the expected number of visited search nodes with i elements to go. Obviously, E(1) = pN_ It is easily proven that the recursion results in:

The probability pN at each stage of the search is equal to the probability that there is a set s E S which starts with the elements that would be represented on a path to N. It is an open question, how an upper limit for pN can be determined. In the worst-case, when all nodes N are present in the tree, we get pN = 1 and E(n) = 2n -1 search nodes for a query set of size n. 3

3 It should be noticed, that, when matching rules or determining unsatisfiable goals in planning, the query sets are small while lSI is very large. Thus, searching 2n nodesis still much better than checking lSI sets for inclusion.

The number of nodes visited by the lookup...sups function is only dominated by the total number of nodes that are in the forest. Let emax denote the maximal element with respect to the total order­ ing, i.e., e < emax for all e f emax· Trying to find all supersets of the query set {emax}, lookup...sups has to search the whole structure. Consequently, we determine an upper bound for the total number of nodes in the tree.

Theorem 2 Let T be a forest in which exactly the sets s E S have been iteratively inserted. If the total number of distinct elements in all of the sets s E S is P, then the total number of nodes in T is at most 2P- 1.

The worst case occurs if and only if all sets con­ taining emax are contained in S.

4 Empirical Evaluation

To demonstrate the effectiveness of the approach, we discuss examples taken from the use of UBTree in the IPP planning system [Koehler et al., 1997]. Following [Hellerstein et al., 1997], the workload for UBTree is determined by the following factors:

• the domain, which is the set of all possible sets, i.e., given P logical atoms to characterize states, the domain comprises 2P sets,
• an instance of the domain is the finite subset S ~ 2P that is currently stored in T,
• the set of queries, which is the set of goals that are constructed during planning.

Note that the workload is dynamic. Starting with an empty UBTree structure T, a generated goal set is added if no plan was found by the plan­ ning system, i.e., T is monotonically growing con­ taining lSI sets at the end.

Since it is extremely difficult to make distribu­ tion assumptions for instances and query sets in a planning system, we use the following parameters to characterize the size of a UBTree:

• P : the total number of distinct logical atoms inS.
• lSI = l{so, ... , Sk-dl : the number of all stored sets.
• ITI : the total number of nodes in the forest T.
• C = E~~J' 1 1 s, 1 : the storage cost, which would be equal to 1 in a trivial data structure simply representing all sets separately.
• IQI : the total number of queries that have been answered during the process.

Figure 7 shows the parameters for forests of in­ creasing size in two different planning domains (the blocksworld shown in the upper part and the brief­ case world shown in the lower part of the table).

The larger UBTree grows (reflected by increasing lSI and ITI) and the smaller P is, the better values are obtained for the storage cost.

Figures 8, 9, 10, and 11 illustrate the runtime be­ havior of the query functions reflected in the num­ ber of searched nodes for a given query-set size lql and lSI. Note that lSI is shown on a logarithmic scale in all figures.

Figure 8 indicates that the lookupJirst func­ tion needs significantly less search time on queries where it can retrieve a subset than on those where it must fail. In fact, the average runtime behavior in the positive case was linear in the size of the query set and completely independent of the in­ stance size throughout all our experiments. The function never visited more than an average of lql * 2.5. search nodes on positive queries. In the general case, the behavior tends to be logarith­ mic in the instance size. The behavior with re­ spect to the query-set size varied in different do­ mains: sometimes clearly polynomial, even sublinear; sometimes, as in the case of Figure 9, possi­ bly exponential, but to a small degree( as indicated by equation 1).

A behavior as shown in Figure 10 is typical for the lookup..subs function: clearly logarithmic in lSI and probably exponential, to a small degree, in the query set size.

Figure 11 shows a typical picture for lookup ..sups that we found in all investigated domains. It turns out that the performance of this function decreases for small query sets. This happens because small sets are likely to have more supersets than big ones. The behavior with respect to the instance size tends to be linear. Note that again, Sis shown on a logarithmic scale and that the z scale is dif­ ferent here.

5 Related Work

In order to deal with set queries in planning, a partial subset test that only considers sets of size /q/ - 1 to a given query set of size /q/ has been developed in [Blum and Furst, 1997]. Obviously, this can be done in linear time, but such a test must be inherently incomplete. With UBTree, a complete test is available that runs in almost linear time in practice despite its exponential worst-case behavior.

For databases, RD trees [Hellerstein and Pfeffer, 1994) have been proposed as an effective means in answering superset queries, but they are very limited in handling subset queries. In contrast to UBTree where a set is spread over several nodes, an RD tree is organized such that the leaf nodes contain the sets and non-leaf nodes contain super­ sets (of different size) of their children nodes to effectively guide search. To handle subset queries, inverted RD trees are used which are equivalent to RD trees on the complements of the base sets. Two serious problems occur in this approach. First, a non-leaf node needs to be recomputed if a new set is inserted into one of its leaf-children. Second, even if only small sets are stored in the leaves, their complements and their supersets in the cor­ responding parent nodes grow impractically large. UBTree avoids both problems.

An optimized implementation of the RETE pat­ tern matching algorithm [Forgy, 1982) to handle large numbers of production rules is described in [Doorenbos, 1994]. The indexing structure for pre­ conditions of rules is similar to UBTree, but the way how the elements of the query set match the stored sets in the indexing structure is quite dif­ ferent because the preconditions can contain vari­ ables, while UBTree deals with sets of ground atoms only. Thus, the problem of null activations, where rule nodes are activated though not all of their preconditions are satisfied by the current in­ put, can occur in RETE, but not in UBTree, which would index all ground instances of pattern match­ ing rules instead.

6 Conclusion

Depending on the particular requirements of an application, UBTree can be further optimized. For example, if one is only interested in keeping mini­ mal sets, all non-minimal sets can be pruned from the tree. Furthermore, if all sets s E S are con­ structed from a finite and fixed domain of ele­ ments, an implicit bitmap representation of the sets can further reduce memory consumption and query times.

As we saw in Section 4, the worst-case behav­ ior of the algorithms, especially of the lookup_sups function, depends on the ordering of the elements. In application areas where one has information about the likelihood of appearance of the elements in any set s, it should be possible to generate a total ordering that minimizes the number of tree nodes. One simply orders elements with high like­ lihood of appearance before those with low values. Thereby, both storage and search costs can be re­ duced.