基于时间窗口聚类的时序数据索引压缩

子序列匹配是时间序列挖掘的经典课题,旨在发现大型数据集中的相似数据序列.很多文献关注固定时间段的序列的查询.但对于多种不同时间段的查询的问题仍然未解决好.基于时间段的查询含义是有时间窗口限制的查询.为了满足多时间段上的查询,简单地为每个时间段的子序列构建索引既耗时又耗存储空间.从目前的文献来看,已有的索引无法满足具有不...     

IC-索引：一种支持时间序列反向查询的索引方法

为解决时间序列的反向查询问题，提出了一种新的时间序列动态索引方法——IC-索引。采用单调链表示时间序列的状态变化，利用AVL树对时间序列的变化区间进行索引。实验结果表明，算法的运行时间比现有的IP-索引减少了50％。     

基于线性散列索引的时间序列查询方法研究

随着信息化的发展,大量的数据被产生。在新产生的数据中,时间序列数据是一种重要的数据类型,而对该类数据进行高效的查询处理成为了当前研究的热点。本文针对线性散列的索引机制,提出了一种新型的时间序列的查询处理方法,以降低索引创建时间和提高查询效率。实验证明,本方法中的线性散列索引,在创建时的时间耗费有所下降。在查询阶段采用K近邻与下界距离相结合的方法,能有效地过滤掉多余的结果,提高了时间序列查询处理的效率和精确度。     

基于滑动窗口的数据流反向查询方法

提出了一种基于滑动窗口的数据流动态索引方法——DS-索引,采用滑动窗口保存数据流的最新数据,利用AVL树对数据流的变化区间进行索引,有效地解决了数据流的反向查询问题。     

IP*-索引在时间序列反向查询中的应用

针对时间序列中的反向查询，提出了一种新的索引方法——IP*-索引，并介绍了IP*-索引的实现过程，最后介绍了IP*-索引在具体实距中的应用。     

基于F&B索引的XML查询处理算法

XML已成为信息交换和表示的标准.对XML数据的查询将返回满足特定约束的XML节点子集.对于大文件的XML数据的查询处理通常分为两步:1.为该XML数据建立一个索引;2.在索引上完成查询处理无需访问源文档.XML索引为查询处理提供了高效的帮助,其中F&B索引是已知的处理分枝查询最小的索引,但快速创建F&B索引和利用F&B索引完成查询处理的算法却很少有人研究.提出了一种素数序列标记法,这种标记法不仅有助于快速地建立F&B索引,更可以高效地完成F&B索引上的查询处理.此外,还给出了F&B索引上的区间标记法与CCPI的创建过程,这两种编码创建过程无需在建立F&B索引后二次创建,仅需与F&B索引创建过程一起对文档使用SAX解析器分析一次即可得到.这样,可以在F&B索引的区间标记法上使用TwigStack算法执行查询处理,在F&B索引的CCPI标记法上使用关联路径连接算法执行查询处理.还给出了基于素数序列标记法的查询处理算法,即素数整除匹配算法,该算法可以高效地判定某节点是否有某分枝子结构.实验表明基于素数序列标记法的F&B索引创建方法比SAM算法快,在多个数据集F&B索引上素数整除匹配算法优于关联路径连接算法和Twi...     

CMRS:聚类的多解析度字符串索引结构

随着基因测序技术和人类基因组计划的发展，从大量的生物数据中寻找相似的序列就越来越成为当前研究的热点问题．本文提出了一种聚类的多解析度字符串索引结构，用于解决生物序列的相似性查询问题．首先，以较小容量的MBR（最小绑定矩形）构造基因序列的多解析度字符串索引结构，然后通过对MBR的聚类以夏保序技术的应用，减小索引中MBR的平均体积，从而增加了查询向量到索引的空间距离，提高了索引的过滤能力．还给出了一种新的后处理方法，通过大量的减少编辑距离的计算，提高索引的性能．文中给出了该索引结构并详细介绍了索引的相关算法．实验表明，该索引结构是一种有效的处理生物数据的相似性查询的索引结构．     

