Sparse-Memory Graph Search

1 Introduction

Graph search algorithms such as Dijkstra's algorithm and A* use an Open list to store nodes on the search frontier, and a Closed list to keep track of already expanded nodes. The Closed list performs two important functions.

1. It allows the optimal solution path to be reconstructed after completion of the search by tracing pointers back­ wards from the goal node to the start node.
2. In graph search problems, it allows nodes that have al­ ready been reached along one path to be recognized if they are reached along another path, in order to prevent duplicate search effort.

Although both functions are important, storing all expanded nodes in a Closed list can quickly use all available memory.

If one is willing to give up the ability to recognize when the same node is reached along different paths, IDA* and RBFS can solve search problems in linear space [Korf, 1985; 1993]. Related search algorithms provide a limited abil­ ity to prevent duplicate search effort by storing a limited number of expanded nodes [Reinefeld and Marsland, 1994; Miura and Ishida, 1998]. In complex graph search problems with many duplicate paths, however, an inability to prevent all duplicate search effort often leads to poor performance.

Fortunately, it is not necessary to store all expanded nodes in a Closed list in order to eliminate all duplicate search ef­ fort. It is only necessary to store enough nodes to form a "boundary" in the search graph that prevents previously closed nodes from being revisited. This is the strategy adopted by a pair of recent search algorithms [Korf, 1999; Korf and Zhang, 2000], which are related to earlier work on reducing the memory requirements of dynamic program­ ming algorithms for sequence comparison [Hirschberg, 1975; Myers and Miller, 1988]. If not all expanded nodes are stored in a Closed list, an alternative method of solution extraction is needed- since closed nodes along an optimal solution path may no longer be in memory when the search ends. So, these algorithms preserve information about nodes that are in the middle of a solution path. After the search ends, they use this information to divide the original problem into sub-problems - employing a divide-and-conquer strategy to recursively re­ construct an optimal solution path. This approach to reduc­ ing memory requirements results in an algorithm with two distinct phases; the first phase searches from the start to the goal node, and the second phase uses a divide-and-conquer method to reconstruct an optimal solution path.

In this paper, we describe some improvements of this search strategy. Earlier search algorithms that use this strat­ egy do not store a Closed list at all [Korf, 1999; Korf and Zhang, 2000]. Instead they include extra information in open nodes, and even insert additional nodes into the Open list, to ensure that it forms a "boundary" that prevents "leaks" back into the closed region. Instead of adding information to the Open list, our algorithm preserves some already ex­ panded nodes in a Closed list - but only enough to create a boundary and allow efficient solution reconstruction. Much of the closed region of the search can be removed from mem­ ory. Thus, we call this a sparse representation of the Closed list, and a sparse-memory approach to graph search. We show that it results in a more flexible approach to reducing memory requirements that offers several advantages.

2 Background

The most closely related algorithms to the search algorithm we introduce in this paper are Divide-and-Conquer Bidirec­ tional Search (DCBS) [Korf, 1999] and Divide-and-Conquer Frontier Search (DCFS) [Korf and Zhang, 2000]. Although both are general graph-search algorithms, they were devel­ oped as an approach to performing multiple sequence align­ ment, and the memory-saving technique they use was first used by related dynamic programming algorithms for sequence comparison [Hirschberg, 1975; Myers and Miller, 1988]. To provide some perspective, we begin with a brief description of the multiple sequence alignment problem. For a detailed description of this problem, we refer to our refer­ ences.

2.1 Multiple sequence alignment

Alignment of multiple DNA or protein sequences is an im­ portant problem in computational biology. It provides a way to measure the similarity between sequences and detect re­ lated segments. Alignment involves inserting gaps into se­ quences in order to maximize the number of matching "char­ acters." lt is well-known that this problem can be formal­ ized as a shortest-path problem in a n-dimensional lattice, where n is the number of sequences to be aligned. The number of nodes in the lattice is zn' where l is the aver­ age length of sequences, and thus grows polynomially with the length of sequences, and exponentially with the num­ ber of sequences. Although dynamic programming is the traditional method for solving this problem, A* has been shown to outperform it by using an admissible heuristic to limit the number of nodes in the lattice that need to be ex­ amined to find an optimal alignment [Ikeda and Imai, 1999; Lermen and Reinert, 2000]. But given the large number of nodes that usually must be examined, memory is a bottleneck, and techniques for solving this problem in reduced memory can be very helpful.

