Full Text:   <1379>

CLC number: TP311

On-line Access: 

Received: 2006-10-13

Revision Accepted: 2006-12-29

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3205

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2007 Vol.8 No.4 P.529~537


Monitoring nearest neighbor queries with cache strategies

Author(s):  PAN Peng, LU Yan-sheng

Affiliation(s):  College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

Corresponding email(s):   panppl@163.com, lys@mail.hust.edu.cn

Key Words:  K-nearest neighbors (K-NNs), Continuous query, Object cache, Query cache

PAN Peng, LU Yan-sheng. Monitoring nearest neighbor queries with cache strategies[J]. Journal of Zhejiang University Science A, 2007, 8(4): 529~537.

@article{title="Monitoring nearest neighbor queries with cache strategies",
author="PAN Peng, LU Yan-sheng",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Monitoring nearest neighbor queries with cache strategies
%A PAN Peng
%A LU Yan-sheng
%J Journal of Zhejiang University SCIENCE A
%V 8
%N 4
%P 529~537
%@ 1673-565X
%D 2007
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2007.A0529

T1 - Monitoring nearest neighbor queries with cache strategies
A1 - PAN Peng
A1 - LU Yan-sheng
J0 - Journal of Zhejiang University Science A
VL - 8
IS - 4
SP - 529
EP - 537
%@ 1673-565X
Y1 - 2007
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2007.A0529

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[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.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE