External priority queues for general weights are involved. An I/O-efficient algorithm for the Single-Source Shortest Paths problem simulates Dijkstra's algorithm by replacing the priority queue with the Tournament Tree data structure. It is a priority queue data structure that was developed with the application to graph search algorithms in mind; it is similar to an external heap, but it holds additional information. The tree stores pairs , where identifies the element, and y is called the key. The Tournament Tree is a complete binary tree, except for possibly some right-most leaves missing. It has leaves. There is a fixed mapping of elements to the leaves, namely, IDs in the range from through the map to the i th leaf. Each element occurs exactly once in the tree. Each node has an associated list of to M elements, which are the smallest ones among all descendants. Additionally, it has an associated buffer of size M. Using an amortization argument, it can be shown that a sequence of k Update, Delete, or DeleteMin operations on a tournament tree containing N elements requires at most accesses to external memory.

The Buffered Repository Tree is a variant of the Tournament Tree that provides two operations: Insert inserts element x under key y, where several elements can have the same key. ExtractAll returns and removes all elements that have key y. As in a Tournament Tree, keys come from a key set , and the leaves in the static height-balanced binary tree are associated with the key ranges in the same fixed way. Each internal node stores elements in a buffer of size B, which is recursively distributed to its two children when it becomes full. Thus, an Insert operation needs I/O amortized operations. An ExtractAll operation requires accesses to secondary memory, where the first term corresponds to reading all buffers on the path from the root to the correct leaf, and the second term reflects reading the x reported elements from the leaf. Moreover, a Buffered Repository Tree T is used to remember nodes that were encountered earlier. When v is extracted, each incoming edge is inserted into T under key u. If at some later point u is extracted, then ExtractAll on T yields a list of edges that should not be traversed because they would lead to duplicates. The algorithm takes I/Os to access adjacency lists. The operations on the priority queues take at most times, leading to a cost of . Additionally, there are Insert and ExtractAll operations on T, which add up to I/Os; this term also dominates the overall complexity of the algorithm.

More efficient algorithms can be developed by exploiting properties of particular classes of graphs. In the case of directed acyclic graphs (DAGs) like those induced in Multiple Sequence Alignment problems, we can solve the shortest path problem following a topological ordering, in which for each edge the index of u is smaller than that of v. The start node has index 0. Nodes are processed in this order. Due to the fixed ordering, we can access all adjacency lists in time. Since this procedure involves priority queue operations, the overall complexity is .

It has been shown that the Single-Source Shortest Paths problem can be solved with I/Os for many subclasses of sparse graphs; for example, for planar graphs that can be drawn in a plane in the natural way without having edges cross between nodes. Such graphs naturally decompose the plane into faces. For example, route planning graphs without bridges and tunnels are planar. As most special cases are local, virtual intersections may be inserted to exploit planarity.

We next consider external DFS and BFS exploration for more general graph classes.

External DFS relies on an external stack data structure. The search stack is often small compared to the overall search but in the worst-case scenario it can become large. For an external stack, the buffer is just an internal memory array of 2B elements that at any time contains the elements most recently inserted. We assume that the stack content is bounded by at most N elements. A pop operation incurs no I/O, except for the case when the buffer has run empty, where I/O to retrieve a block of B elements is sufficient. A push operation incurs no I/O, except for the case the buffer has run full, where I/O is needed to retrieve a block of B elements. Insertion and deletion take I/Os in the amortized sense.

The I/O complexity for external DFS for explicit (possibly directed) graphs is . There are phases where the internal buffer for the visited state set becomes full, in which case it is flushed. Duplicates are eliminated not via sorting (as in the case of external BFS) but by removing marked states from the external adjacency list representation by a file scan. This is possible as the adjacency is explicitly represented on disk and done by generating a simplified copy of the graph and writing it to disk. Successors in the unexplored adjacency lists that are visited are marked not to be generated again, such that all states in the internal visited list can be eliminated. As with external BFS in explicit graphs, I/Os are due to the unstructured access to the external adjacency list. Computing strongly connected components in explicit graphs also takes I/Os.

Dropping the term of I/O as with external BFS, however, is a challenge. For implicit graphs, no access to an external adjacency list is possible, so that we cannot access the search graph that has not been seen so far. Therefore, the major problem for external DFS exploration in implicit graphs is that adjacencies defining the successor relation cannot be filtered out as done for explicit graphs.

Recall the standard internal memory BFS algorithm, visiting each reachable node of the input problem graph G one by one utilizing a FIFO queue. After a node is extracted, its adjacency list (the sets of successors in G) is examined, and those that haven't been visited so far are inserted into the queue in turn. Naively running the standard internal BFS algorithm in the same way in external memory will result in I/Os for unstructured accesses to the adjacency lists, and I/Os to check if successor nodes have already been visited. The latter task is considerably easier for undirected graphs, since duplicates are constrained to be located in adjacent levels.

The algorithm of Munagala and Ranade improves I/O complexity for the case of undirected graphs, in which duplicates are constrained to be located in adjacent levels.

