›› 2013, Vol. 28 ›› Issue (4): 625-635.doi: 10.1007/s11390-013-1363-z

Special Issue: Data Management and Data Mining

• Special Section of EDB2012 • Previous Articles     Next Articles

Dominant Skyline Query Processing over Multiple Time Series

Hao Wang1,2,3 (汪浩), Chao-Kun Wang2,3,4,* (王朝坤), Member, CCF, ACM, IEEE, Ya-Jun Xu2,3,4 (徐亚军) and Yuan-Chi Ning2,3,4 (宁苑池)   

  1. 1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
    2. Tsinghua National Laboratory for Information Science and Technology, Beijing 100084, China;
    3. Key Laboratory for Information System Security, Ministry of Education, Beijing 100084, China;
    4. School of Software, Tsinghua University, Beijing 100084, China
  • Received:2012-09-20 Revised:2013-04-29 Online:2013-07-05 Published:2013-07-05
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant No. 61170064, the National High Technology Research and Development 863 Program of China under Grant No. 2013AA013204, and the Tsinghua National Laboratory for Information Science and Technology (TNLIST) Cross-Discipline Foundation.

Multiple time series (MTS), which describes an object in multi-dimensions, is based on single time series and has been proved to be useful. In this paper, a new analytical method called α/β-Dominant-Skyline on MTS and a formal definition of the α/β-dominant skyline MTS are given. Also, three algorithms, called NL, BC and MFB, are proposed to address the α/β-dominant skyline queries over MTS. Finally experimental results on both synthetic and real data verify the correctness and effectiveness of the proposed method and algorithms.

[1] Pei J, Jiang B, Lin X, Yuan Y. Probabilistic skylines on un-certain data. In Proc. the 33rd International Conference onVery Large Data Bases, Sept. 2007, pp.15-26.

[2] Zhai C, Xie L. A new approach of selecting real input groundmotions for seismic design: The most unfavourable real seis-mic design ground motions. Earthquake Engineering & Struc-tural Dynamics, 2007, 36(8): 1009-1027.

[3] Borzsonyi S, Kossmann D, Stocker K. The skyline operator.In Proc. the 17th International Conference on Data Engi-neering, Apr. 2001, pp.421-430.

[4] Wang H, Wang C, Xu Y, Ning Y. Dominant skyline queryprocessing over multiple time series. In Proc. the 4th Inter-national Conference on Emerging Databases —— Technologies,Applications, and Theory, Aug. 2012.

[5] Prado R, Molina F, Huerta G. Multivariate time series model-ing and classification via hierarchical VAR mixtures. Journalof the Computational Statistics & Data Analysis, 2006, 51(3):1445-1462.

[6] Keogh E. A fast and robust method for pattern matching in time series databases. In Proc. the 9th International Confer-ence on Tools with Artificial Intelligence, Nov. 1997, pp.578-584.

[7] Bloomfield P. Fourier Analysis of Time Series: An Introduc-tion (2nd edition). Wiley-Interscience, 2000.

[8] Kung H T, Luccio F, Preparata F P. On finding the maximaof a set of vectors. Journal of the ACM, 1975, 22(4): 469-476.

[9] Buchta C. On the average number of maxima in a set of vec-tors. Information Processing Letters, 1989, 33(2): 63-65.

[10] Papadias D, Tao Y, Fu G, Seeger B. An optimal and progres-sive algorithm for skyline queries. In Proc. the 22nd ACMSIGMOD International Conference on Management of Data,Jun. 2003, pp.467-478.

[11] Papadias D, Tao Y, Fu G, Seeger B. Progressive skylinecomputation in database systems. ACM Transactions onDatabase Systems, 2005, 30(1): 41-82.

[12] Tan K L, Eng P K, Ooi C B. Efficient progressive skylinecomputation. In Proc. the 27th International Conference onVery Large Data Bases, Sept. 2001, pp.301-310.

[13] Kossmann D, Ramsak F, Rost S. Shooting stars in the sky:An online algorithm for skyline queries. In Proc. the 28thInternational Conference on Very Large Data Bases, Aug.2002, pp.275-286.

[14] Fagin R, Lotem A, Naor M. Optimal aggregation algorithmsfor middleware. In Proc. the 12th ACM SIGMOD SIGACT-SIGAET Symp. Principles of Database Systems, May 2001,pp.102-113.

[15] Jiang B, Pei J. Online interval skyline queries on time series.In Proc. the 25th International Conference on Data Engi-neering, Mar. 2009, pp.1036-1047.

[16] Vlachou A, Vazirgiannis M. Ranking the sky: Discovering theimportance of skyline points through subspace dominance re-lationships. Journal of Data & Knowledge Engineering, 2010,69(9): 943-964.

[17] Chomicki J, Godfrey P, Gryz J, Liang D. Skyline with pre-sorting. In Proc. the 19th International Conference on DataEngineering, Mar. 2003, pp.717-719.
No related articles found!
Full text



[1] Zhang Fuyan; Cai Shijie; Wang Shu; Ge Ruding;. The Human-Computer Dialogue Management of FCAD System[J]. , 1988, 3(3): 221 -227 .
[2] Zhu Mingyuan;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[3] Wang Hui; Liu Dayou; Wang Yafei;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[4] Cao Cungen;. Expansion Nets and Expansion Processes of Elementary Net Systems[J]. , 1995, 10(4): 325 -333 .
[5] Gao Qingshi; Liu Zhiyong;. K-Dimensional Optimal Parallel Algorithm for the Solution of a General Class of Recurrence Equations[J]. , 1995, 10(5): 417 -424 .
[6] Peng Chenglian;. Combining Gprof and Event-Driven Monitoring for Analyzing Distributed Programs:A Rough View of NCSA Mosaic[J]. , 1996, 11(4): 427 -432 .
[7] Zhang Chenghong; Hu Yunfa; Shi Baile;. A Reasoning Mechanism for DeductiveObject-Oriented Databases[J]. , 1997, 12(4): 337 -345 .
[8] Wen-Cheng Wang, Feng Wei, and En-Hua Wu. View Dependent Sequential Point Trees[J]. , 2006, 21(2): 181 -188 .
[9] Xian-Yong Fang, Ming-Min Zhang, Zhi-Geng Pan, and Peng Wang. A New Method of Manifold Mosaic for Large Displacement Images[J]. , 2006, 21(2): 218 -223 .
[10] Zhi-Wei Xu, Hao-Jie Zhou, and Guo-Jie Li. Usability Issues of Grid System Software[J]. , 2006, 21(5): 641 -647 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved