Dynamic Reverse Furthest Neighbor Querying Algorithm of Moving Objects

详细信息    查看全文

• 关键词：Moving objects ; Reverse furthest neighbor ; Uncertain moving object ; Pruning ; Long tail
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10086
• 期：1
• 页码：266-279
• 全文大小：1,082 KB
• 参考文献：1.Liu, J., Chen, H., Furuse, K., Kitagawa, H.: An efficient algorithm for arbitrary reverse furthest neighbor queries. In: Sheng, Q.Z., Wang, G., Jensen, C.S., Xu, G. (eds.) APWeb 2012. LNCS, vol. 7235, pp. 60–72. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-29253-8_​6 CrossRef
  2.Korn, F., Muthukrishnan, S.: Influence sets based on reverse nearest neighbor queries. ACM Sigmod Record 29(2), 201–212 (2000)CrossRef
  3.Lian, X., Chen, L.: Probabilistic group nearest neighbor queries in uncertain databases. IEEE Trans. Knowl. Data Eng. 20(6), 809–824 (2008)CrossRef
  4.Lian, X., Chen, L.: Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data. VLDB J. 18(18), 787–808 (2009)CrossRef
  5.Cheema, M.A., Lin, X., Wang, W., et al.: Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Trans. Knowl. Data Eng. 22(4), 550–564 (2010)CrossRef
  6.Zhu, J., Wang, X., Li, Y.: Predictive nearest neighbor queries over uncertain spatial-temporal data. In: Cai, Z., Wang, C., Cheng, S., Wang, H., Gao, H. (eds.) WASA 2014. LNCS, vol. 8491, pp. 424–435. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-07782-6_​39
  7.Li, K., Malik, J.: Fast k-Nearest neighbour search via dynamic continuous indexing. arXiv preprint arXiv:​1512.​00442 (2015)
  8.Li, J., Wang, B., Wang, G.: Efficient probabilistic reverse k-nearest neighbors query processing on uncertain data. In: Meng, W., Feng, L., Bressan, S., Winiwarter, W., Song, W. (eds.) DASFAA 2013. LNCS, vol. 7825, pp. 456–471. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-37487-6_​34 CrossRef
  9.Xu, C., Gu, Y., Chen, L., et al.: Interval reverse nearest neighbor queries on uncertain data with markov correlations. In: Data Engineering ICDE 2013, pp. 170–181 (2013)
  10.Emrich, T., Kriegel, H.-P., Mamoulis, N., Niedermayer, J., Renz, M., Züfle, A.: Reverse-nearest neighbor queries on uncertain moving object trajectories. In: Bhowmick, S.S., Dyreson, C.E., Jensen, C.S., Lee, M.L., Muliantara, A., Thalheim, B. (eds.) DASFAA 2014. LNCS, vol. 8422, pp. 92–107. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-05813-9_​7 CrossRef
  11.Trajcevski, G., Tamassia, R., Ding, H., et al.: Continuous probabilistic nearest-neighbor queries for uncertain trajectories. In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pp. 874–885. ACM (2009)
  12.Yao, B., Li, F., Kumar, P.: Reverse furthest neighbors in spatial databases. In: ICDE 2009, pp. 664–675 (2009)
  13.Liu, J., Chen, H., Furuse, K., Kitagawa, H.: An efficient algorithm for reverse furthest neighbors query with metric index. In: Bringas, P.G., Hameurlain, A., Quirchmayr, G. (eds.) DEXA 2010. LNCS, vol. 6262, pp. 437–451. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-15251-1_​34 CrossRef
  14.Cheng, R., Prabhakar, S., Kalashnikov, D.V.: Querying imprecise data in moving object environments. IEEE Trans. Knowl. Data Eng. 16(9), 1112–1127 (2004)CrossRef
  15.Tao, Y., Papadias, D., Lian, X.: Reverse kNN search in arbitrary dimensionality. In: Proceedings of VLDB Endowment, pp. 744–755 (2004)
  16.Emrich, T., Kriegel, H.P., Ger, P., et al.: Boosting spatial pruning: on optimal pruning of MBRs. In: SIGMOD, pp. 39–50 (2010)
  17.Said, A., et al.: User-centric evaluation of a k-furthest neighbor collaborative filtering recommender algorithm. In: Proceedings of the 2013 conference on computer supported cooperative work. ACM (2013)
  18.Averbakh, I., Bereg, S.: Facility location problems with uncertainty on the plane. Discrete Optim. 2(1), 3–4 (2005)MathSciNet CrossRef MATH
  19.Cabello, S., Díaz-Báñez, J.M., Langerman, S., Seara, C., Ventura, I.: Facility location problems in the plane based on reverse nearest neighbor queries. Eur. J. Oper. Res. 202(1), 99–106 (2010)MathSciNet CrossRef MATH
  20.Yin, H., Cui, B., Li, J., Yao, J., Chen, C.: Challenging the long tail recommendation. Proc. VLDB Endowment 5(9), 896–907 (2012)CrossRef
  
• 作者单位：Bohan Li (18) (19) (22)
  Chao Zhang (18) (23)
  Weitong Chen (22)
  Yingbao Yang (20)
  Shaohong Feng (21)
  Qiqian Zhang (20)
  Weiwei Yuan (18) (19)
  Dongjing Li (18) (24)
  
  18. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China
  19. Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing, China
  22. School of Information Technology and Electrical Engineering, University of Queensland, Brisbane, Australia
  23. Jiangsu Easymap Geographic Information Technology Corp., Ltd, Nanjing, China
  20. College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing, China
  21. College of Electronic and Information Engineering, NUAA, Nanjing, China
  24. Department of Payment and Settlement, JD Finance, Nanjing, China
  
• 丛书名：Advanced Data Mining and Applications
• ISBN：978-3-319-49586-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：10086

文摘

With the development of wireless communications and positioning technologies, locations of moving objects are highly demanding services. The assumption of static data is majorly applied on previous researches on reverse furthest neighbor queries. However, the data are dynamic property in the real world. Even, the data-aware are uncertain due to the limitation of measuring equipment or the delay of data communication. To effectively find the influence of querying a large number of moving objects existing in boundary area vs querying results of global query area, we put forward dynamic reverse furthest neighbor query algorithms and probabilistic reverse furthest neighbor query algorithms. These algorithms can solve the query of weak influence set for moving objects. Furthermore, we investigate the uncertain moving objects model and define a probabilistic reverse furthest neighbor query, and then present a half-plane pruning for individual moving objects and spatial pruning method for uncertain moving objects. The experimental results show that the algorithm is effective, efficient and scalable in different distribution and volume of data sets.