一种基于时间序列窗口查询的新索引方法

文章介绍了一种关于时间序列的窗口查询,它是一种关于时间序列的前向查询与反向查询的综合查询技术。为了弥补传统方法在解决窗口查询方面的不足,提出了一种TW-索引专门用于解决时间序列窗口查询。文章对TW-索引的建立过程作了详细地介绍,并对基于TW-索引的窗口查询作了阐述;同时,讨论了当数据处于动态更新时TW-索引的建立及查询方法。然后,将TW-索引与其它索引方法进行了详细地比较。最后,介绍了TW-索引在时间序列窗口查询中的应用。     

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

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

基于LSH的时间子序列查询算法

子序列的相似性查询是时间序列数据集中的一种重要操作,包括范围查询和k近邻查询.现有的大多算法是基于欧几里德距离或者DTW距离的,缺点在于查询效率低下.文中提出了一种新的基于LSH的距离度量方法,可以在保证查询结果质量的前提下,极大提高相似性查询的效率;在此基础上,给出一种DS-Index索引结构,利用距离下界进行剪枝,进而还提出了两种优化的OLSH-Range和OLSH-kNN算法.实验是在真实的股票序列集上进行的,数据结果表明算法能快速精确地找出相似性查询结果.     

基于MapReduce的时间序列索引与批量查询技术

针对基于不平衡树的时间序列索引对海量时间序列数据查询性能较差的问题,提出一种基于MapReduce的DB-DSTree索引。利用平衡的时间序列索引DHD作为路由树创建分布式的DSTree,并充分挖掘批量查询中的数据局部性,将相似的查询路由到局部节点上,以改善DSTree索引的非平衡性。实验结果表明,DB-DSTree索引的平衡性和局部性较好,可减少子树的查询范围和磁盘I/O次数,提高查询效率。     

DSI:一种基于动态分段的时间序列查询索引

时间序列数据主要依据采集时间进行排序,时间序列上相邻的数据具有一定的关联性,当用户读取时间序列数据时不只是读取一条数据,而是连续读取一段时间序列数据。针对时间序列的局部性特点,提出一种基于动态分段的时间序列索引DSI,通过设置差值及差值等级对时间序列数据进行动态分段,使用区间树快速查找不同长度的数据分段块,并利用层次聚类算法优化查询结果集合。实验结果表明,DSI索引的查询效率优于现有时间序列查询索引。     

用基于移动均值的索引实现时间序列相似查询

提出了基于移动均值的索引来解决子序列匹配中的"ε-查询"问题:提出并证明了基于移动均值的缩距定理和缩距比关系定理,后者具有很好的"裁减"能力,可以在相似查询时淘汰大部分不符合条件的候选时间序列,从而达到快速相似查找的目的;引入了由Jagadish等人提出的BATON~*-树,并在此基础上适当修改,建立了MABI索引,极大地加快了相似查询过程;最后,在一个股票交易数据集上进行了实验,证明了MABI索引的良好性能.     

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

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

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

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

基于分段极值的时间序列数据查询显示方法

时间序列数据在许多领域广泛存在,有海量和复杂的特点,直接查询出所有的原始数据并对其进行分析十分耗时,且对计算机的内存消耗极大。为此,提出一种基于分段极值的时间序列数据查询显示方法,对需要查询分析数据的时间范围进行分段,根据各个时间段数据的极值及总取点个数来确定该时间段的取点个数,通过数据库本身的查询机制实现均匀取点,并结合多线程机制实现各时间段数据的并行查询及曲线绘制。实验结果表明,与传统查询及可视化方法相比,该方法能够指定取点数量,并在取点数量确定的情况下,绘制曲线能较好地逼近原始曲线,且极大地缩短曲线的查询绘制时间,具有较好的工程实用性。     

层次序列索引的大规模动态标签图子图查询

标签图常用于智能交通网、生物信息网等新兴领域的建模。子图查询作为图数据分析的关键问题，引起了研究者的广泛关注。对现有子图查询算法的研究发现，随着图数据规模增大且频繁更新，传统子图查询算法普遍存在查询效率低，存储开销大，忽略顶点标签信息等问题。为此，提出了一种支持大规模动态标签图子图查询的层次序列索引（Dynamic Hierarchical Sequence，DHS），该索引提取数据图中带有顶点编号的层次拓扑序列关系以实现子图查询；针对图的动态变化，提出了更新点拓扑扩展式索引维护策略，仅从局部变化顶点及边开始进行增量式更新，大大降低了重建索引造成的巨大开销；提出了基于DHS索引的子图查询方法，仅需将查询图与数据图的层次序列进行匹配即可获得候选集，并在其上利用关系匹配策略获得最终查询结果。实验证明提出的方法在保证高效查询的同时降低了索引的创建及维护时间，提高了子图查询效率。     

Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services

