考量反向式天際線之Top-k查詢處理

Top-k Query Processing Considering Reverse Skyline Retrieval

吳柏輝(Po-Hui Wu)

指導教授 ： 陳良弼

國立清華大學/電機資訊學院/資訊工程學系/碩士(2012年)

https://doi.org/10.6843/NTHU.2012.00673

摘要

給定一群使用者的需求規格以及一群產品的規格，雙資料型態的反向式天際線對於單一產品會取得一群使用者，而這些使用者依照本身規格需求皆會把此產品視為天際線之一。
最近的研究關於解決雙資料型態的反向式天際線問題中，目前以[WTW09]發表的BRS演算法為目前為止最佳的演算法，此演算法利用R-tree索引結構的特性藉由減少存取索引的次數去加快處理時間。BRS 針對單一的產品能快速地取得此產品的反向式天際線。在本篇論文中，我們第一個提出此新的問題，在反向式天際線的概念下找尋最受歡迎的k個產品。倘若我們利用BRS去解決此問題，勢必要對於每一個產品都套用BRS演算法取得每個產品的反向式天際線大小，在經由排序去挑出具有最大反向式天際線的前k個產品。不同於以上所提到的方法，我們設計了一個演算法直接評估哪k個產品具有最大的反向式天際線，預先避免去計算那些不可能成為答案的產品。我們結合了R-tree索引結構的特性也利用的計算過的資訊去加速評估的時間。最後，我們藉由許多實驗將我們的方法比較了上述提到的BRS以及另一個解決此問題的基礎方法。如結論所示，當使用者需求的量大時我們的演算法將會有很好的效能。

關鍵字

反向式天際線

並列摘要

Given a set of products and users, the Bichromatic Reverse Skyline query from a product returns a set of users who consider this product as one of their skyline points.
In recent researches on addressing bichromatic reverse skyline query, the state-of-the-art algorithm is the BRS algorithm [WTW09], which utilizes some properties of R-tree index structure to speed up the processing time by reducing IO accesses. BRS finds the reverse skyline of one product rapidly. In this thesis, we make the first attempt to study a new problem on extracting the k most popular products by reverse skyline retrieval. If using BRS to solve this problem, BRS has to be applied to every product, and the reverse skyline of all products generated has to be sorted such that the top k products are the results. Different from the above method, we design an algorithm to directly estimate which k products have the most reverse skyline, avoiding calculating some products that could not be the answers in advance. We combine the properties of R-tree structure and the computed information to speed up the estimating time. Then we compare our method with a basic method and the BRS algorithm by many experiments. As in conclusion, we get a good performance when the amount of users is big.

並列關鍵字

Reverse Skyline ； Top-k ； R-tree

參考文獻

[BKS01] S. Borzsonyi, D. Kossmann, and K. Stocker. The skyline operator. In Proceedings of the 17th International Conference on Data Engineering, ICDE2001, Heidelberg, Germany, pp. 421-430.

[HLK10] A. Han, Z. Li, D. Kwon and Y. Park. An Efficient Method for Processing Reverse Skyline Queries over Arbitrary Spatial Objects. In Proceedings of the 2nd International Workshop on Database Technology and Applications, DBTA2010, Wuhan, Hubei, China, pp. 1-4.

[LC08] X. Lian and Lei. Chen. Monochromatic and bichromatic reverse skyline search over uncertain databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD2008, Vancouver, BC, Canada, pp. 213-226.

[PTF05] D. Papadias, Y. Tao, G. Fu, and B. Seeger. Progressive skyline computation in database systems. ACM Trans. Database Syst. 30, 1 (Mar. 2005) pp. 41-82.

[SBS08] D. Sacharidis, P. Bouros, and T. Sellis. Caching dynamic skyline queries. In Proceedings of the 20th International Conference on Statistical and Scientific Database Management, SSDBM2008, Hong Kong, China, pp. 455-472.