有效降低分布式SKYLINE查询网络传输代价

 分布式网络中的skyline查询是近年来信息检索学科的一个研究重点．目前大多数研究工作均没有考虑在分布式网络中,如何有效降低skyline查询的网络传输代价．为此,提出一种在分布式网络中,有效降低skyline查询传输代价的方法RTCSQDN(Reducing the Transferring Cost of Skyline Queries over Distributed Networks)．RTCSQDN算法充分利用父空间skyline对象集与子空间skyline对象集间的语义关系通过三个阶段来平衡网络传输量和查询时间开销．同时,文章给出一种新颖的多维对象传送策略PTGPV(Policy for Transferring Grouping Position Values)来避免直接传送skyline对象本身,从而最小化数据传输量．详细的理论分析和大量实验评估表明,文章给出的算法具有有效性和实用性．     

MapReduce框架下的优化高维索引与KNN查询

针对大规模高维数据近似查询效率低下的问题,利用MapReduce编程模型在大规模集群上的数据与任务的并行计算与处理优势,提出MapReduce框架下大规模高维数据索引及KNN查询方法（iPBM）,重点突破MapReduce数据块（block）的优化划分与各数据块对计算的共同贡献两大难题,利用两阶段数据划分策略并依据相关性与并行性原则将数据均匀分配到各数据块中,设计分布式的双层空间索引结构与并行KNN查询算法,检索时利用全局索引、局部索引与二维位码索引实现三层数据过滤,大幅缩小搜索范围并降低高维向量计算代价,实验表明iPBM对大规模高维数据的近似查询具有准确性、高效性和扩展性.     

SKYLINE查询解析

现有的研究工作只考虑如何对单个底层关系表进行skyline计算,即它们假定用户所提交的skyline查询不涉及任何传统的关系操作,并且所有skyline维度均落入同一个关系表中.显然,在实际应用中,由于这种假设的不成立,使得在多数情况下用户查询的效率极其低下.基于此,将skyline计算作为一个特殊的关系操作符,研究它与传统关系操作符间执行顺序变换的等价规则.从而,利用这些等价变换规则,通过改变skyline操作符与传统关系操作符之间的执行顺序来有效提高查询的效率.同时,给出充分的理论证明来论证所给等价变换规则的正确性,并通过实验验证其有效性.     

基于Web Service柔性异构数据集成系统设计及查询处理

提出的异构数据集成系统框架包括源模式层、局部模式层、全局模式层和用户模式层.利用Web service接口完成从源模式层到局部模式层的转换,利用模式融合和冲突解决实现从局部模式到全局模式的转换,并嵌入数据查询过程.用户模式层作为全局模式层的一个子集,可以动态调整,方便集成数据的查询处理,还定义了一个基于XML的统一数据模型以支持异构数据的集成中的查询处理,提出了一个相应的查询处理过程.     

基于Voronoi图预划分的LBS位置隐私保护方法

为了解决服务器面临大量用户请求时匿名效率下降的问题,分别提出适用于静态用户和动态用户的协作匿名方法。首先基于Voronoi图划分全局区域,再由中心服务器组织本区域内用户实现协作匿名,由于服务器无需为每个用户单独构造匿名区,降低了服务端的负担;针对查询过程中用户提供真实位置信息带来位置隐私泄露的问题,提出了逆向增量近邻查询算法。用户以固定锚点代替真实位置,向位置服务器逐步获取兴趣点候选集并计算出想要的结果,避免位置隐私直接泄漏的同时获取精准查询结果。该算法同时解决了锚点与用户过近而带来的位置隐私被推断问题。实验表明本方法在有效保护用户位置隐私的同时,具有良好的工作效率。     

面向DNS日志的MapReduce性能优化技术研究

DNS日志是互联网中重要的访问日志,数量巨大且承载着大量信息,需要借助大数据技术进行处理和分析.现网DNS日志数据量大,且数据倾斜现象严重,对MapReduce的性能有较为严重的影响.基于上述问题,采用小文件合并方法优化分片,缓解Map端的数据倾斜问题,并实现动态设置分片大小,提高MapReduce作业执行效率.该方法有效均衡了Map任务的负载,从而提高了数据倾斜情况下的MapReduce作业的执行效率和资源利用率.实验表明,使用该方法可以有效缩短MapReduce作业的执行时间.     

面向时空数据场景的数据库索引选择框架

