一类近似查询提纲的小波方法的应用研究

在数据仓库以及联机分析处理等许多领域中，聚集数据的处理是一个非常重要的核心问题。本文分析了聚集数据查询的特点，引入了基于聚集数据的近似查询计算模型，并针对该计算模型的提纲构建问题，给出了一类近似查询提纲的Haar小波方法，来实现对聚集数据和聚集视图的快速查询计算。     

基于实化聚集视图的查询计算及其应用研究

对基于实化聚集视图的查询计算及相关研究进行了分析，并将相关的数据仓库的查询计算理论与面向应用的近视查询处理方法相结合，提出了一种基于实化聚集视图的近似查询计算方案，该方案具有广泛的应用前景。     

SQL聚集函数扩展

已经存在的SQL聚集函数在计算百分比方面有明显的限制，提出2种水平与垂直百分比聚集函数用于计算百分比。新的聚集函数容易使用，有广泛的用途，可以被用于作为一种框架去研究百分比查询，能有效地生成SQL代码。实验研究给出百分比聚集方法与SQL/OLAP聚集方法的执行性能，结果显示这2种方法在性能上比SQL/OLAP聚集方法有一定的改善。     

基于数据流的近似查询计算及其应用研究

通过分析基于实化聚集视图的查询重写方法，将相关的查询计算理论与数据流的查询相结合，针对数据流的特征，给出了一种具有广泛应用前景的基于数据流的近似查询计算方案。     

用后缀树构造XML路径字典加快路径查询评价速度

后缀树的重要性可以为多年来学术界对它总是有新的发现而印证．它的结构简单，但可以在线性的时间里解决许多复杂的问题，被大量的使用在字符串及树的模式匹配中，对于XML标准，有很多基于关系库和对象库的索引技术和查询方案被提出来，我们试图给出一种基于后缀树进行路径导航的查询机制：用后缀树构造XML路径字典加速路径查询评价速度，我们提出可以在线地建立一个trie树的后缀树，讨论了XML路径字典中的后缀树建树算法，阐述了整个索引方案和查询机制，并探讨了包括RPE在内的它所支持的各种查询操作，XML路径字典被用于加快路径查询的评价速度．     

动态分片在线聚集

传统的在线聚集方法为了避免执行中随机I/O导致的性能下降,假设数据本身近似随机分布于数据文件中,用顺序I/O来代替随机I/O. 数据随机分布于数据文件的假设在很多实际的应用场景中是难以成立的,从而导致查询结果产生很大误差.提出了动态数据分片在线聚集算法DDPOA(dynamic data-partitioned online aggregation),将整个数据集分片,对各个子数据集独立计算,线性组合子集结果进而得到全集最终结果,一方面降低了在线聚集对整体数据集随机分布的要求,提高了准确性,另一方面动态调整分片数量以改善I/O性能,缩短完成时间.真实系统负载上的实验表明:DDPOA与传统在线聚集相比,在完成时间相差不大的情况下准确性有了大幅提高.     

关于OCSP应用模式的注记

文献《在线证书状态协议的改进及应用》提出了一个基于OCSP(Online Certificate Status Protocol，在线证书状态协议)查询的数字签名验证应用方案，这个方案的安全性与可行性是值得商榷的。该文给出了一种攻击方法，并分析了其中的几个问题及问题产生的根源；最后给出了一种解决方案。     

概率数据库的聚集查询

在概率关系中,聚集查询的目标是每一个可能世界,而可能世界的数目随着概率关系元组数目的增长呈指数增长,当元组数目较多时,聚集查询在线性时间内无法计算。针对该问题,分别为每一个聚集函数定义3个聚集分量,通过对原概率关系进行编码,分别采用转换、存储过程和近似计算的方法,在线性时间内实现聚集查询,理论证明和实验结果表明该方法的正确性和有效性。     

无须附加空间的数据立方体联机聚集

