動態有效搜尋之潛在天際線查詢

天際線查詢是一個應用於決策系統上支援搜尋多維度資料庫的重要查詢，我們提出一個支援多維度動態物件的潛在天際線查詢。不同於其他的天際線查詢論文，本論文主要聚焦在提升動態潛在天際線查詢。我們提出一個「動態有效搜尋之潛在天際線」( DyE-Spot: A Dynamic Efficient Search for Potential Skylines,簡稱DyE-Spot )之演算方法，同時設計一個在動態物件上的潛在天際線的技巧，主要的方法是使用預先計算的第二序列天際線作為提升為潛在天際線的候選集合。同時，依照提升成本排序前K個潛在天際線時，搭配著第二序列天際線的效率以及遞增式提升技巧上面更為有利。由於使用第二序列天際線當作潛在天際線的候選集合，我們的方法可以有效率地找出依據提升成本依序排序的潛在天際線的點。最後，我們設計一個成本模型，這個模型計算最小提升成本的同時可被視為剪枝方法( Pruning method )，以避免搜尋全部的資料庫。我們將此方法和目前已知的方法加以比較，實驗結果顯示本論文的方法表現更好，同時透過大量的動態實驗數據也可以看出我們的方法更有效率也更具有擴展性。關鍵字: 多維度資料庫、時空資料庫、天際線查詢、動態天際線查詢

關鍵字

動態天際線查詢；天際線查詢；時空資料庫；多維度資料庫

並列摘要

Skyline queries are an important technique for the search of multi-dimensi- onal databases as useful knowledge is retrieved for decision making applica- tions while observing user preferences. We address the new problem of the potential skyline queries over dynamic objects with d dimensions. In con- trast to most of the prior work, we focus on the issue of promoting a poten- tial skyline, while handling both static and dynamic objects. In this paper, we propose an algorithm termed DyE-SPOT: a Dynamic Efficient Search for Potential Skylines, and design an efficient promotion technique for potential skylines over dynamic objects, by utilizing a pre-computed second-ordered skyline set as a candidate set for the promotion. The second-ordered skyline facilitates an efficient and incremental promotion technique to retrieve a set of top k potential skyline ranked by promotion cost. With the knowledge of the second-order skyline set as a candidate set for promotion, our approach efficiently finds the potential skyline points ranked by their promotion cost in ascending order. Finally, we design a cost model to evaluate the promotion cost which is eventually utilized in a pruning method to avoid scanning the entire data set for promotion. We compare our method to the existing tech- niques and the results demonstrate better performance. Extensive experiment results show that our method on dynamic datasets are both efficient and scal- able. Keywords: Multi-dimensional Databases, Spatial-temporal Databases, Dy- namic skyline queries, Potential skyline search

並列關鍵字

Dynamic skyline queries ； Spatial-temporal Databases ； Multi-dimensional Databases ； Potential skyline search

參考文獻

[1] S. B¨orzs¨onyi, D. Kossmann, and K. Stocker, “The skyline operator,” in Proceedings

[2] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “An Optimal and Progressive Algorithm

for Skyline Queries,” in Proceedings of the 2003 ACM SIGMOD international con-

[4] Z. Huang, H. Lu, B. C. Ooi, and A. K. H. Tung, “Continuous Skyline Queries for

Moving Objects,” IEEE Trans. Knowl. Data Eng., vol. 18, no. 12, pp. 1645–1658,

國際替代計量

動態有效搜尋之潛在天際線查詢

未授權

主題瀏覽