2.2 Divide-and-conquer frontier search

Both Divide-and-Conquer Bidirectional Search (DCBS) [Korf, 1999] and Divide-and-Conquer Frontier Search (DCFS) [Korf and Zhang, 2000] use the same strategy for reducing memory requirements. The difference is that DCBS uses bidirectional search and DCFS uses unidirectional search. Korf and Zhang [2000] find that unidirectional search results in better performance, and so we refer to DCFS in the rest of this paper.

DCFS reduces memory requirements by storing only the frontier nodes of the search, not the interior nodes - that is, by using an Open list but not a Closed list. Because it does not use a Closed list, DCFS must use some other method to avoid duplicate node expansions and to extract an optimal solution path at the end of the search. The problem of avoiding dupli­ cate node expansions is particularly important in the case of multiple sequence alignment because there are combinatori­ ally many paths from the start node to any other node. For this reason, linear-space search algorithms that do not test for duplicates, such as IDA*, have "pitiful results" (in the words of Korf [ 1999]), when used for multiple sequence alignment. Even bounded-memory search algorithms that detect some but not all duplicates have been reported to perform poorly on this problem [Yoshizumi et al., 2000].

To avoid duplicate node expansions, DCFS uses the fol­ lowing techniques to prevent the search from "leaking" back into the closed region, that is, to prevent closed nodes from being re-generated. First, it stores in each node a list of for­ bidden operators. This list includes one operator for each neighbor (predecessor or successor) of this node that has al­ ready been generated. When the node is later selected for expansion, only operators that are not among the forbidden operators are used to generate its successor nodes. This pre­ vents the search from re-generating nodes that may have been already closed and removed from memory. However, a com­ plication arises in the case of directed graphs - in particu­ lar, directed graphs in which a node can have predecessors that are not also potential successors. If a node is expanded and removed from memory before all of its predecessors have been generated and inserted into the Open list, it can be re­ generated if one of these predecessor nodes is later expanded. To prevent this, DCFS modifies the Open list in a second way. When a node is expanded, it generates not only its successor nodes, but all of its predecessor nodes- even if the search has not yet found a path to these predecessor nodes. Ifthere is not yet a legal path to these predecessor nodes, they are assigned an infinite f-cost to prevent them from being expanded until a legal path is found.

To make it possible to reconstruct the solution path at the end of the search, DCFS modifies nodes in a further way. In each node past the midpoint of the search, it stores all in­ formation about a node on its path that is about halfway be­ tween the start and goal node. Then, when the search is com­ pleted, DCFS knows a middle node on the optimal solution path, and can reconstruct the solution path by a divide-and­ conquer approach. Using the same search algorithm, it recur­ sively solves the subproblems of finding an optimal path from the start node to the middle node, and then from the middle node to the goal node. This recursive method of solution re­ construction is essentially the divide-and-conquer idea first proposed by Hirschberg [1975].

2.3 Limitations

Korf and Zhang [2000] show that DCFS can be very effec­ tive in "problem spaces that grow polynomially with prob­ lem size, but contain large numbers of short cycles," includ­ ing path-planning in two-dimensional grids and multiple se­ quence alignment, assuming a small number of sequences. They acknowledge that their search algorithm is not as ef­ fective in an "exponential problem space with a branching factor of two or more." In that case, they explain, the Open list is much larger than the Closed list and "not storing the Closed list doesn't save much." In fact, the multiple sequence alignment problem is an exponential problem space (and NP­ complete [Just, 2001]), when the number of sequences to be aligned is not bounded. Its branching factor is 2n -1 (where n is the number of sequences), and the size of the Open list can dwarf the size of the Closed list when aligning as few as five or six sequences. This problem is well-known and has moti­ vated development of techniques for reducing the size of the Open list when using A* to align multiple sequences. These include use of an upper bound to prune open nodes that can­ not lead to an optimal solution [Ikeda and Imai, 1999], and use of partial node expansions [Yoshizumi et al., 2000] .

As it turns out, it is difficult to combine DCFS with tech­ niques for reducing the size of the Open list without creating inefficiencies, or even "leaks" back into the closed region. It is possible to combine DCFS with Partial Expansion A*, a technique for reducing the size of the Open list by allowing partially expanded nodes [Yoshizumi et al., 2000]. This can be beneficial in some cases. But allowing nodes to be partially expanded has the effect of reducing the number of nodes that are closed. In turn, this reduces the memory-saving effect of DCFS by reducing the number of nodes eligible to be re­ moved from memory, as our experimental results will show.