The algorithm builds from as follows: Let be the multiset of successors of nodes in ; is created by concatenating all adjacency lists of nodes in . Then the algorithm removes duplicates by external sorting followed by an external scan. Since the resulting list is still sorted, filtering out the nodes already contained in the sorted lists or is possible by parallel scanning. This completes the generation of . Set U maintains all unvisited nodes necessary to be looked at when the graph is not completely connected. Algorithm 8.1 provides the implementation of the algorithm of Munagala and Ranade in pseudo code. The algorithm can record the nodes' BFS level in additional time using an external array.

An example is provided in Figure 8.3. When generating we unify with . Removing the duplicates in yields set . Removing reduces the set to ; omitting results in the final node set .

The bottleneck of the algorithm are the unstructured accesses to adjacency lists. The following refinement of Mehlhorn and Meyer consists of a preprocessing and a BFS phase, arriving at a complexity of I/Os.

The preprocessing phase partitions the graph into K disjoint subgraphs with small internal shortest path distances; the adjacency lists are accordingly partitioned into consecutively stored sets as well. The partitions are created by choosing seed nodes independently with uniform probability . Then K BFS are run in parallel, starting from the seed nodes, until all nodes of the graph have been assigned to a subgraph. In each round, the active adjacency lists of nodes lying on the boundary of their partition are scanned; the requested destination nodes are labeled with the partition identifier, and are sorted (ties between partitions are arbitrarily broken). Then, a parallel scan of the sorted requests and the graph representation can extract the unvisited part of the graph, as well as label the new boundary nodes and generate the active adjacency lists for the next round. The expected I/O bound for the graph partitioning is ; the expected shortest path distance between any two nodes within a subgraph is . The main idea of the second phase is to replace the nodewise access to adjacency lists by a scanning operation on a file H that contains all in sorted order such that the current BFS level has at least one node in . All subgraph adjacency lists in are merged with H completely, not node by node. Since the shortest path within a partition is of order , each stays in H accordingly for at most levels. The second phase uses I/Os in total; choosing , we arrive at a complexity of I/Os. An alternative to the randomized strategy of generating the partition described here is a deterministic variant using a Euler tour around a minimum spanning tree. Thus, the bound also holds in the worst case.

A variant of Munagala and Ranade's algorithm for BFS in implicit graphs has been coined with the term delayed duplicate detection for frontier search. Let s be the initial node, and be the implicit successor generation function. The algorithm maintains BFS layers on disk. Layer is scanned and the set of successors are put into a buffer of a size close to the main memory capacity. If the buffer becomes full, internal sorting followed by a duplicate elimination phase generates a sorted duplicate-free node sequence in the buffer that is flushed to disk. The outcome of this phase are k presorted files. Note that delayed internal duplicate elimination can be improved by using hash tables for the blocks before being flushed to disk. Since the node set in the hash table has to be stored anyway, the savings by early duplicate detection are often small.

In the next step, external merging is applied to unify the files into by a simultaneous scan. The size of the output files is chosen such that a single pass suffices. Duplicates are eliminated. Since the files were presorted, the complexity is given by the scanning time of all files. We also have to eliminate and from to avoid recomputations; that is, nodes extracted from the external queue are not immediately deleted, but kept until the layer has been completely generated and sorted, at which point duplicates can be eliminated using a parallel scan. The process is repeated until becomes empty, or the goal has been found.

The corresponding pseudo code is shown in Algorithm 8.2. Note that the explicit partition of the set of successors into blocks is implicit. Termination is not shown, but imposes no additional implementation problem.

In search problems with a bounded branching factor we have , and thus the complexity for implicit external BFS reduces to I/Os. If we keep each in a separate file for sparse problem graphs (e.g., simple chains), file opening and closing would accumulate to I/Os. The solution for this case is to store the nodes in , , and so forth, consecutively in internal memory. Therefore, I/O is needed, only if a level has at most B nodes.

The algorithm shares similarities with the internal frontier search algorithm (see Ch. 6) that was used for solving the Multiple Sequence Alignment problem. In fact, the implementation has been applied to external memory search with considerable success. The BFS algorithm extends to graphs with bounded locality. For this case and to ease the description of upcoming algorithms, we assume to be given a general file subtraction procedure as implemented in Algorithm 8.3.

In an internal, not memory-restricted setting, a plan is constructed by backtracking from the goal node to the start node. This is facilitated by saving with every node a pointer to its predecessor. For memory-limited frontier search, a divide-and-conquer solution reconstruction is needed for which certain relay layers have to be stored in the main memory. In external search divide-and-conquer solution reconstruction and relay layers are not needed, since the exploration fully resides on disk.

There is one subtle problem: predecessors of the pointers are not available on disk. This is resolved as follows. Plans are reconstructed by saving the predecessor together with every state, by scanning with decreasing depth the stored files, and by looking for matching predecessors. Any reached node that is a predecessor of the current node is its predecessor on an optimal solution path. This results in a I/O complexity that is at most linear to scanning time .

Even if conceptually simpler, there is no need to store the Open list in different files , . We may store successive layers appended in one file.

In weighted graphs, external BFS with delayed duplicate detection does not guarantee an optimal solution. A natural extension of BFS is to continue the search when a goal is found and keep on searching until a better goal is found or the search space is exhausted. In searching with nonadmissible heuristics we hardly can prune states with an evaluation larger than the current one. Essentially, we are forced to look at all states. However, if with monotone heuristic function h we can prune the exploration.

