Evolutionary Rule Mining in Time Series Databases

Data mining in the form of rule discovery is a growing field of investigation. A recent addition to this field is the use of evolutionary algorithms in the mining process. While this has been used extensively in the traditional mining of relational databases, it has hardly, if at all, been used in mining sequences and time series. In this paper we describe our method for evolutionary sequence mining, using a specialized piece of hardware for rule evaluation, and show how the method can be applied to several different mining tasks, such as supervised sequence prediction, unsupervised mining of interesting rules, discovering connections between separate time series, and investigating tradeoffs between contradictory objectives by using multiobjective evolution.     

大规模时间序列数据库降维及相似搜索

提出一种基于分段多项式表示（PPR）的时间序列数据库相似查询的系统化方法．PPR是一类基于线性多项式回归的正交变换．用PPR变换索引时间序列数据在理论上具备非漏报性质．文中分析了PPR的计算复杂性以及查询阈值的下界,并提出了一种衡量时间序列相似查询算法之查询效率的定量指标．与基于离散傅立叶变换（DFT）和离散小波变换（DWT）的时间序列相似查询算法所作的对比实验表明,所提算法可以用低的索引结构维数获得高的查询效率．     

Triggered Updates for Temporal Consistency in Real-Time Databases

A real-time database systemhas temporal consistency constraints in addition to timing constraints.The timing constraints require a transaction to be completedby a specified deadline, and the temporal consistency constraintsrequire that temporal data read by a transaction be up-to-date.If a transaction reads out-of-date data, it will become temporallyinconsistent. A real-time database system consists of differenttypes of temporal data objects, including derived objects. Thevalue of a derived object is computed from a set of other objects,known as the read-set of the derived object. The derived objectmay not always reflect the current state of its read-set; a derivedobject can become out-of-date even if its read-set is up-to-date.Any subsequent transaction reading the derived object will thenbecome temporally inconsistent. In this case, in order to readup-to-date objects, a transaction will have to wait until someother transaction updates the out-of-date object. However, indoing so, the waiting transaction may miss its deadline, particularlyif the update is not periodic but instead arrives randomly. Wepropose to update the outdated objects so that not only is thetemporal consistency improved, but also the number of misseddeadlines does not increase significantly, and as a result thereis an overall improvement in the performance of the system. Wepropose, implement and study a novel approach, to be known astriggered updates, to improve temporal consistency in firm real-timedatabase systems when updates are not periodic. We identify propertiesof triggered updates and explain how they work by giving bothan intuitive and a probabilistic analysis. We present strategiesfor generating triggered updates, discuss their suitability invarious contexts and perform a detailed simulation study to evaluatetheir performance. Results show that it is possible to improvetemporal consistency without degrading the timeliness of real-time database systems to a great deal.     

多时间粒度下时态数据库设计中时态类型的处理

在许多大型信息系统中需要存储大量的历史数据．为了有效地组织这些时间变化数据，可以使用时态函数依赖（TFDs）对时态数据库进行有效地设计．由于多时间粒度的使用，数据库设计算法需要在计算机上实现表示时态类型间的关系的逻辑结构和时态类型间的相关操作．为此提出了细于关系矩阵和封闭的时态类型集，并且对于给定的时态类型集及其细于关系矩阵，给出了一个自动生成它的一个封闭集及封闭集对应的细于关系矩阵的有效算法，通过提出的细于关系矩阵和封闭集算法，可以方便地在计算机上实现时态数据库设计算法需要的时态类型间的细于关系比较和glb操作。     

Compositional Verification of Multi-Agent Systems in Temporal Multi-Epistemic Logic

Compositional verification aims at managing the complexity of theverification process by exploiting compositionality of the systemarchitecture. In this paper we explore the use of a temporal epistemiclogic to formalize the process of verification of compositionalmulti-agent systems. The specification of a system, its properties andtheir proofs are of a compositional nature, and are formalized within acompositional temporal logic: Temporal Multi-Epistemic Logic. It isshown that compositional proofs are valid under certain conditions.Moreover, the possibility of incorporating default persistence ofinformation in a system, is explored. A completion operation on aspecific type of temporal theories, temporal completion, is introducedto be able to use classical proof techniques in verification withrespect to non-classical semantics covering default persistence.     

