Multiple k nearest neighbor search

Yu Chi Chung, I. Fang Su, Chiang Lee, Pei Chi Liu

研究成果: Article同行評審

5 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)371-398
期刊World Wide Web
出版狀態Published - 2017 3月 1

All Science Journal Classification (ASJC) codes

  • 軟體
  • 硬體和架構
  • 電腦網路與通信


深入研究「Multiple k nearest neighbor search」主題。共同形成了獨特的指紋。