Searching k-Nearest Neighbors to be Appropriate under Gamming Environments

Authors: Jae Moon Lee

Abstract:

In general, algorithms to find continuous k-nearest neighbors have been researched on the location based services, monitoring periodically the moving objects such as vehicles and mobile phone. Those researches assume the environment that the number of query points is much less than that of moving objects and the query points are not moved but fixed. In gaming environments, this problem is when computing the next movement considering the neighbors such as flocking, crowd and robot simulations. In this case, every moving object becomes a query point so that the number of query point is same to that of moving objects and the query points are also moving. In this paper, we analyze the performance of the existing algorithms focused on location based services how they operate under gaming environments.

Keywords: Flocking behavior, heterogeneous agents, similarity, simulation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1093345

References:

[1] Guttman, A., "R-trees: a dynamic index structure for spatial searching", ACM SIGMOD Rec., 14(2), 1984, pp. 47-57.
[2] Reynolds, C. W., "Flocks, Herds, and Schools: A Distributed Behavioral Model", SIGGRAPH, 21(4), 1987, pp. 25-34.
[3] Mat Buckland, "Programming Game AI by Example", ISBN 1556220782, Wordware Publications, 2005.
[4] Yu, X., Pu, K.Q., Koudas, N., "Monitoring k-Nearest Neighbor Queries over Moving Objects", 21st Int. Conf. on Data Engineering, 2005, pp. 631-642.
[5] Xiong, X., Mokbel, M.F., Aref, W.G., "SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-Temporal Databases. 21st Int. Conf. on Data Engineering, 2005, pp. 643-654.
[6] Mouratidis, K., Hadjieleftheriou, M., Papadias, D., "Conceptual Partitioning: an Efficient Method for Continuous Nearest Neighbor Monitoring", Proc. ACM SIGMOD Int. Conf. on Management of Data, 2005, pp. 634-645.
[7] Junglas, I.A., Watson, R.T., "Location-based services", Commun. ACM, 51(3), 2008, pp. 65-69.
[8] Jae Moon Lee, "An Efficient Algorithm to Find k-Nearest Neighbors in Flocking Behavior", Information Processing Letters, 110, 2010, pp. 576-579.
[9] Jun Min Park, Jae Moon Lee, "Performance Analysis for finding continuous k-nearest neighbors of moving objects under game environments", Proc. of Korea Game Society, Spring, 2013.
[10] Jae Moon Lee, Young Mee Kwon, "A Model of Pursuing Energy of Predator in Single Predator-Prey Environment", Journal of Korea Game Society, 13(1), 2013, pp. 41-48.
[11] Sangchul Kim and Zhong Yong Che, "A Method for Tennis Swing Recognition Using Accelerator Sensors on a Smartphone", Journal of Korea Game Society, 13(2), 2013, pp. 29-38.
[12] Seongdong Kim, Jae Moon Lee, Varun Ramachandran and Seongah Chin, "A biological simulation game using Prey-Predator model", Information - An international interdisciplinary journal, 16(4), 2013, pp.2607-2618.