We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 29 Issue 2
March  2014
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Lei Zhao, Yan-Yan Yang, Xiaofang Zhou. Continuous Probabilistic Subspace Skyline Query Processing Using Grid Projections[J]. Journal of Computer Science and Technology, 2014, 29(2): 332-344. DOI: 10.1007/s11390-014-1434-9
Citation: Lei Zhao, Yan-Yan Yang, Xiaofang Zhou. Continuous Probabilistic Subspace Skyline Query Processing Using Grid Projections[J]. Journal of Computer Science and Technology, 2014, 29(2): 332-344. DOI: 10.1007/s11390-014-1434-9
shu

Continuous Probabilistic Subspace Skyline Query Processing Using Grid Projections

  • 1 School of Computer Science and Technology, Soochow University, Suzhou 215006, China;
    2 Open System&Storage Interoperability Test Laboratory, IBM, Wuxi 214000, China;
    3 School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, QLD 4072, Australia

Funds: This work is supported by the National Natural Science Foundation of China under Grant Nos. 61073061, 61003044, 61303019, and the Natural Science Foundation of Colleges and Universities of Jiangsu Province of China under Grant No. 12KJB520017.
More Information
  • Author Bio:

    Lei Zhao received the Ph.D. degree in computer science from Soochow University, China, in 2006. He has been a faculty member of the School of Computer Science and Technology of Soochow University since 1998. He is now an associate professor of the Department of Network Engineering. His research interests include distributed data processing, data mining, parallel and distributed computing, etc.

  • Received Date: September 03, 2013
  • Revised Date: December 15, 2013
  • Published Date: March 04, 2014
    Abstract
  • As an important type of multidimensional preference query, the skyline query can find a superset of optimal results when there is no given linear function to combine values for all attributes of interest. Its processing has been extensively investigated in the past. While most skyline query processing algorithms are designed based on the assumption that query processing is done for all attributes in a static dataset with deterministic attribute values, some advanced work has been done recently to remove part of such a strong assumption in order to process skyline queries for real-life applications, namely, to deal with data with multi-valued attributes (known as data uncertainty), to support skyline queries in a subspace which is a subset of attributes selected by the user, and to support continuous queries on streaming data. Naturally, there are many application scenarios where these three complex issues must be considered together. In this paper, we tackle the problem of probabilistic subspace skyline query processing over sliding windows on uncertain data streams. That is, to retrieve all objects from the most recent window of streaming data in a user-selected subspace with a skyline probability no smaller than a given threshold. Based on the subtle relationship between the full space and an arbitrary subspace, a novel approach using a regular grid indexing structure is developed for this problem. An extensive empirical study under various settings is conducted to show the effectiveness and effciency of our PSS algorithm.
    • FullText(HTML)
    • References (29)
  • [1]
    Börzsönyi S, Kossmann D, Stocker K. The skyline operator. In Proc. the 17th ICDE, Apr. 2001, pp.421-430.
    [2]
    Kossmann D, Ramsak F, Rost S. Shooting stars in the sky: An online algorithm for skyline queries. In Proc. the 28th VLDB, Aug. 2002, pp.275-286.
    [3]
    Chomicki J, Godfrey P, Gryz J, Liang D. Skyline with presorting. In Proc. the 19th ICDE, Mar. 2003, pp.717-719.
    [4]
    Tao Y, Papadias D. Maintaining sliding window skylines on data streams. IEEE Trans. Knowl. Data Eng., 2006, 18(2): 377-391.
    [5]
    Zhang W, Lin X, Zhang Y, Wang W, Yu J X. Probabilistic skyline operator over sliding windows. In Proc. the 25th ICDE, Mar. 29-Apr. 2, 2009, pp.1060-1071.
    [6]
    Tan K L, Eng P K, Ooi B C. Effcient progressive skyline com-putation. In Proc. the 27th VLDB, Sept. 2001, pp.301-310.
    [7]
    Godfrey P, Shipley R, Gryz J. Maximal vector computation in large datasets. In Proc. the 31st VLDB, Aug. 30-Sept. 2, 2005, pp.229-240.
    [8]
    Papadias D, Tao Y, Fu G et al. An optimal and progressive algorithm for skyline queries. In Proc. the 22nd SIGMOD, Jun. 2003, pp.467-478.
    [9]
    Lee K C K, Zheng B, Li H, Lee W C. Approaching the skyline in Z order. In Proc. the 33rd VLDB, Sept. 2007, pp.279-290.
    [10]
    Lee J, Hwang S. BSkyTree: Scalable skyline computation us-ing a balanced pivot selection. In Proc. the 13th EDBT, Mar. 2010, pp.195-206.
    [11]
    Zhang S, Mamoulis N, Cheung D W. Scalable skyline com-putation using object-based space partitioning. In Proc. the 28th SIGMOD, Jun. 29-July 2, 2009, pp.483-494.
    [12]
    Lin X, Zhang Y, Zhang W, Cheema M A. Stochastic skyline operator. In Proc. the 27th ICDE, Apr. 2011, pp.721-732.
    [13]
    Köhler H, Yang J, Zhou X. Effcient parallel skyline processing using hyperplane projections. In Proc. the 30th SIGMOD, Jun. 2011, pp.85-96.
    [14]
    Cho S R, Lee J, Hwang S W. Vskyline: Vectorization for eff-cient skyline computation. In Proc. the 29th SIGMOD, Jun. 2010, pp.19-26.
    [15]
    Kontaki M, Papadopoulos A N, Manolopoulos Y. Continu-ous top-k dominating queries in subspaces. In Proc. the 2008 Panhellenic Conference on Informatics, Aug. 2008, pp.31-35.
    [16]
    Yiu M L, Mamoulis N. Multi-dimensional top-k dominating queries. VLDB J., 2009, 18(3): 695-718.
    [17]
    Lian X, Chen L. Monochromatic and bichromatic reverse sky-line search over uncertain databases. In Proc. the 2008 SIG-MOD, Jun. 2008, pp.213-226.
    [18]
    Zhang W, Lin X, Zhang Y, Pei J, Wang W. Threshold-based probabilistic top-k dominating queries. VLDB J., 2010, 19(2): 283-305.
    [19]
    Lin X, Yuan Y, Wang W, Lu H. Stabbing the sky: Effcient skyline computation over sliding windows. In Proc. the 21st ICDE, Apr. 2005, pp.502-513.
    [20]
    Morse M D, Patel J M, Grosky W I. Effcient continuous sky-line computation. In Proc. the 22nd ICDE, Apr. 2006, p.108.
    [21]
    Pei J, Jin W, Ester M, Tao Y. Catching the best views of skyline: A semantic approach based on decisive subspaces. In Proc. the 31st VLDB, Aug. 30-Sept. 2, 2005, pp.253-264.
    [22]
    Yuan Y, Lin X, Liu Q, Wang W, Yu J X, Zhang Q. Effcient computation of the skyline cube. In Proc. the 31st VLDB, Oct. 2005, pp.241-252.
    [23]
    Tao Y, Xiao X, Pei J. SUBSKY: Effcient computation of skylines in subspaces. In Proc. the 22nd ICDE, Apr. 2006, p.65.
    [24]
    Pei J, Fu A W, Lin X,Wang H. Computing compressed multi-dimensional skyline cubes effciently. In Proc. the 23rd ICDE, Apr. 2007, pp.96-105.
    [25]
    Raïssi C, Pei J, Kister T. Computing closed skycubes. PVLDB, 2010, 3(1): 838-847.
    [26]
    Pei J, Jiang B, Lin X, Yuan Y. Probabilistic skylines on un-certain data. In Proc. the 33rd VLDB, Sept. 2007, pp.15-26.
    [27]
    Atallah M J, Qi Y. Computing all skyline probabilities for un-certain data. In Proc. the 28th PODS, Jun. 29-July 2, 2009, pp.279-287.
    [28]
    Mouratidis K, Bakiras S, Papadias D. Continuous monitor-ing of top-k queries over sliding windows. In Proc. the 2006 SIGMOD, Jun. 2006, pp.635-646.
    [29]
    Kontaki M, Papadopoulos A N, Manolopoulos Y. Continuous top-k dominating queries. IEEE Trans. Knowl. Data Eng., 2012, 24(5): 840-853.
    • Relative Articles

  • Related Articles

    [1]Rui Zhu, Bin Wang, Shi-Ying Luo, Xiao-Chun Yang, Guo-Ren Wang. Approximate Continuous Top-k Query over Sliding Window[J]. Journal of Computer Science and Technology, 2017, 32(1): 93-109. DOI: 10.1007/s11390-017-1708-0
    [2]Wen Liu, Yan-Ming Shen, Peng Wang. An Efficient Approach of Processing Multiple Continuous Queries[J]. Journal of Computer Science and Technology, 2016, 31(6): 1212-1227. DOI: 10.1007/s11390-016-1693-8
    [3]Hai-Da Zhang, Zhi-Hao Xing, Lu Chen, Yun-Jun Gao. Efficient Metric All-k-Nearest-Neighbor Search on Datasets Without Any Index[J]. Journal of Computer Science and Technology, 2016, 31(6): 1194-1211. DOI: 10.1007/s11390-016-1692-9
    [4]Hao Wang, Chao-Kun Wang, Ya-Jun Xu, Yuan-Chi Ning. Dominant Skyline Query Processing over Multiple Time Series[J]. Journal of Computer Science and Technology, 2013, 28(4): 625-635. DOI: 10.1007/s11390-013-1363-z
    [5]Dan Yang, De-Rong Shen, Ge Yu, Yue Kou, Tie-Zheng Nie. Query Intent Disambiguation of Keyword-Based Semantic Entity Search in Dataspaces[J]. Journal of Computer Science and Technology, 2013, 28(2): 382-393. DOI: 10.1007/s11390-013-1338-0
    [6]Ying-Yuan Xiao, Yue-Guo Chen. Efficient Distributed Skyline Queries for Mobile Applications[J]. Journal of Computer Science and Technology, 2010, 25(3): 523-536.
    [7]Jin Huang, Feng Zhao, Jian Chen, Jian Pei, Jian Yin. Towards Progressive and Load Balancing Distributed Computation: A Case Study on Skyline Analysis[J]. Journal of Computer Science and Technology, 2010, 25(3): 431-443.
    [8]Zhen-Hua Huang, Jian-Kui Guo, Sheng-Li Sun, Wei Wang. Efficient Optimization of Multiple Subspace Skyline Queries[J]. Journal of Computer Science and Technology, 2008, 23(1): 103-111.
    [9]Pin Liao, Li Shen, Yi-Qiang Chen, Shu-Chang Liu. Unified Model in Identity Subspace for Face Recognition[J]. Journal of Computer Science and Technology, 2004, 19(5).
    [10]Zhang Zhongyun, Li Guojie. Optimal Partitioning and Granularity of Uniform Task Graphs[J]. Journal of Computer Science and Technology, 1991, 6(2): 185-194.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (15) PDF downloads (1645) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return