Similarity based retrieval from sequence databases using automata as queries
Aravinda Prasad Sistla, Tao Hu, Vikas Chowdhry · 2002
Similarity based retrieval from sequence databases is of importance in many applications such as time-series, video and textual databases. In this paper, automata based formalisms are introduced for specifying queries over such databases. Various measures defining the distance of a database sequence from an automaton are defined. Efficient methods for similarity based retrieval are presented for each of the distance measures. These methods answer nearest neighbor queries (i.e. retrieval of k closest subsequences), or range queries (i.e., retrieval of all sequences with in a given distance).