language: en

Performance of Temporal Reasoning Systems

Ed Yampratoom James F. Allen
The University of Rochester Computer Science Department
Rochester, New York 14627
TRAINS Technical Note 93-1 May 1993

Abstract This paper describes the performance evaluation of six temporal reasoning systems. We show that if you are working with large temporal datasets where information is added incrementally throughout the execution of the program, systems using incompletely connected graphs (i.e., TMM, TimeGraph and TimeGraph-II) seem the best option. While they do not offer the constant query time of systems using fully connected graphs (i.e. the systems based on constraint satisfaction), the savings at assertion time are so substantial that the relatively small performance penalty for queries is a reasonable tradeoff. Of course, these systems do not offer the expressiv ity of the interval-based systems as they only handle point-based relations. Of the three, TimeGraph-II offers a wider range of qualitative relations as it handles point inequality. It does not currently handle metric information, however, as do TMM and TimeGraph. Thus decisions between these three may be more determined by the reasoning capabilities required rather than raw performance.

[This material is based upon work supported in part by U.S. Air Force-Rome Laboratory research contract no. F30602-91-C-0010.]