Another approach to reducing the size of the Open list is to prune open nodes when their f -cost is greater than an up­ per bound on the optimal f -cost, as in Enhanced A* [Ikeda and Imai, 1999]. Because this technique does not reduce the number of closed nodes, the idea of combining it with DCFS appears more promising. However, it introduces other dif­ ficulties. Recall that DCFS generates all predecessors of a node when it is expanded, even if it has not yet found a path to these predecessors. If nodes are pruned from the Open list, no path may ever be found to these extra nodes, and the Open list may become cluttered with useless nodes that can never be removed. In directed graphs with the special prop­ erty that the set of successors of each node is disjoint from the set of predecessors, such as the search graph of the multiple sequence alignment problem, this inefficiency is the only neg­ ative effect of pruning the Open list. But in directed graphs that do not share this property, and in all undirected graphs, pruning nodes from the Open list can also result in "leaks" back into the closed region, as follows. The first time a node is generated, there is no guarantee that the best path to it has been found. So, if it is pruned using an upper bound, it may later be re-generated if a better path to it is found. But since the forbidden operators associated with the node when it was first generated were lost when it was pruned, a node that was previously closed could be re-generated.

The difficulty of combining DCFS with techniques for re­ ducing the size of the Open list is a significant limitation. Another potential limitation worth mentioning is the over­ head for storing a list of forbidden operators in each node. For problems with a small branching-factor, this overhead is slight. But for the multiple sequence alignment problem, this overhead grows as the number of sequences grows. Recall that the number of operators (i.e., the branching factor) of multiple sequence alignment is 2n - 1, and DCFS stores in­ coming as well as outgoing edges in the list of forbidden op­ erators. Thus, the total number of edges incident to a node is (2n - 1) x 2 = 2n+1- 2. Although Korfand Zhang [2000] claim that the space complexity of DCFS for multiple se­ quence alignment is O(zn-l ), compared to the O(zn) space complexity of A*, this claim rests on the assumption that a node takes constant storage. As n increases, the storage re­ quired for the list of forbidden operators increases exponen­ tially. In fact, the space complexity of DCFS for mulitple sequence alignment is 0(2nzn-l ), and its advantage over the O(ln) space complexity of A* disappears when n > log2l.

3 Sparse-Memory Search Algorithm

The algorithm we describe in the rest of this paper adopts a strategy for reduced-memory search that is similar to the strategy used by DCFS. However, it implements this strategy in a simpler way that is more compatible with techniques for reducing the size of the Open list, and does not require storing lists of forbidden operators in nodes.

A key difference from DCFS is that our algorithm does not entirely eliminate the Closed list. Instead, we propose a sparse representation of the Closed list that allows many (but not all) closed nodes to be removed from memory. To explain our approach, we note that the search interior (the set of closed nodes) can be partitioned into two disjoint subsets that we call the set of boundary nodes and the kernel of the search interior.

Definition 1 Let I be the set of search interior nodes, i.e., nodes whose lowest-cost paths have been found. The kernel of I, denoted K(I), is defined as follows:

where Fred( k) denotes the set of predecessor nodes ofk, that is, the set of nodes that can make a transition into node k in the underlying graph, which may be directed or undirected.

Basically, the kernel is the set of nodes whose predecessor nodes are all interior (i.e., closed) nodes.

Definition 2 The set of boundary nodes of search interior I, denoted B(I), is defined as the non-kernel nodes of I, that is:

Another way of describing a boundary node is to say that at least one of its predecessor nodes is not an interior node, or mathematically,

Figure 1 illustrates the relationship between the kernel and boundary of the search interior. Note that nodes in the bound­ ary can enter the kernel, but once a node is in the kernel it remains there. The nodes in the kernel are eligible for re­ moval from memory because they are not needed to prevent duplicate search effort.

The intuitive meaning of "boundary" can be explained as follows. Because every closed node is reachable from the start node, the set of closed nodes can be considered a "vol­ ume" in the underlying graph that encompasses the starting node. Nodes outside this volume cannot reach nodes inside the volume without passing through some node in the bound­ ary. Thus, storing only the boundary nodes in the Closed list is as effective as storing the entire "volume," with respect to preventing the search from "leaking" back into the closed re­ gion. (From this perspective, one could say that DCFS adds nodes to the Open list - i.e., the search frontier - in order to ensure that the frontier forms a boundary, and it treats the Closed Jist as the kernel that can be removed from memory.)

