GDG:一种基于逆支配点集的top-k高效查询索引方法

考虑偏好top-k计算问题,提出一种整合网格索引和DG索引的Gridded Dominant Graph(GDG)混合索引结构.首先,提出基于数据点逆支配点集性质的剪枝自由点方法,该方法大大减少了构建索引中的数据点及查询时可能访问的数据点.通过网格索引高效地计算逆支配点集,并得出网格中"k-最大运算区域"和"k-最大查找区域",分别在建立索引和top-k查询阶段近似地剪枝自由点.然后,分析了查询索引阶段层次式索引(如dominant graph(DG))在同一层次中无序访问数据点的不足,通过增加网格索引而使访问有序.计算网格概要信息并将网格单元按函数分值排序,使层次内数据点依据网格单元顺序而访问有序.由于附加的网格索引增加计算和存储开销较少,同时性能有较大提升,所以GDG适用性强.理论分析和实验结果均验证了上述方法的有效性.     

面向移动对象的高效组最近邻居查询方法

组最近邻居查询是移动对象数据库重要的查询类型之一。本文提出了一种基于网格索引结构的剪枝搜索策略,将空间区域划分为网格,通过对象点的网格单元标识减少组最近邻居查询所需要的节点访问代价。用步长迭代法得到查询对象集的质心,提出了一种移动对象组最近邻居查询MOGNN算法,采用更精确的裁剪搜索空间准则,减少了查询所需要访问的节点数目。实验结果与分析表明,基于网格索引的MOGNN查询算法具有良好的查询性能。     

数据流上连续动态skyline查询研究

skyline查询能够从大规模数据集上计算满足多个标准的最优点.数据流上的skyline计算是数据流上最基本的查询操作之一,对于很多在线应用具有非常重要的意义,尤其在移动计算环境、网络监控、通信网络以及传感器网络等领域.不同于大部分传统的skyline研究,主要研究数据流上约束skvline和动态skyline计算问题.采用网格索引存储元组,提出了GBDS算法用于计算和维护动态skvline.通过为每个查询定义影响区域,使得在元组到达和失效时需要处理的元组个数最小化.理论分析和实验结果证明了提出方法的有效性.     

不确定数据流上Top-k异常点查询算法

近几年,随着数据流和不确定数据的产生,不确定数据流上的异常点检测成为新的研究热点。然而,现有的不确定数据的异常点定义中涉及3个参数,这对于用户是非常难设定的,以致不能查询到适合的异常点。在大多时候,用户更想知道最可能是异常点的对象,因此提出了不确定数据流上的top-k异常点查询算法。该算法通过估计数据对象异常点的概率范围而进行剪枝,从而减少了一些不必要的计算,同时增量地计算数据对象异常点的概率范围。在真实数据集和合成数据集上进行了一系列的模拟实验,证明了算法的性能。     

基于网格索引的连续Skyline计算方法

考虑按任意顺序随机增删的数据流场景下连续Skyline计算问题,首先基于已有工作提出了一个基本算法BCSC;然后基于"影响区域"的观察,提出了一个基于网格索引数据结构的算法GICSC,其基本思想为:(1)将数据空间划分为若干大小相等的网格,采用网格索引方法对数据点进行组织和管理;(2)用网格将数据空间表示为自由区域和影响区域两部分,发生在自由区域中的数据变化可以从理论上保证不影响计算结果,因此仅需对落于影响区域的数据增删进行运算,从而降低数据规模;(3)算法的计算模块通过逐步扩展的方法,无需遍历全部数据便可获得初始的Skyline集合及影响区域,维护模块通过类似方法计算数据变化对Skyline集合的影响,同时动态更新影响区域的大小.由于没有对数据流特性进行假设限制,因此BCSC和GICSC算法具有更广泛的适应性.理论分析和实验结果均验证了上述方法的有效性.     

空间资源索引与top-k查询研究

以空间资源索引结构R-tree为基础, 考虑人们对空间资源能力指标的要求, 利用道路网络模型进行空间距离的计算, 提出了一种包含能力维度信息的空间资源索引结构和top-k查询算法, 并与传统遍历算法进行对比实验, 验证了查询算法的有效性。     