索引是一种用于提高数据库查询效率的数据结构,良好执行计划的生成和选择很大程度上取决于数据表上是否存在合适的索引。然而,面对复杂的时空数据场景,现有的索引选择方法存在很多不足,如无法高效处理大量范围查询、容易造成索引冗余、无法有效应对动态的工作负载等问题。针对上述问题,提出一种新型基于深度确定策略梯度(Deep Deterministic Policy Gradient,DDPG)模型和索引效益评估网络的索引选择框架:ST-IS(Index Selection method tailored for Spatio-Temporal data scenarios)。ST-IS集成了对SQL语句和索引集的新型编码方法,有效避免索引冗余或索引缺失。ST-IS使用索引效益评估网络来优化强化学习的奖励机制,同时支持动态的工作负载。大量实验结果表明,在真实时空数据集和TPC-DS标准数据集上,ST-IS的性能优于现有的索引选择方法。     

一种基于单点收益的轨迹隐私保护方法

如何在轨迹数据发布时保护用户隐私信息并且最大程度地减少数据损失是隐私保护研究领域的一个重要课题.本文提出一种基于单点收益的轨迹隐私保护方法,在满足用户隐私要求的情况下,根据收益计算结果,在轨迹数据集中抑制位置点或者添加假轨迹,保证每次处理轨迹数据集时能达到最大收益,从而减少信息损失.理论分析和实验结果表明,在隐私容忍度要求较高或者攻击者数量较多的情况下,本文方法能在保证隐私保护强度前提下有效降低数据损失率.     

一种高维大数据全k近邻查询算法

全k近邻(all k-nearest neighbor,AkNN)查询,是k近邻查询的一个变型,旨在在一个查询过程中为给定数据集的每个对象确定k个最近邻.提出了一种在Hadoop分布式平台下处理高维大数据的AkNN查询算法.首先使用行条化思想结合p-stable LSH算法将高维数据对象降维,然后结合空间填充曲线Z-order的优良特性,把降维后的数据嵌入一维空间中,接着进行范围查询.整个过程使用MapReduce框架分布式并行处理.实验结果表明,所提出的算法可以高效处理高维大数据的AkNN查询.     

一种基于 MapReduce 的 XML 查询的优化方法

基于 MapReduce 的 XML 查询逐渐成为研究热点,如何提高 XML 文档查询的效率是关键问题之一.在保障查询结果正确和 XML 数据分块一致的前提下,采用 XPath 投影的方法对 XML 数据分块预处理,使得 XML 分块中仅包含与查询有关的数据.实验表明,该方法有效缩小了数据分块的规模、缩短了 XML 数据服务的查询处理时间.     

Energy-efficient skyline query optimization in wireless sensor networks

With the deployment of wireless sensor networks (WSNs) for environmental monitoring and event surveillance, WSNs can be treated as virtual databases to respond to user queries. It thus becomes more urgent that such databases are able to support complicated queries like skyline queries. Skyline query which is one of popular queries for multi-criteria decision making has received much attention in the past several years. In this paper we study skyline query optimization and maintenance in WSNs. Specifically, we first consider skyline query evaluation on a snapshot dataset, by devising two algorithms for finding skyline points progressively without examining the entire dataset. Two key strategies are adopted: One is to partition the dataset into several disjoint subsets and produce the skyline points in each subset progressively. Another is to employ a global filter that consists of some skyline points in the processed subsets to filter out unlikely skyline points from the rest of unexamined subsets. We then consider the query maintenance issue by proposing an algorithm for incremental maintenance of the skyline in a streaming dataset. A novel maintenance mechanism is proposed, which is able to identify which skyline points from past skylines to be the global filter and determine when the global filter is broadcast. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms on both synthetic and real sensing datasets, and the experimental results demonstrate that the proposed algorithms significantly outperform existing algorithms in terms of network lifetime prolongation.     

Efficient Continuous Skyline Query Processing Scheme over Large Dynamic Data Sets

Performing continuous skyline queries of dynamic data sets is now more challenging as the sizes of data sets increase and as they become more volatile due to the increase in dynamic updates. Although previous work proposed support for such queries, their efficiency was restricted to small data sets or uniformly distributed data sets. In a production database with many concurrent queries, the execution of continuous skyline queries impacts query performance due to update requirements to acquire exclusive locks, possibly blocking other query threads. Thus, the computational costs increase. In order to minimize computational requirements, we propose a method based on a multi‐layer grid structure. First, relational data object, elements of an initial data set, are processed to obtain the corresponding multi‐layer grid structure and the skyline influence regions over the data. Then, the dynamic data are processed only when they are identified within the skyline influence regions. Therefore, a large amount of computation can be pruned by adopting the proposed multi‐layer grid structure. Using a variety of datasets, the performance evaluation confirms the efficiency of the proposed method.     

Securing sensor data storage and query based on k‐out‐of‐ n coding

