Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 09491

Graph Search Engineering

( Nov 29 – Dec 04, 2009 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



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.

  • Deepak Ajwani (Aarhus University, DK) [dblp]
  • Husain Aljazzar (Universität Konstanz, DE)
  • David A. Bader (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Björn Borowsky (Leverkusen, DE)
  • Dragan Bosnacki (TU Eindhoven, NL) [dblp]
  • Gene Cooperman (Northeastern University - Boston, US)
  • Martin Dietzfelbinger (TU Ilmenau, DE) [dblp]
  • Stefan Edelkamp (Universität Bremen, DE) [dblp]
  • Eric Hansen (Mississippi State University, US)
  • Malte Helmert (Universität Freiburg, DE) [dblp]
  • Riko Jacob (TU München, DE) [dblp]
  • Peter Kissmann (TU Dortmund, DE)
  • Sebastian Kupferschmid (Universität Freiburg, DE)
  • Stefan Leue (Universität Konstanz, DE) [dblp]
  • Alberto Lluch Lafuente (University of Pisa, IT) [dblp]
  • Hartmut Messerschmidt (Universität Bremen, DE)
  • Ulrich Carsten Meyer (Goethe-Universität - Frankfurt a. M., DE) [dblp]
  • Vitaly Osipov (KIT - Karlsruher Institut für Technologie, DE)
  • Kairong Qian (Synopsys Inc. - Mountain View, US)
  • Wheeler Ruml (University of New Hampshire - Durham, US)
  • Theo Ruys (University of Twente, NL)
  • Peter Sanders (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Viktor Schuppan (Bruno Kessler Foundation - Trento, IT)
  • Stefan Schwoon (TU München, DE)
  • Pavel Simecek (Masaryk University - Brno, CZ)
  • Johannes Singler (KIT - Karlsruher Institut für Technologie, DE)
  • Carsten Sinz (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Nathan Sturtevant (University of Alberta - Edmonton, CA) [dblp]
  • Damian Sulewski (Universität Bremen, DE)
  • Enrico Tronci (Sapienza University of Rome, IT)
  • Martin Wehrle (Universität Freiburg, DE) [dblp]
  • Anton Wijs (INRIA - Grenoble, FR) [dblp]
  • Philipp Woelfel (University of Calgary, CA) [dblp]
  • Rong Zhou (Xerox PARC - Palo Alto, US)

  • 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