概率数据上基于EMD距离的并行Top-k相似性连接算法

以无线传感器网络为代表的新型数据应用和以图像处理为基础的传统数据应用都产生了大规模的概率数据.在概率数据的管理中,Top-k相似性连接操作返回最相似的k 对概率数据,具有重要应用价值.直方图是最常用的概率数据模型之一,而EMD（Earth Mover’s Distance）距离因其较强的鲁棒性可更准确地量化直方图概率数据之间的相似性.然而EMD距离的计算却具有三次方的时间复杂度,给基于EMD距离的Top-k 相似性连接带来巨大挑战.基于流行的MapReduce并行处理框架,利用EMD距离对偶线性规划问题的优良特性,提出了两种大规模概率数据上基于EMD距离的Top-k相似性连接算法.首先提出基于块嵌套循环连接思想的基本解决方法,命名为Top-k BNLJ算法.进而改进数据划分策略,提出基于数据局部性进行数据划分的Top-k DLPJ 算法,有效降低了MapReduce作业执行过程中的数据传输量.使用大规模真实数据集对两种算法进行评估,证实了本文提出的Top-k DLPJ算法的高效性和处理大规模数据集时的良好扩展性.     

关系数据库中支持语义的Top-K关键字搜索

为了增强关系数据库中的关键字搜索查询结果,考虑了多表之间以及元组之间的语义关系,提出了一种语义评分函数.该语义评分函数不仅涵盖了当前的评分思想,并且加入新指标来衡量查询结果与查询关键字之间的相关性.基于该评分函数,提出两种以数据块为处理单位的Top-K搜索算法,分别为BA(blocking algorithm)算法和EBA(early-stopping blocking algorithm)算法.EBA在BA基础上引入了过滤域值,以便尽早终止算法的迭代次数.最后实验结果显示语义评分函数保证了     

Top-k相似连接算法性能优化

相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用.现有相似连接算法有两种类型：基于相似度阈值的相似连接和Top-k相似连接.Top-k连接算法非常适合于相似度阈值未知的应用场景,目前最为有效的Top-k相似连接算法是Xiao等人提出的Topk-join.为了解决Topk-join中存在的性能问题,提出了一种Top-k相似连接算法Opt-join,该算法将Token批处理技术集成在现有的事件驱动框架中,以降低前缀事件的处理代价;通过置换哈希查找与过滤操作的执行位置来降低哈希查找代价,并理论证明了该置换的正确性.实验结果表明：与Topk-join算法相比,Opt-join取得了1.28倍~3.09倍的性能提升.实验数据还显示：随着数据长度的增加或k值的增长,Opt-join的性能优势有不断增加的趋势.     

一种无线传感器网络中的多维K-NN查询优化算法

提出了一种基于过滤器的无线传感器网络多维K-NN查询优化算法PREDICTOR.过滤器是设置在节点端的取值分布区间,用来屏蔽节点发送属于区间内的数据,从而节省节点能耗.在服务器端保存有各节点的历史样本数据,根据K-NN查询请求和样本数据的分布范围为节点定义过滤器.提出了3种优化策略:(1) 过滤器覆盖区间大小分配策略的动态调整方法,使得进入最终查询结果可能性小的节点拥有较大的覆盖区间;(2) 节点间过滤器共享方法,使得历史样本数据相近的节点使用相同的过滤器;(3) 过滤器压缩传输方法,减少为不同K-NN查询更新过滤器的代价.通过实验评价,验证了PREDICTOR算法的能量有效性,与朴素算法相比,极大地降低了数据传输量.     

用户群体满意度最大化的Top-k在线服务评价

