loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Michael D. Morse, Electrical Engineering and Computer Science University of Michigan
Jignesh M. Patel, Electrical Engineering and Computer Science University of Michigan
William I. Grosky, Dept. of Computer Science University of Michigan-Dearborn
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.