Nearest neighbor and reverse nearest neighbor queries for moving objects
Tóm tắt
With the proliferation of wireless communications and the rapid advances in technologies for tracking the positions of continuously moving objects, algorithms for efficiently answering queries about large numbers of moving objects increasingly are needed. One such query is the reverse nearest neighbor (RNN) query that returns the objects that have a query object as their closest object. While algorithms have been proposed that compute RNN queries for non-moving objects, there have been no proposals for answering RNN queries for continuously moving objects. Another such query is the nearest neighbor (NN) query, which has been studied extensively and in many contexts. Like the RNN query, the NN query has not been explored for moving query and data points. This paper proposes an algorithm for answering RNN queries for continuously moving points in the plane. As a part of the solution to this problem and as a separate contribution, an algorithm for answering NN queries for continuously moving points is also proposed. The results of performance experiments are reported.
Từ khóa
#Nearest neighbor searches #Recurrent neural networks #Databases #Neural networks #Internet #Computer science #Wireless communication #Proposals #Home appliances #Computer industryTài liệu tham khảo
10.1145/253260.253347
kollios, 1999, Nearest Neighbor Queries in a Mobile Environment, Proceedings of the International Workshop on Spatio-Temporal Database Management, 119, 10.1007/3-540-48344-6_7
10.1145/342009.335415
korn, 1996, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22nd VLDB Conference, 215
10.1109/ICDE.1998.655772
preparata, 1993, Computational Geometry. An Introduction, Texts and Monographs in Computer Science
10.1145/223784.223794
10.1109/ICDE.2002.994759
10.1145/342009.335427
10.1145/276304.276319
10.1145/290593.290596
10.1109/ICDE.1998.655779
10.1145/602259.602266
elliott, 2001, Text Messages Turn Towns into Giant Computer Game, Sunday Times
henrich, 1994, A Distance Scan Algorithm for Spatial Access Structures, Proceedings of the Second ACM Workshop on Geographic Information Systems, 136
hellerstein, 1995, Generalized Search Trees for Database Systems, Proceedings of the 21st VLDB Conference, 562
10.1007/s00778-005-0166-4
10.1145/320248.320255
10.1145/93597.98741
10.1109/ICDE.1997.581973
song, 2001, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Spatial and Temporal Databases, 79, 10.1007/3-540-47724-1_5
smid, 1997, Closest Point Problems in Computational Geometry, Handbook on Computational Geometry, 877
10.1109/ICDE.1996.492202
stanoi, 2000, Reverse Nearest Neighbor Queries for Dynamic Databases, Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 44
10.1109/ICDE.2001.914862