考虑用户评价准则不一致的在线服务评价通常以服务的完整排序作为评价结果,而不是选择出使用户群体满意度最大的Top-k在线服务集合,使评价结果难以满足Top-k在线服务评价场景的合理性和公平性需求.为此,提出了一种用户群体满意度最大化的Top-k在线服务评价方法.该方法首先定义用户群体满意度指标,以衡量选择的k个在线服务的合理性;其次,考虑用户评价准则不一致及用户偏好信息不完整的情况,采用Borda规则将用户对在线服务的偏好关系构造为用户-服务满意度矩阵;然后借鉴Monroe比例代表思想,将Top-k在线服务评价问题建模为寻找最大化用户群体满意度的在线服务集合的优化问题;最后采用贪心算法对该优化问题进行求解,将得到的在线服务集合作为Top-k评价结果.通过理论分析和实验验证了该方法的合理性和有效性.理论分析表明,该方法满足Top-k在线服务评价所需的比例代表性和公平性.同时,实验结果也表明,该方法能够在合理的时间内获得接近用户群体满意度理想上界的评价结果,可以有效地辅助用户群体做出正确的服务选择决策.另外,该方法还可以在用户偏好不完整的情况下实现Top-k在线服务评价.     

一种基于K-Means局部最优性的高效聚类算法

K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率.     

基于关键字密度的XML关键字检索

关键字检索具有友好的用户操作体验,该检索方式已在文本信息检索领域得到了广泛而深入的应用.对XML数据采用关键字检索是目前研究的热点.基于查询语义的XML关键字检索方法存在返回大量与用户查询意图无关的查询片段或者丢失符合用户查询意图的片段这两个问题.针对这些问题,在考虑LCA横向和纵向两个维度的基础上,提出了用户查询意图与LCA相关性的两个规则,根据两个规则定义了LCA的边密度和路径密度,建立了综合的LCA节点评分公式,最后设计TopLCA-K算法对LCA进行排名,并利用中心位置索引CI提高了TopLCA-K算法的效率.实验结果显示,利用所提出的方法返回的查询节点更加符合用户需求.     

无线传感器网络中基于Top-|K|查询分布式数据重构方法

针对分簇结构或多Sink节点的无线传感器网络应用场景,提出了一种基于Top-|K|查询的分布式数据重构方法.该方法包括分布式迭代硬阈值算法和基于双阈值的分布式Top-|K|查询算法两个部分.其中,管理节点和成员节点同时运行分布式迭代硬阈值算法,以分布式方式实现迭代硬阈值计算.同时,管理节点和成员节点运行基于双阈值的分布式Top-|K|查询算法,以分布式方式实现前一算法中查询绝对值最大的前K项元素和操作.实验结果表明,该方法的数据重构性能与现有方法无明显差异,同时能够有效地减少管理节点和成员节点之间的交互次数,并且降低网络中传输的数据量.     

一种针对反向空间偏好top-k查询的高效处理方法

随着地理位置定位技术的蓬勃发展,基于在线位置服务技术的应用也越来越多.提出一种查询类型——反向空间偏好top-k查询.类似于传统的反向空间top-k查询,对于给定的空间查询对象,该查询返回使该对象满足top-k属性得分的那些用户.但不同的是,该对象的属性不是自身具有的特性,而是通过计算该对象与其他偏好对象之间的空间关系（如距离）而确定.这种查询在市场分析等许多重要领域具有需求,例如,根据查询结果,分析出某个地区中某个设施受欢迎的程度.但是,由于大量空间对象的存在导致对象之间空间关系的计算代价非常高,如何实时地计算出对象的空间属性得分,给查询处理带来很大的挑战.针对该问题提出优化的查询处理算法包括：数据集剪枝、数据集批量处理、基于权重的用户分组等策略.通过理论分析和充分的实验验证,证明了所提出方法的有效性.与普通方法相比,这些方法能够大幅度提高查询处理的执行时间和I/O效率.     

面向移动对象连续k近邻查询的双层索引结构