基于时间约束Petri网的工作流动态一致性检验

工作流系统中的时间管理是工作流建模和分析的重要组成部分。支持动态修改是人们在实际应用中对工作流系统提出的新要求。文中在基于时间约束的Petri网模型基础上,根据时间约束推理规则,提出一种动态修改时间约束时检验工作流一致性的方法,从而丰富了工作流的时间管理功能。     

Clustering Time Series with Clipped Data

Clustering time series is a problem that has applications in a wide variety of fields, and has recently attracted a large amount of research. Time series data are often large and may contain outliers. We show that the simple procedure of clipping the time series (discretising to above or below the median) reduces memory requirements and significantly speeds up clustering without decreasing clustering accuracy. We also demonstrate that clipping increases clustering accuracy when there are outliers in the data, thus serving as a means of outlier detection and a method of identifying model misspecification. We consider simulated data from polynomial, autoregressive moving average and hidden Markov models and show that the estimated parameters of the clipped data used in clustering tend, asymptotically, to those of the unclipped data. We also demonstrate experimentally that, if the series are long enough, the accuracy on clipped data is not significantly less than the accuracy on unclipped data, and if the series contain outliers then clipping results in significantly better clusterings. We then illustrate how using clipped series can be of practical benefit in detecting model misspecification and outliers on two real world data sets: an electricity generation bid data set and an ECG data set.     

Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases

The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial problem because of the inherent high dimensionality of the data. The most promising solutions involve first performing dimensionality reduction on the data, and then indexing the reduced data with a spatial access method. Three major dimensionality reduction techniques have been proposed: Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise Aggregate Approximation (PAA). We theoretically and empirically compare it to the other techniques and demonstrate its superiority. In addition to being competitive with or faster than the other methods, our approach has numerous other advantages. It is simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and the index can be built in linear time. Received 16 May 2000 / Revised 18 December 2000 / Accepted in revised form 2 January 2001     

基于重要点的时间序列固定分段数分段算法

基于重要点探测技术的时间序列线性分段算法能较好地保留序列的全局特征和拟合高精确度。传统的基于重要点时间序列分段算法,只能通过误差阈值来控制分段,该方法不能预计分段数量,不能适应后期要求分段数量一定的应用。提出一种基于序列重要点的时间序列固定分段数的分段算法—PLR_FPIP,该方法借用二叉树层次遍历的思路,重新调整原方法的分段次序,使用重要点组成的直线段近似描述时间序列,该方法能够在分段数量一定的情况下对时间序列分段。实验证明,该分段算法能在固定分段数的情况下反映时间序列的主体特征,算法简单快速,整体拟合误差小。     

基于分段时间弯曲距离的时间序列挖掘

在时间序列库中的数据挖掘是个重要的课题,为了在挖掘的过程中比较序列的相似性,大量的研究都采用了欧氏距离度量或者其变形,但是欧氏距离及其变形对序列在时间轴上的偏移非常敏感．因此,采用了更鲁棒的动态时间弯曲距离,允许序列在时间轴上的弯曲,并且提出了一种新的序列分段方法,在此基础上定义了特征点分段时间弯曲距离．与经典时间弯曲距离相比,大大提高了效率,而且保证了近似的准确性．     

First-Order Temporal Verification in Practice

First-order temporal logic, the extension of first-order logic with operators dealing with time, is a powerful and expressive formalism with many potential applications. This expressive logic can be viewed as a framework in which to investigate problems specified in other logics. The monodic fragment of first-order temporal logic is a useful fragment that possesses good computational properties such as completeness and sometimes even decidability. Temporal logics of knowledge are useful for dealing with situations where the knowledge of agents in a system is involved. In this paper we present a translation from temporal logics of knowledge into the monodic fragment of first-order temporal logic. We can then use a theorem prover for monodic first-order temporal logic to prove properties of the translated formulas. This allows problems specified in temporal logics of knowledge to be verified automatically without needing a specialized theorem prover for temporal logics of knowledge. We present the translation, its correctness, and examples of its use. Partially supported by EPSRC project: Analysis and Mechanisation of Decidable First-Order Temporal Logics (GR/R45376/01).     

