A Practical Approach to Cost Estimation for Searching on the SH-tree

Coming along with the development of modern database applications, various index structures have been created to support the efficient storage and retrieval of data. These index structures include multidimensional access methods (MAMs), which take a fundamental and vital role in modern database applications. However, to integrate MAMs into standard DBMSs smoothly, we must face several non-trivial problems in order to make MAMs function properly and efficiently in those DBMSs. In this paper, we address such an indispensable problem, the cost estimation for queries. We present a simple and efficient solution to the problem for the SH-tree, which has been introduced recently and proven to be a very powerful MAM. Experimental results with both synthetic and real data sets confirm our theoretical analyses