| Home > Publications > Reports > Informatics (CW) |
CW 500
Beata Sarna-Starosta and Tom Schrijvers
Indexing techniques for CHR based on program tranformation
Abstract
Multi-headed rules are essential for the expressiveness of CHR, but incur a considerable performance penalty. Current indexing techniques are often unable to address this problem. They are effective only when matchings have a particular form, or offer good run-time complexity rather than good absolute figures. In this paper we describe three advanced indexing techniques: (1) two program transformations that make other indexing techniques more effective, (2) an index for ground terms more efficient than hash tables, and (3) a post-processing program transformation that eliminates runtime overhead of (1) and (2). We compare these techniques with the current state of the art, and give measurements of their effectiveness in K.U.Leuven CHR and CHRd.
report.pdf (202K) / mailto: T. Schrijvers