Similar articles

Abstract: The problem of continuously monitoring multiple K-nearest neighbor (K-NN) queries with dynamic object and query dataset is valuable for many location-based applications. A practical method is to partition the data space into grid cells, with both object and query table being indexed by this grid structure, while solving the problem by periodically joining cells of objects with queries having their influence regions intersecting the cells. In the worst case, all cells of objects will be accessed once. Object and query cache strategies are proposed to further reduce the I/O cost. With object cache strategy, queries remaining static in current processing cycle seldom need I/O cost, they can be returned quickly. The main I/O cost comes from moving queries, the query cache strategy is used to restrict their search-regions, which uses current results of queries in the main memory buffer. The queries can share not only the accessing of object pages, but also their influence regions. Theoretical analysis of the expected I/O cost is presented, with the I/O cost being about 40% that of the SEA-CNN method in the experiment results.

[1] Gedik, B., Wu, K.L., Yu, P.S., Liu, L., 2006. Processing moving queries over moving objects using motion-adaptive indexes. IEEE Trans. on TKDE, 18(5):651-668.

[2] Iwerks, G.S., Samet, H., Smith, K.P., 2006. Maintenance of K-nn and spatial join queries on continuously moving points. ACM Trans. on Database Systems, 31(2):485-536.

[3] Mokbel, M.F., Xiong, X., Aref, W.G., 2004. SINA: Scalable Incremental Processing of Continuous Queries in Spatio-Temporal Databases. Proc. SIGMOD, p.623-634.

[4] Mouratidis, K., Hadjieleftheriou, M., Papadias, D., 2005a. Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring. Proc. SIGMOD, p.634-645.

[5] Mouratidis, K., Papadias, D., Bakiras, S., Tao, Y., 2005b. A threshold-based algorithm for continuous monitoring of k nearest neighbors. IEEE Trans. on TKDE, 17(11):1451-1464.

[6] Prabhakar, S., Xia, Y., Kalashnikov, D.V., Aref, W.G., Hambrusch, S.E., 2002. Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects. IEEE Trans. on Computers, 51(10):1124-1140.

[7] Wu, K.L., Chen, S.K., Yu, P.S., 2006. Incremental processing of continual range queries over moving objects. IEEE Trans. on TKDE, 18(11):1560-1575.

[8] Xiong, X., Mokbel, M.F., Aref, W.G., 2005. SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-Temporal Databases. International Conference on Data Engineering, p.643-654.

[9] Yu, X., Pu, K.Q., Koudas, N., 2005. Monitoring K-Nearest Neighbor Queries Over Moving Objects. International Conference on Data Engineering, p.631-642.