https://www.dagstuhl.de/09491

29. November – 04. Dezember 2009, Dagstuhl-Seminar 09491

Graph Search Engineering

Organisatoren

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)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Seminar Proceedings DROPS
Teilnehmerliste

Summary

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.

Classification

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

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

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.