臺灣博碩士論文加值系統

天際線查詢會回傳在資料集中所有沒有被Dominate的物件，過去已經有很多這類計算天際線查詢的方法被提出──例如bitmap和divide-and-conquer，我們也將這類結果不會產生改變的天際線查詢稱為snapshot天際線查詢。但是在現今世界中，這種snapshot天際線查詢似乎越來越不符合近來產生的一種新需求──移動式的查詢，這種查詢需要根據查詢點即時更新結果，像是在開車時發出的請求，我們就需要去觀察它的動態以確保結果在大多數時間內是正確的。相對於snapshot天際線查詢，這種查詢一般被稱作連續性的天際線查詢。近年來因為手持裝置的流行，導致連續性的查詢越來越受到重視，使得相關的研究數量開始增長，例如連續性最近鄰居查詢、連續性最近k個鄰居查詢、連續性天際線查詢等等，而本文著重於連續性天際線查詢的探討。在連續性天際線查詢上現有的方法有預測法、安全區域(safe region)等等，而本文中提出的方法根據更新時機能夠實做成多種樣式，我們將介紹更新的方式、接著示範將此方法實作於歐基里德空間以及真實道路網路的方法，並經由實驗驗證其優缺點及執行效能。 

Skyline query returns objects that are not being dominated in the data set, many of the contributions to compute skyline query such as bit-map and divide-and-conquer has been proposed, we also call this kind of query as snapshot skyline query since their results are static, but nowadays those snapshot skyline query seems not enough for real-world situation, they don’t meet our new requirements which people needs to get the real-time results while moving, for example: one may request when driving, therefore we need to observe the results to ensure that its correct in most of the time, in contrast to snapshot skyline query, this kind of query is known as continuous skyline query. Due to the popularity of mobile devices, researches of continuous query such as continuous nearest neighbor query, continuous k nearest neighbor query, and continuous skyline query have been taken more attention than before; in this paper, we will focus on continuous skyline query. Exists approaches such as prediction methods, safe region can well handle the skyline result continuously, in contrast, our approach can be easily implement on different environment by changing its update timing, we will introduce the way to implement our algorithms on both Euclidean space and real-world road networks; the advantages and disadvantages can be seem through experiments.

摘 要 i
Abstract ii
致 謝 iv
Contents v
List of Figures vii
List of Tables ix
List of Algorithms x
Chapter 1 INTRODUCTION 1
Chapter 2 RELATED WORK 5
2.1 Snapshot Skyline Queries 5
2.1.1 Bitmap 5
2.1.2 Branch and Bound Skyline Algorithm (BBS) 7
2.2 Continuous Skyline Queries 9
2.2.1 Prediction method 10
2.2.2 Safe zone based skyline 11
2.2.3 Distance-based skyline 13
Chapter 3 GETTING STARTED 16
Chapter 4 BASIC ALGORITHM 18
4.1 Initialization 18
4.2 Adjustment 20
Chapter 5 IMPLEMENTATION 30
5.1 In Euclidean Space 30
5.2 In Road Networks 32
Chapter 6 IMPROVED ALGORITHM 34
Chapter 7 EXPERIMENTS 36
7.1 Setup 36
7.2 Performance Analysis 36
7.2.1 Initialization phase 36
7.2.2 Continuous Skyline Query in Euclidean Space 38
7.2.3 Continuous Skyline Query in Road Networks 42
Chapter 8 CONCLUSIONS 52
Chapter 9 REFERENCES 53

