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

FieldValue
dc.contributor.authorYe, Xun
dc.date.accessioned2013-11-07T19:31:24Z
dc.date.available2013-11-07T19:31:24Z
dc.date.created2011
dc.date.issued2011
dc.identifier.citationSource: Masters Abstracts International, Volume: 49-06, page: 3903.
dc.identifier.urihttp://hdl.handle.net/10393/28826
dc.identifier.urihttp://dx.doi.org/10.20381/ruor-13738
dc.description.abstractThe 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.
dc.format.extent77 p.
dc.language.isoen
dc.publisherUniversity of Ottawa (Canada)
dc.subject.classificationComputer Science.
dc.titleDesign and Implementation of Routing Algorithms for Supporting Multi-dimensional Range Query in HD Tree
dc.typeThesis
dc.degree.nameM.C.S.
dc.degree.levelMasters
CollectionTh├Ęses, 1910 - 2010 // Theses, 1910 - 2010

Files
MR74159.PDF3.05 MBAdobe PDFOpen