Traditional nearest-neighbor (NN) search is based on two basic indexing approaches: object-based indexing and solution-based indexing. The former is constructed based on the locations of data objects: using some distance heuristics on object locations. The latter is built on a precomputed solution space. Thus, NN queries can be reduced to and processed as simple point queries in this solution space. Both approaches exhibit some disadvantages, especially when employed for wireless data broadcast in mobile computing environments. In this paper, we introduce a new index method, called the grid-partition index, to support NN search in both on-demand access and periodic broadcast modes of mobile computing. The grid-partition index is constructed based on the Voronoi diagram, i.e., the solution space of NN queries. However, it has two distinctive characteristics. First, it divides the solution space into grid cells such that a query point can be efficiently mapped into a grid cell around which the nearest object is located. This significantly reduces the search space. Second, the grid-partition index stores the objects that are potential NNs of any query falling within the cell. The storage of objects, instead of the Voronoi cells, makes the grid-partition index a hybrid of the solution-based and object-based approaches. As a result, it achieves a much more compact representation than the pure solution-based approach and avoids backtracked traversals required in the typical object-based approach, thus realizing the advantages of both approaches. We develop an incremental construction algorithm to address the issue of object update. In addition, we present a cost model to approximate the search cost of different grid partitioning schemes. The performances of the grid-partition index and existing indexes are evaluated using both synthetic and real data. The results show that, overall, the grid-partition index significantly outperforms object-based indexes and solution-based indexes. Furthermore, we extend the grid-partition index to support continuous-nearest-neighbor search. Both algorithms and experimental results are presented. Edited by R. Guting     

LIGHT: A Query-Efficient Yet Low-Maintenance Indexing Scheme over DHTs

DHT is a widely used building block for scalable P2P systems. However, as uniform hashing employed in DHTs destroys data locality, it is not a trivial task to support complex queries (e.g., range queries and k-nearest-neighbor queries) in DHT-based P2P systems. In order to support efficient processing of such complex queries, a popular solution is to build indexes on top of the DHT. Unfortunately, existing over-DHT indexing schemes suffer from either query inefficiency or high maintenance cost. In this paper, we propose LIGhtweight Hash Tree (LIGHT)—a query-efficient yet low-maintenance indexing scheme. LIGHT employs a novel naming mechanism and a tree summarization strategy for graceful distribution of its index structure. We show through analysis that it can support various complex queries with near-optimal performance. Extensive experimental results also demonstrate that, compared with state of the art over-DHT indexing schemes, LIGHT saves 50-75 percent of index maintenance cost and substantially improves query performance in terms of both response time and bandwidth consumption. In addition, LIGHT is designed over generic DHTs and hence can be easily implemented and deployed in any DHT-based P2P system.     

ADS: the adaptive data series index

Numerous applications continuously produce big amounts of data series, and in several time critical scenarios analysts need to be able to query these data as soon as they become available. This, however, is not currently possible with the state-of-the-art indexing methods and for very large data series collections. In this paper, we present the first adaptive indexing mechanism, specifically tailored to solve the problem of indexing and querying very large data series collections. We present a detailed design and evaluation of our method using approximate and exact query algorithms with both synthetic and real data sets. Adaptive indexing significantly outperforms previous solutions, gracefully handling large data series collections, reducing the data to query delay: By the time state-of-the-art indexing techniques finish indexing 1 billion data series (and before answering even a single query), our method has already answered \(3*10^5\) queries.     

Skyframe: a framework for skyline query processing in peer-to-peer systems

This paper looks at the processing of skyline queries on peer-to-peer (P2P) networks. We propose Skyframe, a framework for efficient skyline query processing in P2P systems, which addresses the challenges of quick response time, low network communication cost and query load balancing among peers. Skyframe consists of two querying methods: one is optimized for network communication while the other focuses on query response time. These methods are different in the way in which the query search space is defined. In particular, the first method uses a high dominating point that has a large dominating region to prune the search space to achieve a low cost in network communication. On the other hand, the second method relaxes the search space in order to allow parallel query processing to speed up query response. Skyframe achieves query load balancing by both query load conscious data space splitting/merging during the join/departure of nodes and dynamic load migration. We further show how to apply Skyframe to both the P2P systems supporting multi-dimensional indexing and the P2P systems supporting single-dimensional indexing. Finally, we have conducted extensive experiments on both real and synthetic data sets over two existing P2P systems: CAN (Ratnasamy in A scalable content-addressable network. In: Proceedings of SIGCOMM Conference, pp. 161–172, 2001) and BATON (Jagadish et al. in A balanced tree structure for peer-to-peer networks. In: Proceedings of VLDB Conference, pp. 661–672, 2005) to evaluate the effectiveness and scalability of Skyframe.     