以往在数据立方体上实现的联机聚集往往需要附加空间来存储联机聚集估算所需要的信息,极大地影响了数据立方体的存储和维护性能.提出了基于QC-Tree的用于范围查询处理的联机聚集PE(progressively estimate)算法以及它与简单聚集算法相结合的混合聚集算法HPE(hybrid progressively estimate);还提出了一种能够同时处理多个范围查询的联机聚集算法MPE(multiple progressively estimate).与以往联机聚集算法不同,这些算法不需要任何附加空间,而是利用QC-Tree自身保存的聚集数据和语义关系来估算聚集结果.由于QC-Tree是一种极为高效的数据立方体存储结构,因此能够以较理想的性能实现数据立方体上的联机聚集.对算法的分析和实验结果表明,所提出的算法具有较好的性能.     

云数据管理系统中查询技术研究综述

作为一种全新的互联网应用模式,云计算在工业界和学术界备受关注.人们可以通过终端设备便捷地获取云端服务,并以按需使用的方式获得存储资源、计算资源以及软硬件资源.云计算的发展带来了一系列挑战性问题,而云数据的管理问题首当其冲.文中结合云数据的特点提出了一个云数据管理系统的框架,并在此基础上从索引管理、查询处理、查询优化以及在线聚集等几个方面对云数据管理系统中查询技术的研究工作进行了总结分析,指明了该领域面临的挑战和未来的研究工作.     

联机分析查询处理中的一种聚集算法

联机分析处理(online analytical processing,简称OLAP)查询是涉及大量数据的即席复杂查询,从SQL(structured query language)角度来看,这些查询通常都包含多表连接和分组聚集操作.从OLAP查询处理角度出发,提出一种新的基于排序的聚集查询算法MuSA(sort-based aggregation with multi-table join).该方法充分考虑到数据仓库星型模式的特点,将聚集操作和新的多表连接算法MJoin相结合,排序时采用     

基于分组序号的聚集算法

联机分析处理OLAP(online analytical processing)查询作为一种复杂查询,当使用SQL(structured query language)语句来表述时,通常都包含多表连接和分组聚集操作,因此提高多表连接和分组聚集计算的性能就成为ROLAP(relational OLAP)查询处理的关键问题.提出一种基于分组序号的聚集算法MuGA(group number based aggregation with multi-table join),该方法充分考虑数据仓库星型模式的特点,将聚集操作和新的多表连接算法MJoin(multi-table join)相结合,使用分组序号进行分组聚集计算,代替通常的排序或者哈希计算,从而有效地减少CPU运算以及磁盘存取的开销.算法的实验数据表明,提出的MuGA算法与传统的关系数据库聚集查询处理方法以及改进后的基于排序的聚集算法相比,性能都有显著提高.     

一种基于维层次编码的OLAP聚集查询算法

联机分析处理(OLAP)查询往往需在海量数据上进行即席的复杂分组聚集查询，在其SQL语句中通常包含多表连接和分组聚集操作，因而减少多表连接和压缩关键字，以及对查询数据进行有效地分组聚集操作，成为ROLAP查询处理的关键问题。提出了一种基于维层次编码的新型预分组聚集算法DHEPGA．DHEPGA算法充分利用了编码长度较小的维层次编码及其前缀，来快速检索出与查询关键字相匹配的维层次编码，求得维层次属性的查询范围，减少了I／O开销，提高了OLAP查询效率。理论分析和实验结果表明，DHEPGA算法性能是非常有效的。     

Balancing energy efficiency and quality of aggregate data in sensor networks

