Skyline index for time series data

被引:21
作者
Li, QZ [1 ]
López, IFV
Moon, B
机构
[1] Univ Arizona, Dept Comp Sci, Tucson, AZ 85721 USA
[2] Univ Autonoma Sinaloa, Escuela Informat, Culiacan, Sinaloa, Mexico
基金
美国国家科学基金会;
关键词
data approximation; dimensionality reduction; similarity search; skyline bounding region; skyline index; time series data;
D O I
10.1109/TKDE.2004.14
中图分类号
TP18 [人工智能理论];
学科分类号
081104 [模式识别与智能系统]; 0812 [计算机科学与技术]; 0835 [软件工程]; 1405 [智能科学与技术];
摘要
We have developed a new indexing strategy that helps overcome the curse of dimensionality for time series data. Our proposed approach, called Skyline Index, adopts new Skyline Bounding Regions (SBR) to approximate and represent a group of time series data according to their collective shape. Skyline bounding regions allow us to define a distance function that tightly lower bounds the distance between a query and a group of time series data. In an extensive performance study, we investigate the impact of different distance functions by various dimensionality reduction and indexing techniques on the performance of similarity search, including index pages accessed, data objects fetched, and overall query processing time. In addition, we show that, for kappa-nearest neighbor queries, the proposed Skyline index approach can be coupled with the state of the art dimensionality reduction techniques such as Adaptive Piecewise Constant Approximation ( APCA) and improve its performance by up to a factor of 3.
引用
收藏
页码:669 / 684
页数:16
相关论文
共 37 条
[1]
Agrawal R., 1995, VLDB '95. Proceedings of the 21st International Conference on Very Large Data Bases, P490
[2]
Agrawal R., 1993, P 4 INT C FDN DAT OR, V730, P69
[3]
[Anonymous], P 1998 ACM SIGMOD IN
[4]
[Anonymous], 1995, P 21 INT C VER LARG
[5]
[Anonymous], P 9 INT C INF KNOWL
[6]
[Anonymous], P INT C FDN DAT ORG
[7]
[Anonymous], 2001, P ACM SIGMOD C MAN D
[8]
[Anonymous], P ACM SIG MOD INT C
[9]
BECKMANN N, 1990, SIGMOD REC, V19, P322, DOI 10.1145/93605.98741
[10]
Berndt D. N. A. I. N. J., 1994, AAA1-94 Workshop on Knowledge Discovery in Databases, V10, P359