IJEEEE 2013 Vol.3(6): 463-467 ISSN: 2010-3654
DOI: 10.7763/IJEEEE.2013.V3.279
DOI: 10.7763/IJEEEE.2013.V3.279
Processing Multiple k Nearest Neighbor Queries
I-Fang Su, Yu-Chi Chung, Pei-Chi Liu, and Chiang Lee
Abstract— k Nearest Neighbor (kNN) query has received considerable attention from the database and information retrieval communities. The applications of kNN query are widely, not only in spatio-temporal database but also in many areas. The past studies of kNN query processing did not consider the case that the server may receive multiple kNN queries at a time. Their algorithms process queries independently. Thus, server will busy with continuously re-accessing database to obtain the data that already acquired. It results in wasting I/O cost and degrading the performance of whole system. In this paper, we focus on this problem and propose an algorithm that namely Multiple kNN Search. The main idea of this problem is “information sharing” strategy that server re-uses the query results of previously executed queries for efficiently processing subsequent queries. We conduct a comprehensive set of experiments to analyze the performance of Multiple kNN Search and compare it with Best-First Search (BFS) algorithm. Empirical studies indicate that the performance of Multiple kNN Search outperforms BFS, achieves lower I/O cost and less running time.
Index Terms— k Nearest Neighbor, Multiple kNN query, spatio-temporal database, information sharing strategy, query processing.
I-Fang Su is with MIS of Fortune Institute Technology, Taiwan (e-mail: emily@csie.ncku.edu.tw).
Yu-Chi Chung and Chiang Lee are with CSIE of Chang Jung Christian University, Taiwan (e-mail: justim@mail.cjcu.edu.tw, leec@mail.ncku.edu.tw).
Pei-Chi Liu is with Chunghwa Telecom Laboratories, Taiwan (e-mail: ayumi416@imus.csie.ncku.edu.tw).
Index Terms— k Nearest Neighbor, Multiple kNN query, spatio-temporal database, information sharing strategy, query processing.
I-Fang Su is with MIS of Fortune Institute Technology, Taiwan (e-mail: emily@csie.ncku.edu.tw).
Yu-Chi Chung and Chiang Lee are with CSIE of Chang Jung Christian University, Taiwan (e-mail: justim@mail.cjcu.edu.tw, leec@mail.ncku.edu.tw).
Pei-Chi Liu is with Chunghwa Telecom Laboratories, Taiwan (e-mail: ayumi416@imus.csie.ncku.edu.tw).
Cite: I-Fang Su, Yu-Chi Chung, Pei-Chi Liu, and Chiang Lee, " Processing Multiple k Nearest Neighbor Queries," International Journal of e-Education, e-Business, e-Management and e-Learning vol. 3, no. 6, pp. 463-467, 2013.
General Information
ISSN: 2010-3654 (Online)
Abbreviated Title: Int. J. e-Educ. e-Bus. e-Manag. e-Learn.
Frequency: Quarterly
DOI: 10.17706/IJEEEE
Editor-in-Chief: Prof. Kuan-Chou Chen
Executive Editor: Ms. Nancy Lau
Abstracting/ Indexing: EBSCO, Google Scholar, Electronic Journals Library, QUALIS, ProQuest, INSPEC (IET)
E-mail: ijeeee@iap.org
-
Nov 04, 2022 News!
The paper published in Vol 12, No 4 has received dois from Crossref
-
Oct 28, 2022 News!
IJEEEE Vol 12, No 4 is available online! [Click]
-
Jul 28, 2022 News!
The papers published in Vol 12, No 2 & No 3 have all received dois from Crossref
-
Jul 26, 2022 News!
IJEEEE Vol 12, No 3 is available online! [Click]
-
Apr 25, 2022 News!
IJEEEE Vol 12, No 2 is available online! [Click]
- Read more>>