In addition to keeping boundary nodes in the Closed list, our sparse-memory approach keeps some other, non­ boundary nodes that allow solution reconstruction. The method of solution reconstruction is different from the one used by DCFS. Recall that DCFS stores in each node all infor­ mation about a "middle" node on the path through this node to the goal. In our approach, each node in the search graph maintains a pointer to its predecessor node along the best path to this node, or to some earlier, ancestral node along this path. 1 In the latter case, we have a sparse solution path.

Definition 3 A sparse solution path is an ordered list of nodes P = {P[O], P[1], · · ·, P[d]},such that d;::: 1, P[O] is a start node, P[d] is a goal node, and 2:1~~ 8(P[i], P[i + 1]) = 8( start, goal), where 8( u, v) denotes the cost of the lowest­ cost path between two nodes u and v.

If a node in a sparse solution path has a pointer to an an­ cestral node instead of a pointer to its predecessor, we call the ancestral node a relay node to indicate that it skips over some nodes in an original, "dense" solution path. We also consider the start node (which has no backward pointer) are­ lay node. How relay nodes are created and used in solution reconstruction is explained below. Here, we simply note that relay nodes are never removed from the Closed list because they are needed for solution reconstruction. Thus, a sparse representation of the Closed list includes all boundary nodes and all relay nodes. Nodes that do not fall in either category may be removed from memory.

It is well-known that A* can be viewed as Dijkstra's al­ gorithm applied to a transformed graph with the same set of nodes and edges, but modified edge costs given by the equation c(u,v) = c(u,v)- h(u) + h(v), where c(u,v) (or c( u, v)) is the cost of edge ( u, v) in the untransformed (or transformed) graph and h( u) (or h( v)) is the cost esti­ mate of the lowest-cost path from node u (or v) to the goal node. Therefore, we present our sparse-memory algorithm as a modification of Dijkstra's algorithm, and note that our de­ scription applies to A* also. Our sparse-memory approach requires two assumptions. First, the transformed (or untrans­ formed) graph cannot contain any negative-cost edges. This means the heuristic used by A* must be consistent. With­ out this assumption, it is impossible for our algorithm (or any heuristic search algorithm) to accurately identify the interior of the search, and DCFS makes the same assumption. Sec­ ond, we assume that our algorithm knows the in-degree (in the underlying graph) of every node it visits. For comparison, DCFS assumes that it knows every predecessor (in the under­ lying graph) of a node it visits. Thus, our second assumption is weaker than that made by DCFS.

1 Because pointers require less memory than state information about a midpoint node, the memory required to store all pointers plus relay nodes could be less than the memory required to copy state information about the same midpoint node into many other nodes.