For the domains where cost is monotonically increasing, external breadth-first branch-and-bound (external BFBnB) with delayed duplicate detection does not prune away any node that is on the optimal solution path and ultimately finds the optimal solution. In Algorithm 8.4, the algorithm is presented in pseudo code. The sets Open denote the BFS layers and the sets A, , are temporary variables to construct the search frontier for the next iteration. States with are pruned and states with lead to a bound that is updated.

Table 8.2 gives an impression of cost-optimal search in a selected optimization problem, reporting the number of nodes in each layer obtained after refinement with respect to the previous layers. An entry in the goal cost column corresponds to the best goal cost found in that layer.

For unit cost search graphs the external branch-and-bound algorithm simplifies to external breadth-first heuristic search (see Ch. 6).

In Chapter 6 we have introduced enforced hill-climbing (a.k.a. iterative improvement) as a more conservative form of hill-climbing search. Starting from a start state, a (breadth-first) search for a successor with a better heuristic value is started. As soon as such a successor is found, the hash tables are cleared and a fresh search is started. The process continues until the goal is reached. Since the algorithm performs a complete search on every state with a strictly better heuristic value, it is guaranteed to find a solution in directed graphs without dead-ends.

Having external BFS in hand, an external algorithm for enforced hill-climbing can be constructed by utilizing the heuristic estimates. In Algorithm 8.5 we show the algorithm in pseudo-code format. The externalization is embedded in the subprocedure Algorithm 8.6 that performs external BFS for a state that has an improved heuristic estimate. Figure 8.5 shows parts of an exploration for solving a action planning instance. It provides a histogram (logarithmic scale) on the number of nodes in BFS layers for external enforced hill-climbing in a selected planning problem.

Enforced hill-climbing has one important drawback: its results are not optimal. Moreover, in directed search spaces with unrecognized dead-ends it can be trapped, without finding a solution to a solvable problem.

In the following we study how to extend external breadth-first exploration in implicit graphs to an A*-like search. If the heuristic is consistent, then on each search path, the evaluation function f is nondecreasing. No successor will have a smaller f-value than the current one. Therefore, the A* algorithm, which traverses the node set in f-order, expands each node at most once. Take, for example, a sliding-tile puzzle. As the Manhattan distance heuristic is consistent, for every two successive nodes u and v the difference of the according estimate evaluations is either −1 or 1. By the increase in the g-value, the f-values remain either unchanged, or .

As earlier, external A* maintains the search frontier on disk, possibly partitioned into main memory–size sequences. In fact, the disk files correspond to an external representation of a bucket implementation of a priority queue data structure (see Ch. 3). In the course of the algorithm, each bucket addressed with index i contains all nodes u in the set Open that have priority . An external representation of this data structure will memorize each bucket in a different file.

We introduce a refinement of the data structure that distinguishes between nodes with different g-values, and designates bucket to all nodes u with path length and heuristic estimate . Similar to external BFS, we do not change the identifier Open to separate generated from expanded nodes. In external A* (see Alg. 8.7), bucket refers to nodes that are in the current search frontier or belong to the set of expanded nodes. During the exploration process, only nodes from one currently active bucket , where , are expanded, up to its exhaustion. Buckets are selected in lexicographic order for ; then, the buckets with and are closed, whereas the buckets with or with and are open. Depending on the actual node expansion progress, nodes in the active bucket are either open or closed.

To estimate the maximum number of buckets once more we consider Figure 7.14 as introduced in the analysis of the number of iteration in Symbolic A* (see Ch. 7), in which the g-values are plotted with respect to the h-values, such that nodes with the same value are located on the same diagonal. For nodes that are expanded in the successors fall into , , or . The number of naughts for each diagonal is an upper bound on the number of buckets that are needed. In Chapter 7, we have already seen that the number is bounded by .

By the restriction for f-values in the (n² − 1)-Puzzle only about half the number of buckets have to be allocated. Note that is not known in advance, so that we have to construct and maintain the files on-the-fly.

Figure 8.5 shows the memory profile of external A* on a Thirty-Five-Puzzle instance (with 14 tiles permuted). The exploration started in bucket and terminated while expanding bucket . Similar to external BFS but in difference to ordinary A*, external A* terminates while generating the goal, since all states in the search frontier with a smaller g-value have already been expanded. For this experiment three disjoint 3-tile and three disjoint 5-tile pattern databases were loaded, which, together with the buckets for reading and flushing, consumed about 4.9 gigabytes of RAM. The total disk space taken was 1,298,389,180,652 bytes, or 1.2 terabytes, with a state vector of bytes: 32 bytes for the state vector plus information for incremental heuristic evaluation; 1 byte for each value stored, multiplied by six sets of at most 12 pattern databases plus 1 value each for their sum. Factor 2 is due to symmetry lookups. The exploration took about two weeks.

The following result restricts duplicate detection to buckets of the same h-value.

For ease of describing the algorithm, we consider each bucket for the Open list as a different file. Very sparse graphs can lead to bad I/O performance, because they may lead to buckets that contain by far less than B elements and dominate the I/O complexity. For the following, we generally assume large graphs for which and .

