November 29 – December 4 , 2009, Dagstuhl Seminar 09491

Graph Search Engineering


Lubos Brim (Masaryk University – Brno, CZ)
Stefan Edelkamp (Universität Bremen, DE)
Eric Hansen (Mississippi State University, US)
Peter Sanders (KIT – Karlsruher Institut für Technologie, DE)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants


Graph Search algorithms and their variants play an important role in many branches of computer science. All use duplicate detection in order to recognize when the same node is reached via alternative paths in a graph. This traditionally involves storing already-explored nodes in random-access memory (RAM) and checking newly-generated nodes against the stored nodes. However, the limited size of RAM creates a memory bottleneck that severely limits the range of problems that can be solved with this approach. Although many clever techniques have been developed for searching with limited RAM, all eventually are limited in terms of scalability, and many practical graph-search problems are too large to be solved using any of these techniques.

Over the past few years, several researchers have shown that the scalability of graph-search algorithms can be dramatically improved by using external memory, such as disk, to store generated nodes for use in duplicate detection. However, this requires very different search strategies to overcome the six orders-of-magnitude difference in random-access speed between RAM and disk. We discussed recent work on external-memory graph search, including duplicate-detection strategies (delayed, hash-based, and structured); integration of these strategies in external-memory versions of breadth-first search, breadth-first heuristic, and frontier search; the inclusion of a perfect hash function, as well as combining parallel and disk-based search; external-memory pattern-database heuristics; and applications of external-memory search to AI planning, automated verification, and other search problems. Implicit graph search that is in the scope of the seminar included deterministic and non-deterministic models, as well as game-theoretical and probabilistic models.

Moreover, the seminar was specifically concerned with algorithm designs for implicit graph search on modern personal computer architectures, e.g. subject to several processing units on the graphic card, and hierarchical memory including solid-state disks. Applications areas for new algorithm designs that exploit modern hardware were found in the model checking community, but also in AI planning and game playing.

The industrial impact was located mostly in the area of software validation, and to some extent in the area of hardware verification. We saw large social network analyses and efficient route planning that were close to industrial application. Investment of parallel and distributed hardware led to new and scalable solutions. In some cases, advances in PC hardware like SSD and GPU already could made a difference. We have had one guest from Synopsis that indicated how influencing actual research is in validating chip design. Other participants from industry were discussing the news in the field.

The seminar mixture of graph theoreticians and application oriented researchers was fruitful. On the one hand, we had the algorithm engineers with theoretical background in hierarchical memory algorithm designs, then the AI researchers concerned with solving their single- and multi-agent search challenges, and last but not least the formal method people, trying to certify or falsify hard- and software designs.

Overall, the seminar was a big success for seeding future research. Tutorials helped to bring the communities together. We thereby established that the gap between the fields was not big. Recently published results were mixed with new insights right from the research labs. Among many other important bricks of work there was the observation that different cache structures are very effective in detecting duplicates in RAM. To address new challenges we have had "open spaces" for discussing and attacking unresolved problems and current research trends.


  • Seminar
  • Ai/robotics
  • Ds/alg/compl
  • Semantics/formal
  • Softcomp/evolalg
  • Sweng
  • Verification/logic
  • Interdisciplinary
  • Industry


  • 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


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.