Processing k-skyband,constrained skyline,and group-by skyline queries on incomplete data |
| |
| Affiliation: | 1. College of Computer Science, Zhejiang University, 38 Zheda Road, Hangzhou 310027, China;2. Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong;1. University of Information Technology, Vietnam National University, Ho Chi Minh, Viet Nam;2. Information Technology Department, Ton Duc Thang University, Ho Chi Minh, Viet Nam;3. Department of Computer Science, University of Science, Vietnam National University, Ho Chi Minh, Viet Nam;1. National Taipei University, No. 151, University Road, San Shia District, Taipei 23741, Taiwan;2. Takming University of Science and Technology, No.56, Sec.1, Huanshan Rd., Taipei 11451, Taiwan;3. National Chengci University, No. 64, Sec. 2, Zhi-Nan Road, Taipei 11605, Taiwan;1. Department of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China;2. College of Computer Science, Zhejiang University, Hangzhou 310027, China;3. Stanford University, Stanford, CA 94305, USA;4. Hewlett-Packard Labs, 94304 Palo Alto, CA, USA;5. School of Finance and Economics, Zhejiang University of Finance & Economics, Dongfang College Jiaxing, Hangzhou 314408, China;1. Department of Computer Science and Information Engineering, National Cheng Kung University, 1, University Road, Tainan City 701, Taiwan, ROC;2. Department of Computer Science and Information Engineering, National Kaohsiung University of Applied Sciences, Kaohsiung 80778, Taiwan, ROC;3. Cloud Service Technology Center, Industrial Technology Research Institute (ITRI South), Tainan, Taiwan, ROC;1. Renesas Mobile Europe Ltd., Elektroniikkatie 10, FI-90570 Oulu, Finland;2. VTT Technical Research Centre of Finland, Finland |
| |
| Abstract: | The skyline operator has been extensively explored in the literature, and most of the existing approaches assume that all dimensions are available for all data items. However, many practical applications such as sensor networks, decision making, and location-based services, may involve incomplete data items, i.e., some dimensional values are missing, due to the device failure or the privacy preservation. This paper is the first, to our knowledge, study of k-skyband (kSB) query processing on incomplete data, where multi-dimensional data items are missing some values of their dimensions. We formalize the problem, and then present two efficient algorithms for processing it. Our methods introduce some novel concepts including expired skyline, shadow skyline, and thickness warehouse, in order to boost the search performance. As a second step, we extend our techniques to tackle constrained skyline (CS) and group-by skyline (GBS) queries over incomplete data. Extensive experiments with both real and synthetic data sets demonstrate the effectiveness and efficiency of our proposed algorithms under various experimental settings. |
| |
| Keywords: | Skyline Constrained skyline Group-by skyline Incomplete data Query processing |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