Algorithm 8.7 depicts the pseudo code of the external A* algorithm for consistent estimates and unit cost and undirected graphs. The algorithm maintains the two values and to address the currently considered buckets. The buckets of are traversed for increasing up to . According to their different h-values, successors are arranged into three different frontier lists: , , and ; hence, at each instance only four buckets have to be accessed by I/O operations. For each of them, we keep a separate buffer of size ; this will reduce the internal memory requirements to M. If a buffer becomes full then it is flushed to disk. As in BFS it is practical to presort buffers in one bucket immediately by an efficient internal algorithm to ease merging, but we could equivalently sort the unsorted buffers for one bucket externally.

There can be two cases that can give rise to duplicates within an active bucket (see Fig. 8.6, black bucket): two different nodes of the same predecessor bucket generating a common successor, and two nodes belonging to different predecessor buckets generating a duplicate. These two cases can be dealt with by merging all the presorted buffers corresponding to the same bucket, resulting in one sorted file. This file can then be scanned to remove the duplicate nodes from it. In fact, both the merging and duplicates removal can be done simultaneously.

Another special case of the duplicate nodes exists when the nodes that have already been evaluated in the upper layers are generated again (see Fig. 8.6). These duplicate nodes have to be removed by a file subtraction process for the next active bucket by removing any node that has appeared in and (buckets shaded in light gray). This file subtraction can be done by a mere parallel scan of the presorted files and by using a temporary file in which the intermediate result is stored. It suffices to remove duplicates only in the bucket that is expanded next, . The other buckets might not have been fully generated, and hence we can save the redundant scanning of the files for every iteration of the innermost while loop.

When merging the presorted sets with the previously existing Open buckets (both residing on disk), duplicates are eliminated, leaving the sets Open , Open , and Open duplicate free. Then the next active bucket Open is refined not to contain any node in Open or Open . This can be achieved through a parallel scan of the presorted files and by using a temporary file in which the intermediate result is stored, before Open is updated. It suffices to perform file subtraction lazily only for the bucket that is expanded next.

If we additionally have , the complexity reduces to I/Os. We next generalize the result to directed graphs with bounded locality.

Internal costs have been neglected in this analysis. Since each node is considered only once for expansion, the internal costs are times the time for successor generation, plus the efforts for internal duplicate elimination and sorting. By setting the weight of all edges to for a consistent heuristic h, A* can be cast as a variant of Dijkstra's algorithm that requires internal costs of , successor of on a bucket-based priority queue. Due to consistency we have , so that, given , internal costs are bounded by , where refers to the total internal sorting efforts.

To reconstruct a solution path, we store predecessor information with each node on disk (thus doubling the state vector size), and apply backward chaining, starting with the target node. However, this is not strictly necessary: For a node in depth g, we intersect the set of possible predecessors with the buckets of depth . Any node that is in the intersection is reachable on an optimal solution path, so that we can iterate the construction process. The time complexity is bounded by the scanning time of all buckets in consideration, namely by I/Os.

Up to this point, we have made the assumption of unit cost graphs; in the rest of this section, we generalize the algorithm to small integer weights in . Due to consistency of the heuristic, it holds for every node u and every successor v of u that . Moreover, since the graph is undirected, we equally have , or ; hence, . This means that the successors of the nodes in the active bucket are no longer spread across three, but over buckets. In Figure 8.7, the region of successors is shaded in dark gray, and the region of predecessors is shaded in light gray.

For duplicate reduction, it is sufficient to subtract the buckets from the active bucket prior to the expansion of its nodes (indicated by the shaded rectangle in Fig. 8.7). We assume I/Os for accessing the files is negligible.

If we do not impose a bound C on the maximum integer weight, or if we allow directed graphs, the runtime increases to I/Os. For larger edge weights and -values, buckets become sparse and should be handled more carefully.

Let us consider how to externally solve Fifteen-Puzzle problem instances that cannot be solved internally with A* and the Manhattan distance estimate. Internal sorting is implemented by applying Quicksort. The external merge is performed by maintaining the file pointers for every flushed buffer and merging them into a single sorted file. Since we have a simultaneous file pointers capacity bound imposed by the operating system, a two-phase merging applies. Duplicate removal and bucket subtraction are performed on single passes through the bucket file. As said, the successor's f-value differs from the parent node by exactly 2.

In Table 8.3 we show the diagonal pattern of nodes that is developed during the exploration for a simple problem instance. Table 8.4 illustrates the impact of duplicate removal () and bucket subtraction () for problem instances of increasing complexity. In some cases, the experiment is terminated because of the limited hard disk capacity.

One interesting feature of our approach from a practical point of view is the ability to pause and resume the program execution in large problem instances. This is desirable, for example, in the case when the limits of secondary storage are reached, because we can resume the execution with more disk space.

Is the complexity for external A* I/O-optimal?

Recall the definition of big-oh notation in Chapter 1: We say if there are two constants and c, such that for all we have . To devise lower bounds for external computation, the following variant of the big-oh notation is appropriate: We say if there is a constant c, such that for all M and B there is a value , such that for all we have . The classes and are defined analogously. The intuition for universally quantifying M and B is that the adversary first chooses the machine, and then we, as the good guys, evaluate the bound.

