Parallel Data Cube Storage Structure for Range Sum Queries and Dynamic Updates

I/O parallelism is considered to be a promising approach to achieving high performance in parallel data warehousing systems where huge amounts of data and complex analytical queries have to be processed. This paper proposes a parallel secondary data cube storage structure (PHC for short) to efficiently support the processing of range sum queries and dynamic updates on data cube using parallel computing systems. Based on PHC, two parallel algorithms for processing range sum queries and updates are proposed also. Both the algorithms have the same time complexity, O(logdn/P). The analytical and experimental results show that PHC and the parallel algorithms have high performance and achieve optimum speedup.     

轨迹图谱：一种基于知识图谱结构的轨迹信息抽取方法

现有的这些方法对轨迹数据需根据不同的应用设计不同的数据结构、存储结构、查询算法等,缺少通用性。为了使得轨迹数据更具有通用性,提出了将轨迹转换为知识图谱结构的方法。该方法结合轨迹数据的特点及知识图谱的定义,分别抽取出轨迹数据的实体、关系、属性并构造了轨迹图谱。转换为轨迹图谱后的轨迹数据具有通用的图结构,可直接支持轨迹的基本查询、范围查询、最近邻查询、关键词查询、模式查询等,并可轻易地将其添加到各种现有的知识库中。最终通过在真实数据集上的实验,对比了各类轨迹查询在轨迹图谱方法及普通数据库方法中的表现,证明了轨迹图谱方法的高效性及通用性。     

一种有效的空间数据仓库区域聚集查询索引结构

空间数据仓库有效地支持对空间数据的管理和分析，提供更加全面的决策支持．讨论了一种有效的空间决策支持手段——空间区域聚集查询的实现．基于aggregate cubetree和aR—tree提出了一个可以有效地在空间维和非空间维上进行区域聚集查询的索引结构aCR-tree及其相关算法，并计算分析了查询算法的时间复杂度．与现有技术相比aCR-tree降低了存储代价和每次查询访问的节点数，通过实验证明，该索引结构可以提供较好的存储性能和查询性能．     

Analysis and comparison of declustering schemes for interactivenavigation queries

Declustering schemes enable parallel retrievals of raster-spatial data by allocating data among multiple disks. Previous work in the literature has focused on static range queries. In this paper, we focus on interactive navigation queries, which exhibit a new class of data access patterns. We analyze and compare the performance of previously known declustering schemes from the perspective of navigation queries. These schemes include a class of latin-square-based schemes, Disk Modulo, Fieldwise Exclusive-OR, Hilbert Curve Allocation Method, and a random assignment scheme. We show that, unlike the case of range queries, disk module outperforms other schemes and gives nearly optimal performance for navigation queries. In addition, we propose a new scheme under the constraint of bounded window size-a common constraint in practice due to resource limitation such as monitor resolution or memory size. Through extensive analysis, we establish guidelines on how these schemes can be tuned to provide guaranteed performance under the constraint of bounded window size     

Searching for Complex Human Activities with No Visual Examples

We describe a method of representing human activities that allows a collection of motions to be queried without examples, using a simple and effective query language. Our approach is based on units of activity at segments of the body, that can be composed across space and across the body to produce complex queries. The presence of search units is inferred automatically by tracking the body, lifting the tracks to 3D and comparing to models trained using motion capture data. Our models of short time scale limb behaviour are built using labelled motion capture set. We show results for a large range of queries applied to a collection of complex motion and activity. We compare with discriminative methods applied to tracker data; our method offers significantly improved performance. We show experimental evidence that our method is robust to view direction and is unaffected by some important changes of clothing.     

基于开放区域的定量方向关系查询技术

扩展开放区域的基本抽象类，提出了开放梯形和开放扇形的概念，利用扩展的开放区域理论对空间对象的方向关系进行建模，给出定量方向关系查询的解决方法，并扩展绝对参考框架下定量方向关系查询技术的通用性应用于不同参考框架下的定量和定性的方向关系查询处理，实验证明该技术与传统范围查询方法相比在性能上的优势。     

Indexing range sum queries in spatio-temporal databases

