Efficient similarity search in digital libraries

Digital libraries are a core information technology. When the stored data is complex, e.g. high-resolution images or molecular protein structures, simple query types like the exact match query are hardly applicable. In such environments similarity queries, particularly range queries and k-nearest neighbor queries, turn out to be important query types. Numerous approaches have been proposed for the processing of similarity queries which mainly concen-trate on highly dynamic data sets where insertion, update, and deletion operations permanently occur. However, only little effort has been devoted to the case of rather static data sets- a case that frequently occurs in digital libraries. In this paper, we introduce a novel technique for efficient similarity search on top of static or rarely changing data sets. In par-ticular, we propose a special sorting order on the data objects which can be effectively exploited to substantially reduce the total query time of similarity queries. An exten-sive experimental evaluation with real-world data sets emphasizes the practical impact of our technique