Analysis of the n-dimensional quadtree decomposition for arbitrary hyper-rectangles

dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorJagadish, H.V.en_US
dc.contributor.authorManolopoulos, Yannisen_US
dc.date.accessioned2004-05-31T22:29:03Z
dc.date.available2004-05-31T22:29:03Z
dc.date.created1994-12en_US
dc.date.issued1998-10-15en_US
dc.description.abstractWe give a closed-form expression for the average number of $n$-dimensional quadtree nodes (`pieces' or `blocks') required by an $n$-dimensional hyper-rectangle aligned with the axes. Our formula includes as special cases the formulae of previous efforts for 2-dimensional spaces \cite{Faloutsos92Analytical}. It also agrees with theoretical and empirical results that the number of blocks depends on the hyper-surface of the hyper-rectangle and not on its hyper-volume. The practical use of the derived formula is that it allows the estimation of the space requirements of the $n$-dimensional quadtree decomposition. Quadtrees are used extensively in 2-dimensional spaces (geographic information systems and spatial databases in general), as well in higher dimensionality spaces (as oct-trees for 3-dimensional spaces, e.g. in graphics, robotics and 3-dimensional medical images [Arya et al., 1994]. Our formula permits the estimation of the space requirements for data hyper-rectangles when stored in an index structure like a ($n$-dimensional) quadtree, as well as the estimation of the search time for query hyper-rectangles. A theoretical contribution of the paper is the observation that the number of blocks is a piece-wise linear function of the sides of the hyper-rectangle. (Also cross-referenced as UMIACS-TR-94-130)en_US
dc.format.extent233438 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/678
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3381en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-94-130en_US
dc.titleAnalysis of the n-dimensional quadtree decomposition for arbitrary hyper-rectanglesen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3381.ps
Size:
227.97 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3381.pdf
Size:
212.92 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3381.ps