A New Set of Pivot Elimination Schemes for Increasing the Query Performance

Abstract

M-Tree, Slim-Tree, DF-Tree, and Omni-Tree are some of the popular dynamic structures which can grow incrementally by splitting overflowed nodes, and adding new levels to the tree very much like the B-tree variants. Unfortunately, they have been shown to perform very poorly compared to flat structures such as AESA, LAESA, Spaghettis, and Kvp that use a fixed set of global pivots. HKvp index structure is an extension of Kvp allowing the elimination of pivots as well as the database objects. The number of pivots can be easily increased to provide more selectivity and query performance. However, there is an optimum number of pivots for a given query radius, and using too many pivots increases the costs of queries and index initialization. In this paper, a new set of pivot elimination mechanisms is proposed to determine the right number of pivots for different query radii. The suggested pivot elimination schemes perform significant cost reduction in terms of number of distance computations, and they estimate the drop rate value for HKvp on query time.