MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

MapReduce框架下基于超平面投影划分的Skyline计算

近年来,Skyline计算在决策应用中起着越来越重要的作用.针对单机处理的研究已较为成熟.现今大数据爆炸,Skyline计算面临着大数据处理的问题.MapReduce是一个并行模型,广泛应用于数据密集型应用处理中.众所周知,MapReduce处理要求任务是可分解的.Skyline计算在MapReduce上执行时,分解任务的方法有网格划分、基于角度的划分等.网格划分仅在数据维度较低时表现良好;基于角度的划分适用于低维和高维数据,但在划分前需要一个复杂并且费时的坐标转换过程.现采用一种与基于角度的划分类似的基于超平面投影的划分来分解数据集,这种划分适用于低维和高维数据,而且其在划分前的坐标转换较为简单.根据超平面投影的划分提出了一种在MapReduce上处理Skyline计算的算法MR-HPP(MapReduce with hyperplane-projections-based partition),并在该算法的过滤阶段提出了一种有效的过滤算法PSF(presorting filter).大量基于Hadoop平台的对比实验表明该算法的准确性、高效性和稳定性.     

海量高维向量的并行Top-k连接查询

在很多应用领域中,向量的Top-k连接查询是一种很重要的操作,给定两个向量集合R和S,Top-k连接查询要求从R和S中返回距离最小的前k个向量对.由于数据的海量性和高维特性,传统的集中式算法已经无法在可接受的时间内完成连接查询任务.MapReduce作为一个并行处理框架,能够有效地处理大规模数据.由于其高可扩展性、高可用性等特点,MapReduce已经成为海量数据处理的首选实现方案,在很多领域都得到了广泛的应用.文中基于分段累积近似法对高维向量进行降维,然后利用符号累积近似法对高维向量进行分组;在此基础上,结合MapReduce框架,提出了基于SAX的并行Top-k连接查询算法.实验表明,文中所提方案具有良好的性能和扩展性.     

基于MapReduce的Skyline查询处理算法

Skyline查询是一个典型的多目标优化查询,在多目标优化、数据挖掘等领域有着广泛的应用。现有的Skyline查询处理算法大都假定数据集存放在单一数据库服务器中,查询处理算法通常也被设计成针对单一服务器的串行算法。随着数据量的急剧增长,特别是在大数据背景下,传统的基于单机的串行Skyline算法已经远远不能满足用户的需求。基于流行的分布式并行编程框架MapReduce,研究了适用于大数据集的并行Skyline查询算法。针对影响MapReduce计算的因素,对现有基于角度的划分策略进行了改进,提出了Balanced Angular划分策略;同时,为了减少Reduce过程的计算量,提出了在Map端预先进行数据过滤的策略。实验结果显示所提出的Skyline查询算法能显著提升系统性能。     

基于ImpaIa的大数据查询分析计算性能研究

分析了 Cloudera 公司推出的 Impala 实时查询引擎原理与架构,并深入比较 Impala 与传统 MapReduce 的性能与特点,针对 Impala 进行复杂大数据处理方面的不足,提出了 MapReduce 与 Impala 结合的大数据处理方法,通过使用 MapReduce 对 Impala 的输入数据进行预处理,利用 MapReduce 在复杂作业处理方面的长处弥补了Impala 在这方面的不足。最后对电信手机上网日志进行大数据查询和分析计算实验,实验结果表明,在大数据查询性能方面,基于 MapReduce 与 Impala 结合的大数据处理速度比传统 MapReduce 快了一倍。特别地,在迭代查询实验中,基于 MapReduce 与 Impala 结合的处理方法超过传统 MapReduce 方法八倍以上。基于 MapReduce与 Impala 结合的处理方法在单次查询中的效率仍然高于传统 MapReduce;而在迭代查询中,MapReduce 与 Impala结合的处理方法远远地超过了 MapReduce。因此,MapReduce 与 Impala 结合的处理方法能够发挥 Impala 和 Ha-doop 各自的优点,让处理效率远超传统 MapReduce,对于复杂的大数据处理的能力高于 Impala。     