Although spatio-temporal databases have received considerable attention recently, there has been little work on processing range sum queries on the historical records of moving objects despite their importance. Since the direct access to a huge amount of data to answer range sum queries incurs prohibitive computation cost, materialization techniques based on existing index structures are suggested. A simple but effective solution is to apply the materialization technique to the MVR-tree known as the most efficient structure for window queries with spatio-temporal conditions. Aggregate structures based on other index structures such as the HR-tree and the 3DR-tree do not provide satisfactory query performance. In this paper, we propose a new index structure called the Adaptively Partitioned Aggregate R-Tree (APART) and query processing algorithms to efficiently process range sum queries in many situations. Our experimental results show that the performance of the APART is typically 1.3 times better than that of its competitor for a wide range of scenarios.     

基于R树的方向关系查询处理

方向关系描述了对象间的空间顺序关系.近年来,方向关系查询处理逐渐受到空间数据挖掘和地理信息系统等空间数据库应用领域研究者的关注.方向关系查询处理需要执行方向连接操作,目前有关空间连接的研究主要集中在拓扑关系和距离关系方面,而较少考虑方向关系.研究了基于R树的方向关系查询处理方法,定义了四元组模型表示对象MBR间的方向关系,提出了基于R树的处理方向关系查询过滤(filter)步骤的方法,并将提炼(refinement)步骤细化为3种不同的操作.所提出的方法能够高效处理任意对象间的方向关系查询.考虑到空间数据挖掘中方向关系查询通常是在满足一定距离约束条件的对象之间进行,还提出了一种同时利用方向和距离约束限制R树搜索空间的查询处理算法.实验证明,与不利用R树的方向关系查询处理方法相比,所提出的方法在I/O开销和CPU开销两方面都具有很高的性能.     

Performance Evaluation of Range Queries in Key Value Stores

Recently there has been a considerable increase in the number of different Key-Value stores, for supporting data storage and applications on the cloud environment. While all these solutions try to offer highly available and scalable services on the cloud, they are significantly different with each other in terms of the architecture and types of the applications, they try to support. Considering three widely-used such systems: Cassandra, HBase and Voldemort; in this paper we compare them in terms of their support for different types of query workloads. We are mainly focused on the range queries. Unlike HBase and Cassandra that have built-in support for range queries, Voldemort does not support this type of queries via its available API. For this matter, practical techniques are presented on top of Voldemort to support range queries. Our performance evaluation is based on mixed query workloads, in the sense that they contain a combination of short and long range queries, beside other types of typical queries on key-value stores such as lookup and update. We show that there are trade-offs in the performance of the selected system and scheme, and the types of the query workloads that can be processed efficiently.     

Exemplar queries: a new way of searching

Modern search engines employ advanced techniques that go beyond the structures that strictly satisfy the query conditions in an effort to better capture the user intentions. In this work, we introduce a novel query paradigm that considers a user query as an example of the data in which the user is interested. We call these queries exemplar queries. We provide a formal specification of their semantics and show that they are fundamentally different from notions like queries by example, approximate queries and related queries. We provide an implementation of these semantics for knowledge graphs and present an exact solution with a number of optimizations that improve performance without compromising the result quality. We study two different congruence relations, isomorphism and strong simulation, for identifying the answers to an exemplar query. We also provide an approximate solution that prunes the search space and achieves considerably better time performance with minimal or no impact on effectiveness. The effectiveness and efficiency of these solutions with synthetic and real datasets are experimentally evaluated, and the importance of exemplar queries in practice is illustrated.     

A General Model for Authenticated Data Structures