External sorting in this model has the aforementioned complexity of I/Os. As internal set inequality, set inclusion, and set disjointness require at least comparisons, the lower bounds on the number of I/Os for these problems are also .

For the internal duplicate elimination problem the known lower bound on the number of comparisons needed is , where is the multiplicity of record i. The main argument is that after the duplicate removal, the total order of the remaining records is known. This result can be lifted to external search and leads to an I/O complexity of at mostfor external delayed duplicate detection. For the sliding-tile puzzle with two preceding buckets and a branching factor we have . For general consistent estimates in unit cost graphs we have , with c being an upper bound on the maximal branching factor.

A related lower bound also applicable to the multiple disk model establishes that solving the duplicate elimination problem with N elements having P different values needs at least I/Os, since the depth of any decision tree for the duplicate elimination problem is at least . For a search with consistent estimates and a bounded branching factor, we assume to have , so that the I/O complexity reduces to .

Hash-based duplicate detection is designed to avoid the complexity of sorting. It is based on either one or two orthogonal hash functions. The primary hash function distributes the nodes to different files. Once a file of successors has been generated, duplicates are eliminated. The assumption is that all nodes with the same primary hash address fit into the main memory. The secondary hash function (if available) maps all duplicates to the same hash address. This approach can be illustrated by sorting a card deck of 52 cards. If we have only 13 internal memory places the best strategy is to hash cards to different files based on their suit in one scan. Next, we individually read each of the files to the main memory to sort the cards or search for duplicates.

The idea goes back to Bucket Sort. In its first phase, real numbers are thrown into n different buckets . All the lists that are contained in one bucket can be sorted independently by some other internal sorting algorithm. The sorted lists for are concatenated to a fully sorted list. In the worst case, each element is thrown into the same bucket, such that Bucket Sort does not improve the sorting. However, in the average case, the (internal) algorithm is much better. Let be a random variable that denotes how many elements fall into bucket i; that is, denotes the length of bucket list . For every bucket we might assume that the probability that an element falls into bucket for is . Therefore, follows a binomial distribution with parameters n and . The mean is and the variance is .

By iterating Bucket Sort, it is not difficult to come up with an external version of Radix Sort that scans the files more than once according to a radix representation of the key values. We briefly illustrate how it works. Say that we have some numbers in the range of 0 and 99, say 48, 26, 28, 87, 14, 86, 50, 23, 34, 69; and 17 in decimal (10-ary) representation. We devise 10 buckets , representing the numbers . We have two distribution and collection phases. In the first phase we distribute according to the right-most decimal, yielding , , , , , , , , , and . We collect the data by scanning 50, 23, 14, 34, 26, 86, 87, 17, 48, 28, 69, and distribute this set according to the left-most decimal, yielding , , , , , , , , , and for a final scan that produces the sorted outcome.

For the Fifteen-Puzzle problem in ordinary vector representation with a number for each board position, we have 16 phases for radix sort using 16 buckets.

If we have N data elements with a radix representation of length l with base b then the internal time complexity of Radix Sort is , and the internal space complexity . Since all operations can be buffered, the external time complexity reduces to I/Os. Since we may assume that the number b of buckets needed is small, we have an improvement to External Mergesort, if .

Structured duplicate detection incorporates a hash function that maps nodes into an abstract problem graph; this reduces the successor scope of nodes that have to be kept in main memory. Such hash projections are state space homomorphisms (as introduced in Ch. 4), such that for each pair of consecutive abstract nodes the pair of original nodes are also connected. A bucket now corresponds to the set of original states, which all map to the same abstract state. In difference to delayed duplicate detection, structured duplicate detection detects duplicates early, as soon as they are generated. Before expanding a bucket, not only the bucket itself, but all buckets that are potentially affected by successor generation have to be loaded and, consequently, fit into main memory.

This gives rise to a different definition of locality, which determines a handle for the duplicate detection scope. In difference to the locality for delayed duplicate detection the locality for structured duplicate detection is defined as the maximum node branching factor in the abstract state space .

If there are different abstractions to choose from, a suggestion is to take those that have the smallest ratio of maximum node branching factor and abstract state space size . The idea is that smaller abstract state space sizes should be preferred but usually lead to larger branching factors.

In the example of the Fifteen-Puzzle (see Fig. 8.8), the projection is based on nodes that have the same blank position. This state space abstraction also preserves the additional property that the successor set and the expansion sets are disjoint, yielding no self-loops in the abstract problem graph. The duplicate scope defines the successor buckets that have to be read into main memory.

The method is crucially dependent on the availability and selection of suitable abstraction functions that adapt to the internal memory constraints. In contrast, delayed duplicate detection does not rely on any partitioning beside the heuristic function and it does not require the duplicate scope to fit in the main memory.

Structured duplicate detection is compatible with ordinary and hash-based duplicate detection; in case the files that have to be loaded into the main memory no longer fit, we have to delay. However, the structured partitioning may have truncated the file sizes for duplicate detection to a manageable number. Each heuristic or hash function defines a partitioning of the search space but not all partitions provide a good locality with respect to the successor or predecessor states. State space abstractions are specialized hash functions in which we can study the successor relationship.