基于不规则区域划分方法的k-Nearest Neighbor查询算法

随着越来越多的数据累积, 对数据处理能力和分析能力的要求也越来越高. 传统k-Nearest Neighbor (kNN)查询算法由于其容易导致计算负载整体不均衡的规则区域划分方法及其单个进程或单台计算机运行环境的较低数据处理能力. 本文提出并详细介绍了一种基于不规则区域划分方法的改进型kNN查询算法, 并利用对大规模数据集进行分布式并行计算的模型MapReduce对该算法加以实现. 实验结果与分析表明, MapReduce框架下基于不规则区域划分方法的kNN查询算法可以获得较高的数据处理效率, 并可以较好的支持大数据环境下数据的高效查询.     

基于MapReduce的XML结构连接处理

可扩展标记语言(extensible markup language,XML)已经成为Web上数据表达和数据交换的事实标准,Hadoop已成为云计算和大数据处理典型支撑框架之一,基于Hadoop MapReduce来实现XML查询处理十分必要。为了实现基于MapReduce的XML查询处理,首先实现了区间编码、前缀编码和层次编码等3种不同的XML数据编码方式,以此为基础来研究和实现基于MapReduce的XML结构连接处理。为查询处理建立了代价模型,通过代价估算获得优化的查询计划树。最后开展了XML查询处理实验评估,结果表明相对其他两种XML编码方式,区间编码方式下实现的查询处理速度较快,基于代价估算的优化方法能进一步有效地提高XML查询处理性能。     

基于γ划分策略的高维数据索引结构的研究

提出了一种压缩金字塔树,将d维数据空间划分为2d个金字塔,由于在低维空间中无效的信息在高维数据空间中往往无效,采用γ划分策略对低维空间中的数据进行压缩,减小索引结构,克服了金字塔技术的缺点。给出了压缩金字塔树的构造方法以及基于压缩金字塔树的查询算法。实验证明,压缩金字塔树是一种有效的空间划分策略,在高维稀疏空间有良好的性能。     

基于γ划分策略的高维索引结构

提出了一种压缩金字塔树,将d雏数据空间划分为2d个金字塔,由于在低维空间中无效的信息在高维数据空间中往往无效,采用γ划分策略对低维空间中的数据进行压缩,减小索引结构,克服了金字塔技术的缺点.给出了压缩金字塔树的构造方法以及基于压缩金字塔树的查询算法.实验证明,压缩金字塔树是一种有效的空间划分策略,在高维稀疏空间有良好的性能.     

混合MapReduce环境下大数据划分的查询优化

在MapReduce与数据库的混合架构中,数据划分是影响查询性能的重要因素。对于开销最大的连接和聚集操作,采用混合MapReduce的方式实现,需要大规模数据的跨结点传输,网络传输和I/O开销巨大。为了减少传输的数据量,并提高连接操作的查询效率,提出了划分建议器模型。实现了MapReduce和数据库混合架构上的划分建议器,并计算划分代价,生成最优的数据划分方案,提高了系统效率。为了减少查询时间,依据划分建议器模型,提出了基于代价优先的生成策略和空间搜索算法,减少了划分建议器生成最优方案的时间。通过实验验证了划分建议器的有效性,使系统的整体查询代价最小,显著提高了系统性能。     

利用分区和距离实现高维空间快速KNN查询

在高维空间KNN查询算法中,近似向量和一维转换表示法能有效克服维数灾难,结合这两种思想,提出一种基于区位码和距离的索引结构(BD)以实现快速KNN查询.根据高维空间向量分布特点,合理分区使得大量分布在空间表面的点尽可能地划分到不同的分区中,提高检索剪枝效率.引入区位码概念和转换函数,将高维向量近似表示并转换为一维数值形式,组织成B 树索引.利用快速KNN查询算法,实现两层过滤,缩小搜索范围,降低树搜索代价.采用模拟数据和真实数据,大量实验验证了BD比其他同类索引具有更高的检索效率.     