Query answers from on-line databases can easily be corrupted by hackers or malicious database publishers. Thus it is important to provide mechanisms which allow clients to trust the results from on-line queries. Authentic publication allows untrusted publishers to answer securely queries from clients on behalf of trusted off-line data owners. Publishers validate answers using hard-to-forge verification objects VOs), which clients can check efficiently. This approach provides greater scalability, by making it easy to add more publishers, and better security, since on-line publishers do not need to be trusted. To make authentic publication attractive, it is important for the VOs to be small, efficient to compute, and efficient to verify. This has lead researchers to develop independently several different schemes for efficient VO computation based on specific data structures. Our goal is to develop a unifying framework for these disparate results, leading to a generalized security result. In this paper we characterize a broad class of data structures which we call Search DAGs, and we develop a generalized algorithm for the construction of VOs for Search DAGs. We prove that the VOs thus constructed are secure, and that they are efficient to compute and verify. We demonstrate how this approach easily captures existing work on simple structures such as binary trees, multi-dimensional range trees, tries, and skip lists. Once these are shown to be Search DAGs, the requisite security and efficiency results immediately follow from our general theorems. Going further, we also use Search DAGs to produce and prove the security of authenticated versions of two complex data models for efficient multi-dimensional range searches. This allows efficient VOs to be computed (size O(log N + T)) for typical one- and two-dimensional range queries, where the query answer is of size T and the database is of size N. We also show I/O-efficient schemes to construct the VOs. For a system with disk blocks of size B, we answer one-dimensional and three-sided range queries and compute the VOs with O(log_B N + T/B) I/O operations using linear size data structures.     

Modelling topological spatial relations: Strategies for query processing

This paper investigates the processing of spatial queries with topological constraints, for which current database solutions are inappropriate. Topological relations, such as disjoint, meet, overlap, inside, and contains, have been well defined by the 9-intersection, a comprehensive model for binary topological relations. We focus on two types of queries: (1) “Which objects have a stated topological relation with a given spatial object?” and (2) “What is the topological relation between two given spatial objects?” Such queries are processed at two levels of detail. First, Minimum Bounding Rectangles are used as an approximation of the objects' geometry and as a means of identifying candidates that might satisfy the query. Next, the nine intersections that determine the topological relations between candidate pairs are calculated. We present algorithms for minimizing these computations. Considerable performance can be gained by exploiting the semantics of spatial relations. We also compare the approach for a naive cost model, which assumes that all relations have the same frequency of occurrence, with a refined cost model, which considers the probability of occurrence of the topological relations. The strategies presented here have three key benefits: (1) they are based on a well-defined formalism; (2) they are customizable; and (3) they can take into account important statistical information about the data.     

扩展的锥形方向关系查询处理方法

通过加入距离约束,扩展锥形方向关系的描述方式,提出新的查询处理方法——扩展锥形方向二叉树,该方法能处理方向空间连接的查询过滤,通过组合方向和距离关系,提高定性推理的准确性。与传统基于索引的方法相比,该方法能够有效处理大数据集中任意对象间方向关系的查询和定性推理,实现简单、查询效率和推理准确性较高。     

Main Memory Evaluation of Monitoring Queries Over Moving Objects

In this paper we evaluate several in-memory algorithms for efficient and scalable processing of continuous range queries over collections of moving objects. Constant updates to the index are avoided by query indexing. No constraints are imposed on the speed or path of moving objects or fraction of objects that move at any moment in time. We present a detailed analysis of a grid approach which shows the best results for both skewed and uniform data. A sorting based optimization is developed for significantly improving the cache hit-rate. Experimental evaluation establishes that indexing queries using the grid index yields orders of magnitude better performance than other index structures such as R*-trees.     

Range Query Processing in Multidisk Systems

In order to reduce the disk access time,a database can be stored on several simultaneously accessible disks.In this paper,we are concerned with the dynamic d-attribute database allocation problem for range queries,An allocation method,called coordinate moule allocation method,is proposed to allocate data in a d-attribute database among disks so that the maximum disk accessing concurrency can be achieved for range queries.Our analysis and experiments show that the method achieves the optimum or near-optimum parallelism for range queries.The paper offers the conditions under which the method is optimal .The worst case bounds of the performance of the method are also given.In addition,the parallel algorithm of processing range queries in described at the end of the paper.The method has been used in the statistic and scientific database management system whic is being designed by us.     

Computing complete answers to queries in the presence of limited access patterns

