Title: Efficient evaluation of radial queries using the target tree

Authors: Michael Morse, Jignesh M. Patel, William I. Grosky

Addresses: Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor MI 48105, USA. ' Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor MI 48105, USA. ' Department of Computer and Information Science, University of Michigan-Dearborn, Dearborn MI 48128, USA

Abstract: We propose a novel indexing structure, called the target tree, which is designed to answer a new type of spatial query, called the radial query. A radial query finds all objects in the spatial data set that intersect with line segments emanating from a single target point. Many biomedical applications use radial queries, including neurosurgical planning. A target tree uses a regular hierarchical decomposition of space using wedge shapes that emanate from the target point. We compare the target tree with the R*-tree and quadtree, and show that the target tree is significantly faster than these methods.

Keywords: spatial databases; spatial indexing structures; query evaluation; target tree; radial query; bioinformatics; biomedical data; biomedical engineering; neurosurgical planning; neurosurgery; computer-assisted surgery.

DOI: 10.1504/IJBRA.2007.011833

International Journal of Bioinformatics Research and Applications, 2007 Vol.3 No.1, pp.24 - 41

Published online: 26 Dec 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article