Efficient spatial indexes for approximate range searching

M.W.A. Streppel, K. Yi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

32 Downloads (Pure)


Building efficient spatial indexes for range searching is a central problem in spatial databases. The Rtree has been a popular spatial index thanks to its simplicity, ability to answer various queries, and the flexibility to store spatial objects of different shapes. However, the R-tree is known to be a heuristic-based structure and no guarantees can be made on its query performance. In this paper, we present two disk-based indexes for approximate range searching that are as versatile as the R-tree, and at the same time provide good guarantees on the query performance, albeit in the approximate sense.
Original languageEnglish
Title of host publicationCollection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria
EditorsO. Aichholzer, T. Hackl
Place of PublicationGraz, Austria
PublisherVerlag der Technischen Universität Graz
ISBN (Print)978-3-902465-62-7
Publication statusPublished - 2007
Eventconference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21 -
Duration: 19 Mar 200721 Mar 2007


Conferenceconference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21
OtherEWCG 2007, Graz, Austria

Cite this