Improving Search Using Indexing: A Study with Temporal CSPs

Abstract

Most studies concerning constraint satisfaction
\nproblems (CSPs) involve variables that take values
\nfrom small domains. This paper deals with
\nan alternative form of temporal CSPs; the number
\nof variables is relatively small and the domains
\nare large collections of intervals. Such
\nsituations may arise in temporal databases where
\nseveral types of queries can be modeled and
\nprocessed as CSPs. For these problems, systematic
\nCSP algorithms can take advantage of temporal
\nindexing to accelerate search. Directed
\nsearch versions of chronological backtracking
\nand forward checking are presented and tested.
\nOur results show that indexing can drastically
\nimprove search performance.