AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (3.1 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Efficient Processing of Skyline Group Queries over a Data Stream

Xi GuoHailing LiAziguli Wulamu( )Yonghong XieYajing Fu
Beijing Key Laboratory of Knowledge Engineering for Materials Science, University of Science and Technology Beijing, Beijing 100083, China.
Show Author Information

Abstract

In this paper, we study the skyline group problem over a data stream. An object can dominate another object if it is not worse than the other object on all attributes and is better than the other object on at least one attribute. If an object cannot be dominated by any other object, it is a skyline object. The skyline group problem involves finding k-item groups that cannot be dominated by any other k-item group. Existing algorithms designed to find skyline groups can only process static data. However, data changes as a stream with time in many applications, and algorithms should be designed to support skyline group queries on dynamic data. In this paper, we propose new algorithms to find skyline groups over a data stream. We use data structures, namely a hash table, dominance graph, and matrix, to store dominance information and update results incrementally. We conduct experiments on synthetic datasets to evaluate the performance of the proposed algorithms. The experimental results show that our algorithms can efficiently find skyline groups over a data stream.

References

[1]
Xu C. and Gao Y., A novel approach for selecting the top skyline under users’ references, in Information Management and Engineering (ICIME), 2010 The 2nd IEEE International Conference on, 2010, pp. 708712.
[2]
Im H. and Park S., Group skyline computation, Information Sciences, vol. 188, pp. 151-169, 2011.
[3]
Li C., Rajasekaran S., Zhang N., Hassan N., and Das G., On skyline groups, IEEE Transactions on Knowledge and Data Engineering (TKDE), vol. 26, no. 4, pp. 942-956, 2014.
[4]
Börzsönyi S. and Stocker D. K. K., The skyline operator, in Proceedings of the International Conference on Data Engineering (ICDE), 2001, pp. 421430.
[5]
Chomicki J., Godfrey P., Gryz J., and Liang D., Skyline with presorting, in Proceedings of the International Conference on Data Engineering (ICDE), 2003, pp. 717719.
[6]
Chaudhuri S., Dalvi N., and Kaushik R., Robust cardinality and cost estimation for skyline operator, in Proceedings of the International Conference on Data Engineering (ICDE), 2006, p. 64.
[7]
Tao Y. and Papadias D., Maintaining sliding window skylines on data streams, IEEE Transactions on Knowledge and Data Engineering (TKDE), vol. 18, no. 3, pp. 377- 391, 2006.
[8]
Liu X., Yang D., Ye M., and Lee W., U-skyline: A new skyline query for uncertain databases, IEEE Transactions on Knowledge and Data Engineering (TKDE), vol. 25, no. 4, pp. 945-960, 2013.
[9]
Li Y., Qu W., Li Z., Xu Y., Ji C., and Wu J., Sky line query based on user preference with mapreduce, in 2014 IEEE 12th International Conference on Dependable, Autonomic and Secure Computing, 2014, pp. 153158.
[10]
Godfrey P., Shipley R., and Gryz J., Maximal vector computation in large data sets, in Proceedings of International Conference on Very Large Data Bases (VLDB), 2005, pp. 229240.
[11]
Lee K. C. K., Lee W., Zheng B., Li H., and Tian Y., Z-sky: An efficient skyline query processing framework based on z-order, The VLDB Journal, vol. 19, no. 3, pp. 333-362, 2010.
[12]
Kossemann D., Ramsak F., and Rost S., Shooting stars in the sky: An online algorithm for skyline queries, in Proceedings of International Conference on Very Large Data Bases (VLDB), 2002, pp. 275286.
[13]
Papadias D., Tao Y., Fu G., and Seeger B., An optimal and progressive algorithm for skyline queries, in ACM SIGMOD 2003, 2003, pp. 467478.
[14]
Ercha A., Huang W., Liu S., Shi L., Gong J., Chen Y., and Shen H., A regional ionospheric tec mapping technique over China and adjacent areas: Gnss data processing and dineof analysis, SCIENCE CHINA Information Sciences, vol. 58, no. 10, p. 107201, 2015.
[15]
Li X., Wang H., Ding B., and Li X., Mabpan optimal resource allocation approach in data center networks, SCIENCE CHINA Information Sciences, vol. 57, no. 16, p. 102801, 2014.
[16]
Aggarwal C. C., ed., Data Streams: Models and Algorithms. Springer, 2007.
[17]
Morse M., Patel J. M., and Grosky W. I., Efficient continuous skyline computation, in Proceedings of the International Conference on Data Engineering (ICDE), 2006, p. 108.
[18]
Lee Y., Lee K., and Kim M. H., Efficient processing of multiple continuous skyline queries over a data stream, Information Sciences, vol. 221, pp. 316-337, 2013.
Tsinghua Science and Technology
Pages 29-39
Cite this article:
Guo X, Li H, Wulamu A, et al. Efficient Processing of Skyline Group Queries over a Data Stream. Tsinghua Science and Technology, 2016, 21(1): 29-39. https://doi.org/10.1109/TST.2016.7399281

509

Views

25

Downloads

11

Crossref

N/A

Web of Science

13

Scopus

2

CSCD

Altmetrics

Received: 01 September 2015
Accepted: 13 October 2015
Published: 04 February 2016
© The author(s) 2016
Return