BC-iDistance:基于位码的优化高维索引

在高维空间KNN查询算法中,近似向量和一维转换表示法能有效克服维数灾难,本文结合这两种思想,提出一种基于位码的优化高维索引结构（BC-iDistance）.针对iDistance缺点,高维向一维转换引起的大量数据信息丢失,BC-iDistance不仅利用一维距离表示点对象和参考点间的远近关系,而且引入位码近似表示它们之间的位置关系,将高维向量压缩为二维向量表示.利用特殊的B＋树组织,KNN检索时实现两层剪枝处理,降低I/O和距离计算代价.采用模拟数据和真实数据,实验验证了优化后的索引具有更高的检索效率.     

基于Δ-tree的递归深度优先KNN查询算法

基于Δ-tree提出一种用于高维数据的主存K最近邻(KNN)查询算法。该算法利用递归调用方法深度优先遍历Δ-tree,找到距离查询点较近的叶子节点,并选择其中较优的KNN候选点进行查询,从而缩小修剪距离、提高查询速度。实验结果表明,与已有算法相比,该算法具有更高的查询效率。     

Indexing high-dimensional data for efficient in-memory similarity search

In main memory systems, the L2 cache typically employs cache line sizes of 32-128 bytes. These values are relatively small compared to high-dimensional data, e.g., >32D. The consequence is that existing techniques (on low-dimensional data) that minimize cache misses are no longer effective. We present a novel index structure, called /spl Delta/-tree, to speed up the high-dimensional query in main memory environment. The /spl Delta/-tree is a multilevel structure where each level represents the data space at different dimensionalities: the number of dimensions increases toward the leaf level. The remaining dimensions are obtained using principal component analysis. Each level of the tree serves to prune the search space more efficiently as the lower dimensions can reduce the distance computation and better exploit the small cache line size. Additionally, the top-down clustering scheme can capture the feature of the data set and, hence, reduces the search space. We also propose an extension, called /spl Delta//sup +/-tree, that globally clusters the data space and then partitions clusters into small regions. The /spl Delta//sup +/-tree can further reduce the computational cost and cache misses. We conducted extensive experiments to evaluate the proposed structures against existing techniques on different kinds of data sets. Our results show that the /spl Delta//sup +/-tree is superior in most cases.     

基于流形空间的交互式人脸图像索引

认知科学表明基于流形学习的人脸图像检索能准确反映人脸图片的内在相似性和人类的视觉感知本质. 提出一种基于相关反馈的人脸高维索引方法--NDL,以提高人脸图像检索的性能.同时在该索引基础上提出一种流形空间下的相似查询--虚拟k近邻查询(Vk-NN), 该查询方法特别为基于NDL的人脸检索而设计.首先通过在一定阈值约束下计算任何两个人脸图片的相似度,建立一个称为邻接距离表(NDL)的二维距离图. 同时将距离值用B+-树建立索引.最后, 高维流形空间的Vk-NN查询转化为一维空间的基于B+树的查询. 实验表明:NDL索引在流形空间的检索效率明显优于顺序检索,特别适合海量人脸图片的检索.     

Composite Distance Transformation for Indexing and k-Nearest-Neighbor Searching in High-Dimensional Spaces

Due to the famous dimensionality curse problem, search in a high-dimensional space is considered as a "hard" problem. In this paper, a novel composite distance transformation method, which is called CDT, is proposed to support a fast k-nearest-neighbor (k-NN) search in high-dimensional spaces. In CDT, all (n) data points are first grouped into some clusters by a k-Means clustering algorithm. Then a composite distance key of each data point is computed. Finally, these index keys of such n data points are inserted by a partition-based B -tree. Thus, given a query point, its k-NN search in high-dimensional spaces is transformed into the search in the single dimensional space with the aid of CDT index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of the proposed scheme. Our results show-that this method outperforms the state-of-the-art high-dimensional search techniques, such as the X-Tree, VA-file, iDistance and NB-Tree.     