移动对象连续k近邻（CKNN）查询是指给定一个连续移动的对象集合,对于任意一个k近邻查询q,实时计算查询q的k近邻并在查询有效时间内对查询结果进行实时更新.现实生活中,交通出行、社交网络、电子商务等领域许多基于位置的应用服务都涉及移动对象连续k近邻查询这一基础问题.已有研究工作解决连续k近邻查询问题时,大多需要通过多次迭代确定一个包含k近邻的查询范围,而每次迭代需要根据移动对象的位置计算当前查询范围内移动对象的数量,整个迭代过程的计算代价占查询代价的很大部分.为此,提出了一种基于网络索引和混合高斯函数移动对象分布密度的双重索引结构（grid GMM index,GGI）,并设计了移动对象连续k近邻增量查询算法（incremental search for continuous k nearest neighbors,IS-CKNN）.GGI索引结构的底层采用网格索引对海量移动对象进行维护,上层构建混合高斯模型模拟移动对象在二维空间中的分布.对于给定的k近邻查询q,IS-CKNN算法能够基于混合高斯模型直接确定一个包含q的k近邻的查询区域,减少了已有算法求解该区域的多次迭代过程;当移动对象和查询q位置发生变化时,进一步提出一种高效的增量查询策略,能够最大限度地利用已有查询结果减少当前查询的计算量.最后,在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验,充分验证了算法的性能.     

Top-k dominating queries on incomplete large dataset

Top-k dominating (TKD) query is one of the methods to find the interesting objects by returning the k objects that dominate other objects in a given dataset. Incomplete datasets have missing values in uncertain dimensions, so it is difficult to obtain useful information with traditional data mining methods on complete data. BitMap Index Guided Algorithm (BIG) is a good choice for solving this problem. However, it is even harder to find top-k dominance objects on incomplete big data. When the dataset is too large, the requirements for the feasibility and performance of the algorithm will become very high. In this paper, we proposed an algorithm to apply MapReduce on the whole process with a pruning strategy, called Efficient Hadoop BitMap Index Guided Algorithm (EHBIG). This algorithm can realize TKD query on incomplete datasets through BitMap Index and use MapReduce architecture to make TKD query possible on large datasets. By using the pruning strategy, the runtime and memory usage are greatly reduced. What’s more, we also proposed an improved version of EHBIG (denoted as IEHBIG) which optimizes the whole algorithm flow. Our in-depth work in this article culminates with some experimental results that clearly show that our proposed algorithm can perform well on TKD query in an incomplete large dataset and shows great performance in a Hadoop computing cluster.

     

Reducing network traffic in unstructured P2P systems using Top-k queries

A major problem of unstructured P2P systems is their heavy network traffic. This is caused mainly by high numbers of query answers, many of which are irrelevant for users. One solution to this problem is to use Top-k queries whereby the user can specify a limited number (k) of the most relevant answers. In this paper, we present FD, a (Fully Distributed) framework for executing Top-k queries in unstructured P2P systems, with the objective of reducing network traffic. FD consists of a family of algorithms that are simple but effective. FD is completely distributed, does not depend on the existence of certain peers, and addresses the volatility of peers during query execution. We validated FD through implementation over a 64-node cluster and simulation using the BRITE topology generator and SimJava. Our performance evaluation shows that FD can achieve major performance gains in terms of communication and response time. Recommended by: Sunil Prabhakar Work partially funded by the ARA Massive Data of the Agence Nationale de la Recherche.     

Supporting top-<Emphasis Type="Italic">k</Emphasis><Emphasis Type="Italic">join</Emphasis> queries in relational databases

