Estimating the performance of multidimensional access methods based on nonoverlapping regions
Byunggu Yu, Thomas Bailey, Ratko Orlandić · International Journal of Intelligent Systems · 2007
Most cost models for the prediction of the performance of multidimensional access methods are based on Minkowski operations. However, this approach does not correspond to the space-partitioning strategy of multidimensional access methods that produce nonoverlapping index regions, for example, the KDB-tree and its variants. This article proposes a new cost model for the prediction of the selection (search) performance of the related access methods, including its adaptation for nonuniform data. The results of an extensive set of experiments conducted on both simulated and real data show that the cost model and its extension provide a basis for a highly accurate analysis of these structures in both low- and high-dimensional situations. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 259–277, 2007.