File

Document Identifiers

Subject Classification

Metrics

Abstract

State-of-the-art external-memory graph search algorithms rely on a hashfunction, or equivalently, a state-space projection function, that partitionsthe stored nodes of the state-space search graph into groups of nodes that are stored as separate files on disk. The scalability and efficiency of the search depends on properties of the partition: whether the number of unique nodes in a file always fits in RAM, the number of files into which the nodes of the state-space graph are partitioned, and how well the partitioning of the state space captures local structure in the graph. All previous work relies on a static partitioning of the state space. In this paper, we introduce a method for dynamic partitioning of the state-space search graph and show that it leads to substantial improvement of search performance.

Cite AsGet BibTex

@InProceedings{zhou_et_al:DagSemProc.09491.2,  author ={Zhou, Rong and Hansen, Eric A.},  title ={{Dynamic State-Space Partitioning in External-Memory Graph Search}},  booktitle ={Graph Search Engineering},  pages ={1--7},  series ={Dagstuhl Seminar Proceedings (DagSemProc)},  ISSN ={1862-4405},  year ={2010},  volume ={9491},  editor ={Lubos Brim and Stefan Edelkamp and Erik A. Hansen and Peter Sanders},  publisher ={Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},  address ={Dagstuhl, Germany},  URL ={https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09491.2},  URN ={urn:nbn:de:0030-drops-24334},  doi ={10.4230/DagSemProc.09491.2},  annote ={Keywords: External-memory graph search, heuristic search}}

Author Details