Technical Report No.108 - Abstract

Joerg Hoffmann, Jana Koehler
A new Method to Index and Query Sets

Let us consider the following problem: Given a (probably huge) set of sets S and a query set q, is there some set s \in S such that s \subseteq q? This problem occurs in at least three application areas: the matching of a large number (usually several 100,000s) of production rules, the processing of queries in data bases supporting set-valued attributes, and the identification of inconsistent subgoals during artificial intelligence planning. In this paper, we introduce a data structure and algorithm that allow a compact representation of such a huge set of sets and an efficient answering of subset and superset queries.