数据流环境下基于距离的离群点检测算法

面向滑动窗口的连续离群点检测问题是数据流管理领域中的重要问题.该问题在信用卡欺诈检测、网络入侵防御,地质灾害预警等诸多领域发挥着重要作用.现有算法大多需要利用范围查询判断对象之间的位置关系,而范围查询的查询代价大,无法满足实时性要求.本文提出基于滑动窗口模型下的查询处理框架GBEH(grid-based excepted heap).首先,它以网格为基础构建索引GQBI(grid queue based index)管理数据流.该索引一方面维护数据流之间的位置关系,另一方面利用队列维护数据流的时序关系.其次, GBEH提出离群点检测算法PBH(priority based heap).该算法利用查询范围与网格单元格的相交面积计算该单元格中包含于查询范围对象数目的数学期望,并以此为基础构建基于小顶堆执行范围查询,从而有效降低范围查询代价,实现高效检测.理论分析和实验验证GBEH的高效性和稳定性.     

基于网格的数据流连续约束Skyline处理技术研究

作为数据流上的一种重要查询,skyline对于很多在线应用都非常重要,包括移动运算环境、网络监控、传感器网络、股票交易等。与大多数数据流skyline处理技术不同,本文着重于约束skyline的处理。约束skyline支持用户定义在某些属性上的偏好,系统中存在多个约束skyline查询,为skyline查询处理技术带来了新的挑战。为了在高速数据流上对约束skyline进行高效处理,本文使用了一种网格索引存储元组,并提出两个算法用于计算和维护skyline集合,我们还为每个查询定义了影响区域,以减少在新元组到达和旧元组失效时需要处理的网格数目。理论分析和实验证明了该方法的有效性。     

基于相对距离哈希方法的一种高维索引

人们设计了许多索引以有效地处理高维空间中的近邻查询和区域查询。已经证明,维数较高时利用高维索引处理这两类查询几乎不可能比线性扫描快。提出了一种两层索引以自适应地识别数据集中的聚簇;数据集具有聚簇特性时,用该索引处理邻近查询和区域查询比现有的索引结构快;对其他数据集,利用该索引处理邻近查询和区域查询与线性扫描大致相当。该索引的上层结构将一些参考点组织成一棵二叉树,下层结构是一系列动态哈希表。数据集中的数据点根据它们到参考点的相对距离被哈希到相应的哈希桶中。查询处理时用查询点到参考点的距离进行剪除搜索。实验表明,提出的索引结构具有良好的性能。     

基于网格索引的数据流子空间概率轮廓查询

在数据流子空间上的连续概率轮廓查询(CPSQS)基础上,提出一种基于网格索引结构的概率轮廓查询算法。采用适合于子空间轮廓计算的网格索引结构,将数据空间划分成若干个格,利用格间的支配关系,减少对象之间的比较次数。同时挖掘全空间与子空间上格的概率上下界关系,设计有效的剪枝策略提高CPSQS算法的性能。理论分析和实验结果表 明,该算法能满足实际应用中用户的个性化查询要求,降低查询响应时间。     

Efficient processing of top-k dominating queries in distributed environments

Due to the recent massive data generation, preference queries are becoming an increasingly important for users because such queries retrieve only a small number of preferable data objects from a huge multi-dimensional dataset. A top-k dominating query, which retrieves the k data objects dominating the highest number of data objects in a given dataset, is particularly important in supporting multi-criteria decision making because this query can find interesting data objects in an intuitive way exploiting the advantages of top-k and skyline queries. Although efficient algorithms for top-k dominating queries have been studied over centralized databases, there are no studies which deal with top-k dominating queries in distributed environments. The recent data management is becoming increasingly distributed, so it is necessary to support processing of top-k dominating queries in distributed environments. In this paper, we address, for the first time, the challenging problem of processing top-k dominating queries in distributed networks and propose a method for efficient top-k dominating data retrieval, which avoids redundant communication cost and latency. Furthermore, we also propose an approximate version of our proposed method, which further reduces communication cost. Extensive experiments on both synthetic and real data have demonstrated the efficiency and effectiveness of our proposed methods.     

