Large graph searches, such as finding optimal solutions to sliding-tile puzzles, planning problems, or protein alignments, have to remember which states they have already seen. The standard check is a hash-table lookup for every newly generated state. When that table outgrows RAM, there are two established ways to keep going. Delayed duplicate detection (DDD) writes new states sequentially to disk and removes duplicates later in large batches. Immediate duplicate detection (IDD) puts the table on a solid-state drive (SSD) and probes it right away. Each fails somewhere. DDD searches blindly between batches: it cannot use good tie-breaking, and it must expand an entire final layer of equally promising states before it can certify the answer. IDD pays a random SSD read whenever its in-RAM filter cannot rule a state out, and for cheap-to-generate states that read becomes the bottleneck.
We propose a third policy that decides per state. A compact in-RAM fingerprint table answers one question for each new state: "definitely never seen" or "maybe seen." States that are definitely new go straight into an in-memory priority queue, exactly as in ordinary A*. "Maybe seen" states are not probed on the SSD. They are appended to a sequential log and reconciled in a batch, as in DDD. The RAM given to fingerprints is a tunable budget. As it shrinks, fingerprints are dropped bucket by bucket, and the search slides smoothly from IDD-like behaviour toward pure DDD, with no performance cliff in between. The claim to test is that this policy uses zero random SSD reads, removes most of the final-layer penalty, and degrades predictably as RAM shrinks. Both pure strategies are endpoints of this single dial.
Where this sits in prior work
The DDD line supplies the batch machinery we reuse. It includes Korf's sort-merge formulation in Delayed Duplicate Detection: Extended Abstract. It also includes hash-partitioned bucket files in Best-First Frontier Search with Delayed Duplicate Detection and in PE2A* (External Memory Best-First Search for Multiple Sequence Alignment), which solved all 82 affine-gap BAliBASE instances. Its most recent use is the bidirectional PEM-BAE* (On Parallel External-Memory Bidirectional Search). All of these defer every state, including the large majority that are genuinely new.
The bidirectional paper motivates the proposal directly. Its authors report that delayed detection makes the two search frontiers find their meeting point late, which causes redundant expansions. Revisiting Immediate Duplicate Detection in External Memory Search provides both the closest method and the key constraint. Lin and Fukunaga keep compact partition keys in RAM to skip pointless SSD probes, and they beat DDD by 3–5x on IPC planning problems. However, they concede that DDD still wins on the 15-puzzle, because a random SSD read costs too much relative to generating one node.
Our difference from Lin and Fukunaga is one decision: what happens when the filter says "maybe." They probe the SSD; we defer to a sequential batch. That choice is what should let one system win on both kinds of domain. Structured Duplicate Detection (Structured Duplicate Detection in External-Memory Graph Search) supplies the locality idea we use to decide which buckets keep their fingerprints in RAM. Its own rigid requirement, that the whole active scope must fit in memory, is the kind of cliff we aim to avoid.
Core Claim
Let $d$ be the fraction of generated states that are true duplicates, and let $\epsilon$ be the filter's false-positive rate on new states. The fraction of states sent to the delayed log is then
$$ \delta = d + (1-d)\,\epsilon . $$
Only these states incur deferral cost. All other states get immediate, A*-quality treatment. Both pure strategies are special cases. With no fingerprints, $\epsilon = 1$ and every state is deferred, which is pure DDD. With exact fingerprints, $\epsilon = 0$, but true duplicates still cost a sequential write instead of a random read, which is cheaper than IDD.
Optimality is preserved by one rule. Before the search expands from the priority queue at cost bound $f$, every deferred state with a lower bound below $f$ must be reconciled. Deferred states tied at the goal's $f$ value never need reconciling once a goal is selected. The final-layer penalty therefore shrinks from "the whole final layer" to roughly $\delta$ of it.
For a fixed fingerprint size, $\epsilon$ is controlled by how many fingerprint bits per stored state the RAM budget allows. The claim therefore predicts a smooth runtime-versus-RAM curve, not a cliff.
Research Program
We will build the policy on top of a hash-bucketed external A* in the style of PE2A* and PEM-BiHS, so that the bucket files and merge phases are shared code with the baselines.
Each disk bucket gets an optional fingerprint table: a quotient-style table of short hashes of the states closed in that bucket. Absence of a matching fingerprint guarantees the state is new. New fingerprints are inserted at generation time, so two identical new states generated close together are caught as well; the second is simply deferred.
When the RAM budget cannot hold all tables, the system evicts the tables of buckets that received the fewest successors in the previous cost layer, and those buckets revert to pure DDD. This borrows SDD's observation that successors concentrate in a few neighbouring regions of the state space, but applies it softly, as a cache, instead of as a hard fit requirement.
We will analyse three things. The first is how $d$ and $\epsilon$ predict deferral volume and final-layer work across domains. The second is whether the eviction rule beats random or static assignment. The third is where the IDD/DDD crossover reported by Lin and Fukunaga falls under each policy. A bidirectional variant, which tests for frontier meetings at generation time for definitely-new states, is a natural extension aimed at PEM-BAE*'s late-meeting problem. It is secondary to the unidirectional study.
Baselines
The naive reference point is in-memory A* given the same RAM cap, with the operating system's swap on the same NVMe SSD. It shows the cliff we claim to avoid.
The first strong competitor is pure hash-based DDD external A*, our own implementation of the PE2A*/PEM-BiHS bucket scheme. On the 15-puzzle it is the method Lin and Fukunaga found hardest to beat, although the file gives no numeric 15-puzzle runtime ("no reported result found on Lacuna for 15-puzzle DDD runtime"). On the 24-puzzle, PEM-BAE* is reported to expand 4.4% of AIDA*'s nodes and run 4.5x faster.
The second strong competitor is A*-IDD with segmented compression from Revisiting Immediate Duplicate Detection in External Memory Search. It reports solving 33 of 34 IPC instances, against 27 of 34 for standard compression, with 3–5x speedups over DDD External A*. This is the strongest method on planning domains and the one we must match there.
All methods share the state encoding, heuristics, bucket hash function, SSD, thread count, and an identical total RAM cap. The RAM cap is swept from roughly 2% to 100% of what in-memory A* needs on each instance. Each method's tunable parameters (bucket count, partition count $p$, fingerprint width) get the same per-domain grid-search budget on held-out instances. Beating the baselines means the following. On the 15-puzzle and 24-puzzle, we must be no slower than pure DDD at every RAM level and faster where RAM permits fingerprints. On the IPC set, we must match or exceed A*-IDD's 33/34 coverage and its runtime. On BAliBASE, we must solve all 82 instances with lower total time than PE2A*-style DDD.
The key ablation keeps our filter and RAM budget identical but sends "maybe" states to a random SSD probe instead of the delayed log. This is essentially IDD with our filter, and it isolates the defer-on-uncertainty decision. A second ablation replaces the locality-based eviction rule with random eviction.
Why not just…?
Why not just use Lin and Fukunaga's immediate detection everywhere? Their own paper reports that DDD stays faster on the 15-puzzle, because even filtered random SSD reads dominate when generating a node costs a few instructions. Our probe-versus-defer ablation tests this directly. If probing matches deferring on the 15-puzzle at our filter's false-positive rate, the advantage of our design shrinks to the planning domains, and we will report that.
Why not just keep pure DDD and accept its overhead? It cannot use good tie-breaking, and it must expand the full final layer before certifying the solution. The bidirectional study observes late frontier meetings for the same reason. We will measure final-layer expansions directly. If $\delta$ is close to 1 in practice, meaning the domain is dominated by true duplicates, our method collapses to DDD with only filter overhead added. That is a real possibility in domains with many duplicates, such as the 4-peg Towers of Hanoi, and we will include it.
Why not just run in-memory A* on fast swap or remote paging? COMEX (Cooperative Memory Expansion via OS Kernel Support for Networked Computing Systems) reports native Linux swapping up to 170x slower than its remote paging when the working memory is 10x local DRAM. Even remote RDMA memory without a local cache costs about 783 µs per read (One Buffer Manager to Rule Them All: Using Distributed Memory with Cache Coherence over RDMA), because hash lookups scatter across the address space. The swap baseline in our RAM sweep quantifies this on our hardware.
Why not just compress states harder and stay in RAM? Semantic compression such as Blitzcrank: Fast Semantic Compression for In-memory Online Transaction Processing cut TPC-C memory by 85%, a constant factor. SDD's 15-puzzle results show gaps of 28 GB versus 42 MB, which compression alone cannot close. Compression is complementary: it would make the fingerprint tables smaller, but it does not replace externalization.
Proposed Experiments
We use the 100 standard 15-puzzle instances and the 24-puzzle instances as the cheap-node domains, the 34-instance IPC STRIPS selection described by Lin and Fukunaga as the expensive-node domain, BAliBASE Reference Set 1 as the high-branching domain, and 4-peg Towers of Hanoi as a domain dominated by duplicates. For every RAM level we record wall time, coverage, nodes expanded, final-layer expansions, bytes of sequential versus random SSD I/O, and the measured $d$ and $\epsilon$.
The decisive check is the runtime-versus-RAM curve on the 15-puzzle and on the IPC set. The proposal succeeds if one configuration of our method stays at or below the better of pure DDD and A*-IDD across the whole sweep. In particular, it must beat DDD on the 15-puzzle wherever fingerprints fit, and match A*-IDD's coverage on the IPC set. A second check is whether the measured $\delta$ predicts final-layer work and deferral volume within a small error. If it does, $\delta$ becomes a practical, pre-computable guide for choosing how to spend RAM in external search.
References
- Delayed Duplicate Detection: Extended Abstract
- Best-First Frontier Search with Delayed Duplicate Detection
- External Memory Best-First Search for Multiple Sequence Alignment
- On Parallel External-Memory Bidirectional Search
- Revisiting Immediate Duplicate Detection in External Memory Search
- Structured Duplicate Detection in External-Memory Graph Search
- Cooperative Memory Expansion via OS Kernel Support for Networked Computing Systems
- One Buffer Manager to Rule Them All: Using Distributed Memory with Cache Coherence over RDMA
- Blitzcrank: Fast Semantic Compression for In-memory Online Transaction Processing