In-network aggregation has been proposed as one method for reducing energy consumption in sensor networks. In this paper, we explore two ideas related to further reducing energy consumption in the context of in-network aggregation. The first is by influencing the construction of the routing trees for sensor networks with the goal of reducing the size of transmitted data. To this end, we propose a group-aware network configuration method that clusters along the same path sensor nodes that belong to the same group. The second idea involves imposing a hierarchy of output filters on the sensor network with the goal of both reducing the size of transmitted data and minimizing the number of transmitted messages. More specifically, we propose a framework to use temporal coherency tolerances in conjunction with in-network aggregation to save energy at the sensor nodes while maintaining specified quality of data. These tolerances are based on user preferences or can be dictated by the network in cases where the network cannot support the current tolerance level. Our framework, called TiNA, works on top of existing in-network aggregation schemes. We evaluate experimentally our proposed schemes in the context of existing in-network aggregation schemes. We present experimental results measuring energy consumption, response time, and quality of data for Group-By queries. Overall, our schemes provide significant energy savings with respect to communication and a negligible drop in quality of data.Received: 22 October 2003, Accepted: 16 April 2004, Published online: 12 November 2004Edited by: J. Gehrke and J. HellersteinThis work is supported in part by NSF award ANI-0123705. The first author is supported in part by the Andrew Mellon Predoctoral Fellowship. This paper expands on the material presented in two workshops [31,2].     

Sampling-based estimators for subset-based queries

We consider the problem of using sampling to estimate the result of an aggregation operation over a subset-based SQL query, where a subquery is correlated to an outer query by a NOT EXISTS, NOT IN, EXISTS or IN clause. We design an unbiased estimator for our query and prove that it is indeed unbiased. We then provide a second, biased estimator that makes use of the superpopulation concept from statistics to minimize the mean squared error of the resulting estimate. The two estimators are tested over an extensive set of experiments. Material in this paper is based upon work supported by the National Science Foundation via grants 0347408 and 0612170.     

混合传感器网络中基于事件的位置相关查询

在混合传感器网络中,传感器移动性使得查询区域产生动态变化。针对动态查询区域内的数据聚集查询难以有效处理的问题,提出了一种基于事件的位置相关查询(ELAQ)处理方法,它包括查询分发算法、最大距离投影代理选择算法、网络内查询传播和聚集算法。ELAQ模型的特点是查询由事件触发,查询结果依赖于移动传感器的位置。实验结果显示,相比TinyDB查询处理方法,该方法提高了查询结果准确率,缩短了查询响应时间。     

用于数据仓储的一种改进的多维存储结构

对于数据仓库中数据的物理存储组织,目前主要有关系和多维数组两种方式.这两种方式各有自己的优缺点,从提高联机分析处理(online analytical processing,简称OLAP)查询处理性能的角度出发,多维数组方式相对较优,目的主要是解决数据仓库的多维存储结构问题.针对当前多维数组存储组织方式存在的一些问题,提出了Cube(立方体)逻辑存储和物理存储的概念,首先将原多维数据空间划分为逻辑子空间,逻辑块再划分为多个物理块.在物理存储时充分考虑了多维数组的大容量和高稀疏度的问题,并采用新的多维数组的分布和压缩方法.这些概念和方法有效地解决了维内部层次结构的聚集操作和Cube操作的效率问题,显著提高了涉及维内部层次的聚集查询的响应速度,同时还解决了增量维护的效率问题.     

抗窃听攻击的传感器网络空间范围聚集查询处理算法

现有传感器网络聚集查询隐私保护方法采用加解密的形式保护节点感知数据,且需要网络中的所有节点参与查询处理。过多加解密操作会大量消耗节点能量,且用户可能只对其中部分区域的聚集结果感兴趣。针对这些问题,提出一种抗窃听攻击的传感器网络空间范围聚集查询处理算法PCPDA。该算法沿着既定路线,一边查询一边聚集,使得算法不依赖于预先构造好的拓扑结构,适用于网络拓扑结构动态变化的传感器网络,节省了维护拓扑结构的开销。该算法在未采用任何加密措施情况下保证了节点感知数据的隐私性。理论分析和仿真结果表明,PCPDA在能量损耗和隐私保护方面都优于现有算法。     

无线传感器网络中数据融合算法研究

在提供高效的数据融合的同时保障数据的安全是无线传感器网络的研究的一个具有挑战性的问题。本文为加法融合函数设计了一种具有隐私保护功能的数据融合算法——基于分簇的安全数据融合。该算法利用了分簇协议和多项式的代数性质。其优点为带来的通信开销较小。研究的主要目标是提高无线传感器网络中数据融合效率的同时,保证数据的安全性。