With in‐network sensor data storage and query, sensed data are stored locally and further accessed by users on demand. Thus, without proper protection for sensor data and user queries, compromise of sensor nodes may reveal sensitive information about the sensed environment as well as users’ query patterns. Furthermore, the adversary can alter some stored data and prevent users from recovering information correctly. In this paper, we propose and analyze the use of maximum‐distance separable codes to address the problem. First, initial data is encoded in (n, k) maximum‐distance separable code and spread from a single data source to a set of storage nodes for higher survivability. Second, a blind signature‐based privacy scheme is explored to preserve user query, such that authorized user's identity and privacy interests are concealed from others. Finally, an efficient data retrieval scheme is carried out such that the redundancy symbols in the remaining nodes are accessed only if the user fails to decode the data, which reduces the communication and computation cost. Analysis and evaluation verify the efficiency of the proposed scheme. Copyright © 2011 John Wiley & Sons, Ltd.     

MapReduce模型的调度及容错机制研究

MapReduce是一种并行编程模型,可以用来处理和生成大量数据集。它的调度以及容错机制是模型的重要一部分。通过对MapReduce模型的执行过程进行分析,提取得到其上面的调度以及容错模型。并将P2P模型中常用的调度思想使用于MapReduce调度模型上,对原来的调度机制和容错机制做一定的修改。     

概率数据流上Skyline查询处理算法

 概率数据流管理与分析逐步引起了研究者们的关注.Skyline查询技术是近年来数据库领域的研究热点.此前相关工作仅限于静态数据集或传统确定性数据流上的Skyline查询处理,尚无人考虑概率数据流上的Skyline计算问题,本文提出的SOPDS算法则较好地解决了该问题.在采用适应性更强的网格索引的基础上,提出了概率定界、逐步求精、提前淘汰与选择补偿等启发式规则对算法从时间和空间两方面进行了系统地优化.实验表明,算法在时间与空间上具有较高的整体性能.     

云计算环境中基于用户访问需求的角色查找算法

提出了一种云计算环境中基于角色的访问控制模型CARBAC,将角色分为用户角色和资源拥有者管理角色。针对管理角色对用户访问的角色指派,提出了在混杂角色层次关系中基于用户权限的角色查找算法。对于一组给定的授权,该算法能在云计算系统的角色中选择一组数量最少的角色指派给用户。仿真实验表明,针对云计算环境中的海量用户访问,本算法能显著减少系统中角色的数量,缩短用户授权时间,提高系统运行效率。     

基于用户反馈的关系数据库关键字查询系统

关系数据库中的关键字查询问题使得用户无需掌握查询SQL语言与数据库模式相关知识就可以进行数据库查询,因此受到人们的广泛关注,许多方法和原型被提出。当前流行的关系数据库中关键字查询技术存在较慢的查询时间或者不准确的查询结果。针对这两个问题,提出了一种基于用户反馈的查询方法,根据用户输入的关键字动态地生成一个在数据库中包含关键字的属性所组成的Form表单提供给用户,用户在Form中进行选择并提交,最后,根据用户的选择和数据库模式图进行连接算法并执行SQL获得最终结果。     

Reinforcement learning for cooperative sensing gain in cognitive radio ad hoc networks

Spectrum sensing is a fundamental function in cognitive radio networks for detecting the presence of primary users in licensed bands. The detection performance may be considerably compromised due to multipath fading and shadowing. To resolve this issue, cooperative sensing is an effective approach to combat channel impairments by cooperation of secondary users. This approach, however, incurs overhead such as delay for reporting local decisions and the increase of control traffic. In this paper, a reinforcement learning-based cooperative sensing (RLCS) method is proposed to address the cooperation overhead problem and improve cooperative gain in cognitive radio ad hoc networks. The proposed algorithm is proven to converge and capable of (1) finding the optimal set of cooperating neighbors with minimum control traffic, (2) minimizings the overall cooperative sensing delay, (3) selecting independent users for cooperation under correlated shadowing, and (4) excluding unreliable users and data from cooperation. Simulation results show that the RLCS method reduces the overhead of cooperative sensing while effectively improving the detection performance to combat correlated shadowing. Moreover, it adapts to environmental change and maintains comparable performance under the impact of primary user activity, user movement, user reliability, and control channel fading.     

基于父节点的XML查询优化算法

本文提出了基于父节点的XML查询优化算法,它主要利用关键词的顺序循环查找父节点,把查找出来的父节点集合求交集,所得的父节点交集集合中的元素即为最小子树根节点,最后根据所得出的最小子树根节点得到用户所需的最紧致片段。通过选取经典的INEX数据集算法进行测试。实验结果表明,与传统的XML查询优化算法相比,基于父节点的XML查询优化算法有较高的准确率,更能满足用户需求。