時間-空間資料庫主要是在將有著空間與時間的特性之資料結合在一起。與時間-空間相關的查詢已經被廣泛的使用在很多應用，像是行動通訊系統、交通控制系統、地理資訊系統、以及多媒體應用。Continuous Range (CR) query 和 Continuous K-Nearest Neighbor (CKNN) query 為兩類重要且被廣泛使用的時間-空間查詢。一個 CR query 可以用來找出在一個時間區段內的每個時間點，那些與移動查詢物體的 Euclidean 距離落於一個距離範圍內的移動物體。至於 CKNN query，可以被利用來找出時間區段 [ts, te] 內每個時間點，查詢物體的 K-Nearest Neighbors (KNNs)。

本論文的研究方向根據物體是在 Euclidean space 上還是在 road networks 上移動來分成兩個部分。在第一個部份中，我們研究如何針對在 Euclidean space 內移動之物體去有效地處理時間-空間查詢(也就是說，判斷查詢結果的準則為每個移動物體與查詢物體之間的 Euclidean 距離)。然而，目前處理時間-空間查詢的方法都是假設每個物體是以固定的速度 (速率和方向) 在移動。不同於這些現存之方法，我們放寬這個固定速度之假設，而允許每個物體的速度可以為不確定。速度的不確定性必定會導致處理時間-空間查詢有著極高的複雜度。我們將會討論因為這個不確定性所引發的複雜情形，並且提出數個有效的方法來針對有著不確定性的物體去回答時間-空間查詢。我們的實驗結果論證了所提出的方法之效能。

在第二部份中，我們將注意力著重在如何針對 road networks 上移動之物體去處理時間-空間查詢。由於物體的移動式被侷限在一個 road network 上，兩物體之間距離的計算應該是要根據整個 road network 的聯結關係來求得而不是單純考慮物體的位置。我們會先討論目前現存的處理時間-空間查詢的方法所面臨之限制，然後提出一個有效率的方法來克服這些限制。利用我們所提出的方法，我們可以在底下三種情況下去判斷出時間-空間查詢的結果。這三種情況為 (1) 所有物體 (包括查詢物體) 都在 road network 上持續地移動，(2) 兩物體之間的距離被定義為他們在 road network 上的最短路徑之長度，和 (3) 每個時間點之查詢結果都要被判斷出來。
大量的實驗被用來研究所提出的方法之有效性。

Spatio-temporal databases aim at combining the spatial and temporal characteristics of data. Spatio-temporal queries have been used in many applications such as mobile communication systems, traffic control systems, geographical information systems, location-aware advertisement, and multimedia applications. Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important and widely used spatio-temporal queries.A CR query is to find the moving objects whose Euclidean distances to the moving query object are within a distance at each time instant within a time interval [ts, te]. As for the CKNN query, it can be utilized to retrieve the query object's K-Nearest Neighbors (KNNs)
at each time instant within [ts, te].

The context of this dissertation is categorized into two parts according to whether objects are moving in Euclidean space or road networks. In the first part, we investigate how to efficiently process these spatio-temporal queries over moving objects in Euclidean space (that is, the results are determined based on the Euclidean distance between each moving object and the query object). Existing methods for processing spatio-temporal queries, however, assume that each object moves with a fixed velocity (speed and direction). Different from the existing methods, we relieve this assumption by allowing the velocity of each object to be uncertain. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose several efficient methods to answer the spatio-temporal queries over moving objects with uncertainty. Our performance results demonstrate the effectiveness and the efficiency of the proposed approaches.

In the second part of this dissertation, we focus our attention on processing the spatio-temporal queries over moving objects in road networks. As the movements of objects are constrained to a road network, the distance between two objects should be computed based on the connectivity of the road network rather than the two objects' locations. We first highlight the limitations of the existing apporaches for processing the spatio-temporal queries in road networks, and then propose a cost-effective method to overcome these limitations. By using the proposed method, we can determine the result set of spatio-temporal queries under the following three conditions: (1) All objects (including the query object) move continuously in a road network. (2) The distance between two objects is defined as the distance along the shortest path between them in the network. (3) The result set of the query object at each timestamp should be completely determined. Comprehensive experiments are performed to investigate the efficiency of this method.

