Similarity based retrieval from sequence databases using automata as queries A. Prasad Sistla, Tao Hu, and Vikas Chowdhry   View Paper (PDF)   Return to Sequence similarity search and access methods Abstract 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). DiSC'03 © 2003 Association for Computing Machinery