| ¡¡ | Chinese Journal of Computers Full Text |
| Title | Efficient Computation of Subspace Skylines over Data Streams |
| Authors | SUN Sheng-Li HUANG Zhen-Hua LI Jin-Jiu GUO Jian-Kui ZHU Yang-Yong |
| Address | (Department of Computing and Information Technology, Fudan University, Shanghai 200433) |
| Year | 2007 |
| Issue | No.8(1418¡ª1428) |
| Abstract & Background | Abstract Data stream processing and Skyline computing within subspaces have recently received a lot of attentions in database and data mining community. Previous works only sought to maintain full space Skylines over sliding windows. No one considered the problem of computing subspace Skylines over sliding windows. In this paper, the authors adopt an efficient full space Skyline maintaining method leveraging grid index structure, and based on this, propose an efficient top-town algorithm to incrementally output the Skyline objects within specified subspaces. Moreover, the authors present a set of optimizing heuristics to speed up these processes. Theoretical analysis and extensive experiments demonstrate that the proposed algorithm can generate the first result only taking a little overhead compared with previous works, and the methods are both efficient and scalable. keywords Skyline computing; data stream; subspace Skyline; grid index; incremental method background This paper is partially supported by the National Natural Science Foundation of China under Grants No.60373111 and No. 60573068, Program for New Century Excellent Talents in University (NCET), Natural Science Foundation of Chongqing under grant No.2005BA2003, Science & Technology Research Program of Chongqing Education Commission under grant No.KJ060517. In the research of rough set theory, many researchers have proposed many algorithms for attribute reduction. However, it is difficult for the existed attribute reduction algorithms to process huge data sets. There are two reasons. One is the time complexity, and the other is the space complexity. Especially in processing huge data set, the space complexity of an algorithm will affect greatly its efficiency. In this paper, a quick algorithm for attribute reduction of ordered attributes is proposed based on the divide and conquer method. Its average time complexity is O(£üU£ü¡Á£üC£ü¡Á(£üC£ü+log£üU£ü)) and space complexity is O(£üU£ü+£üC£ü). The algorithm is suitable for huge data processing. It may be helpful to put rough set theory into industry applications. |