DROPS

Document

09491 Abstracts Collection – Graph Search Engineering

Authors: Lubos Brim, Stefan Edelkamp, Eric A. Hansen, and Peter Sanders

Published in: Dagstuhl Seminar Proceedings, Volume 9491, Graph Search Engineering (2010)

Abstract

From the 29th November to the 4th December 2009, the Dagstuhl Seminar 09491 ``Graph Search Engineering '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Lubos Brim, Stefan Edelkamp, Eric A. Hansen, and Peter Sanders. 09491 Abstracts Collection – Graph Search Engineering. In Graph Search Engineering. Dagstuhl Seminar Proceedings, Volume 9491, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{brim_et_al:DagSemProc.09491.1,
  author =	{Brim, Lubos and Edelkamp, Stefan and Hansen, Eric A. and Sanders, Peter},
  title =	{{09491 Abstracts Collection – Graph Search Engineering}},
  booktitle =	{Graph Search Engineering},
  pages =	{1--31},
  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.1},
  URN =		{urn:nbn:de:0030-drops-24315},
  doi =		{10.4230/DagSemProc.09491.1},
  annote =	{Keywords: Model Checking, Artificial Intelligence, AI Planning, State Explosion Problem, Error Detection, Protocol Analysis, Software Verification and Validation, Heuristics, Pattern/Abstraction Databases, I/O Efficient Search, Solid State Disks, GPU}
}

Document

DOI: 10.4230/DagSemProc.09491.2

Dynamic State-Space Partitioning in External-Memory Graph Search

Authors: Rong Zhou and Eric A. Hansen

Published in: Dagstuhl Seminar Proceedings, Volume 9491, Graph Search Engineering (2010)

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.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Search Results

Documents authored by Hansen, Eric A.

09491 Abstracts Collection – Graph Search Engineering

Abstract

Cite as

Dynamic State-Space Partitioning in External-Memory Graph Search

Abstract

Cite as

Thanks for your feedback!

Could not send message