text: The like regular expression predicate has been part of the SQL standard since at least 1989. However, despite its popularity and wide usage, database vendors provide only limited indexing support for regular expression queries which almost always require a full table scan. In this paper we propose a rigorous and robust approach for providing indexing support for regular expression queries. Our approach consists of formulating the indexing problem as a combinatorial optimization problem. We begin with a database, abstracted as a collection of strings. From this data set we generate a query workload. The input to the optimization problem is the database and the workload. The output is a set of multigrams (substrings) which can be used as keys to records which satisfy the query workload. The multigrams can then be integrated with the data structure (like B+ trees) to provide indexing support for the queries. We provide a deterministic and a randomized approximation algorithm (with provable guarantees) to solve the optimization problem. Extensive experiments on synthetic data sets demonstrate that our approach is accurate and efficient. We also present a case study on PROSITE patterns - which are complex regular expression signatures for classes of proteins. Again, we are able to demonstrate the utility of our indexing approach in terms of accuracy and efficiency. Thus, perhaps for the first time, there is a robust and practical indexing mechanism for an important class of database queries.
  @cite_4: Abstract We present a new index for approximate string matching. The index collects text q -samples, that is, disjoint text substrings of length q , at fixed intervals and stores their positions. At search time, part of the text is filtered out by noticing that any occurrence of the pattern must be reflected in the presence of some text q -samples that match approximately inside the pattern. Hence the index points out the text areas that could contain occurrences and must be verified. The index parameters permit load balancing between filtering and verification work, and provide a compromise between the space requirement of the index and the error level for which the filtration is still efficient. We show experimentally that the index is competitive against others that take more space, being in fact the fastest choice for intermediate error levels, an area where no current index is useful.
  @cite_2: We study approximate string matching in connection with two string distance functions that are computable in linear time. The first function is based on the so-called @math -grams. An algorithm is given for the associated string matching problem that finds the locally best approximate occurences of pattern @math , @math , in text @math , @math , in time @math . The occurences with distance @math can be found in time @math . The other distance function is based on finding maximal common substrings and allows a form of approximate string matching in time @math . Both distances give a lower bound for the edit distance (in the unit cost model), which leads to fast hybrid algorithms for the edit distance based string matching.
  @cite_12: Multi-purpose, adjustable stabilizing cleats which can be attached to various types of transmission and or drive shaft tunnel or hump mounted trays with adjustment of the cleats enabling them to be positioned for effective engagement with surface areas of transmission humps or tunnels of different shapes and configurations. The cleats can also be attached to other objects for engaging carpeted surfaces, upholstered furniture and the like.
  @cite_11: 
summary: In another stream of research, inverted files @cite_11 and q-grams @cite_2 @cite_12 @cite_4 are two designs which support information retrieval and informatics. However, both are not suitable for regular expression queries because they rely on a predefined list of words.