Abstract
Similarity search in transaction databases has been an important issue. Most existing methods use the branch and bound technique to prune transactions that are impossible to be the answers. However, only the distance lower bounds are estimated for the pruning. Also these methods only consider the environment of the static databases. As a result, these methods are not efficient enough when they are employed in the dynamic environment where the transaction database is frequently updated. In this paper, a novel two-level bounding mechanism for efficient range query processing is developed. In our approach, we first group the transactions in the database into clusters. By representing the cluster based on the intersection and union of the items in the transactions belonging to the cluster, the distance lower and upper bounds between a given query and the transactions in the cluster are derived for the query processing. Then, whether the cluster contains no transaction that is similar to the query within distance threshold or all the transactions in the cluster are answers to the query can be determined efficiently at the first-level bounding mechanism. In a cluster, we group the transactions into sets. By the distance correlations between each set of transactions and the representative features of the cluster, the distance lower and upper bounds between the given query and the transactions in the set are derived further for the query processing. Thus, whether the set of transactions contains no transaction that is similar to the query within distance threshold or all the transactions in the set are answers to the query can be determined efficiently at the second-level bounding mechanism. Only the real distances between the remaining sets of transactions and the query should be computed. The maintenance of the proposed mechanism is efficient. The cluster of a new transaction can be easily determined using the bounding mechanism. In addition, the update after a transaction is inserted into or deleted from a cluster is also easy since only the sets in that cluster are affected. Experimental results show that our approach is superior to the previous works in query processing time, pruning effects and processing time for update.