多时间序列k′/k-支配Skyline查询处理
摘要
时间序列是各个领域中大量存在的一类数据,有着极广泛的应用.多时间序列是其中常见的一种数据类型,它从多个角度以单时间序列的形式去描述同一个对象.目前关于时间序列的研究主要集中于单时间序列,而多时间序列的研究工作则相对较少,如多时间序列的查询处理等,但是在实际生活中多时间序列的查询却有着非常广泛的应用.首先定义了多时间序列的支配关系,然后在此基础上给出多时间序列k′/k-支配Skyline查询的定义,并提出了GMS和GMI两种查询算法,对算法的正确性和复杂性也进行了证明和分析.合成数据和真实数据上的大量实验表明,两种算法都可以得到较好的查询结果,而GMI算法的查询效率较GMS算法有很大程度地提升.
Time series have been widely used in many fields of nature and society.And they can be divided into single time series and multiple time series.Multiple time series,consisting of interrelated single time series,can describe an object by many aspects.Therefore,multiple time series are more complex than single time series.At present the research of time series mainly focuses on single time series,and the research of multiple time series is relatively little,such as the query over multiple time series.However,multiple time series are very useful in our life.In addition,most of researches of single time series cannot be used in or extended to multiple time series directly,which makes the study of multiple time series necessary.In this paper we give the definition of the dominant relation between multiple time series,and then propose the k'/k-dominant skyline query over multiple time series.We also present the proof of correctness of algorithms in this paper.Finally a set of experiments are conducted on both synthetic and real data to verify the proposed algorithms.The experiment results prove that both of these two algorithms are effective,and GMI algorithm is much more efficient than GMS.
Time series have been widely used in many fields of nature and society.And they can be divided into single time series and multiple time series.Multiple time series,consisting of interrelated single time series,can describe an object by many aspects.Therefore,multiple time series are more complex than single time series.At present the research of time series mainly focuses on single time series,and the research of multiple time series is relatively little,such as the query over multiple time series.However,multiple time series are very useful in our life.In addition,most of researches of single time series cannot be used in or extended to multiple time series directly,which makes the study of multiple time series necessary.In this paper we give the definition of the dominant relation between multiple time series,and then propose the k'/k-dominant skyline query over multiple time series.We also present the proof of correctness of algorithms in this paper.Finally a set of experiments are conducted on both synthetic and real data to verify the proposed algorithms.The experiment results prove that both of these two algorithms are effective,and GMI algorithm is much more efficient than GMS.
引文
[1]Zhao Zhe,Cui Bin,Tok W H,et al.Efcient similarity matching of time series cliques with natural relations[C]//Proc of Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2010:908-911
[2]Jiang Bin,Pei Jian.Online interval skyline queries on time series[C]//Proc of Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2009:1036-1047
[3]Zhai Changhai,Xie Lili.The severest design ground motions for seismic design and analysis of structures[J].China Civil Engineering Journal,2005,38(12):51-58(in Chinese)(翟长海,谢礼立.抗震结构最不利设计地震动研究[J].土木工程学报,2005,38(12):51-58)
[4]Keogh E.A fast and robust method for pattern matching in time series databases[C]//Proc of the9th In Conf on Tools with Artificial intelligence.Los Alamitos,CA:IEEE Computer Society,1997:578-584
[5]Raquel P,Francisco M,Gabriel H.Multivariate time series modeling and classification via hierarchical VAR mixtures[J].Computational Statistics&Data Analysis,2006,51(3):1445-1462
[6]Brzsnyi S,Kossmann D,Stocker K.The skyline operator[C]//Proc of Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2001:421-430
[7]Papadias D,Tao Y,Fu G,et al.Progressive skyline computation in database systems[J].ACM Trans on Database Systems,2005,30(1):41-82
[8]Yuan Y,Lin X,Liu Q,et al.Efcient computation of the skyline cube[C]//Proc of Very Large Data Bases.New York:ACM,2005:241-252
[9]Chan C Y,Jagadish H V,Tan K L,et al.Finding k-dominant skylines in high dimensional space[C]//Proc of Int Conf on Management of Data.New York:ACM,2006:503-514
[10]X Lin,Y Yuan,Q Zhang,et al.Selecting stars:The k most representative skyline operator[C]//Proc of Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2007:86-95
[11]Wei Xiaojuan,Yang Jing,Li Cuiping,et al.Skyline query processing[J].Journal of Software,2008,19(6):1386-1400(in Chinese)(魏小娟,杨婧,李翠平,等.Skyline查询处理[J].软件学报,2008,19(6):1386-1400)
[12]Vlachou A,Vazirgiannis M.Ranking the sky:Discovering the importance of skyline points through subspace dominance relationships[J].Data&Knowledge Engineering,2010,69(9):943-964
[13]Yin Jian,Yao Shuyu,Xue Shao'e,et al.An index based efficient k-dominant skyline algorithm[J].Chinese Journal of Computers,2010,33(7):1236-1245(in Chinese)(印鉴,姚树宇,薛少锷,等.一种基于索引的高效k-支配Skyline算法[J].计算机学报,2010,33(7):1236-1245)
[14]Xu Yajun,Wang Chaokun,Wei Dongmei,et al.An earthquake ground motion database system with automaticrecord selection methods[J].Journal of Computer Research and Development,2011,48(SupplⅡ):435-440(in Chines)(徐亚军,王朝坤,魏冬梅,等.一种支持自动化选波的地震波数据库系统[J].计算机研究与发展,2011,48(增刊Ⅱ):435-440)
[15]Sacharidis D,Papadopoulos S,Papadias D.Topologically sorted skylines for partially ordered domains[C]//Proc of Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2009:1072-1083
[2]Jiang Bin,Pei Jian.Online interval skyline queries on time series[C]//Proc of Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2009:1036-1047
[3]Zhai Changhai,Xie Lili.The severest design ground motions for seismic design and analysis of structures[J].China Civil Engineering Journal,2005,38(12):51-58(in Chinese)(翟长海,谢礼立.抗震结构最不利设计地震动研究[J].土木工程学报,2005,38(12):51-58)
[4]Keogh E.A fast and robust method for pattern matching in time series databases[C]//Proc of the9th In Conf on Tools with Artificial intelligence.Los Alamitos,CA:IEEE Computer Society,1997:578-584
[5]Raquel P,Francisco M,Gabriel H.Multivariate time series modeling and classification via hierarchical VAR mixtures[J].Computational Statistics&Data Analysis,2006,51(3):1445-1462
[6]Brzsnyi S,Kossmann D,Stocker K.The skyline operator[C]//Proc of Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2001:421-430
[7]Papadias D,Tao Y,Fu G,et al.Progressive skyline computation in database systems[J].ACM Trans on Database Systems,2005,30(1):41-82
[8]Yuan Y,Lin X,Liu Q,et al.Efcient computation of the skyline cube[C]//Proc of Very Large Data Bases.New York:ACM,2005:241-252
[9]Chan C Y,Jagadish H V,Tan K L,et al.Finding k-dominant skylines in high dimensional space[C]//Proc of Int Conf on Management of Data.New York:ACM,2006:503-514
[10]X Lin,Y Yuan,Q Zhang,et al.Selecting stars:The k most representative skyline operator[C]//Proc of Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2007:86-95
[11]Wei Xiaojuan,Yang Jing,Li Cuiping,et al.Skyline query processing[J].Journal of Software,2008,19(6):1386-1400(in Chinese)(魏小娟,杨婧,李翠平,等.Skyline查询处理[J].软件学报,2008,19(6):1386-1400)
[12]Vlachou A,Vazirgiannis M.Ranking the sky:Discovering the importance of skyline points through subspace dominance relationships[J].Data&Knowledge Engineering,2010,69(9):943-964
[13]Yin Jian,Yao Shuyu,Xue Shao'e,et al.An index based efficient k-dominant skyline algorithm[J].Chinese Journal of Computers,2010,33(7):1236-1245(in Chinese)(印鉴,姚树宇,薛少锷,等.一种基于索引的高效k-支配Skyline算法[J].计算机学报,2010,33(7):1236-1245)
[14]Xu Yajun,Wang Chaokun,Wei Dongmei,et al.An earthquake ground motion database system with automaticrecord selection methods[J].Journal of Computer Research and Development,2011,48(SupplⅡ):435-440(in Chines)(徐亚军,王朝坤,魏冬梅,等.一种支持自动化选波的地震波数据库系统[J].计算机研究与发展,2011,48(增刊Ⅱ):435-440)
[15]Sacharidis D,Papadopoulos S,Papadias D.Topologically sorted skylines for partially ordered domains[C]//Proc of Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2009:1072-1083
版权所有：© 2023 中国地质图书馆 中国地质调查局地学文献中心