Multiple k nearest neighbor search

详细信息    查看全文

• 作者：Yu-Chi Chung ; I-Fang Su ; Chiang Lee ; Pei-Chi Liu
• 关键词：Indexing techniques ; Shared execution mechanism ; Query result reuse ; Query correlations
• 刊名：World Wide Web
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：20
• 期：2
• 页码：371-398
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Information Systems Applications (incl.Internet); Database Management; Operating Systems;
• 出版者：Springer US
• ISSN：1573-1413
• 卷排序：20

文摘

The problem of kNN (k Nearest Neighbor) queries has received considerable attention in the database and information retrieval communities. Given a dataset D and a kNN query q, the k nearest neighbor algorithm finds the closest k data points to q. The applications of kNN queries are board, not only in spatio-temporal databases but also in many areas. For example, they can be used in multimedia databases, data mining, scientific databases and video retrieval. The past studies of kNN query processing did not consider the case that the server may receive multiple kNN queries at one time. Their algorithms process queries independently. Thus, the server will be busy with continuously reaccessing the database to obtain the data that have already been acquired. This results in wasting I/O costs and degrading the performance of the whole system. In this paper, we focus on this problem and propose an algorithm named COrrelated kNN query Evaluation (COKE). The main idea of COKE is an “information sharing” strategy whereby the server reuses the query results of previously executed queries for efficiently processing subsequent queries. We conduct a comprehensive set of experiments to analyze the performance of COKE and compare it with the Best-First Search (BFS) algorithm. Empirical studies indicate that COKE outperforms BFS, and achieves lower I/O costs and less running time.