An Efficient Grid Method for Continuous Skyline Computation over Dynamic Data Set
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
Skyline queries are an important new search capability for multi-dimensional databases. Most of the previous works have focused on processing skyline queries over static data set. However, most of the real applications deal with the dynamic data set. Since dynamic data set constantly changes as time passes, the continuous skyline computation over dynamic data set becomes ever more complicated. In this paper, we propose a multiple layer grids method for continuous skyline computation (MLGCS) that maintains multiple layer grids to manage the dynamic data set. The proposed method divides the work space into multiple layer grids and creates the skyline influence region in the grid of each layer. In the continuous environment, the continuous skyline queries are only handled when the updating data points are in the skyline influence region of each layer grid. Experiments based on various data distributions show that our proposed method outperforms the existing methods.
Abstract
Skyline queries are an important new search capability for multi-dimensional databases. Most of the previous works have focused on processing skyline queries over static data set. However, most of the real applications deal with the dynamic data set. Since dynamic data set constantly changes as time passes, the continuous skyline computation over dynamic data set becomes ever more complicated. In this paper, we propose a multiple layer grids method for continuous skyline computation (MLGCS) that maintains multiple layer grids to manage the dynamic data set. The proposed method divides the work space into multiple layer grids and creates the skyline influence region in the grid of each layer. In the continuous environment, the continuous skyline queries are only handled when the updating data points are in the skyline influence region of each layer grid. Experiments based on various data distributions show that our proposed method outperforms the existing methods.
참고문헌 (14)
- S. Borzsonyi, "The skyline operator", Proc. ICDE, pp.421~430 (2001)
- K.L. Tan, "Efficient Progressive Skyline Computation", Proc. VLDB, pp.301~10 (2001)
- D. Papadias, "An optimal and progressive algorithm for skyline queries", Proc. SIGMOD, pp.467~478 (2003)
- D. Papadias, "Progressive skyline computation in database system", ACM Journal, 30(1), pp.41~82 (2005)
- W.T. Balke, "Efficient distributed skyline for web information systems", Proc. EDPT’04, pp.256~273 (2004)
- M. Morse, "Efficient Continuous Skyline Computation", Proc. ICDE, pp.108~108 (2006)
- X.M. Lin, "Stabbing the Sky: Efficient Skyline Computation over Sliding Windows", Proc. ICDE, pp.502~513 (2005)
- Y.F. Tao, "Maintianing sliding window skylines on data streams", IEEE Journal, 18(3), pp.377~391 (2006)
- Z.Y. Huang, "Continuous skyline queries for moving objects", IEEE Journal, 18(12), pp.1645~1658 (2006)
- L. Tian, "Continuous Monitoring of Skyline Query over Highly Dynamic Moving Objects", Proc. MobiDE’07, pp.59~66 (2007)
- L. Tian, "Grid Index Based Algorithm for Continuous Skyline Computation", Chinese Journal of Computers, 6(6), pp.988~1012 (2008)
- H.T. Kung, "On finding the maxima of a set of vectors", ACM Journal, 22(4), pp.469~476 (1975)
- Jan Chomicki, "Skyline with presorting", Proc. ICDE, pp.717~719 (2003)
- D. Kossmann, "Shooting Stars in the Sky: an Online Algorithm for Skyline Queries", Proc. VLDB, pp.275~286 (2002)