Title :
Performance analysis of R*-trees with arbitrary node extents
Author :
Tao, Yufei ; Papadias, Dimitris
Author_Institution :
Dept. of Comput. Sci., City Univ. of Hong Kong, China
fDate :
6/1/2004 12:00:00 AM
Abstract :
Existing analysis for R-trees is inadequate for several traditional and emerging applications including, for example, temporal, spatio-temporal, and multimedia databases because it is based on the assumption that the extents of a node are identical on all dimensions, which is not satisfied in these domains. We propose analytical models that can accurately predict R*-tree performance without this assumption. Our derivation is based on the novel concept of extent regression function, which computes the node extents as a function of the number of node splits. Detailed experimental evaluation reveals that the proposed models are accurate, even in cases where previous methods fail completely.
Keywords :
multimedia databases; regression analysis; temporal databases; tree data structures; visual databases; R-tree; cost model; multimedia database; regression function; spatial database; spatio-temporal database; temporal database; Analytical models; Banking; Costs; Helium; History; Indexes; Indexing; Multimedia databases; Performance analysis; Spatial databases; 65; Database; R-tree; cost model.; spatial database;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
DOI :
10.1109/TKDE.2004.13