Many external memory algorithms arrange the data flow in a directed acyclic graph, with nodes representing physical sources. Every node writes or reads streams of elements.

Pipelining is a technique inherited from the database community, and improves algorithms that read data from and write data to buffered files. Pipelining allows algorithms to feed the output as a data stream directly to the algorithm that consumes the output, rather than writing it to the disk first.

Streaming nodes is equivalent to scan operations in nonpipelined external memory algorithms. The difference is that nonpipelined conventional scanning needs a linear number of I/Os, whereas streaming often does not incur any I/O, unless a node needs to access external memory data structures.

The nonpipelined and pipelined version of external breadth-first search are compared in Figure 8.9. In the pipelined version the whole algorithm is implemented in one scanner module that reads the nodes in and and scans through the stream in just one pass, and outputs the nodes in the current level and the multiset , which is passed directly to the sorter. The output of the sorter is scanned once to delete duplicates and its output is used as in the next iteration.

Pipelining can save constant factors in the I/O complexity of an algorithm. There is a trade-off, since it usually increases internal computational costs.

While external A* requires a constant amount of memory for the internal read and write buffers, IDA* requires very little memory that scales linear with the search depth. External A* removes all duplicates from the search, but to succeed it requires access to disk, which tends to be slow. Moreover, in search practice disk space is limited, too. Therefore, one option is to combine the advantages of IDA* and external A*.

As a first observation, pruning strategies for IDA* search (e.g., omitting predecessors from the successor lists) can help save external space and access time. The reason is that when detecting duplicates late, larger amounts of disk space may be required for generating them.

The integration of IDA* in external A* is simple. Starting with external A*, the buckets up to a predefined f-value (the split value) are generated. Then with increasing depth all buckets on the diagonal are read, and all states contained in the buckets are fed into IDA* as initial states, which is initialized to an anticipated solution length . As a side effect of all such runs being pairwise independent they can be easily distributed (e.g., on different processor cores).

Table 8.5 shows the results of solving a Twenty-Four-Puzzle instance according to different f-value splits to document the potential of such hybrid algorithms. In another instance (with an optimal step plan of 100 moves) a split value of 94 generated 367,243,074,706 nodes using 4.9 gigabytes on disk. A split value of 98 resulted in 451,034,974,741 generated nodes and 169 gigabytes on disk. We see that there is potential savings based on the different ordering of moves. By its breadth-first ordering, external A* necessarily expands the entire -diagonal, whereas by its depth-first ordering IDA* does not need to look at all states in the -diagonal. It can stop at the first goal found.

External pattern databases correspond to complete explorations of abstract state spaces. Most frequently they correspond to external BFS with delayed duplicate detection. The construction of external pattern databases is especially suited to frontier search, as no solution path has to be reconstructed.

During construction each BFS layer i has been assigned to an individual file . All states in have the same goal distance, and all states that map to a state in i share the heuristic estimate i. For determining the h-value for some given state u in algorithms like external A* we first have to scan the files to find u.

As this is a cost-intensive operation, whenever possible, pattern database lookup should be delayed, so that the heuristic estimates for a larger set of states can be retrieved in one scan. For example, external A* distributes the set of successor states of each bucket according to their heuristic estimates. Hence, it can be adapted to delayed lookup, intersecting the set of successor states with (the state set represented by) the abstract states in the file of a given h-value.

To keep the pattern database partitioned, we have to assume that the number of files that can be opened simultaneously does not exceed . We observe that matches the locality of an abstract state space graph.

Note that external breadth-first heuristic search with optimal bound directly leads to I/Os, but iteratively searching for is involved.

Can we avoid the additional sorting requests on the successor set? One solution is to already sort the successor sets in original space according to the order in abstract space. To allow full duplicate elimination, synonyms have to be disambiguated. A hash function h will be called order preserving, if for all u in original space implies . For a pattern database heuristics it not difficult to obtain an order-preserving hash function. In concrete space with state comparison function we can include any hash function that has been used to order the states in abstract space as a prefix to . We extend state u to and define if either or and .

When using maximization over multiple-pattern databases, a hash function that is order preserving with respect to more than one abstraction is more difficult to obtain. However, successive projection and resorting always works. As the successor sets for resorting have no duplicates, external sorting can be attributed to the set V not to E. For this case, the number of pattern databases k leads to the overall complexity of I/Os.

If a heuristic estimate is needed as soon as a node is generated, an appropriate choice for creating external memory pattern databases is a backward BFS with structured duplicate detection, as structured duplication already provides locality with respect to a state space abstraction function. Afterwards, the construction patterns are arranged according to pattern blocks, one for each abstract state. When a concrete heuristic search algorithm expands nodes, it must check whether the patterns from the pattern-lookup scope are in the main memory, and if not, it reads them from disk. Pattern blocks that do not belong to the current pattern-lookup scope are removed. When the part of internal memory is full, the search algorithm must decide which pattern block to remove from internal memory, for example, by adopting the least-recently used strategy.

Symbolic pattern databases can also be constructed externally. Each BFS level (in the form of a BDD) can be flushed to disk, so that the memory for representing this level can be reused. Again the heuristic is partitioned into files and pattern database lookup in algorithms like external A* is delayed.

