臺灣博碩士論文加值系統

在過去幾年，天際線查詢的相關議題已經備受關注。而近年來，能應用在環境監控、商業決策等許多應用的反向天際線查詢，也讓許多的學者開始著手研究。在大部份反向天際線查詢的應用中，使用者所考量的查詢經常是同時有多個查詢點。處理此類多查詢點最簡單直覺的作法就是，針對每一查詢點進行個別的處理。很不幸地，此種方式將會花費極高的處理成本。在本論文中，我們提出了一個非常有效的演算法，稱為同步反向天際線演算法(CRS)，來處理多查詢點的反向天際線查詢。此演算法同時將查詢點之間的關係，以及查詢點和資料點之間的關係考量在演算法的設計中。同時，它也利用批次處理的技巧去降低處理成本。因此，同步反向天際線演算法能降低每個查詢點的平均處理成本。實驗的結果也證實，我們所提出的演算法在各種環境中皆能進行有效的處理。

The related issues of skyline query have become more popular in the past few years. Recently, many researchers have focused on the reverse skyline query because it is very useful in many applications, such as environment monitoring and commercial decision. In most applications of reverse skyline query, users consider several query points at the same time. The na?ve method for processing multiple query points is to deal with each query point one by one. Unfortunately, this method incurs significant cost for processing query. In this paper, we propose an efficient processing algorithm, named Concurrent Reverse Skyline algorithm (CRS), for reverse skyline query with multiple points. It takes into account the relationships not only between query points but also between query point and data. And a batch processing technique is used to lower the processing cost. Thus the CRS could reduce the average processing cost of each query point. The experiment results also show the efficiency and effectively of our proposed algorithm under various environments.

摘要 I
ABSTRACT II
致謝 III
目錄 IV
圖目錄 VI
表目錄 VIII
CHAPTER 1 INTRODUCTION 1
CHAPTER 2 RELATED WORK 8
2.1 動態天際線查詢處理 (DYNAMIC SKYLINE QUERY PROCESSING) 8
2.2 反向天際線查詢處理 (REVERSE SKYLINE QUERY PROCESSING) 10
2.2.1 單一資料集合反向天際線查詢 (Monochromatic Reverse Skyline Query) 10
2.2.2 雙資料集合反向天際線查詢 (Bichromatic Reverse Skyline Query) 11
2.3 其餘議題探討 15
CHAPTER 3 PRELIMINARIES 18
3.1 PROBLEM DEFINITION 18
CHAPTER 4 CONCURRENT REVERSE SKYLINE ALGORITHM (CRS) 22
4.1 多查詢點的處理問題 22
4.2 共同區域與非共同區域的處理行為 23
4.3 查詢點集合的分群 27
4.4 查詢點群組與資料群組的處理 29
4.4.1 過濾階段 (Filtering Phase) 30
4.4.2 精煉階段 (Refinement Phase) 32
4.5 CRS演算法實例 34
CHAPTER 5 EXPERIMENTAL EVALUATION 40
5.1 參數設定 40
5.2 實驗資料 41
5.3 實驗結果與討論 42
CHAPTER 6 CONCLUSIONS AND FUTURE WORK 53
BIBLIOGRAPHY 55

