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
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