RE:Tree: An Efficient Index Structure for Regular Expressions

Abstract: Due to their flexibility, expressive power, and ability to capture structure, Regular Expressions (REs) are quickly becoming an integral part of language specifications for several important application scenarios. Examples include the XPath pattern language for XML documents and the policy language of the Border Gateway Protocol (BGP) for exchanging routing information across Internet domains. Many of these applications have to manage huge databases of RE specifications and need to provide an effective matching mechanism that, given an input string, quickly identifies the REs in the database that match it. This ``RE retrieval'' problem is important for a number of Internet- infrastructure components, including XML routing, XML filtering, BGP routing, information dissemination, and event notification. In this paper, we propose the RE-tree, a novel index structure for large databases of RE specifications. Given an input query string, the RE-tree speeds up the retrieval of matching REs by focusing the search and comparing the input string with only a small fraction of REs in the database. Even though the RE-tree is similar in spirit to other tree-based structures that have been proposed for indexing multi-dimensional and metric spaces, RE indexing is significantly more challenging since REs typically represent infinite sets of strings with no well-defined notion of spatial locality. To address these new challenges, our RE-tree index structure relies on several novel measures for comparing the relative sizes of infinite regular languages; these range from ``rate-of-growth'' estimates to encoding costs of sample strings using the corresponding REs. We also propose innovative solutions for the various RE-tree operations, including the effective splitting of RE-tree nodes and computing a ``tight'' bounding RE (under a space constraint) for a collection of REs. Finally, we demonstrate how sampling-based approximation algorithms can be used to significantly speed up the performance of RE-tree operations. To the best of our knowledge, the RE-tree is the first index structure proposed for the efficient storage and retrieval of REs in their full generality. Our experimental results with synthetic data sets indicate that the RE-tree is very effective in pruning the search space and easily outperforms naive sequential search approaches by factors ranging between 2 and 3.