21st International Conference on Data Engineering Workshops (ICDEW'05) Efficient Evaluation of Radial Queries using the Target Tree Tokyo, Japan April 05-April 08 ISBN: 0-7695-2657-8
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2005.214
In this paper, we propose a novel indexing structure, called the target tree, which is designed to efficiently answer a new type of spatial query, called a radial query. A radial query seeks to find all objects in the spatial data set that intersect with line segments emanating from a single, designated target point. Many existing and emerging biomedical applications use radial queries, including surgical planning in neurosurgery. Traditional spatial indexing structures such as the R*-tree and quadtree perform poorly on such radial queries. A target tree uses a regular hierarchical decomposition of space using wedge shapes that emanate from the target point, resulting in an index structure that is very efficient for evaluating radial queries. We present a detailed performance evaluation of the target tree, comparing with the R*-tree and quadtree indexing methods, and show that the target tree method outperforms these existing methods by at least a factor of 2-10.
Citation:
Michael D. Morse, Jignesh M. Patel, William I. Grosky, "Efficient Evaluation of Radial Queries using the Target Tree," icdew, pp.1168, 21st International Conference on Data Engineering Workshops (ICDEW'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||