Adapting metric indexes for searching in multi-metric spaces

An important research issue in multimedia databases is the retrieval of similar objects. For most applications in multimedia databases, an exact search is not meaningful. Thus, much effort has been devoted to develop efficient and effective similarity search techniques. A recent approach that has been shown to improve the effectiveness of similarity search in multimedia databases resorts to the usage of combinations of metrics (i.e., a search on a multi-metric space). In this approach, the desirable contribution (weight) of each metric is chosen at query time. It follows that standard metric indexes cannot be directly used to improve the efficiency of dynamically weighted queries, because they assume that there is only one fixed distance function at indexing and query time. This paper presents a methodology for adapting metric indexes to multi-metric indexes, that is, to support similarity queries with dynamic combinations of metric functions. The adapted indexes are built with a single distance function and store partial distances to estimate the dynamically weighed distances. We present two novel indexes for multimetric space indexing, which are the result of the application of the proposed methodology.     

Processing moving queries over moving objects using motion-adaptive indexes

This paper describes a motion-adaptive indexing scheme for efficient evaluation of moving continual queries (MCQs) over moving objects. It uses the concept of motion-sensitive bounding boxes (MSBs) to model moving objects and moving queries. These bounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequently changing object positions, we index less frequently changing object and query MSBs, where updates to the bounding boxes are needed only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to the indexes. More importantly, we use predictive query results to optimistically precalculate query results, decreasing the number of searches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Furthermore, we introduce the concepts of guaranteed safe radius and optimistic safe radius to extend our motion-adaptive indexing scheme to evaluating moving continual k-nearest neighbor (kNN) queries. Our experiments show that the proposed motion-adaptive indexing scheme is efficient for the evaluation of both moving continual range queries and moving continual kNN queries.     

Divide, Compress and Conquer: Querying XML via Partitioned Path-Based Compressed Data Blocks

We propose a novel partition path-based (PPB) grouping strategy to store compressed XML data in a stream of blocks. In addition, we employ a minimal indexing scheme called block statistic signature (BSS) on the compressed data, which is a simple but effective technique to support evaluation of selection and aggregate XPath queries of the compressed data. We present a formal analysis and empirical study of these techniques. The BSS indexing is first extended into effective cluster statistic signature (CSS) and multiple-cluster statistic signature (MSS) indexing by establishing more layers of indexes. We analyze how the response time is affected by various parameters involved in our compression strategy such as the data stream block size, the number of cluster layers, and the query selectivity. We also gain further insight about the compression and querying performance by studying the optimal block size in a stream, which leads to the minimum processing cost for queries. The cost model analysis provides a solid foundation for predicting the querying performance. Finally, we demonstrate that our PPB grouping and indexing strategies are not only efficient enough to support path-based selection and aggregate queries of the compressed XML data, but they also require relatively low computation time and storage space when compared with other state-of-the-art compression strategies.     

Indexing Techniques of Distributed Ordered Tables: A Survey and Analysis

Many NoSQL (Not Only SQL) databases were proposed to store and query on a huge amount of data. Some of them like BigTable, PNUTS, and HBase, can be modeled as distributed ordered tables (DOTs). Many additional indexing techniques have been presented to support queries on non-key columns for DOTs. However, there was no comprehensive analysis or comparison of these techniques, which brings troubles to users in selecting or proposing a proper indexing technique for a certain workload. This paper proposes a taxonomy based on six indexing issues to classify indexing techniques on DOTs and provides a comprehensive review of the state-of-the-art techniques. Based on the taxonomy, we propose a performance model named QSModel to estimate the query time and storage cost of these techniques and run experiments on a practical workload from Tencent to evaluate this model. The results show that the maximum error rates of the query time and storage cost are 24.2% and 9.8%, respectively. Furthermore, we propose IndexComparator, an open source project that implements representative indexing techniques. Therefore, users can select the best-fit indexing technique based on both theoretical analysis and practical experiments.