在無線網路的環境下, 對於移動中的物體都能利用 GPS 技術準確的將位置定位出來. 使用者可以在任何時間以及地點, 透過無線網路來查詢物體的位置. 提供與物體位置有關的查詢服務被稱為 Location Based Services (LBS).
在 LBS 所提供的查詢中, 舉一個例子來說, "告訴我在一段時間中, 那些離我最近的 K 間加油站". 這一類的查詢稱之為 continuous K-Nearset Nieghbor (CKNN) search.
由於查詢者與物體的位置都是隨著時間在變化, 造成 CKNN search 的結果也會隨著時間變化而不同. 過去有關解決 CKNN search 的研究, 不是以重複執行其方法才能找出結果, 便是為 CKNN search 作一些限制 (例如: 物體是靜止的, 只能找 C1NN) 以簡化問題. 在本篇論文中, 我們發展一個有效的演算法來解決 CKNN search. 另外, 我們也結合 index 來加速處理 CKNN search. 根據實驗的結果顯示, 我們方法的效能的確是優於其他的方法.

　　In a wireless network environment, locations of moving objects can be located accurately by using GPS technology. User can query the locations of objects through wireless network at anytime and anywhere. The services that user can query the information depend on their locations are called Location Based Serviecs (LBS). A LBS query is "show me the K nearest gas stations for a gievn time interval". This kind of query is called a continuous K-Nearest Neighbor (CKNN) search query.
Since the user and the queried moving objects change their locations continuously, the result of a CKNN search changes with time. Past research is either based on repetitive queries to find out the result, or make some restrictions (e.g., static objects, only support C1NN search) to simplify the issue. In this paper we develop an efficient algorithm to find out the result of a CKNN search.
We also design index to speed up the CKNN search.
Finally, the performance results show that our method indeed performs better than other methods.

[BJKS02] Rimantas Benetis, Christian S. Jensen, Gytis Karciauskas, and Simonas Saltenis, Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects, in International Database Engineering and Applications Symposium, Canada, July 17-19 2002.
[BSKO00] Markde Berg, Otfried Schwarzkopf, Marcvan Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications, Chapter 7, Springer-Verlag, 2000.
[Gut84] A. Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, in ACM SIGMOD Conf, 1984, pp 47-57.
[HNP95] Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer, Generalized Search Trees for Database Systems, in Proceedings of the 21st VLDB Conference, Zurich, Switzerland, September 1995, pp 562-573.
[HS99] Gisli R. Hjaltason and Hanan Samet, Distance browsing in spatial databases, in ACM Transactions on Database Systems, Vol.24, No. 2, 1999, pp 265-318.
[ISS03] Glenn Iwerks, Hanan Samet, and Ken Smith, Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates, in International Conference on Very Large Data Bases, Berlin, Germany, September 9-12 2003.
[KM00] Flip Korn and S. Muthukrishnan, Influence sets based on reverse nearest neighbor queries, in Proceedings of the ACM SIGMOD International Conference on Management of Data, Dallas, Texas, USA, May 16-18 2000, pp 201-212.
[RKV95] Nick Roussopoulos, Stephen Kelley, and Frederic Vincent, Nearest neighbor queries, in Proceedings of ACM Sigmod, 1995, pp 71-79.
[Ros00] Sheldon Ross, Introduction to Probability and Statistics for Engineers and Scientists, ISBN 0125984723, 2000.
[SAA00] Ioana Stanoi, Divyakant Agrawal, and Amr El Abbadi, Reverse Nearest Neighbor Queries for Dynamic Databases, in ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2000, pp 44-53.
[Sam90a] Hanan Samet,mThe Design and Analysis of Spatial Data Structures, Addison-Wesley, ISBN 0-201-50255-0, 1990.
[Sam90b] Hanan Samet, Application of Spatial Data Structure, Addison-Wesley, ISBN 0-201-50300-X, 1990.
[SJLL00] Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, and Mario A. Lopez, Indexing the Positions of Continuously Moving Objects, in SIGMOD Conference, 2000, pp 331-342.
[SR01] Zhexuan Song and Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, in Proceedings of 7th International Symposium on Advances in Spatial and Temporal Databases, LNCS2121, Redondo Beach, CA, USA, July 12-15 2001, pp 79-96.
[SWCD97] A. Prasad Sistla, Ouri Wolfson, Sam Chamberlain, and Son Dao, Modeling and Querying Moving Objects, in International Conference on Data Engineering, 1997, pp 422-432.
[TP02] Yufei Tao and Dimitris Papadias, Time Parameterized Queries in Spatio-Temporal Databases,
in Proceedings of the 2002 ACM SIGMOD international conference on Management of data, Madison, Wisconsin, 2002, pp 334-345.
[TPS02] Yufei Tao, Dimitris Papadias, and Qiongmao Shen, Continuous Nearest Neighbor Search, in International Conference on Very Large Data Bases,
Hong Kong, China, August 20-23 2002, pp 279-290.
[TSPM98] Yannis Theodoridis, Timos K. Sellis, Apostolos Papadopoulos, and Yannis Manolopoulos, Specifications for Efficient Indexing in Spatiotemporal Databases, in Proceedings 10th International Conference on Scientific and Statistical Database Management, Capri, Italy, 1998, pp 123-132.
[WXCJ98] Ouri Wolfson, Bo Xu, Sam Chamberlain, and Liqin Jiang, Moving Objects Databases: Issues and Solutions, in Statistical and Scientific Database Management, 1998, pp 111-122.
[ZL01] Baihua Zheng and Dik Lun Lee, Semantic Caching in Location-Dependent Query Processing, in Proceedings of the 7th SSTD Symposium, 2001, pp 97-116.