Design and Implementation of Routing Algorithms for Supporting Multi-dimensional Range Query in HD Tree.

摘要

The HD Tree is a novel data structure, which was recently proposed by Yunfeng Gu to support multi-dimensional range queries in a distributed environment. My thesis work is a follow-up to the research on the HD Tree. It focuses on the basic routing strategies in order to support multi-dimensional range queries in the HD Tree. There are two basic routing strategies supported by the HD Tree data structure: hierarchical routing and distributed routing. Hierarchical routing is an adapted version of routing in the tree structure, while distributed routing is a novel routing strategy built over the distributed structure of the HD Tree in order to accommondate the distributed environment. Hierarchical routing can be applied to any source and destination pair in the HD Tree, but results in a massive work load on nodes near the root. It also has very limited options in case of a node failure. Although distributed routing is applied only to the source and destination pair at the same depth of the HD Tree, its communication load is distributed to two sets of nodes at neighboring depths. Distributed routing has more options to survive a node failure. In my thesis work, four distributed routing algorithms were explored. Each of these four is a stand-alone routing algorithm, and can be applied in different routing conditions. Both theoretical analysis and experimental results indicate that any routing algorithm alone is able to achieve similar or better performance compared to the equivalent tree structure. However, the significance of this thesis work pertains not only to the performance issue. These different routing algorithms provide multiple options to accommondate a changing environment. Based on my thesis work, there were two advanced routing algorithms developed, a X2X routing algorithm which is a combination of four distributed routing algorithms, and a DROCR algorithm which is a combination of the hierarchical and distributed routing algorithms. These algorithms not only achieve considerable performance gain over its equivalent tree structure, but also make the routing in the HD Tree highly error resilient and load balancing. They are the fundamental algorithms in supporting multi-dimensional range queries in the HD Tree.