Hike: A High Performance kNN Query Processing System for Multimedia Data

摘要

Internet continues to serve as the dominating platform for sharing and delivering multimedia contents. kNN queries are an enabling functionality for many multimedia applications. However, scaling kNN queries over large highdimensional multimedia datasets remains challenging. In this paper we present Hike, a high performance multimedia kNN query processing system, it integrate the proposed novel Distance-Precomputation based R-tree (DPR-Tree) index structure, coupled with the fast distance based pruning methods. This unique coupling improves the computational performance of kNN search and consequently reducing I/O cost. Since Hike's index structure DPR-Tree by design generates two types of query independent precomputed distances during the index construction, and it can intelligently utilizes the precomputed distances to design a suite of computationally inexpensive pruning techniques, which make the Hike system can filter out irrelevant index nodes and data objects, and minimize the amount of duplicate computations among different kNN queries.We conduct an extensive experimental evaluation using real-life web multimedia datasets. Our results show that DPRTree indexing coupled with precomputed distance based query processing make the Hike system can significantly reduce the overall cost of kNN search, and is much faster than the existing representative methods.