In data applications such as information integration, there can be limited access patterns to relations, i.e., binding patterns require values to be specified for certain attributes in order to retrieve data from a relation. As a consequence, we cannot retrieve all tuples from these relations. In this article we study the problem of computing the complete answer to a query, i.e., the answer that could be computed if all the tuples could be retrieved. A query is stable if for any instance of the relations in the query, its complete answer can be computed using the access patterns permitted by the relations. We study the problem of testing stability of various classes of queries, including conjunctive queries, unions of conjunctive queries, and conjunctive queries with arithmetic comparisons. We give algorithms and complexity results for these classes of queries. We show that stability of datalog programs is undecidable, and give a sufficient condition for stability of datalog queries. Finally, we study data-dependent computability of the complete answer to a nonstable query, and propose a decision tree for guiding the process to compute the complete answer.Received: 6 December 2001, Accepted: 25 November 2002, Published online: 3 April 2003Chen Li: This article combines and integrates some content in the technical report at Stanford University [25] and the paper presented in the 8th International Conference on Database Theory (ICDT), London, UK, January, 2001 [28]. In addition to the prior materials, this article contains more results and complete proofs that were not included in the original reports.     

Time Lattice: A Data Structure for the Interactive Visual Analysis of Large Time Series

Advances in technology coupled with the availability of low‐cost sensors have resulted in the continuous generation of large time series from several sources. In order to visually explore and compare these time series at different scales, analysts need to execute online analytical processing (OLAP) queries that include constraints and group‐by's at multiple temporal hierarchies. Effective visual analysis requires these queries to be interactive. However, while existing OLAP cube‐based structures can support interactive query rates, the exponential memory requirement to materialize the data cube is often unsuitable for large data sets. Moreover, none of the recent space‐efficient cube data structures allow for updates. Thus, the cube must be re‐computed whenever there is new data, making them impractical in a streaming scenario. We propose Time Lattice, a memory‐efficient data structure that makes use of the implicit temporal hierarchy to enable interactive OLAP queries over large time series. Time Lattice is a subset of a fully materialized cube and is designed to handle fast updates and streaming data. We perform an experimental evaluation which shows that the space efficiency of the data structure does not hamper its performance when compared to the state of the art. In collaboration with signal processing and acoustics research scientists, we use the Time Lattice data structure to design the Noise Profiler, a web‐based visualization framework that supports the analysis of noise from cities. We demonstrate the utility of Noise Profiler through a set of case studies.     

Bucket‐based authentication for outsourced databases

When outsourced database owners delegate their data to service providers, which might be untrusted or compromised, two issues of data security emerge, including data confidentiality and data integrity. Most of the previous research focuses on only one issue and the solution to integrate two approaches is expensive. In this paper, we propose bucket‐based authentication that can keep data confidentiality and meanwhile guarantee data integrity. Specifically, we first propose a new approach based on bucket checksum, which can be used for the authentication of multiple tuples at one time. We then apply bucket checksum to the authentication of various types of queries in static scenarios, including range queries and aggregation queries, such as MIN, MAX, SUM and COUNT queries. In the authentication of aggregation queries, several pruning rules have been proposed to improve performance further. We also extend our approach to dynamic scenarios based on incremental hash. Cost analysis shows the advantages of our approach over previous ones in terms of construction and verification cost. Experimental results show that our approach is both efficient and effective. Copyright © 2010 John Wiley & Sons, Ltd.     

Optimal Data-Space Partitioning of Spatial Data for Parallel I/O

It is desirable to design partitioning methods that minimize the I/O time incurred during query execution in spatial databases. This paper explores optimal partitioning for two-dimensional data for a class of queries and develops multi-disk allocation techniques that maximize the degree of I/O parallelism obtained in each case. We show that hexagonal partitioning has optimal I/O performance for circular queries among all partitioning methods that use convex non-overlapping regions. An analysis and extension of this result to all possible partitioning techniques is also given. For rectangular queries, we show that hexagonal partitioning has overall better I/O performance for a general class of range queries, except for rectilinear queries, in which case rectangular grid partitioning is superior. By using current algorithms for rectangular grid partitioning, parallel storage and retrieval algorithms for hexagonal partitioning can be constructed. Some of these results carry over to circular partitioning of the data—which is an example of a non-convex region.