一种快速的子序列匹配算法

提出一种在时间序列上快速匹配子序列的算法,该算法不同于FRM算法,而是采用VA-file这种索引结构,将数据点直接存储在索引上,并在该索引的基础上设计了一种进行范围查询的方法.实验采用了三种时间序列数据集,从不同的角度验证算法的有效性,结果表明该算法大大提高了查询性能.     

BioIndex：一种生物序列相似性查询的高效索引

有效管理生物数据并提供高效的查询方法是生物信息处理的重要研究内容.BioSeg是一个新的生物序列数据模型.查询优化研究是生物数据库管理系统开发的重要内容之一.研究当前生物数据索引技术,针对BioSeg数据模型的特点和生物序列相似性查询需求设计了一种新的生物序列数据索引BioIndex,并设计相应的查询算法.首先,使用MEME(Multiple EM for Moeif Elicitation)算法挖掘生物序列集中的序列模式作为索引建立索引序列库;之后,在索引序列库中查找与查询序列最相似的索引序列,将其对应的序列集作为候选集;再在候选集中查找与查询序列最相似的序列.在真实生物序列数据集上的实验表明使用新的生物序列数据索引BioIndex的序列查询算法提高了序列查询的效率.     

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

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

Decomposing a window into maximal quadtree blocks

Window operations serve as the basis of a number of queries that can be posed in a spatial database. Examples of window-based queries include the exist query (i.e., determining whether or not a spatial feature exists inside a window), the report query (i.e., report the identity of all the features that exist inside a window), and the select query (i.e., determine the locations covered by a given feature inside a window). Often spatial databases make use of a quadtree decomposition, which yields a set of maximal blocks, to enable the features to be accessed quickly without having to search the entire database. One way to perform a window query is to decompose the window into its maximal quadtree blocks. An algorithm is described for decomposing a two-dimensional window into its maximal quadtree blocks inO(nlog logT) time for a window of sizen×n in a feature space (e.g., an image) of sizeT×T (e.g., pixel elements).The support of the National Science Foundation under Grant IRI-9017393 is gratefully acknowledged.     

基于小波变换的时间序列相似模式匹配

提出了一种新的时序相似模式匹配方法，它采用小波分析的方法实现时间序列数据的降维，采用小波序列表示原序列，将小波序列组织为多维索引结构R-tree存储，在该索引结构基础上，基于一种表示相似性的距离函数，定义了范围查询和最近邻查询算法，实验结果证明这种方法性能优于传统的基于傅立叶变换的相似模式匹配方法。     

搜索引擎用户访问量模型

基于大规模分布式WWW搜索引擎系统---北大“天网”的用户日志,该文研究了搜索引擎用户访问量建模分析和预测的一般方法;将用户的访问量看成按时间次序排列的随机变量序列,利用时间序列分析的方法,分别建立了天网用户的查询量、点击量和不同IP用户访问量的潜周期模型;结果显示模型对实际数据拟合效果较好;用户访问的主周期为24小时,其它周期依次为12小时、6小时、8小时、5小时、168小时(即一周);用户的异常访问情况可通过小波技术检测。     

RLC: ranking lag correlations with flexible sliding windows in data streams

Lag correlation between two time series is the correlation shifted in time relative to one another. Existing work focuses on two computation models, landmark (where the lag correlation is computed over the entire stream) and sliding window (where the lag correlation is computed over the current window). However, these models may suffer from problems like result freshness (e.g., perished items in the landmark model) and parametric tuning (e.g., setting a proper length in the sliding window model). In this work, we attempt to analyze the lag correlation which is computed based on flexible sliding windows. In view of that, a new query called RLC (ranking lag correlations with flexible sliding windows in data streams) is proposed. The key challenge in answering the RLC query is that the number of windows to be analyzed will grow quadratically with the length of the stream, resulting a quadratic computation cost. To boost the computation, we employ the running sum and the geometric probing techniques to facilitate the query processing. We also present an approximate solution that further reduces the computation cost with an acceptable error rate in practice. The extensive experiments verify the efficiency of our proposed methods. We also demonstrate some lag correlations discovered from real datasets to show the practicality of this work.     

