Improved Partial-Match Search Algorithms for BD Trees
Sivarama P. Dandamudi · The Computer Journal · 1991
Partial-match search queries form an important class of queries posed to a database system. Several storage structures have been proposed to answer these queries efficiently. The BD tree is an example of such a storage structure. A partial-match search algorithm, called AORIG, is given in Ref. 5. This paper presents three algorithms – ALOCAL, ACOMP and AGLOBAL – that represent three levels of improvement to AORIG. Each one yields successively more benefit at the cost of more complexity. All the improvements centre on avoiding the exploration of unnecessary OUT branches. It is shown that AGLOBAL is the best partial-match search algorithm in the sense that no other algorithm searches fewer internal and external nodes. The worst-case complexity of performing a partial-match search in BD trees using AGLOBAL is shown to be the same as that for the k-d trees.