Premium
Estimating the performance of multidimensional access methods based on nonoverlapping regions
Author(s) -
Yu Byunggu,
Bailey Thomas,
Orlandic Ratko
Publication year - 2007
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.20200
Subject(s) - computer science , extension (predicate logic) , set (abstract data type) , access method , data mining , basis (linear algebra) , tree (set theory) , selection (genetic algorithm) , algorithm , artificial intelligence , mathematics , database , mathematical analysis , geometry , programming language
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.