On Stubborn Sets in the Verification of Linear Time Temporal Properties

The stubborn set method is one of the methods that try to relieve the state space explosion problem that occurs in state space generation. This article is concentrated on the verification of next-time-less LTL (linear time temporal logic) formulas with the aid of the stubborn set method. The essential contribution is a theorem that gives us a way to utilize the structure of the checked formula when the stubborn set method is used and there is no fairness assumption. The theorem also applies to verification under fairness assumptions, including those which allow a predefined subset of actions to be treated unfairly.This work has been funded by the National Technology Agency of Finland, the Academy of Finland, Helsinki Graduate School in Computer Science and Engineering, Nokia Research Center, Nokia Networks, Elisa Communications, and Finnish Rail Administration.     

时态查询语言对处理不明确时间间隔的扩展

关于时态数据库的先前工作，主要是建立在时态属性的时间间隔和事件的开始／终止点都十分清楚的基础上，然而，在许多实际情况中，事件的时间界限并不十分清楚。因此，表示不明确时间，并给出处理不明确时间查询的方法，是对时态数据库中目前仍缺少的一个有效的扩展。讨论了时态数据库处理不明确时间存在的一些问题，并描述不明确时间隔的方法，之后扩展了各种时态运算，并给出了与不明确时间相关的新运算符。也提出了能够处理不明确时间的查询语言扩展。在此讨论的时是询语言对处理不明确时间间隔的扩展和丰富时态数据库的适应性有一定作用。     

Formal Semantics for Composite Temporal Events in Active Database Rules

A major thrust of current research in active databases focuses on allowing complex patterns of temporal events to serve as preconditions for rule triggering. Currently, there is no common formalism for specifying the semantics of composite event languages. Different systems have used an assortment of different techniques, including Finite State Automata, Petri Nets and Event Graphs. In this paper, we propose a unifying approach, based on a syntax-directed translation of composite event expressions into Datalog _1S rules, whose formal semantics defines the meaning of the original expressions. We demonstrate our method by providing a formal specification of the Event Pattern Language (EPL) developed at UCLA. This method overcomes problems and limitations affecting previous approaches and is applicable to other languages such as ODE, SNOOP and SAMOS—thus, allowing a more direct comparison across different systems.     

基于置换乱序的混沌加密算法

本文分析国内外部分研究成果的新进展 ,指出混沌序列在实际加密应用过程中存在的一个本质缺陷。由于混沌序列具有类随机性、对初始条件敏感性、序列相关性、复杂性和较宽的频谱等优良的密码学性能 ,作者针对这一现代密码学重要的研究方向。提出一个可实施的加密改进方案 ,该方案可有效提高混沌加密算法的抗破译性。     

时间序列相似模式的分层匹配

首先将时间序列经EMD分解成细节部分和趋势部分,对低频趋势部分的序列数据进行线性分段近似表示,完成对序列数据的压缩,并将其变换成一种0-1串的形式,以适应趋势序列的快速匹配;然后通过对趋势序列模式聚类,达到对序列的粗匹配;最后对粗匹配的序列进行距离计算,从而获取细匹配的模式．实验结果表明该算法是有效的．     

基于变化点的时间序列近似表示

时间序列的近似表示能够提高时间序列数据挖掘的效率和可靠性。提出了一种基于变化点的时间序列近似表示,具有简单直观、近似质量高、适应能力强等优点。在来自不同领域的真实数据集上的实验表明:与时间序列的重要点分段表示和分段常量表示相比,基于变化点的时间序列近似表示在近似质量和适应能力上都具有明显的优势。     

一种周期时间序列的预测算法

时间序列分析作为现代数据分析处理的有效方法之一,目前广泛地应用于商业、金融、证券、电信等领域,由于人们生活及消费模式的自然规律性,时间序列往往呈现出明显的周期变化趋势。论文依据移动通信网管测量数据,提出了一种针对周期时间序列的线性预测算法——自循环算法,实验表明预测精度高于传统的线性预测分析方法。