概率Top-κ查询的层次索引

由于在经济、军事等领域的广泛应用,不确定数据的查询处理技术成为近年来数据库领域的研究热点.概率top-κ查询根据打分函数和概率两个维度来对数据进行排序,因此具有多种查询语义.作为I/O密集型查询,概率top-κ查询需要具备一定通用性的索引技术来提高查询效率.本文从分析概率top-κ查询满足的性质入手,分别基于skyline和支配频率的概念,提出两种层次索引.通过理论分析和实验证明了满足特定性质的概率top-κ查询均可以利用这两种索引来提高I/O效率,其中基于支配频率的索引具有更好的鲁棒性.     

Efficient Process of Top-k Range-Sum Queries over Multiple Streams with Minimized Global Error

Due to the resource limitation in the data stream environments, it has been reported that answering user queries according to the wavelet synopsis of a stream is an essential ability of a Data Stream Management System (DSMS). In the literature, recent research has been elaborated upon minimizing the local error metric of an individual stream. However, many emergent applications, such as stock marketing and sensor detection, also call for the need of recording multiple streams in a commercial DSMS. As shown in our thorough analysis and experimental studies, minimizing global error in multiple-stream environments leads to good reliability for DSMS to answer the queries; in contrast, only minimizing local error may lead to significant loss of query accuracy. As such, we first study in this paper the problem of maintaining the wavelet coefficients of multiple streams within collective memory so that the predetermined global error metric is minimized. Moreover, we also examine a promising application in the multistream environment, i.e., the queries for top-k range sum. We resolve the problem of efficient top-k query processing with minimized global error by developing a general framework. For the purposes of maintaining the wavelet coefficients and processing top-k queries, several well-designed algorithms are utilized to optimize the performance of each primary component of this general framework. We also evaluate the proposed algorithms empirically on real and simulated data streams and show that our framework can process top-k queries accurately and efficiently.     

Discovering and Exploiting Causal Dependencies for Robust Mobile Context-Aware Recommenders

Due to the resource limitation in the data stream environments, it has been reported that answering user queries according to the wavelet synopsis of a stream is an essential ability of a data stream management system (DSMS). In the literature, recent research has been elaborated upon minimizing the local error metric of an individual stream. However, many emergent applications such as stock marketing and sensor detection also call for the need of recording multiple streams in a commercial DSMS. As shown in our thorough analysis and experimental studies, minimizing global error in multiple-stream environments leads to good reliability for DSMS to answer the queries. In contrast, only minimizing local error may lead to a significant loss of query accuracy. As such, we first study in this paper the problem of maintaining the wavelet coefficients of multiple streams within collective memory so that the predetermined global error metric is minimized. Moreover, we also examine a promising application in the multistream environment, that is, the queries for top-k range sum. We resolve the problem of efficient top-k query processing with minimized global error by developing a general framework. For the purposes of maintaining the wavelet coefficients and processing top-k queries, several well- designed algorithms are utilized to optimize the performance of each primary component of this general framework. We also evaluate the proposed algorithms empirically on real and simulated data streams and show that our framework can process top-k queries accurately and efficiently.     

The Threshold Algorithm: From Middleware Systems to the Relational Engine

The answer to a top-k query is an ordered set of tuples, where the ordering is based on how closely each tuple matches the query. In the context of middleware systems, new algorithms to answer top-k queries have been recently proposed. Among these, the threshold algorithm (TA) is the most well-known instance due to its simplicity and memory requirements. TA is based on an early-termination condition and can evaluate top-k queries without examining all the tuples. This top-k query model is prevalent not only over middleware systems, but also over plain relational data. In this work, we analyze the challenges that must be addressed to adapt TA to a relational database system. We show that, depending on the available indices, many alternative TA strategies can be used to answer a given query. Choosing the best alternative requires a cost model that can be seamlessly integrated with that of current optimizers. In this work, we address these challenges and conduct an extensive experimental evaluation of the resulting techniques by characterizing which scenarios can take advantage of TA-like algorithms to answer top-k queries in relational database systems     

