Using machine learning to balance metric trees

Abstract

The emergence of complex data objects that must to be indexed and accessed in databases has created a need for access methods that are both dynamic and efficient. Lately, metric tree structures have become a popular way of handling this because of the advantages they have compared to traditional methods based on spatial indexing. The most common way to handle indexing is to build tree structures and then prune out branches of the trees during search, and for a dynamic indexing structure it is important that these trees stay balanced in order to keep the worst case search time as low as possible. Normally, this is done based on complex criteria and reshuffling operations. Another way to handle balancing is General Balanced Trees (GBT), proposed by Arne Andersson (Journal of Algorithms 30, 1999), which uses simple, global criteria for rebalancing binary search trees by using total and partial rebuilding. This thesis explores if it is possible to apply this to metric tree structures, and especially two static metric tree structures called the Vantage Point Tree and the Multiple Vantage Point Tree. It discusses how to best make these into dynamic tree structures and how to apply balancing by using GBT paradigms on them. The results of the performance of the new tree structures are analyzed, and the results are compared against already existing structures. The results shows that this works for balancing the trees, and that the structures perform reasonably well compared to already existing structures.