近幾年以來，許多研究團體針對道路網路 (road network) 去處理天際線查詢 (skyline query)。
天際線查詢可以抓取那些在靜態維度 (static attributes) 與動態維度 (dynamic attribute) 上不會被其他物體給支配 (dominate) 的天際線點 (skyline points)。
過去的研究 [1] 著重在針對道路網路去處理連續天際線之查詢，並且提出兩類以距離為基礎的天際線查詢，名稱分別為 continuous dε-skyline query(Cdε-SQ) 和 continuous k nearest neighbor-skyline query(Cknn-SQ)。
由於道路網路上的交通狀況變化以及物體屬性會經常更新，Cdε-SQ 和 Cknn-SQ 的結果會隨時間改變。
這會造成 [1] 所提出之方法會沒有效率，因為它們的重複執行查詢所耗費之成本很高。

因此在本論文中，我們探討如何針對有著頻繁更新的道路網路去有效地處理 Cdε-SQ 和 Cknn-SQ。
當更新發生時，為了能快速地得到新天際線結果，我們先設計多個資料結構來記錄在靜態與動態維度上物體之間的支配關係。
然後，會利用到這些資料結構來發展 Cdε-SQ 和 Cknn-SQ 的更新機制。
我們使用真實道路網路資料來實作大量的實驗，以便能驗證所提出的機制之有效性與效能。

In recent years, the research community introduced various methods for processing skyline query in road networks. The skyline query retrieves the skyline points that are not dominated by others in terms of static attributes and dynamic attribute (i.e., the road distance). The previous work [1] focused on processing continuous skyline query in road networks and presented two distance-based skyline queries, namely the continuous dε-skyline query (Cdε-SQ) and the continuous k nearest neighbor-skyline query (Cknn-SQ). Due to varying traffic conditions in road networks and frequent updates of objects’ attributes, the results of Cdε-SQ and Cknn-SQ would change with time. This makes the methods proposed in [1] inefficient because of their high query re-evaluation cost.
As a result, in this paper we address the issue of efficiently processing Cdε-SQ and Cknn-SQ in a road network with frequent updates. In order to rapidly obtain the new skyline results when updates occur, we first design various data structures to maintain the dominance relationships between objects, in terms of static attributes and dynamic attribute. Then, the updating mechanisms for Cdε-SQ and Cknn-SQ are developed by making use of these data structures. Extensive experiments using real road network dataset are conducted to demonstrate the effectiveness and the efficiency of the proposed mechanisms.

[1] Y.-K. Huang, C.-H. Chang, and C. Lee, “Continuous skyline queries in road networks,”pp. 175–263, 2010.
[2] S. Borzsonyi, D. Kossmann, and K. Stocker, “The skyline operator,” in 17th International Conference on Data Engineering, pp. 421–430, 2001.
[3] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, “Skyline with presorting,” in Nineteenth International Conference on Data Ingineering, pp. 717–719, 2003.
[4] B. Jiang and J. Pei, “Online interval skyline queries on time series,” in International Conference on Data Engineering, pp. 1036–1047, March 2009.
[5] W. Jin, A. K. H. Tung, M. Ester, and J. Han, “On efficient processing of subspace skyline queries on high dimensional data,” in International Conference on Scientific
and Statistical Database Management, pp. 1–10, 2007.
[6] D. Kossmann, F. Ramsak, and S. Rost, “Shooting stars in the sky: an online algorithm for skyline queries,” in Proceedings of the VLDB Conference, pp. 50–62,2002.
[7] X. Lin, Y.Yuan, Q. Zhang, and Y. Zhang, “Selecting stars: the k most representative skyline operator,” in International Conference on Data Engineering, pp. 86–95, 2007.
[8] J. Lee, G. W. You, and S. W. Hwang, “Personalized top-k skyline queries in highdimensional space,” in Information System, pp. 45–61, 2009.
[9] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “An optimal and progressive algorithm for skyline queries,” in ACM SIGMOD, pp. 467–478, 2003.
[10] N. Sarkas, G. Das, N. Koudas, and A. K. H. Tung, “Categorical skylines for streaming data,” in ACM SIGMOD, pp. 239–250, 2008.
[11] K.-L. Tan, P.-K. Eng, and B. C. Ooi, “Efficient progressive skyline computation,” in International Conference on Very Large Data Bases, pp. 301–310, 2001.
[12] Y. Tao, X. Xiao, and J. Pei, “Subsky: efficient computation of skylines in subspaces,” in IEEE International Conference on Data Engineering, pp. 350–362, 2006.
[13] K. Deng, X. Zhou, and H. T. Shen, “Multi-source skyline query processing in road networks,” in 23rd International Conference on Data Engineering, pp. 796–805,2007.
[14] K. Mouratidis, Y. Lin, and M. L. Yiu, “Preference queries in large multi-cost transportation networks,” in International Conference on Data Engineering, pp. 533–544, 2010.
[15] M. Schubert, M. Renz, and H. Kriegel, “Route skyline queries: A multi-preference path planning approach,” in International Conference on Data Engineering, pp. 261–272, 2010.
[16] L. Zou, L. Chen, M. T. Ozsu, and D. Zhao, “Dynamic skyline queries in large graphs,” in International Conference on Database Systems for Advanced Applications,
pp. 1–15, 2010.
[17] E. W. Dijkstra, “A note on two problems in connection with graphs,” Numeriche Mathematik, vol. 1, pp. 269–271, 1959.
[18] 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, pp. 537–548, 1986.
[19] I. Bartolini, P. Ciaccia, and M. Patella, “Efficient sort-based skyline evaluation,” ACM TODS, vol. 33, no. 4, pp. 1–45, 2008.
[20] X. Lin, Y. Yuan, W. Wangnicta, and H. Lu, “Stabbing the sky: Efficient skyline computation over sliding windows,” in International Conference on Data Engineering,
pp. 502–513, 2005.
[21] M. Morse, J. Patel, and W. Grosky, “Efficient continuous skyline computation,” in Information System, pp. 3411–3437, 2007.
[22] Y. Tao and D. Papadias, “Maintaining sliding window skylines on data streams,” IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 2, pp. 377–391, 2006.
[23] W. Zhang, X. Lin, Y. Zhang, W. Wang, and J. X. Yu, “Probabilistic skyline operator over sliding windows,” in IEEE International Conference on Data Engineering,
pp. 1060–1071, Washington, DC, USA, 2009.
[24] Z. Huang, B. O. H. Lu, and A. Tung, “Continuous skyline queries for moving objects,” IEEE Transactions on Knowledge and Data Engineering, vol. 18, pp. 1645–1658, December 2006.
[25] M. Sharifzadeh and C. Shahabi, “The spatial skyline queries,” in International Conference on Very Large Data Bases, pp. 751–762, 2006.
[26] H.-P. Kriegel, M. Renz, and M. Schubert, “Route skyline queries: A multipreference path planning approach,” in International Conference on Data Engineering, pp. 261–272, 2010.
[27] http://www.rtreeportal.org.
[28] http://www.cs.fsu.edu/ lifeifei/.