Spatial Network k-Nearest Neighbor: A Survey and Future Directives
Keywords:
k-Nearest Neighbor Search, Query Performance, Road Network, Spatial Network Database,Abstract
Nearest neighbor algorithms play many roles in our daily lives. From facial recognition to networking applications, many of these are constantly improved for faster processing time and reliable memory management. There are many types of nearest neighbor algorithms. One of them is called k-nearest neighbor (k-NN), a technique that helps to find number of k closest objects from a user location within a specified range of area. k-NN road network algorithm studies have been through various query performance discussions. Each algorithm is usually judged based on query time over few selected parameters which are; number of k, network density and network size. Many studies have claimed different opinions over their techniques and with many results to prove better query performance than others. However, among these techniques, which k-NN road network algorithm has the highest rate of query performance based on the selected parameters? In this paper, reviews on several k nearest neighbor algorithms were made through series of journal extractions and experimentation in order to identify the algorithm that achieves highest query performance. It was found that with the experimentation method, we can identify not only the algorithm’s performance, but also its design flaws and possible future improvement. All methods were tested with some parameters such as varying number of k, road network density and network size. With the results collected, Incremental Expansion Restriction – Pruned Highway Labeling method (IER-PHL) proves to have the best query performance than other methods for most cases.References
E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, Dec. 1959.
A. Guttman, “R-Trees: a dynamic index structure for spatial searching,” in Proc. of the 1984 ACM SIGMOD Int. Conf. on Management of Data, New York, 1984, pp. 47-57.
N. Roussopoulos, S. Kelley, and F. Vincent, “Nearest neighbor queries,” in Proc. of the 1995 ACM SIGMOD Int. Conf. on Management of Data, New York, 1995, pp. 71–79.
G. S. Iwerks, H. Samet, and K. Smith, “Continuous k-nearest neighbor queries for continuously moving points with updates,” in Proc. Of the 29th Int. Conf. on Very Large Data Bases, Berlin, 2003, pp. 512–523.
D. V Kalashnikov, S. Prabhakar, and S. E. Hambrusch, “Main Memory Evaluation of Monitoring Queries Over Moving Objects,” Distributed Parallel Databases, vol. 15, no. 2, pp. 117–135, Mar. 2004.
U. Demiryurek, F. Banaei-Kashani, and C. Shahabi, “Towards knearest neighbor search in time-dependent spatial network databases,” in Databases in Networked Information Systems: 6th International Workshop, DNIS 2010, Aizu-Wakamatsu, Japan, March 29-31, 2010. Proceedings, S. Kikuchi, S. Sachdeva, and S. Bhalla, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 296–310.
M. Bern, “Approximate closest-point queries in high dimensions,” Information Processing Letters, vol. 45, no. 2, pp. 95–99, Feb. 1993.
Y. Cai, K. A. Hua, and G. Cao, “Processing range-monitoring queries on heterogeneous mobile objects,” in IEEE Int. Conf. Mobile Data Management. Proceedings. 2004, pp. 27-38.
C. S. Jensen, J. Kolarvr, T. B. Pedersen, and I. Timko, “Nearest neighbor queries in road networks,” in Proc. of the 11th ACM Int. Sym. on Advances in Geographic Information Systems, New Orleans, 2003, pp. 1–8.
D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao, “Query processing in spatial network databases,” in Proc. Of the 29th Int. Conf. on Very Large Data Bases, Berlin, 2003, pp. 802-813.
M. Kolahdouzan ,and C. Shahabi, “Voronoi-based k- nearest neighbor search for spatial network databases,” in Proc. of the Thirtieth Int. Conf. on Very Large Data Bases, Toronto, 2004, pp. 840–851.
H.-J. Cho and C.-W. Chung, “An efficient and scalable approach to CNN queries in a road network.,” in Proc. of the 31st Int. Conf. on Very Large Data Bases, Trondheim, 2005, pp. 865–876.
X. Huang, C. S. Jensen, and S. Šaltenis, “The islands approach to nearest neighbor querying in spatial networks,” in Advances in Spatial and Temporal Databases: 9th International Symposium, SSTD 2005, Angra dos Reis, Brazil, August 22-24, 2005. Proceedings, C. Bauzer Medeiros, M. J. Egenhofer, and E. Bertino, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 73–90.
J. Sankaranarayanan, H. Alborzi, and H. Samet, “Efficient query processing on spatial networks,” in Proc. of 13th Annual ACM Int. Workshop on Geographic Information Systems, Bremen, 2005, pp. 200–209.
H. Samet, J. Sankaranarayanan, and H. Alborzi, “Scalable network distance browsing in spatial databases,” in Proc. of the 2008 ACM SIGMOD Int. Conf. on Management of Data, New York, 2008, pp. 43– 54.
X. Du, and J. Ji, “Research of K-NN query processing in road networks,” in 2nd Int. Conf. on Power Electronics and Intelligent Transportation System (PEITS), 2009, pp. 72-76.
K. C. K. Lee, W.-C. Lee, and B. Zheng, “Fast object search on road networks,” in Proc. of the 12th Int. Conf. on Extending Database Technology: Advances in Database Technology, New York, 2009, pp. 1018-1029.
R. Zhong, G. Li, K.-L. Tan, and L. Zhou, “G-Tree: an efficient index for K-NN search on road networks,” in Proc. of the 22nd ACM Int. Conf. on Information & Knowledge Management, New York, 2013, pp. 39- 48.
T. Akiba, Y. Iwata, K. Kawarabayashi, and Y. Kawata, “Fast shortestpath distance queries on road networks by pruned highway labeling,” in Proc. of the Meeting on Algorithm Engineering and Experiments, Oregon, 2014, pp. 147-154.
T. Abeywickrama, M. A. Cheema, and D. Taniar, “K-nearest neighbors on road networks : a journey in experimentation and in-memory implementation,” in Proc. of the VLDB Endowment, 2016, pp. 492– 503.
U. Demiryurek, F. Banaei-Kashani, and C. Shahabi, “Efficient knearest neighbor search in time-dependent spatial networks,” in Database and Expert Systems Applications: 21st International Conference, DEXA 2010, Bilbao, Spain, August 30 - September 3, 2010, Proceedings, Part I, P. G. Bringas, A. Hameurlain, and G. Quirchmayr, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 432–449.
T. Abeywickrama, “Road Network k-NN Experimental Evaluation,” 2016. [Online]. Available: https://github.com/tenindra/RN-k-NN-Exp. [Accessed: 20-Jun-2006].
“9th DIMACS Implementation Challenge: Shortest Paths.,” 2006. [Online]. Available: http://www.dis.uniroma1.it/challenge9/ competition. shtml. [Accessed: 20-Jun-2006].
Downloads
Published
How to Cite
Issue
Section
License
TRANSFER OF COPYRIGHT AGREEMENT
The manuscript is herewith submitted for publication in the Journal of Telecommunication, Electronic and Computer Engineering (JTEC). It has not been published before, and it is not under consideration for publication in any other journals. It contains no material that is scandalous, obscene, libelous or otherwise contrary to law. When the manuscript is accepted for publication, I, as the author, hereby agree to transfer to JTEC, all rights including those pertaining to electronic forms and transmissions, under existing copyright laws, except for the following, which the author(s) specifically retain(s):
- All proprietary right other than copyright, such as patent rights
- The right to make further copies of all or part of the published article for my use in classroom teaching
- The right to reuse all or part of this manuscript in a compilation of my own works or in a textbook of which I am the author; and
- The right to make copies of the published work for internal distribution within the institution that employs me
I agree that copies made under these circumstances will continue to carry the copyright notice that appears in the original published work. I agree to inform my co-authors, if any, of the above terms. I certify that I have obtained written permission for the use of text, tables, and/or illustrations from any copyrighted source(s), and I agree to supply such written permission(s) to JTEC upon request.