[1]S. Borzsonyi, D. Kossmann, and K. Stocker, “The skyline operator, in Proceedings of the 17th International Conference on Data Engineering (ICDE’01), Duesseldorf, Germany, April 2-6,2001, pp. 421-430.
[2]K. L. Tan, P. K. Eng, and B. C. Ooi, “Efficient progressive skyline computation, in Proceedings of 27th International Conference on Very large data bases(VLDB’01), Roma, Italy, Septembe 11-14, 2001, pp.301-310.
[3]J. Chomicki, P. Godfrey, J.Gryz, and D. Liang, “Skyline with Presorting, in Proceedings of the 19th International Conference on Data Engineering (ICDE’03), Hong Kong, China, March 5-8, 2003, pp.717-719.
[4]P. Godfrey, R. Shipley, and J. Gryz, “Maximal Vector Computation in Large Data Sets, in Proceedings of the 31st international conference on Very large data bases (VLDB’05), Trondheim, Norway , August 30 - September 2, 2005, pp. 229-240.
[5]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 conference on Management of data, San Diego, California, Jun 9-12, 2003, pp. 467-478.
[6]X. Lian, and L. Chen, “Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases, in Proceedings of the 2008 ACM SIGMOD international conference on Management of data, Vancouver, BC, Canada, June 10-12, 2008 , pp. 213-226.
[7]Z. Ling, L. Cuiping, and C. Hong, “ Efficient computation of reverse skyline on data stream, in Proceedings of the 2009 International Joint Conference on Computational Sciences and Optimization, CSO 2009, Sanya, Hainan, China, April 24-26, 2009, pp.735-739
[8]A. Guttman, “R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING, in Proceedings of the 1984 ACM SIGMOD international conference on Management of data, Boston, Massachusetts, June 18-21, 1984, pp.47-57.
[9]E. Dellis and B. Seeger, “Efficient Computation of Reverse Skyline Queries, in Proceedings of the 33rd international conference on Very large data bases (VLDB’07), Vienna, Austria, September 23-27, 2007, pp. 291-302.
[10]X. Wu, Y. Tao, R. Chi-Wing Wong, L. Ding, J. Xu Yu, “Finding the Influence Set through Skylines, in Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (EDBT’09), Saint-Petersburg, Russia, March 23-26, 2009, pp. 1030-1041.
[11]Y. Yuan, X. Lin, Q. Liu, W. Wang, J. X. Yu, and Q. Zhang, “Efficient computation of the skyline cube, in Proceedings of the 31st international conference on Very large data bases (VLDB’05), Trondheim, Norway , August 30 - September 2, 2005,pp.241-252.
[12]J. Pei, W. Jin, M. Ester, and Y. Tao, “Catching the best views of skyline: a semantic approach based on decisive subspaces, in Proceedings of the 31st international conference on Very large data bases (VLDB’05), Trondheim, Norway , August 30 - September 2, 2005, pp.253-264.
[13]T. Xia and D. Zhang, “Refreshing the sky: the compressed skycube with efficient support for frequent updates, in Proceedings of the 2006 ACM SIGMOD international conference on Management of data, Chicago, USA, June26-29, 2006, pp.491-502.
[14]Y. Tao, X. Xiao, and J. Pei, “SUBSKY: efficient computation of skylines in subspaces, in Proceedings of the 22nd International Conference on Data Engineering (ICDE’06), Atlanta, GA, USA, 03-07 April, 2006, pp. 65-65.
[15]J. Pei, Ada Wai-Chee Fu, X. Lin, and H. Wang, “Computing compressed skyline cubes efficiently, in Proceedings of the 23rd International Conference on Data Engineering (ICDE’07), Istanbul, Turkey, 15-20 April, 2007, pp.96-105.
[16]X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang, “Selecting stars: the K most representative skyline operator, in Proceedings of the 23rd International Conference on Data Engineering (ICDE’07), Istanbul, Turkey, 15-20 April, 2007, pp. 86-95.
[17]Y. Tao, L. Ding, X. Lin, and J. Pei, “Distance-based Representative Skyline, in Proceedings of the 2009 IEEE International Conference on Data Engineering (ICDE’09), Shanghai, China, March 29-April 2, 2009, pp. 892-903.
[18]D. Sacharidis, S. Papadopoulos, and D. Papadias, “Topologically-sorted Skylines for Partially-ordered Domains, in Proceedings of the 25th International Conference on Data Engineering (ICDE’09), Shanghai, China, March29-April 2, 2009, pp.1072-1083.
[19]M. Morse, J. M. Patel, and H. V. Jagadish, “Efficient Skyline Computation over Low-Cardinality Domains, in Proceedings of the 33rd international conference on Very large data bases(VLDB’07), University of Vienna, Austria, September 23-27, 2007, pp.267-278.
[20]M.Sharifzadeh and C.Shahabi, “The Spatial Skyline Queries, in Proceedings of the 32nd international conference on Very large data bases(VLDB’06), Seoul, Korea, 2006, pp.751-762.
[21]K. Deng, X. Zhou, and Heng Tao Shen, “Multi-source Skyline Query Processing in Road Networksm, in Proceedings of the 23rd International Conference on Data Engineering (ICDE’07), Istanbul, Turkey, 15-20 April, 2007, pp. 796-805.
[22]B.Zheng, Ken C. K. Lee, and Wang-Chien Lee, “Location-Dependent Skyline Query, in Proceedings of the The Ninth International Conference on Mobile Data Management (MDM’08), Beijing, China, April 27-30, 2008, pp. 148-155.
[23]F. Korn and S. Muthukrishnan, “In?uence Sets Based on Reverse Nearest Neighbor Queries, in Proceedings of the 2000 ACM SIGMOD international conference on Management of data, Dallas, Texas, May 14-19, 2000, pp. 201-212.
[24]A. Singh, H. Ferhatosmanoglu, and A. S. Tosun, “High Dimensional Reverse Nearest Neighbor Queries, in Proceedings of the 2003 ACM CIKM International Conference on Information and Knowledge Management, New Orleans, Louisiana, USA, November 2-8, 2003, pp. 91-98.
[25]I. Stanoi, D. Agrawal, and A. E. Abbadi, “Reverse Nearest Neighbor Queries for Dynamic Databases, in ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, Dallas, Texas, May 14-19, 2000, pp. 44-53.
[26]Y. Tao, D. Papadias, and X. Lian, “Reverse kNN Search in Arbitrary Dimensionality in Proceedings of the 30th international conference on Very large data bases(VLDB’04), Toronto, Canada , 29 August - 3 September, 2004, pp. 744–755.
[27]A. Vlachou, C. Doulkeridis, Y. Kotidis, and K. Norvag, “Reverse Top-k Queries, in Proceedings of the 26th International Conference on Data Engineering (ICDE 2010), Long Beach, California, USA, March 1-6, 2010