东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

一种支持多维数据范围查询的对等计算索引框架

期刊名称：计算机研究与发展
时间：0
分类：TP311.133[自动化与计算机技术—计算机软件与理论;自动化与计算机技术—计算机科学与技术]
作者机构：[1]华东师范大学软件学院,上海200062
相关基金：国家自然科学基金项目（60496325,60673137,60673134）;国家“八六三”高技术研究发展计划基金项目（2006AA01Z103）
相关项目：非规范知识交叉领域研究

关键词：多维数据, 范围查询, 对等计算, 架构, 分布式系统, multi-dimensional data, range query, peer-to-peer computing, framework, distributed system

中文摘要：

如何有效地支持多维数据范围查询是传统数据管理领域的研究热点之一．但是，在大规模分布式系统中，这仍然是一个具有挑战性的研究工作．VBI—tree是一个对等计算环境下基于平衡树的索引架构，在该架构上可以实现集中式环境下的多种支持多维数据索引的层次化树结构，例如R—tree，X—tree和M—tree等．VBI—tree设计的查询算法保证查询可以从树的任意位置开始，而不是像集中式环境下层次化树结构那样采用从树的根节点开始查询的方法，从而成功地避免了根节点引起的系统性能瓶颈问题．对于有N个节点的网络，索引方法可以保证查询效率是O（logN）．VBI—tree提出了基于AVL—tree旋转的网络重构负载均衡策略可以有效地均衡负载．另外，在数据操作频繁的情况下，为了提高索引的性能，在VBI—tree上建立特殊的祖先一子孙链接形成VBI^＊-tree的结构．通过使用祖先一子孙链接，可保证对于相关查询区域的探索尽量发生在同层节点之间，而不是一直往根节点方向发送，从而减轻上层节点的查询负担，并且显著地降低了更新代价．模拟实验验证了提出的方法的有效性．

英文摘要：

How to efficiently support multi-dimensional range search is one of the research hotspots in the traditional data management area. The design and implementation of multi-dimensional range query processing in large-scale distributed systems, however, remains to be a great challenge. VBI tree is a peer-to-peer indexing framework based on a balanced tree structure overlay and it can support any kind of multi-dimensional hierarchical tree structures such as R-tree, X-tree, and M-tree to be implemented in peer-to-peer computing environment. VBI-tree designs the search algorithms which can start from any position or any node instead of the root node used in the centralized hierarchical tree structures, thus successfully avoiding the performance bottleneck problem introduced by the root node. Specifically, in a network with N nodes, it guarantees that queries can be answered within O（logN） hops. It takes network restructuring based on AVL-tree rotation method as the load balancing strategy, which can balance work load efficiently. Additionally, a succinct structure of VBI^＊-tree is provided by setting up special ancestor-descendant links when facing a large number of data operations, which can improve the indexing performance. By using such new links, it is ensured that the related area checking to the queries will happen among the nodes of the same level to the greatest extent instead of sending checking requests directly to high level nodes, thereby reducing the load of high level nodes and also system updating cost. Experimental results validate the efficiency and effectiveness of the proposed approach.

同期刊论文项目