Hierarchical Ordering for Approximate Similarity Ranking

We propose a partial ordering that approximates a ranking of the items in a database according to their similarity to a query item. The partial ordering uses a single-link hierarchical clustering of the data items to rank them with respect to the query's closest match. The technique avoids the O(kn) cost of calculating the similarity measure between the query and every item in the database. It requires only O(n) space for pre-computed information. The technique can also provide a criterion for determining which items may not need to be included in the ranking. The results of our experiments suggest that the partial ordering provides a good approximation to the similarity ranking.