Sequence Query Processing

To processing sequence queries, we need to first based on the sequence of features in the images and construct an efficient indexing system.  Next, we shall search for similar sequences and compare to the target query sequence and rank them according to a certain measure. In the following we shall discuss the Index construction procedure and sequence query processing.

Technique and follow by a demonstration.

Index Construction Procedure

The index construction procedure consists of the three steps:

  1. normalization
  2. categorization
  3. suffix tree construction

The short description for the normalization step is shown in (

At the categorization step, we convert each element value into the symbol of the corresponding leaf node of TAH. The detailed description of this step can be found in Appendix A.

At the index construction step, we extract every possible suffix from each sequence and insert it into a suffix tree. The concept and the structure of a suffix tree is shown in Appendix A.

Sequence query processing

The sequence query processing procedure consists of the following three steps:

  1. normalization
  2. suffix tree traversal
  3. post-processing

At the normalization step, we convert each element value of a query sequence into its normalized value. For this step, we maintain the average and the standard deviation values of each dimension.

At the suffix tree traversal step, we traverse the suffix tree to find a set of candidate subsequences using lower-bound time warping distance function. The concept, the definition, and the lower-bound definition of the time warping distance are shown in Appendix A.

The false-hit is detected and discarded at the post-processing step where actual data sub-sequences corresponding to candidate subsequences are retrieved from the database and compared with a query sequence.

The method for handling the nearest-neighbor query is described in (