[1] R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis, “Nearest neighbor and reverse nearest neighbor queries for moving objects,” in Proceedings of the International Database Engineering and Applications Symposium, pp. 44–53, Canada, July 17-19 2002.
[2] R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis, “Nearest neighbor and reverse nearest neighbor queries for moving objects,” VLDB Journal, vol. 15, no. 3,
pp. 229–249, September 2006.
[3] D. V. Kalashnikov, S. Prabhakar, S. Hambrusch, and W. Aref, “Efficient evaluation of continuous range queries on moving objects,” in Proceedings of the 13th International Conference on Database and Expert Systems Applications, pp. 731–740, Aix en Provence, France, September 2–6 2002.
[4] K. C. K. Lee, H. V. Leong, J. Zhou, and A. Si, “An efficient algorithm for predictive continuous nearest neighbor query processing and result maintenance,” in Mobile Data Management, pp. 178–182, 2005.
[5] G. Iwerks, H. Samet, and K. Smith, “Continuous k-nearest neighbor queries for continuously moving points with updates,” in Proceedings of the International Conference on Very Large Data Bases, pp. 512–523, Berlin, Germany, September 9-12 2003.
[6] K. Raptopoulou, A. Papadopoulos, and Y. Manolopoulos, “Fast nearest-neighbor query processing in moving-object databases,” GeoInformatica, vol. 7, no. 2, pp. 113–137, June 2003.
[7] Y. Tao and D. Papadias, “Time parameterized queries in spatio-temporal databases,” in Proceedings of the ACM SIGMOD, pp. 322–333, Madison, Wisconsin, 2002.
[8] Y. Tao, D. Papadias, and Q. Shen, “Continuous nearest neighbor search,” in Proceedings of the International Conference on Very Large Data Bases, pp. 287–298, Hong Kong, China, August 20-23 2002.
[9] K. Mouratidis, M. Hadjieleftheriou, and D. Papadias, “Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring,” in Proceedings of
the ACM SIGMOD, pp. 634–645, 2005.
[10] M. F. Mokbel, X. Xiong, and W. G. Aref, “Sina: Scalable incremental processing of continuous queries in spatio-temporal databases,” in Proceedings of the ACM
SIGMOD, pp. 623–634, 2004.
[11] R. V. Nehme and E. A. Rundensteiner, “Scuba: Scalable cluster-based algorithm for evaluating continuous spatio-temporal queries on moving objects,” in Proceedings
of the EDBT, pp. 1001–1019, 2006.
[12] Z. Song and N. Roussopoulos, “K-nearest neighbor search for moving query point,” in Proceedings of 7th International Symposium on Advances in Spatial and Temporal
Databases, pp. 79–96, Redondo Beach, CA, USA, July 12-15 2001.
[13] X. Xiong, M. F. Mokbel, and W. G. Aref, “Sea-cnn: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases,” in Proceedings of
the International Conference on Data Engineering, pp. 643–654, 2005.
[14] X. Yu, K. Q. Pu, and N. Koudas, “Monitoring k-nearest neighbor queries over moving objects,” in Proceedings of the International Conference on Data Engineering, pp. 631–642, 2005.
[15] A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao, “Modeling and querying moving objects,” in International Conference on Data Engineering, pp. 422–432, 1997.
[16] O. Wolfson, P. Sistla, B. Xu, J. Zhou, S. Chamberlain, T. Yesha, and N. Rishe, “Tracking moving objects using database technology in domino,” in Proceedings of The Fourth Workshop on Next Generation Information Technologies and Systems, pp. 112–119, Zikhron-Yaakov, Israel, July 1999.
[17] S. Dieker and R. H. Guting, “Plug and play with query algebras: Secondo-a generic dbms development environment,” in Proceedings of the International Database Engineering and Applications Symposium, pp. 380–392, 2000.
[18] P. Rigaux, M. Scholl, L. Segoufin, and S. Grumbach, “Building a constraint-based spatial database system: model, languages, and implementation,” Information Systems, vol. 28, no. 6, pp. 563–595, 2003.
[19] A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in ACM SIGMOD Conf, pp. 47–57, 1984.
[20] H. Samet, Application of Spatial Data Structurea. Addison-Wesley, 1990.
[21] S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez, “Indexing the positions of continuously moving objects,” in Proceedings of the ACM SIGMOD, pp. 331–342, 2000.
[22] H. Guting, T. de Almeida, and Z. Ding, “Modeling and querying moving objects in networks,” The VLDB Journal, vol. 15, no. 2, pp. 165–190, 2006.
[23] V. T. de Almeida and R. H. G¨uting, “Supporting uncertainty in moving objects in network databases,” in Proceedings of the 13th annual ACM international workshop
on Geographic information systems, pp. 31–40, 2005.
[24] C. S. Jensen, J. Kol´aˇrvr, T. B. Pedersen, and I. Timko, “Nearest neighbor queries in road networks,” in Proceedings of the 11th ACM international symposium on
Advances in geographic information systems, pp. 1–8, New York, NY, USA, 2003.
[25] D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao, “Query processing in spatial network databases,” in Proceedings of the 29th international conference on Very
Large Data Bases, pp. 802–813, Berlin, Germany, September 9-12 2003.
[26] M. Kolahdouzan and C. Shahabi, “Voronoi-based k nearest neighbor search for spatial network databases,” in Proceedings of the Thirtieth international conference
on Very Large Data Bases, pp. 840–851, 2004.
[27] M. R. Kolahdouzan and C. Shahabi, “Continuous k-nearest neighbor queries in spatial network databases,” in Proceedings of the 2nd International Workshop on
Spatio-Temporal Database Management, pp. 33–40, 2004.
[28] H.-J. Cho and C.-W. Chung, “An efficient and scalable approach to cnn queries in a road network,” in Proceedings of the 31st international conference on Very Large Data Bases, pp. 865–876, 2005.
[29] K. Mouratidis, M. L. Yiu, D. Papadias, and N. Mamoulis, “Continuous nearest neighbor monitoring in road networks,” in Proceedings of the 32nd international
conference on Very Large Data Bases, pp. 43–54, 2006.
[30] X. Dai, M. L. Yiu, N. Mamoulis, Y. Tao, and M. Vaitis, “Probabilistic spatial queries on existentially uncertain data,” in Proceedings. International Conference
on SSTD, pp. 400–417, 2005.
[31] V. Ljosa and A. K. Singh, “Top-k spatial joins of probabilistic objects,” in International Conference on ICDE, 2008.
[32] O. Wolfson, A. P. Sistla, S. Chamberlain, and Y. Yesha, “Updating and querying databases that track mobile units,” Distributed and Parallel Databases, vol. 7, no. 3,
pp. 257–387, 1999.
[33] R. Cheng, D. V. Kalashnikov, and S. Prabhakar, “Querying imprecise data in moving object environments,” IEEE Transactions on Knowledge and Data Engineering,
vol. 16, no. 9, pp. 1112–1127, 2004.
[34] O. Wolfson, S. Chamberlain, S. Dao, L. Jiang, and G. Mendez, “Cost and imprecision in modeling the position of moving objects,” in Proceedings of the International
Conference on Innovative Data Systems Research, pp. 588–596, 1998.
[35] J. Chen and R. Cheng, “Efficient evaluation of imprecise location-dependent queries,” in Proceedings of the International Conference on Data Engineering, pp.
586–595, 2007.
[36] D. Pfoser and C. S. Jensen, “Capturing the uncertainty of moving-object representations,”
in Proceedings of the International Conference on Scientific and Statistical Database Management, pp. 111–132, 1999.
[37] G. Trajcevski, O. Wolfson, F. Zhang, and S. Chamberlain, “The geometry of uncertainty in moving objects databases,” in Proceedings of the International Conference on Extending Database Technology, pp. 233–250, 2002.
[38] V. T. de Almedia, “Towards optimal continuous nearest neighbor queries in spatial databases,” in Proceedings of ACM GIS, November 10-11 2006.
[39] Y. Tao, C. Faloutsos, D. Papadias, and B. Liu, “Prediction and indexing of moving objects with unknown motion patterns,” in Proceedings of the ACM SIGNOD
Conference, Maison de la Chimie, Paris, France, June 13-18 2004.
[40] http://www.rtreeportal.org/.
[41] D. Papadias, Q. Shen, Y. Tao, and K. Mouratidis, “Group nearest neighbor queries,” in Proceedings of the International Conference on Data Engineering, pp. 301–312, 2004.
[42] Y.-K. Huang, C.-C. Chen, and C. Lee, “Continuous k-nearest neighbor query for moving objects with uncertain velocity,” GeoInformatica, vol. 13, no. 1, pp. 1–25,
2009.
[43] R. Baeza-Yates and B. Ribeiro-Neto, Modern Information Retrieval. Addison-Wesley.
[44] H. Hu, D. L. Lee, and J. Xu, “Fast nearest neighbor search on road networks,” in Extending Database Technology, pp. 186–203, 2006.
[45] C. Shahabi, M. R. Kolahdouzan, and M. Sharifzadeh, “A road network embedding technique for k-nearest neighbor search in moving object databases,” Geoinformatica, vol. 7, no. 3, pp. 255–273, 2003.
[46] E. W. Dijkstra, “A note on two problems in connection with graphs,” Numeriche Mathematik, vol. 1, pp. 269–271, 1959.
[47] R. Kung, E. Hanson, Y. Ioannidis, T. Sellis, L. Shapiro, and M. Stonebraker, “Heuristic search in data base system,” in Proceedings of the International Workshop
on Expert Database Systems, 1986.
[48] T. Brinkhoff, “A framework for generating network-based moving objects,” GeoInformatica, vol. 6, no. 2, pp. 153–180, 2002.
[49] S. Borzsonyi, D. Kossmann, and K. Stocker, “The skyline operator,” in Proceedings of the 17th International Conference on Data Engineering, pp. 421–430, Washington, DC, USA, 2001.