Procedure ExpandNode (Node u) 1 for each v E Successors( u) do 2 if v E Open then 3 p(v) <-- p(v)- 1 4 if g(u) + c(u, v) < g(v) then 5 g(v) <-- g(u) + c(u, v) 6 ancestor ( v) <-- u 7 else if v E Closed then 8 p(v) <-- p(v)- 1 9 else /* generate new node *I 10 p(v) <-- in-degree(v)- 1 11 g(v)<--g(u)+c(u,v) 12 ancestor(v) <-- u 13 Open <-- Open U { v} 14 if memory is full then PruneClosedList () Procedure PruneClosedList () 1 for each v E Open U Closed do 2 if ancestor(v) E Pred(v) then 3 a<-- ancestor(v) 4 while a E Closed and p(a) = 0 do 5 a<-- ancestor(a) 6 if a =f. ancestor( v) then 7 ancestor(v) <--a 8 p(a) <-- oo /*never prune relay node*/ 9 for each v E Closed do 10 if p(v) = 0 then 11 Closed <-- Closed\ { v} 12 Delete v Algorithm SMGS (Node start, Node goal) 1 g(start) <-- 0 2 p(start) <-- oo /*never prune start node *I 3 ancestor(start) <--null 4 Open <-- {start} 5 Closed<-- 0 6 while Open =f. 0 do 7 u <-- argminu{g(u) I u E Open} 8 Open <-- Open\ {u} 9 Closed<-- Closed U { u} 10 if u is goal then 11 SSP<-- ExtractSparseSolutionPath(u) 12 DSP <-- 0 13 fori= 1 to length( SSP) do 14 if SSP[i- 1] E Pred(SSP[i]) then 15 DSP.addTail(SSP[i]) 16 else 17 DSP.addTail(SMGS(SSP[i- 1] , SSP[i ])) 18 return DSP 19 else 20 ExpandNode (u)

3.1 Pruning the Closed list

Our search algorithm must be able to efficiently distinguish between the kernel and boundary of the search interior, in order to prune nodes from the kernel. Recall that a node is in the kernel if all of its predecessors are closed. To identify such nodes, we introduce a technique for keeping track of the number of unexpanded predecessors for each generated-and­ stored node. We call this number the p-value of a node. It is initially set to the number of predecessors (the in-degree) of the node in the underlying graph minus one to account for the predecessor that generated it. The p-value is updated during node expansion. As each successor of a node is considered (some of which may already be in the Open or Closed lists), its p-value is decremented. (See lines 3, 8 and 10 of procedure ExpandNode in Figure 2.) This requires negligible time and space overhead, and, given p-values, kernel-membership for a node can be determined in constant time by checking whether it is a closed node with a p-value of zero.

An advantage of the sparse-memory approach is that it does not immediately remove closed nodes from memory, un­ like DCFS. A sparse-memory version ofDijkstra's algorithm (or A*) acts exactly like Dijkstra's algorithm (or A*) until it senses that memory is about to be exhausted. Only then does it invoke procedure PruneC/osedList in Figure 2 to re­ cover memory. This procedure prunes nodes from the Closed list in two steps. First it updates the ancestral pointer of any boundary node whose predecessor is about to be pruned (lines 1-8). This is necessary to allow solution reconstruction and requires finding the relay node that is the closest boundary node along its solution path (lines 3-5), and updating its an­ cestral pointer accordingly (line 7). This makes this boundary node a relay node, and to prevent it from being pruned in the future, its p-value is set to oo (line 8). After this step, kernel nodes are pruned unless they are a start node or relay node created in a previous pruning step (lines 9-12). Updating the ancestral pointers of nodes (followed by pruning) creates a sparse solution path, from which a complete or "dense" solu­ tion path can be reconstructed after the search terminates.

3.2 Solution Path Reconstruction

The fact that the Closed list is not pruned unless memory is close to being exhausted means that the overhead of solution reconstruction can be avoided if memory resources are ade­ quate. In that case, the sparse-memory algorithm acts exactly like Dijkstra's algorithm (or A*) and an optimal solution path is extracted in the conventional way.

If the Closed list has been pruned, an optimal solution path is reconstructed by invoking the Sparse-Memory Graph Search algorithm (SMGS) in Figure 2 recursively. First the sparse solution path (SSP) is extracted (line 11) in the con­ ventional way by tracing pointers backward from the goal. Then the corresponding dense solution path (DSP) is re­ constructed as follows. For each pair of consecutive nodes (SSP[i - 1], SSP[i]) in the SSP (starting from the start node), the algorithm checks to see if SSP[i - 1] is a pre­ decessor of SSP[i] (line 14). If so, node SSP[i] is added to the tail of the DSP (line 15); otherwise, the search algorithm calls itself recursively with SSP[i- 1] and SSP[i] as the new start and goal nodes, in order to get a dense solution path between the two which is added to the tail of DSP (line 17).

Another difference from DCFS that is worth noting is that DCFS divides a problem into two subproblems at each level of the recursion. The sparse-memory approach can divide a problem into two or more subproblems. The extra flexibility is possible because the sparse-memory approach uses relay nodes with ancestral pointers, whereas DCFS stores all infor­ mation about a middle node in each node. When a problem is divided into more than two subproblems, the subproblems are smaller and easier to solve and solution reconstruction can be faster. In fact, relay nodes can be spaced at half intervals, one-third intervals, or any other interval, and allow a tradeoff between the sparseness of the search interior and the speed of solution reconstruction.

3.3 Pruning the Open list

We now consider how easily the sparse-memory approach to pruning the Closed list can be combined with techniques for pruning the Open list. Pruning nodes on the Open list that have an f -cost greater than an upper bound on the optimal f-cost creates difficulties for DCFS, as discussed earlier. An advantage of the sparse-memory approach is that it does not create difficulties, at least in solving problems for which the set of predecessors of a node is disjoint from the set of succes­ sors, such as the multiple sequence alignment problem. This advantage will be illustrated in our experimental results.

For other directed graphs, that is, for directed graphs in which the same node can be both predecessor and succes­ sor of another node, DCFS allows leaks back into the closed region when the Open list is pruned. The sparse-memory ap­ proach does not, and this is another advantage. Unfortunately, the sparse-memory approach has a problem in such graphs. If the best path to a node has not been found when it is first generated, it could be pruned and re-generated later, when a better path is found. Since p-values are erased when the node is pruned, the p-value of such nodes will not be decremented to zero. As a result, the sparse-memory algorithm may not recover as much memory from the Closed list. However, our experimental results suggest that this inefficiency is minor.

In undirected graphs, we noted earlier that DCFS also al­ lows "leaks" back into the closed region when the Open list is pruned. The sparse-memory algorithm does not, if we make a minor modification, as explained in the following.

3.4 Undirected graphs

The pseudocode in Figure 2 shows the ExpandNode proce­ dure for directed graphs. Figure 3 gives the pseudocode of the ExpandNode procedure in undirected graphs. The differ­ ence is that in undirected graphs, p-values are only set and decremented for closed nodes, not open nodes. Thus, prun­ ing open nodes cannot cause any problems by distorting p­ values. In fact, the pseudocode in Figure 3 could be used for directed graphs also. But in directed graphs, it would require considering all predecessors of a node as well as successors during node expansion, in order to set p-values correct. The overhead for this would be significant. This is not a problem in undirected graphs because the set of potential successors of a node is equal to the set of potential predecessors.

3.5 Hybrid algorithms

The sparse-memory algorithm we have described is based on more than one idea. It uses nodes on the Closed list to cre­ ate a "boundary" that prevents re-generation of closed nodes, instead of using the Open list as a boundary. In addition, it uses relay nodes for divide-and-conquer solution reconstruc­ tion, instead of storing in each node state information about a middle node along the search path.

Because these ideas can be considered separately, it is pos­ sible to create search algorithms that are hybrids ofDCFS and the sparse-memory approach. For example, the DCFS tech­ nique of using the Open list as a boundary could be combined with relay nodes. This would create a version of DCFS that is able to divide a solution path into more than two pieces, allowing flexible (and potentially faster) solution reconstruc­ tion; use of relay nodes would also allow DCFS to delay pruning of the Closed list until memory is full. Similarly, some of the techniques used by DCFS can be considered in­ dependently. For example, forbidden operators can be used in combination with the sparse-memory approach, instead of p-values. One advantage of using forbidden operators is that they sometimes speed up search, since it is faster not to gener­ ate a node than to generate it and check for a duplicate on the Open or Closed list. We consider the performance of these hybrid algorithms in the computational results that follow.

4 Computational Results

We first illustrate how a sparse-memory version of Dijkstra's algorithm works by showing how it solves a small pairwise sequence alignment problem. Then we consider the perfor­ mance of sparse-memory A* on more challenging problems.

4.1 Example

Consider the problem of aligning two sequences, ACTGAT and TGACTGC, using a very simple cost function: zero for a match, one unit for a substitution, and two units for a gap. The state space of the problem can be represented by a two­ dimensional grid in which the columns correspond to one se­ quence and the rows to the other. The problem of finding an optimal alignment of the two sequences corresponds to the problem of finding an optimal path from the start node in the upper-left corner to the goal node in the lower-right cor­ ner, where horizontal and vertical moves correspond to gap insertions in one or the other sequence, and diagonal moves correspond to a substitution or match of characters.

Figure 4 shows the behavior of sparse-memory Dijkstra's algorithm at the critical points when memory becomes full and the Closed list is pruned. It assumes that memory ca­ pacity is 30 nodes. Figure 4(a) shows the explored state space when memory is full for the first time. The number in each cell is the g-value of the corresponding state (or node). For closed nodes, the g-value is highlighted in bold italics. Among the 17 closed nodes, 11 are identified as kernel nodes and pruned. Figure4(b) shows the result of pruning. When memory is full the second time, as shown in Figure 4(c), the Closed list is pruned again and 12 kernel nodes are removed from memory, as shown in Figure 4( d), freeing enough mem­ ory for continued search. Figure 4(e) shows the state space in memory when the goal node (the cell in the lower-right cor­ ner) is expanded. The SSP solution is shown as a chain of thick dashed arrows. The arrows drawn in thin dashed lines represent ancestor pointers that are created during pruning.

In this example, it is also possible to see how the Open list can be pruned using the sparse-memory approach. Suppose we know that 8 is an upper bound on the cost of an opti­ mal alignment. Then all nodes with g-values greater than or equal to 8 can be pruned from the Open list, and the search progresses in the same way except for not storing the seven nodes whose g-values equal 8. Note that pruning nodes in the Open list will not change the boundary of the search interior.

4.2 Multiple sequence alignment

We tested Sparse-memory A* (Sparse-A*) on a series of chal­ lenging multiple sequence alignment problems, in order to compare its performance to DCFA * (the DCFS version of A*). We used a 300Mhz Sun UltraS pare II workstation with two gigabytes of RAM. Results are displayed in Table 1.

First, we considered the identical test domain used by Korf and Zhang [2000]: alignment of three random sequences of length 4000 using their simple cost function, with results av­ eraged over 100 trials. Both DCFA *and Sparse-A* are effec­ tive in this domain, whereas A* could not solve any problem instance due to memory limitations. Versions of A* that use special techniques to recover memory by pruning the Open list [Ikeda and Imai, 1999; Yoshizumi et al., 2000] were also unable to solve any of these problem instances. This is be­ cause the Closed list, not the Open list, fills most of mem­ ory in this case. One reason there are so many closed nodes is that the accuracy of the pairwise heuristic used for multi­ ple sequence alignment depends on the similarity of the se­ quences. Because random sequences have only random sim­ ilarities, the heuristic is weak, resulting in many node expan­ sions and closed nodes.

For this problem set, DCFA * is more memory-efficient than Sparse-A*. However, Sparse-A* runs faster. It runs faster for long sequences like these because the solution path is correspondingly long, and solution reconstruction can be faster using relay nodes. At each recursion level, relay nodes make it possible to divide a solution path into several smaller, easier-to-solve subproblems, instead of always dividing it in half. Faster solution reconstruction comes at the expense of a small increase in memory for extra relay nodes, as can be seen by comparing the performance of DCFA * using relay nodes (a hybrid algorithm) to standard DCFA *.

Why can DCFA * be more memory-efficient than Sparse­ A*? One factor is that using relay nodes to divide a solution path into more than two pieces requires extra memory for the extra relay nodes - a classic space-time tradeoff. Another factor is that use of forbidden operators allows a closed node to be pruned as soon as all its predecessors are generated. By contrast, use of p-values requires waiting until all prede­ cessors are closed, before pruning the node. As a result, a hybrid algorithm that combines the sparse-memory approach with forbidden operators outperforms the sparse-memory ap­ proach alone, for this problem set. These two factors may not account for all of the difference in memory efficiency, but we currently have no other explanation.

We next compared Sparse-A* and DCFA * on real protein sequences using the PAM250 cost matrix, which is widely­ used by biologists. In aligning five sequences randomly se­ lected from a pool of low-similarity protein sequences of length 300 used in previous experiments [McNaughton eta!., 2002], Sparse-A* and DCFA * were again effective in solv­ ing all instances. By contrast, A* ran out of memory on most instances. For this problem set, the Enhanced A* al­ gorithm [Ikeda and Imai, 1999], which uses an upper bound to prune nodes from the Open list, performs very well. This is because the number of open nodes is very large for this set of problems. Unlike DCFA*, the sparse-memory approach can be safely combined with this technique of pruning the Open list. This gives it an overall advantage, and Enhanced Sparse-A* is the best-performing algorithm for this prob­ lem set. (Although Enhanced Sparse-A* stores slightly more nodes than DCFA*, it uses less memory because forbidden operators makes the DCFA * nodes larger. We also empha­ size the following point: although the table shows that the running time of Enhanced A* is less than the running time of Enhanced Sparse-A*, this does not mean that it is a faster algorithm. If Enhanced A* by itself can solve a problem in available memory, the sparse-memory version of Enhanced A* does not need to prune the Closed list at all, and has iden­ tical performance. But for these experiments, we adjusted the sparse-memory algorithm to minimize its memory use- since memory is the key factor we are evaluating here.)

A drawback of DCFA * is that its node size increases as the number of sequences being aligned increases. This be­ comes very apparent when DCFA * is used to align seven pro­ tein sequences oflength around 450, randomly selected from a set of similar protein sequences used in previous experi­ ments [Yoshizumi eta!., 2000]. The high similarity of these sequences gives rise to a very accurate heuristic, and makes these sequences much easier to align. Even A* can solve these problems. Although A*, Sparse-A* and DCFA *always expand the same number of nodes, DCFA * generates and stores an average of I 0% more nodes in this domain because it inserts extra nodes in the Open list. A more serious prob­ lem is that the nodes created by DCFA * are two times bigger than the nodes created by the other algorithms, because they include lists of forbidden operators. As a result, DCFA *runs slower and uses more memory than any other algorithm, in­ cluding A*! (In aligning ten sequences, the nodes created by DCFA * are seven times larger than the nodes created by A*, and their relative size almost doubles with each additional se­ quence thereafter.) The table shows Sparse-A* is not as effec­ tive as Enhanced A*, because pruning the Open list is much more important than pruning the Closed list, for this problem set. Nevertheless, Enhanced Sparse-A* performs no worse than Enhanced A*, and this point is important. The sparse­ memory approach improves performance when possible, and complements other techniques for reducing memory.

For perspective, we discuss what happens if we combine DCFA* with Partial Expansion A* [Yoshizumi eta!., 2000]. (In our experiments, we set the cutoff value for Partial Ex­ pansion A* to zero, to minimize memory use.) For the set of seven similar protein sequences, Partial Expansion DCFA * required an average of 29 Mbytes of memory, and 43 7 CPU seconds. The much greater running time is due to the over­ head of partial expansions. The slightly higher memory re­ quirement is because nodes are partially expanded, and nodes that are not closed cannot be pruned by DCFA*. For the set of three random 4000-length sequences, Partial Expan­ sion DCFA * stored 40% more nodes and ran 42% slower than DCFA *. Again, the reason is that partially expanded nodes are not pruned. Finally, we note that when DCFA * is combined with Enhanced A*, it consistently requires more memory (and CPU time) than DCFA* alone, due to the com­ plications discussed earlier.

4.3 15-Puzzle

The 15-puzzle is not a problem for which duplicate detection is a crucial issue. Nevertheless, it is interesting to consider as both a benchmark and an example of an undirected graph. We used 91 of the 100 problem instances in Korf (1985) as a test set. Sparse-A* by itself used an average of 79% of the memory used by A*; DCFA* used an average of 44% of the memory used by A*; and Enhanced A* used an average of 57% of the memory used by A*. A sparse-memory version of Enhanced A* performed best. It used 3 2% of the memory used by A*. We also tested DCFA * combined with Enhanced A*. It is unable to prevent leaks back into the closed region, for reasons discussed earlier, and we noticed many node re­ expansions. Interestingly, it used only 10% of the memory used by A*, due to aggressive pruning, and ran faster than the other algorithms. But this is only because the 15-puzzle is a domain in which node re-generation has less overhead than managing the Open and Closed lists, since IDA* outperforms all of these algorithms on this problem. In undirected graphs with exponentially many duplicate paths, a sparse-memory version of Enhanced A* is likely to perform best.

5 Conclusion

We have proposed a sparse-memory approach to graph search that builds on ideas in earlier work, but implements them in a way that is often more effective. A key advantage of this approach to reducing the size of the Closed list is that it can be combined with a technique for reducing the size of the Open list by upper-bound pruning. This is especially use­ ful for large branching-factor problems where the size of the Open list would otherwise dramatically exceed the size of the Closed list, such as the multiple sequence alignment problem when there are more than four or five sequences.

The sparse-memory approach has other advantages. It al­ lows more flexible, and potentially faster, solution reconstruc­ tion. And last but not least, it can behave exactly like A* (or Enhanced A*, or Dijkstra's algorithm) until it reaches a mem­ ory limit, and only then removes nodes from the Closed list. Thus, there is (virtually) no overhead for this technique un­ less a search problem cannot be solved within a given mem­ ory bound. Then the overhead for solution reconstruction is compensated for by the reduced memory requirements.

Acknowledgments We thank the anonymous reviewers for helpful comments. This work was supported in part by NSF CAREER grant IIS-9984952 and NASA grant NAG-2-1463 .