一种支持多维区间查询的云对等网络索引架构

Cloud P2P network index framework for supporting multidimensional range query

针对用户在大规模云对等网络环境下多维区间查询问题,将基于m叉平衡树的索引架构引入到云对等网络环境下,在该架构上实现集中式环境下支持多维数据索引的层次化树结构,如R树、QR树。多维区间查询算法保证查询从树的任意位置开始,避免了根节点引起的系统性能瓶颈问题。通过计算和实验验证,对于N个节点的网络,多维区间查询效率为O(log_mN)(m>2)(m表示扇出)。由此可见,查询效率与维数d无关,查询效率不会随着维数d的增加而降低。最后建立基于扇出m的代价模型,并且计算出了最优的m值。

This paper introduced index framework which based on m-ary balanced tree （ m is fanout of tree, m 〉 2） in order to solve multidimensional range query in large-scale cloud peer-to-peer network. It could support any kind of multidimensional data indexing hierarchical tree structure such as R-tree, QR-tree. This paper designed search algorithms which could start from any node, thus avoiding system performance bottleneck problem introduced by the root node. Calculation and experiments show that multidimensional range query efficiency limit to O （logmN） （m 〉 2 ）hops in a network with N nodes. It improves search performance of multidimensional range query independent of the dimension. The query efficiency can not reduce with the increase of dimension. It also proposed cost module based on m, and then calculated the optimal value of m.