Ranking queries, also known as top-k queries, produce results that are ordered on some computed score. Typically, these queries involve joins, where users are usually interested only in the top-k join results. Top-k queries are dominant in many emerging applications, e.g., multimedia retrieval by content, Web databases, data mining, middlewares, and most information retrieval applications. Current relational query processors do not handle ranking queries efficiently, especially when joins are involved. In this paper, we address supporting top-k join queries in relational query processors. We introduce a new rank-join algorithm that makes use of the individual orders of its inputs to produce join results ordered on a user-specified scoring function. The idea is to rank the join results progressively during the join operation. We introduce two physical query operators based on variants of ripple join that implement the rank-join algorithm. The operators are nonblocking and can be integrated into pipelined execution plans. We also propose an efficient heuristic designed to optimize a top-k join query by choosing the best join order. We address several practical issues and optimization heuristics to integrate the new join operators in practical query processors. We implement the new operators inside a prototype database engine based on PREDATOR. The experimental evaluation of our approach compares recent algorithms for joining ranked inputs and shows superior performance.Received: 23 December 2003, Accepted: 31 March 2004, Published online: 12 August 2004Edited by: S. AbiteboulExtended version of the paper published in the Proceedings of the 29th International Conference on Very Large Databases, VLDB 2003, Berlin, Germany, pp 754-765     

Optimizing target selection complexity of a recommendation system by skyline query and multi-criteria decision analysis

Various factors related to user consideration cause a target selection problem that may lead users to receive unexpected or confusing results. Traditionally, the recommendation system is constructed to help the user filter out unrelated targets and recommend targets that may be of interest to the user. However, the complexity of target selection requires a more advanced decision-making analysis to offer support. Determining how to optimize the target selection complexity of a recommendation system has become a critical challenge. This study proposes a novel approach using skyline query and multi-criteria decision analysis to recommend Top-k targets for user selection. Skyline query domination reduces the complexity of target selection by filtering out non-dominant candidates and keeping the dominant candidates for multi-criteria decision analysis. After the skyline query processing, the multi-criteria decision analysis is optimized, producing a Top-k ranking order of the candidate targets. The experiment illustrates an empirical case study to verify the effectiveness of the proposed approach. The contribution is optimizing the target selecting complexity of the recommendation system to solve the target selection problem.

     

Finding the K highest-ranked answers in a distributed network

In this paper, we present an algorithm for finding the k highest-ranked (or Top-k) answers in a distributed network. A Top-K query returns the subset of most relevant answers, in place of all answers, for two reasons: (i) to minimize the cost metric that is associated with the retrieval of all answers; and (ii) to improve the recall and the precision of the answer-set, such that the user is not overwhelmed with irrelevant results. Our study focuses on multi-hop distributed networks in which the data is accessible by traversing a network of nodes. Such a setting captures very well the computation framework of emerging Sensor Networks, Peer-to-Peer Networks and Vehicular Networks. We present the Threshold Join Algorithm (TJA), an efficient algorithm that utilizes a non-uniform threshold on the queried attribute in order to minimize the transfer of data when a query is executed. Additionally, TJA resolves queries in the network rather than in a centralized fashion which further minimizes the consumption of bandwidth and delay. We performed an extensive experimental evaluation of our algorithm using a real testbed of 75 workstations along with a trace-driven experimental methodology. Our results indicate that TJA requires an order of magnitude less communication than the state-of-the-art, scales well with respect to the parameter k and the network topology.     

Distributed top-<Emphasis Type="Italic">k</Emphasis> aggregation queries at large

Top-k query processing is a fundamental building block for efficient ranking in a large number of applications. Efficiency is a central issue, especially for distributed settings, when the data is spread across different nodes in a network. This paper introduces novel optimization methods for top-k aggregation queries in such distributed environments. The optimizations can be applied to all algorithms that fall into the frameworks of the prior TPUT and KLEE methods. The optimizations address three degrees of freedom: 1) hierarchically grouping input lists into top-k operator trees and optimizing the tree structure, 2) computing data-adaptive scan depths for different input sources, and 3) data-adaptive sampling of a small subset of input sources in scenarios with hundreds or thousands of query-relevant network nodes. All optimizations are based on a statistical cost model that utilizes local synopses, e.g., in the form of histograms, efficiently computed convolutions, and estimators based on order statistics. The paper presents comprehensive experiments, with three different real-life datasets and using the ns-2 network simulator for a packet-level simulation of a large Internet-style network.