An efficient algorithm for attribute-based subsequence matching

Subsequence matching plays a fundamental role in the solutions to sequence-related problems such as sequence classification and similarity search. Subsequence matching is to find out expected event sequences from a database with a specified sequence composed of events. One cannot specify some or all of the events in the sequence but can give attribute values of these events in some applications. Therefore, a problem is how to find out expected event sequences from a database with an attribute-based sequence composed of attribute values. We propose an algorithm for the problem. The algorithm uses a list structure to store the temporal information about both sequences and events associated with values in a database. The structure can be compressed using a simple technique. Experimental data show that the proposed algorithm is one to two orders of magnitude faster than the state-of-the-art algorithm, especially for real-world databases, and that the technique is effective.