道路網路上連續性天際線查詢的探討

A Study for Continuous Skyline Queries in Road Networks

洪任佐(Jen-Tso Hung)

指導教授 ： 劉傳銘

國立臺北科技大學/電資學院/資訊工程系研究所/碩士(2014年)

https://doi.org/10.6841/NTUT.2014.00655

摘要

天際線查詢會回傳在資料集中所有沒有被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.

並列關鍵字

Continuous Skyline query ； Road networks ； Euclidean space

參考文獻

[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.