- 學位論文
在一個線段上的連續空間天際線查詢
On Continuous Spatial Skyline Query over a Line Segment
摘要
天際線查詢對使用者來說是很有用的，它們可以幫助使用者去做決策。傳統的天際線查詢，資料點的維度都是固定的。有些資料點的維度可能會動態的變動，比如說空間天際線查詢就是考慮某個維度會隨著使用者位置的不同而改變的查詢。舉例來說，針對使用者行駛的一個車輛的路線，使用者想要尋找一間餐廳，這間餐廳距離自己較近，而且靜態屬性也不被其他餐廳支配。 在這篇論文中，我們定義一個新的查詢－在一個線段上的連續空間天際線查詢。在二維平面上給定一個資料集Ｄ、一個線段ｌ以及一個半徑ｒ，空間天際線的查詢在距離ｒ的限制下，對每個ｌ的子線段檢索對應的天際點。我們提出兩個方法去解決這個問題。在基本方法中，我們找尋一些交點，這些交點會使得天際線的答案改變，因此我們只需要在這些交點上去計算；在修剪方法中，發現一些性質可以修剪掉一些資料點，除了減少一些找交點的運算量，也可以降低記算天際線的時間。利用這兩個方法，可以找到一個精準的結果。然而，結果可能會產生很多段數，使用者可能不需要知道這麼複雜的資訊。我們提出一個估計的方法，嘗試能夠縮短段數，並減少時間。另外，也定義一個相似度的距離去測量精準的方法與估計方法的差別。我們進行了實驗的比較，評估兩個精準值的方法，結果顯示修剪方法要比基本方法較有效率。此外，比較了精準方法跟估計方法的差別，結果顯示隨著子線段越來越少，相似度的距離也會越差越大。
並列摘要
The skyline query is useful to users, which helps them make decisions from lots of choices. The traditional skyline query was addressed considering a data space where all dimensions of a data point are static. For example, the distance to the beach of a hotel is static. However, some attributes of a data point may be dynamic. For example, the distance to the beach of a moving car is dynamic, depending on the location of the car. The spatial skyline query to be addressed in this paper considers a data space where some dimensions of a data point are dynamic. Consider a scenario as follows. The route of a moving vehicle can be considered as a series of line segments. A user on the route may issue a skyline query to find restaurants taking into account the static attributes of the restaurants as well as the distance to them. In this paper, we focus on a new skyline query named continuous spatial skyline query over a line segmaent.as described in the following. Given a data set D, a query line segment l (to describe a part of the route), and a distance of r (to describe the acceptable distance for users’ access) in a two-dimensional space, the skyline query retrieves corresponding skyline points within the distance constraint r in each sub-segment of l. We propose two methods to solve the problem. In the basic method, we find some intersection points which may change the skyline results and compute the skyline on these points. In the pruning method, we propose properties to prune some data points for reducing the skyline computation cost. Since many sub-segments can be produced, in order to reduce the number of sub-segments, we also propose an approximate method, and define a similarity function to measure the similarity between the exact result and the approximate result. We perform experiments to evaluate the two methods and the results show that the pruning method is more efficient than the basic method. Moreover, we perform experiments to compare the exact results and approximate results and it shows that there is a trade-off between the reduction of sub-segments and the accuracy of the results.
參考文獻
延伸閱讀
- 黃冠捷（2014）。針對多個天際線查詢的查詢處理機制〔碩士論文，長榮大學〕。華藝線上圖書館。https://doi.org/10.6833/CJCU.2014.00025
- 林以文 (2012). 考慮最近和最遠鄰居為基礎之天際線查詢 [master's thesis, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2012.00675
- CHEN, K. L. (2017). 無須支配關係檢查之高效率天際線聯結查詢方法 [master's thesis, Feng Chia University]. Airiti Library. https://doi.org/10.6341/fcu.M0405822
- 劉益先（2010）。資料串流上以滑動視窗探勘子空間天際線〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu201000124
- Zhang, S. (2011). Scalable skyline evaluation in multidimensional and partially ordered domains [doctoral dissertation, The University of Hong Kong]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0029-1812201200019435