分布式网络中的一种高效top-k求解方法研究

提出了一种新的算法,来解决在分布式的环境中top-k求解问题（求出全局数值最大的前k名）。之前的研究,例如TA、TPUT、HT算法,都会消耗大量的带宽。KLEE算法虽然能够大大地减少带宽的消耗,却不能给出精确解。而提出的算法FT由于添加了一个预处理阶段并且使用了histogram bloom技术,即能有效地减少带宽的消耗,又能给出精确解。实现了FT和相关的算法,并进行了全面的比较。比较是建立在真实的数据集和根据不同情况合成的数据集的基础上的。实验结果显示FT在带宽消耗上面,相对于其他算法有很大的改进和优势。     

Evaluating refined queries in top-k retrieval systems

In many applications, users specify target values for certain attributes/features without requiring exact matches to these values in return. Instead, the result is typically a ranked list of "top k" objects that best match the specified feature values. User subjectivity is an important aspect of such queries, i.e., which objects are relevant to the user and which are not depends on the perception of the user. Due to the subjective nature of top-k queries, the answers returned by the system to an user query often do not satisfy the users need right away, either because the weights and the distance functions associated with the features do not accurately capture the users perception or because the specified target values do not fully capture her information need or both. In such cases, the user would like to refine the query and resubmit it in order to get back a better set of answers. While there has been a lot of research on query refinement models, there is no work that we are aware of on supporting refinement of top-k queries efficiently in a database system. Done naively, each "refined" query can be treated as a "starting" query and evaluated from scratch. We explore alternative approaches that significantly improve the cost of evaluating refined queries by exploiting the observation that the refined queries are not modified drastically from one iteration to another. Our experiments over a real-life multimedia data set show that the proposed techniques save more than 80 percent of the execution cost of refined queries over the naive approach and is more than an order of magnitude faster than a simple sequential scan.     

结构化网络中聚合Top-K查询优化技术

top-k查询在分布式环境中引起越来越多的关注,但是现存的一些top-k算法大都只适用于集中式网络.提出了一个解决分布式网络中top-k查询的新方法—Histogram-Container算法(简称为HC算法),它不仅网络延迟小,网络带宽花费少,而且能够运行在任何结构的分布式网络中.本文将基于一个树型拓扑网络来说明如何使用本地的直方图和bloom filter信息来优化查询,以及如何在中间节点进行部分结果的合并.实验评估和性能分析表明HC算法在网络带宽消耗和查询响应时间方面要优于其他同类方法.     

Efficient Skyline and Top-k Retrieval in Subspaces

Skyline and top-k queries are two popular operations for preference retrieval. In practice, applications that require these operations usually provide numerous candidate attributes, whereas, depending on their interests, users may issue queries regarding different subsets of the dimensions. The existing algorithms are inadequate for subspace skyline/top-k search because they have at least one of the following defects: 1) they require scanning the entire database at least once, 2) they are optimized for one subspace but incur significant overhead for other subspaces, or 3) they demand expensive maintenance cost or space consumption. In this paper, we propose a technique SUBSKY, which settles both types of queries by using purely relational technologies. The core of SUBSKY is a transformation that converts multidimensional data to one-dimensional (1D) values. These values are indexed by a simple B-tree, which allows us to answer subspace queries by accessing a fraction of the database. SUBSKY entails low maintenance overhead, which equals the cost of updating a traditional B-tree. Extensive experiments with real data confirm that our technique outperforms alternative solutions significantly in both efficiency and scalability.     

不确定数据库中概率top-k和排序查询算法

传感器网络等技术的广泛应用产生了大量不确定数据。近年来,对于不确定数据的处理和查询成为数据库和数据挖掘领域研究的热点。其中,传统关系数据库中的top-k查询和排序查询怎样拓展到不确定数据是其中的焦点之一。研究近年来提出的不确定数据库上top-k查询和排序查询算法,归纳和比较目前各种不同查询算法所适应的语义世界和应用场景,并详细分析各种算法的执行效率和算法复杂度。另外,对于不确定数据top-k查询和排序查询所面临的挑战和可能的研究方向进行了总结。