臺灣博碩士論文加值系統

隨著定位技術的發達，著重於管理移動物體進而提供有用資訊的時空資料庫 (spatio-temporal databases) 引起許多研究團隊的注意。在現實生活中，許多應用都與時空查詢 (spatio-temporal queries) 相關，像是地理資訊系統 (geographic information system)，交通監控系統 (traffic monitoring system)，以及行動資訊系統 (mobile information system) 等等。天際線查詢(skyline query) 是一類相當重要的時空查詢。在本篇論文中，我們探討如何將天際線查詢應用於感測器網路 (sensor networks) 的環境下。不同於以往的研究，在感測器網路的環境下，物體的定位不會是依靠全球衛星定位技術 (GPS technique)，而是依靠感測器網路技術 (sensor network technique)。這會使得物體的定位有著較大的定位誤差。在本篇論文中，我們會試著去管理有著不確定位置資訊的物體。利用這些資訊，我們會設計查詢演算法來對物體作天際線查詢。藉由所發展的查詢系統，可以有效地管理移動物體，並提供有用的資訊給使用者。

With the fast advance of positioning techniques, spatio-temporal databases aiming at managing moving objects so as to provide useful information has attracted a lot attention. In real world, there are many applications related to spatio-temporal queries, such as geographic information, traffic monitoring system, and mobile information system. Skyline query is an important type of spatio-temporal queries. In this thesis, we focus on how to apply the skyline query to sensor network environment. Different form the previous research, in the sensor network environment, the positioning technique used is not the GPS technique, but is the sensor network technique. This results in a greater positioning error. In this thesis, we will try to manage the moving objects with uncertain location information. With the location information, we will design query algorithm to process the skyline queries. Benefiting from the developed query system, we can efficiently manage the moving objects and thus provide useful information to the user.

謝誌 I
摘要 II
Abstract III
目次 IV
圖次 VI
第一章 緒論 1
第二章 文獻探討 6
第一節 移動物體的索引架構 6
第二節 相關skyline query處理技術 10
第三章 感測器網路模型 12
第四章 量化物體不確定性 15
第五章 設計索引結構 17
第一節 Grid index structure 17
第二節 Data structures 19
第三節 更新grid index structure 21
第六章 發展Skyline query處理演算法 23
第一節 Skyline query特性 23
第二節 使用的參數 26
第三節 設計過濾準則 27
第四節 發展演算法 28
第七章 設計skyline query機率模型 30
第八章 結論 31
參考文獻 32

