Patent ID: 7805454

Claim:
A method for graph searching comprising: using state-space abstraction to form an abstract state-space graph that is used to partition a graph into multiple independent regions that do not interfere with each other for a period of time during the search, wherein the graph includes at least a plurality of nodes and an abstract node y=p(x) is an image of a node x or a plurality of nodes, under a state-space projection function p($) for the abstract state-space graph, and successors(y) are a set of successor abstract nodes of y in the abstract state-space graph; and using parallel structured duplicate detection to distribute a search work load across multiple processing units for an amount of time during which the independent regions are capable of being maintained as independent, wherein searching of the multiple independent regions of the partitioned graph are undertaken in parallel, and wherein duplicate-detection scopes of nodes x 1 and x 2 , of the plurality of nodes, are disjoint under the state-space projection function p($), if a set of successors(y) of an image of x 1 is disjoint from a set of successors(y) of an image of x 2 , in the abstract state-space graph.