[1]Stephan Borzsonyi, Donald Kossmann, Konrad Stocker. The Skyline Operator. In proceedings of ICDE, pp.421-430, 2001.
[2]Kian-Lee Tan, Pin-Kwang Eng, Beng Chin Ooi. Efficient Progressive Skyline Computation. In proceedings of VLDB, pp.301-310, 2001.
[3]Donald Kossmann, Frank Ramsak, Steffen Rost. Shooting Stars in the Sky: An Online Algorithm for Skyline Queries. In proceedings of VLDB, pp.275-286, 2002.
[4]Zhiyong Huang, Hua Lu, Beng Chin Ooi, Anthony K.H. Tung
Continuous Skyline Queries for Moving Objects. TKDE, 18(12):1645-1658, 2006.
[5]Muhammad Aamir Cheema, Xuemin Lin, Wenjie Zhang, Ying Zhang.
A safe zone based approach for monitoring moving skyline queries. In proceedings of EDBT, pp.275-286, 2013.
[6]Akrivi Vlachou, Christos Doulkeridis, Kjetil Nørvåg. Distributed top-k query processing by exploiting skyline summaries. Distributed and Parallel Databases, 30(3-4):239-271, 2012.
[7]Yufei Tao, Xiaokui Xiao, Jian Pei. Efficient Skyline and Top-k Retrieval in Subspaces. TKDE, 19(8):1072-1088, 2007.
[8]Mohamed A. Soliman, Ihab F. Ilyas, Nick Koudas. Finding Skyline and Top-k Bargaining Solutions. In proceedings of ICDE, pp.1263-1267, 2007.
[9]Jongwuk Lee, Gae-won You, Seung-won Hwang. Personalized top-k skyline queries in high-dimensional space. Information Systems, 34(1):45-61, 2009.
[10]Jian Pei, Wen Jin, Martin Ester, Yufei Tao. Catching the Best Views of Skyline: A Semantic Approach Based on Decisive Subspaces. In proceedings of VLDB, pp.253-264, 2005.
[11]Yidong Yuan, Xuemin Lin, Qing Liu, Wei Wang, Jeffrey Xu Yu, Qing Zhang. Efficient Computation of the Skyline Cube. In proceedings of VLDB, pp.241-252, 2005.
[12]Dimitris Papadias, Yufei Tao, Greg Fu, Bernhard Seeger. An Optimal and Progressive Algorithm for Skyline Queries. In proceedings of ACM SIGMOD International Conference on Management of Data, pp.467-478, 2003.
[13]Maria Kontaki, Apostolos N. Papadopoulos, Yannis Manolopoulos. Continuous Top-k Dominating Queries. TKDE, 24(5):840-853, 2012.
[14]Yufei Tao, Xiaokui Xiao, Jian Pei. Efficient Skyline and Top-k Retrieval in Subspaces. TKDE, 19(8):1072-1088, 2007.
[15]Antomn Guttman. R-trees- a dynamic index structure for spatial searching. In proceedings of ACM SIGMOD International Conference on Management of Data, pp.47-57, 1984.
[16]Shichang Fu, Yihong Dong, Maoshun He. Continuous Probabilistic Skyline Queries for Uncertain Moving Objects. In proceedings of ICINCO, pp.396-399, 2010.
[17]Junchang Xin, Mei Bai, Guoren Wang. Efficient Threshold Skyline Query Processing in Uncertain Databases. In proceedings of ICNC, pp.311-315, 2011.
[18]Yuan-Ko Huang, Chia-Heng Chang, Chiang Lee. Continuous distance-based skyline queries in road networks. Information Systems, 37(7):611-633, 2012.
[19]Su Min Jang, Jae Soo Yoo. Processing Continuous Skyline Queries in Road Networks. In proceedings of CSA, pp.353-356, 2008.
[20]Mu-Woong Lee, Seung-won Hwang. Continuous Skylining on Volatile Moving Data. In proceedings of ICDE, pp.1568-1575, 2009.
[21]Eman El-Dawy, Hoda M. O. Mokhtar, Ali El-Bastawissy. Multi-level Continuous Skyline Queries (MCSQ). In proceedings of ICDKE, pp.36-40, 2011.
[22]Weihuang Huang, Guoliang Li, Kian-Lee Tan, Jianhua Feng.
Efficient Safe-Region Construction for Moving Top-K Spatial Keyword Queries.
In proceedings of CIKM, pp.932-941, 2012.
[23]Muhammad Aamir Cheema, Wenjie Zhang, Xuemin Lin, Ying Zhang. Efficiently processing snapshot and continuous reverse k nearest neighbors queries. The VLDB Journal, 21(5):703-728, 2012.
[24]Real Datasets for Spatial Databases: Road Networks and Points of Interest, http://www.cs.fsu.edu/~lifeifei/SpatialDataset.htm, 2014.