全链接指针B~+树的研究

在对比传统的Ｂ~＋树的定义和操作算法的基础上,定义了一种更适合于物理索引文件结构设计的Ｂ~＋树：ＦＬＰ－Ｂ~＋树。经过对数据的研究和分析表明,与一般 Ｂ~＋树相比, ＦＬＰ－Ｂ~＋树具有更高的空间利用效率。同时,为 ＦＬＰ－Ｂ~＋树索引文件设计了一种全链接的指针结构,以提高系统故障恢复的能力,以及在故障恢复期间保持等效的不中断服务的能力,亦即系统的有效性。     

Toward efficient multifeature query processing

In many advanced applications, data are described by multiple high-dimensional features. Moreover, different queries may weight these features differently; some may not even specify all the features. In this paper, we propose our solution to support efficient query processing in these applications. We devise a novel representation that compactly captures f features into two components. The first component is a 2D vector that reflects a distance range (minimum and maximum values) of the f features with respect to a reference point (the center of the space) in a metric space and the second component is a bit signature, with two bits per dimension, obtained by analyzing each feature's descending energy histogram. This representation enables two levels of filtering: the first component prunes away points that do not share similar distance ranges, while the bit signature filters away points based on the dimensions of the relevant features. Moreover, the representation facilitates the use of a single index structure to further speed up processing. We employ the classical B/sup +/-tree for this purpose. We also propose a KNN search algorithm that exploits the access orders of critical dimensions of highly selective features and partial distances to prune the search space more effectively. Our extensive experiments on both real-life and synthetic data sets show that the proposed solution offers significant performance advantages over sequential scan and retrieval methods using single and multiple VA-files.     

An encoding-based dual distance tree high-dimensional index

The paper proposes a novel symmetrical encoding-based index structure, which is called EDD-tree （for encoding-based dual distance tree）, to support fast k-nearest neighbor （k-NN） search in high-dimensional spaces. In the EDD-tree, all data points are first grouped into clusters by a k-means clustering algorithm. Then the uniform ID number of each data point is obtained by a dual-distance-driven encoding scheme, in which each cluster sphere is partitioned twice according to the dual distances of start- and centroid-distance. Finally, the uniform ID number and the centroid-distance of each data point are combined to get a uniform index key, the latter is then indexed through a partition-based B^＋-tree. Thus, given a query point, its k-NN search in high-dimensional spaces can be transformed into search in a single dimensional space with the aid of the EDD-tree index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of our proposed scheme, and the results demonstrate that this method outperforms the state-of-the-art high-dimensional search techniques such as the X-tree, VA-file, iDistance and NB-tree, especially when the query radius is not very large.     

Effectiveness of NAQ-tree in handling reverse nearest-neighbor queries in high-dimensional metric space

Reverse nearest-neighbor (RNN) query processing is important for many applications such as decision-support systems, profile-based marketing and molecular biology; consequently, RNN query processing has attracted considerable attention in the research community in recent years. Most existing approaches for RNN query processing either rely on nearest-neighbor pre-computation or work for specific data space (e.g., the Euclidean space). The only method for RNN query processing in metric space is based on the M-tree. In this paper, we propose an approach for RNN query processing in high-dimensional metric space using distance-based index structure (in particular, NAQ-tree that outperforms the other distance-based index structures as we have already verified in a previous study). In high-dimensional space, the properties of distance-based index structure provide strong pruning rules than the M-tree. In addition, unlike the previous work, our approach integrates the filtering and verification steps and uses the information obtained in the verification stage to further improve the filtering rate. Our approach delivers results incrementally and hence well serves real-time applications. The reported experimental results demonstrate the applicability and effectiveness of the proposed NAQ-tree-based RNN approach.