多时间序列k′/k-支配Skyline查询处理

k'/k-Dominant Skyline Query over Multiple Time Series

时间序列是各个领域中大量存在的一类数据,有着极广泛的应用.多时间序列是其中常见的一种数据类型,它从多个角度以单时间序列的形式去描述同一个对象.目前关于时间序列的研究主要集中于单时间序列,而多时间序列的研究工作则相对较少,如多时间序列的查询处理等,但是在实际生活中多时间序列的查询却有着非常广泛的应用.首先定义了多时间序列的支配关系,然后在此基础上给出多时间序列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 muItiple 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.