As the BDD representation of a state set is unique, during symbolic pattern database construction no effort for eliminating duplicates in one BFS level is required. Before expanding a state set, however, we have to apply duplicate detection with regard to previous BFS levels. If this is too expensive in some critical level, we may afford some states to be represented more than once, but have to ensure termination.

For the construction of larger pattern databases, the intermediate result of the symbolic successor sets (the image) can also become too large to be completed in the main memory. As a solution, we can compute all subimages individually (one for each individual action), flush them, and externally compute their disjunction (e.g., in the form of a binary tree) in a separate program.

Even if all refinements are played, the external exploration might still be too heavy to complete on disk. Besides starting from scratch with some approximate search, relay search can be directly applied to the best search bucket(s) found on an completed f-diagonal. All other buckets are eliminated from the search. As a result a lower and upper bound on the problem instances are produced.

Figure 8.10 illustrates the memory profile for a relay solution that solves fully random instances of the Thirty-Five-Puzzle with symbolic pattern databases. We observe three exploration peaks, where the search consumed too much resources and it was restarted with the currently best solution buckets. Starting with an initial estimate 152 as a lower bound the obtained range for the optimal solution was . The large-scale exploration consumed bytes ( terabytes).

Typically, a state space is generated by a depth-first or a breadth-first exploration that uses a hash table to avoid reexpansion of states. We choose an external breadth-first exploration to handle large state spaces. Since in an external setting a hash table is not affordable, we rely on delayed duplication detection. It consists of two phases, first removing duplicates within the newly generated layer, and then removing duplicates with respect to previously generated layers. Note that an edge is a duplicate if and only if its predecessor u, its state v, and the action a match an existing edge. Thus, in undirected graphs, there are two different edges for each undirected edge. In our case, sorting-based delayed duplicate detection is best suited as the sorted order and is further exploited during the backward phase.

Algorithm 8.8 shows external value iteration in pseudo code. For each depth value d the algorithm maintains the BFS layers on disk. The first phase ends up by concatenating all layers into one list that contains all edges reachable from s. For bounded locality, the complexity of this phase is I/Os.

This is the most critical part of the approach and deserves more attention. To perform the update on the value of state v, we have to bring together the value of its successor states. Because they both are contained in one file, and there is no arrangement that can bring all successor states close to their predecessor states, we make a copy of the entire graph (file) and deal with the current state and its successor differently. To establish the adjacencies, the second copy, called , is sorted with respect to the node u. Remember that is sorted with respect to the node v.

A parallel scan of files and gives us access to all the successors and values needed to perform the update on the value of v. This scenario is shown in Figure 8.12 for the graph in the example. The contents of Temp and , for , are shown along with the heuristic values computed so far for each edge . The arrows show the flow of information (alternation between dotted and dashed arrows is just for clarity). The results of the updates are written to the file containing the new values for each state after iterations. Once is computed, the file can be removed since it is no longer needed.

Algorithm 8.9 shows the backward update algorithm for the case of MDP models; the other models are similar. It first copies the list in using buffered I/O operations, and sorts the new list according to the predecessor states u. The algorithm then iterates on all edges from and searches for the successors in . Since is sorted with respect to states v, the algorithm never goes back and forth in any of the or files. Note that all reads and writes are buffered and thus can be carried out very efficiently by always doing I/O operations in blocks.

We now discuss the different cases that might arise when an edge is read from . States from Figure 8.11 that comply with each case are referred to in parentheses. The flow of the values in h for the example is shown in Figure 8.12.

For edges read from , we have:

The array is initialized to the edge weight , for each . Once all the successors are processed, the new value for v is the minimum of the values stored in the q-array for all applicable actions.

An important point to note here is that the last edge read from isn't used. The operation Push-back puts back this edge into . This operation incurs in no physical I/O since the file is buffered. Finally, to handle case II, a copy of the last updated node and its value are stored in variables and , respectively.

As an example domain we consider the sliding-tile puzzle, performing two experiments: one with deterministic moves, and the other with noisy actions that achieve their intended effects with probability and no effect with probability . The rectangular sliding-tile puzzle cannot be solved with internal value iteration because the state space did not fit in RAM. External value iteration generated a total of 1,357,171,197 edges taking 45 gigabytes of disk space. The backward update has finished successfully in 72 iterations using 1.4 gigabytes RAM. The value function for initial state converged to 28.8889 with a residual smaller than .

The general setting (see Fig. 8.14) is a background hash table kept on the SSD, which can hold entries. We additionally assume a foreground hash table with entries. The ratio between foreground and background is, therefore, . Collisions especially on the background hash table can yield additional burden. As chaining requires overhead for storing and following links, we are left with open addressing and adequate probing strategies.

As indicated earlier, SSDs prefer sequential writes and sequential reads, but can cope with an acceptable number of random reads. As linear probing finds elements through sequential scanning, it is I/O efficient. For load factor , a successful search requires about accesses on the average, but an unsuccessful search requires about accesses on the average. For a hash table that is filled up to % we have less than three states to look at on the average, which easily fit into the I/O buffer. Given that random access is slower than sequential access, this implies that unless the hash table becomes filled, linear probing with one I/O per lookup per node is an appropriate option for SSD-based hashing.