Logic-based query optimization for object databases

We present a technique for transferring query optimization techniques, developed for relational databases, into object databases. We demonstrate this technique for ODMG database schemas defined in ODL and object queries expressed in OQL. The object schema is represented using a logical representation (Datalog). Semantic knowledge about the object data model, e.g., class hierarchy information, relationship between objects, etc., as well as semantic knowledge about a particular schema and application domain are expressed as integrity constraints. An OQL object query is represented as a logic query and query optimization is performed in the Datalog representation. We obtain equivalent (optimized) logic queries, and subsequently obtain equivalent (optimized) OQL queries for each equivalent logic query. We present one optimization technique for semantic query optimization (SQO) based on the residue technique of U. Charavarthy et al. (1990; 1986; 1988). We show that our technique generalizes previous research on SQO for object databases. We handle a large class of OQL queries, including queries with constructors and methods. We demonstrate how SQO can be used to eliminate queries which contain contradictions and simplify queries, e.g., by eliminating joins, or by reducing the access scope for evaluating a query to some specific subclass(es). We also demonstrate how the definition of a method or integrity constraints describing the method, can be used in optimizing a query with a method     

一种基于分形时变维数的非平稳时间序列相似性匹配方法

随机非平稳时间序列在时空动力学演化过程中呈现出非线性特征和分形特征,传统相似性查询的维数约简方法导致时间序列的非线性和分形这些重要特征消失,序列相似性匹配的局部误差也就会增大．该文提出了序列分形时变维数的概念,给出了时变Hurst指数的小波估计式和算法;提出了一种新的序列相似性判别标准．新方法在某一分辨级水平上进行曲线形状相似性查询和度量的同时也进行维数曲线的度量和匹配．用仿真算例对方法的有效性进行了验证。     

基于Buddy*-Hash的移动对象时空查询方法

索引技术可以提高数据检索和查询效率,为了实现对时空数据库中移动对象的查询操作,需要引入时空索引技术。在传统Buddy-树的基础上提出Buddy*-Hash索引结构,根据扩展查询窗口策略给出范围查询算法。实验结果表明,基于BH索引结构的范围查询算法具有良好性能。     

数据流上加权共享滑动窗口的连接查询处理算法

在数据流应用中,系统经常需要处理大量的滑动窗口连续查询,采用共享滑动窗口技术可以有效节省存储空间,提高系统整体的查询处理能力。但是共享滑动窗口技术会增大单个查询的响应延迟,降低单个查询的服务质量。针对这个问题,论文提出了加权共享滑动窗口的概念,并提出了三种优化的连接执行算法,优先响应重要的滑动窗口查询,从而提高了系统整体的服务质量。理论分析和实验结果表明论文提出的方法是行之有效的。     

Fast retrieval of electronic messages that contain mistyped wordsor spelling errors

This paper presents an index structure for retrieving electronic messages that contain mistyped words or spelling errors. Given a query string (e.g., a search key), we want to find those messages that approximately contain the query, i.e., certain inserts, deletes and mismatches are allowed when matching the query with a word (or phrase) in the messages. Our approach is to store the messages sequentially in a database and hash their "fingerprints" into a number of "fingerprint files." When the query is given, its fingerprints are also hashed into the files and a histogram of votes is constructed on the messages. We derive a lower bound, based on which one can prune a large number of nonqualifying messages (i.e., those whose votes are below the lower bound) during searching. The paper presents some experimental results, which demonstrate the effectiveness of the index structure and the lower bound.