Multiple similarity queries: A basic DBMS operation for mining in metric databases

Metric databases are databases where a metric distance function is defined for pairs of database objects. In such databases, similarity queries in the form of range queries or k-nearest-neighbor queries are the most important query types. In traditional query processing, single queries are issued in dependently by different users. In many data mining applications, however, the database is typically explored by iteratively asking similarity queries for answers of previous similarity queries. In this paper, we introduce a generic scheme for such data mining algorithms and we investigate two ortho gonal approaches, reducing I/O cost as well as CPU cost, to speed-up the pr ocessing of multiple similarity queries. The proposed techniques apply to a ny type of similarity query and to an implementation based on an index or u sing a sequential scan. Parallelization yields an additional impressive spe ed-up. An extensive performance evaluation confirms the efficiency of our a pproach.