The simplest method to apply SSDs in graph search is to store each node at its background hash address in a file, and if occupied, to apply a conflict resolution strategy on disk. By their large seek times, this option is clearly infeasible for HDDs, but it does apply to some extent to SSDs. Nonetheless, besides extensive use of random writes that operate blockwise and are, thus, expected to be slow, one problem of the approach is the initialization time, incurred by erasing all existing data stored in the background hash table.

Hence, we apply a refinement to speed up search. With one additional bitvector array kept in RAM, we denote whether or not a state is already stored on disk. This limits initialization time to reset all bits in main memory, which is much faster. Moreover, this saves lookup time in case of hashing a new state with an unused table entry. Figure 8.15 (left) illustrates the approach. The bitvector occupied memorizes, if the address on the SSD is in use.

The extra amount of RAM additionally limits the size of the search spaces to be processed. In search practice with a full state vector of several hundred bytes to be stored in the background hash table, however, investing one bit per state in RAM does no harm, given that the ratio between main and external memory remains moderate. The only limit for the exploration is imposed by the number of states that can be stored on the solid state disk, which we assume to be sufficiently large.

For analyzing the approach, let n be the number of nodes and e be the number of edges in the state space graph that are looked at. Without occupied vector, this requires e lookup and n insert operations. Let B be the size of a block (amount of data retrieved, or written with one I/O operation) and be the fixed length of the state vector. As long as , at most two blocks are read for each lookup (when linear probing arrives at the end of the table, an additional seek to the start of the file is needed). For no additional random read access is necessary. After the lookup, an insert operation results in one random write. This results in a flash I/O complexity of , where p is the penalty factor for random write operations. Using the occupied vector, the number of read operations reduces from e to n, assuming that no collisions take place.

As the main bottleneck of the approach is random writing to the background hash table, as another refinement we can additionally employ a foreground hash table as a write buffer. Due to numerous insert operations, the foreground hash table will become filled, and then has to be flushed to the background, which incurs writes and subsequent reads. One option that we call merging is to sort the internal hash table with regard to the external hash function before flushing. If the hash functions are correlated, the sequence is already presorted, by means that the number of inversions is small. If is small we use an algorithm like adaptive sort that exploits presorting. While flushing we now have a sequential write (due to the linear probing strategy), such that the total worst-case I/O time for flushing is bounded by the number of flushes times the efforts for sequential writes. Figure 8.15 (right) illustrates the approach. Since we are able to exploit sequential data processing, updating the background hash table corresponds to a scan (see Fig. 8.16). Blocks are read into the RAM and merged with the internal information and then flushed back to SSD.

Here we store all state vectors in a file on the external storage device, and substitute the state vector by its relative file pointer position. For an external hash table of size m this requires bits per entry and bits in total. Figure 8.17 illustrates the approach with arrows denoting the position on external memory. An additional bitvector is no longer needed.

This strategy also results in e lookups and n insert operations. Since the ordering of states on the SSD does not necessarily correlate with the order in main memory, the lookup of states due to linear probing induces multiple random reads. Hence, the amount of individual blocks that have to be read is bounded by . In contrast, all insert operations are performed sequentially, utilizing a cache of B bytes in memory. Subsequently, this approach performs random reads to the SSD. As long as this approach performs less random read operations than mapping. By using another internal hashing strategy, for example, cuckoo hashing (see Ch. 3), we can reduce the maximum number of lookups to 2. As sequential writing of n states of s bytes requires I/Os, the total flash-memory I/O complexity is .

The previous approaches either require significant time to write data according to or request significant sizes of foreground memory. There are further trade-offs that we will consider next.

One first solution, called padding, appends the entire foreground hash table as it is to the existing data on the background table. Hence, the background hash function can be roughly characterized as , where i denotes the current number of flushes, and s the state to be hashed.

Writing is sequential, and conflict resolution strategy is inherited from the internal memory. For several flushing readings, a state for answering membership queries becomes involved, as the search for one state incurs up to r many table lookups. Conflict resolution may lead to an even worse performance. For a moderate number of states that exceed RAM resources only by a very small factor, however, the average performance is expected to be good. As far as all states can reside in main memory no access to the background hash table is needed.

We can safely assume that load factor is small enough, so that the extra amount of work due to linear probing is transparent by using block accesses. Again, e lookups and n insert operations are performed. Let be the number of successors generated in phase i, . For phase 0 no access to the background table is needed. For phase i, , at most blocks have to be read. Together with the sequential write of n elements (in r rounds) this results in a flash-memory complexity of I/Os. An illustration is provided in Figure 8.18 (left). The entire foreground hash table has been flushed once, and the maximum number of flushes is set to 3.

The obvious alternative is to slice the background hash table, such that becomes plus the number of flushes. An illustration is provided in Figure 8.18 (right); this is the situation after one flush, and again, at most three flushes are assumed.

The disadvantage of processing the entire external hash table during flushing is compensated by the fact that the probing sequences in the hash tables can now be searched concurrently. For the lookup we use a bit vector (of size equal to the number of flushes) that monitors if an individual probing sequence has terminated with an empty bucket. If all probing sequences fail, the query itself has failed.