Dynamic State-Space Partitioning in External-Memory Graph Search

Authors Rong Zhou, Eric A. Hansen



PDF
Thumbnail PDF

File

DagSemProc.09491.2.pdf
  • Filesize: 93 kB
  • 7 pages

Document Identifiers

Author Details

Rong Zhou
Eric A. Hansen

Cite AsGet BibTex

Rong Zhou and Eric A. Hansen. Dynamic State-Space Partitioning in External-Memory Graph Search. In Graph Search Engineering. Dagstuhl Seminar Proceedings, Volume 9491, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.09491.2

Abstract

State-of-the-art external-memory graph search algorithms rely on a hash function, or equivalently, a state-space projection function, that partitions the 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.
Keywords
  • External-memory graph search
  • heuristic search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail