簡易檢索 / 詳目顯示
| 研究生： |
陳志瑋 Chen, Chih-wei |
|---|---|
| 論文名稱： |
有效率的連續對在道路網路上移動之物體作 K 個最近鄰居搜尋 Efficient Continuous K-Nearest Neighbor Query over Moving Objects in Road Networks |
| 指導教授： |
李強
Lee, Chiang |
| 學位類別： |
碩士 Master |
| 系所名稱： |
電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering |
| 論文出版年： | 2009 |
| 畢業學年度： | 97 |
| 語文別： | 中文 |
| 論文頁數： | 62 |
| 中文關鍵詞： | 移動物體 、時間-空間資料庫 、K 個最近鄰居 |
| 外文關鍵詞： | spatio-temporal databases, moving objects, K-nearest neighbors |
| 相關次數： | 點閱：118 下載：1 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在時間-空間資料庫(spatio-temporal databases)系統所提供的查詢服務裡, 其中有一項重要的查詢稱之為 continuous K-nearest neighbor query (簡稱為 CKNN query). CKNN query 會判斷出在每個時間點, 查詢者的 K 個最近物體, 而這些物體稱之為查詢者的 K 個最近鄰居 (簡稱為 KNN). 在本篇論文中, 我們研究如何在交通運輸網路 (road network) 上去有效地處理這樣的 CKNN query. 在交通運輸網路中, 判斷 KNNs 的準則是根據物體與查詢者之間的最短道路距離 (shorest network distance) 來作為. 由於物體與查詢者皆隨著時間而移動變化位置, 造成兩者之間的道路距離亦會隨時間而改變. 這意謂著在不同時間點, 查詢者會有不同的 KNN. 我們會先說明目前方法在處理 CKNN query 的一些限制和缺點, 然後再提出一個有效的方法來克服目前方法的限制和缺點. 最後, 我們實作了大量的實驗來驗證我們提出的方法之有效性.
Continuous K-Nearest Neighbor (CKNN) query is an important type of spatio-temporal queries. A CKNN query is to find among all moving objects the K-nearest neighbors (KNNs) of a moving query object at each timestamp. In this paper, we focus on processing such a CKNN query in road networks, where the criterion for determining the KNNs is the shortest network distance between objects. We first highlight the limitations of the existing approaches, and then propose a cost-effective algorithm, namely the Continuous KNN algorithm, to overcome these limitations. Comprehensive experiments are conducted to demonstrate the efficiency of the proposed approach.
[BR02] T. Brinkhoff, ”A framework for generating network-based moving objects.”Geoinformatica, Vol. 6, No. 2, pp. 153-180, 2002.
[CC05] Hyung-Ju Cho, and Chin-Wan Chung, ”An Efficient and Scalable Approach to CNN Queries in a Road Network.”in Proceedings of the 31th International Conference on Very Large Data Bases (VLDB’05), Trondheim, Norway, 2005.
[DI59] E. W. Dijkstra, ”A note on two problems in connection with graphs”Numeriche Mathematik, vol. 1, pp. 269-271, 1959.
[HLX06] Haibo Hu, Dik Lun Lee, and Jianliang Xu, ”Fast nearest neighbor search on road networks”in Extending in Database Technology, 2006, pp.186-203.
[ISS03] Glenn S.Iwerks, Hanan Samet, and Ken Smith , ”Continuous K-nearest neighbor queries for continuously moving points with updates.”in Proceedings of the 29th International Conference on Very Large Data Bases (VLDB’03), Berlin, Germany, September 9-12 2003.
[JKPT03] Christian S. Jensen, Jan Kolar, Torben Bach Pedersen, and Igor Timko, ”Nearest neighbor queries in road networks”in Proceedings of the ACM GIS, New Orleans, Louisiana, USA, November 7-8 2003.
[KHIS+86] 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.
[KS04] Mohammad Kolahdouzan, and Cyrus Shahabi, ”Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases.”in Proceedings of the 30th International Conference on Very Large Data Bases (VLDB’04), Toronto, Canada, 2004.
[KS04] Mohammad Kolahdouzan, and Cyrus Shahabi, ”Continuous K Nearest Neighbor Queries in Spatial Network Databases”in Proceedings of the Spatio-Temporal Databases Management (STDBM), Toronto, Canada, August 30 2004.
[MHP05] KyriakosMouratidis, Marios Hadjieleftheriou, and Dimitris Papadias, ”Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring”in Proceedings of ACM SIGMOD, 2005.
[MYPM06] Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, and Nikos Mamoulis, ”Continuous nearest neighbor monitoring in road networks”in Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB’06), Seoul, Korea, September 12-15 2006.
[PZMT03] Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao, ”Query Processing in Spatial Network Databases”in Proceedings of the 29th International Conference on Very Large Data Bases (VLDB’03), Berlin, Germany, September 9-12 2003.
[RPM03] K. Raptopoulou, A. N. Papadopoulos, and Y. Manolopoulos, ”Fast Nearest-Neighbor Query Processing in Moving-Object Databases”Geoinformatica, vol. 7, no. 2, pp. 113-137, June 2003.
[TIGER] http://www.rtreeportal.org/.
[TP02] Yufei Tao, and Dimitris Papadias, ”Time-parameterized queries in spatio-temporal databases”in Proceedings of ACM SIGMOD, Madison, Wisconsin 2002.
[SKS03] Cyrus Shahabi, Mohammad R. Kolahdouzan, and Mehdi Sharifzadeh, ”A road network embedding technique for k-nearest neighbor search in moving object databases”Geoinformatica, vol. 7, no. 3, pp.255-273, 2003.
[TPS02] Yufei Tao, Dimitris Papadias, and Qiongmao Shen, ”Continuous nearest neighbor search”in Proceedings of the 28th International Conference on Very Large Data Bases (VLDB’02), Hong Kong, China, August 20-23 2002.
[XMA05] Xiaopeng Xiong, Mohamed F. Mokbel, and Walid G. Aref, ”SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases”in Proceedings of the 21st International Conference on Data Engineering (ICDE), Washington, DC, USA, 2005.
[YPK05] Xiaohui Yu, Ken Q. Pu, and Nick Koudas, ”Monitoring k-Nearest Neighbor Queries over Moving Objects”in Proceedings of the 21st International Conference on Data Engineering (ICDE), Washington, DC, USA, 2005.
校內：2011-01-14公開校外：2011-01-14公開