Patent ID: 8694547

Claim:
A method for performing an external memory graph search of a search space by a computing system having at least a computing section, an input/output (I/O) and a memory arrangement, the search space including a plurality of nodes, at least some of the nodes stored on an external memory, the method comprising: applying a projection function for the graph search; applying, during the search, a dynamic partition process that allows the projection function to adapt to at least one of a problem instance, search strategy, and heuristics in a course of the search and monitors a distribution of the nodes among buckets configured to hold the nodes; modifying the projection function to adapt to the distribution of the nodes during the search, wherein the method is performed by the computing system; calculating the largest bucket in an abstraction of the original search space; selecting a state variable from a plurality of state variables which, when added to the projection function, results in a minimum size of the largest bucket; performing the dynamic partition process as an iterative approach to refining an initially null abstraction, which maps nodes to a single bucket, until the size of the largest bucket in the partition is below a predefined threshold or the maximum number of the abstract states in the abstract search space have been reached; and storing the vector of counters at every abstract state such that a size of a largest bucket can be accurately computed without actually moving the nodes to their new buckets.