1.Daniel Barbara, “Mobile Computing and Databases-a Survey”, IEEE Transactions on Knowledge and Data Engineering, 11(1), 1999.
2.I. Bartolini and P. Ciaccia and M. Patella, "Efficient sort-based skyline evaluation", ACM TODS, 33(4), 2008, p.p. 1-45.
3.S. Borzsonyi, D. Kossmann, and K. Stocker "The skyline operator", Proceedings of the International Conference on Data Engineering, 2001, pp. 421-430.
4.Jinchuan Chen and Reynold Cheng, "Efficient Evaluation of Imprecise Location-Dependent Queries", Proceedings of the International Conference on Data Engineering, 2007.
5.J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, "Skyline with presorting", Proceedings of the International Conference on Data Engineering, 2003, p.p. 717-719.
6.A.Civilis, C.S.Jensen, and S.Pakalnis, "Techniques for efficient road-network-based tracking of moving objects", IEEE Transactions on Knowledge and Data Engineering, 2005, 698-712.
7.R. Cheng, D. V. Kalashnikov, and S. Prabhakar, "Querying imprecise data in moving object environments", IEEE TKDE, 16(9), Sept. 2004.
8.Bruce S.E. Chung and Wang-Chien Lee and Arbee L.P. Chen, " Processing Probabilistic Spatio-Temporal Range Queries over Moving Objects with Uncertainty ", Proceedings of the International Conference on EDBT, 2009.
9.Andrea Cali, Domenico Lembo, and Riccardo Rosati, "On the decidability and complexity of query answering over inconsistent and incomplete databases", PODS 2003.
10.S. Chen, B. C. Ooi, and Z. Zhang, "An adaptive updating protocol for reducing moving object database workload", VLDB 2010.
11.R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar, "Preserving user location privacy in mobile data management infrastructures", Proceedings of the 6th Workshop on Privacy Enhancing Technologies, 2006.
12.E. W. Dijkstra, "A Note on Two Problems in Connection with Graphs", Numeriche Mathematik, 1959, pp. 269-271.
13.K. Deng, X. Zhou, and H. T. Shen, "Multi-source skyline query processing in road networks", Proceedings of the International Conference on Data Engineering, 2007, p.p. 796-805.
14.Ping Fan, Guohui Li, Ling Yuan, and Yanhong Li, "Vague continuous K-nearest neighbor queries over moving objects with uncertain velocity in road networks", Information Systems 37(1), 2012.
15.Antonin Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching", Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, p.p.47-57.
16.H. Hu and D. Lee, "Range nearest-neighbor query", IEEE Transactions on Knowledge and Data Engineering, 18(1), 2006.
17.B. Jiang and J. Pei, "Online interval skyline queries on time series", Proceedings of the International Conference on Data Engineering, 2009, p.p. 1036-1047.
18.W. Jin, A. K. H. Tung, M. Ester, and J. Han, "On efficient processing of subspace skyline queries on high dimensional data", Proceedings of the International Conference on Scientific and Statistical Database Management, 2007.
19.R. Kung, E. Hanson, Y. Ioannidis, T. Sellis, L. Shapiro, and M. Stonebreaker, "Heuristic Search in Data Base System", Proceedings of the International Workshop on Expert Databse Systems, 1986.
20.M. E. Khalefa, M. F. Mokbel, and J. J. Levandoski, "Skyline query processing for incomplete data", ICDE 2008.
21.D. Kossmann, F. Ramsak, and S. Rost, "Shooting stars in the sky: an online algorithm for skyline queries", Proceedings of the VLDB Conference, 2002.
22.Mohammad Kolahdouzan and Cyrus Shahabi, "Voronoi-based K nearest neighbor search for spatial network databases", VLDB 2004.
23.Dik Lun Lee, Wang-chien Lee, Jianliang Xu, and Baihua Zheng,"Data Management in location dependent services", IEEE Pervasive Computing, Vol. 1, No. 3, September 2002, p.p. 65-72.
24.J. Lee, G. W. You, and S. W. Hwang, "Personalized top-K skyline queries in high-dimensional space", Information Systems, 2009, pp. 45-61.
25.X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang, "Selecting stars: the k most representative skyline operator", Proceedings of the International Conference on Data Engineering, 2007.
26.Kyriakos Mouratidis, Yimin Lin, and Man Lung Yiu, “Preference Queries in Large Multi-Cost Transportation Networks”, Proceedings of the International Conference on Data Engineering, 2010.
27.B. C. Ooi, C. H. Goh, and K.-L. Tan, "Fast High-Dimensional Data Search in Incomplete Databases", VLDB 1998.
28.Dieter Pfoser and Christian S. Jensen,“Capturing the Uncertainty of Moving-Object Representations”, Proceedings of the SSDBM, 1999.
29.D. Papadias, Y. Tao, G. Fu, and B. Seeger, “An optimal and progressive algorithm for skyline queries”, Proceedings of the ACM SIGMOD, 2003.
30.N. Sarkas, G. Das, N. Koudas, and A. K. H. Tung, "Categorical skylines for streaming data", Proceedings of the ACM SIGMOD, 2008.
31.S. Saltenis, C.S. Jensen, S.T. Leutenegger, and M.A. Lopez, "Indexing the positions of continuously moving objects", ACM SIGMOD 2000.
32.M. Schubert, M. Renz, and H.P. Kriegel, "Route Skyline Queries: A Multi-Preference Path Planning Approach", Proceedings of International Conference on Data Engineering, 2010.
33.A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao, "Modeling and Querying Moving Objects", ICDE 1997.
34.K.-L. Tan, P.-K. Eng, and B. C. Ooi, “Efficient Progressive Skyline Computation", International Conference on Very Large Data Bases, 2001, p.p. 301-310.
35.Y. Tao, X. Xiao, and J. Pei, “SUBSKY: efficient computation of skylines in subspaces", International Conference on Data Engineering, 2006.
36.L. Zou, L. Chen, M. T. Ozsu, and D. Zhao, “Dynamic Skyline Queries in Large Graphs”, Proceedings of the International Conference on Database Systems for Advanced Applications, 2010.