Approximate range searching in external memory

M.W.A. Streppel, K. Yi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
189 Downloads (Pure)

Abstract

In this paper, we present two linear-size external memory data structures for approximate range searching. Our first structure, the BAR-B-tree, stores a set of N points in R d and can report all points inside a query range Q by accessing O(log B N¿+¿e ¿ ¿+¿k e /B) disk blocks, where B is the disk block size, ¿=¿1¿-¿d for convex queries and ¿=¿-¿d otherwise, and k e is the number of points lying within a distance of e·diam(Q) to the query range Q. Our second structure, the object-BAR-B-tree, is able to store objects of arbitrary shapes of constant complexity and provides similar query guarantees. In addition, both structures also support other types of range searching queries such as range aggregation and nearest-neighbor. Finally, we present I/O-efficient algorithms to build these structures.
Original languageEnglish
Title of host publicationProceedings of the 18th International Symposium : Algorithms and Computation (ISAAC 2007) 17-19 December 2007, Sendai, Japan
EditorsT. Tokuyama
Place of PublicationBerlin
PublisherSpringer
Pages536-548
ISBN (Print)978-3-540-77118-0
DOIs
Publication statusPublished - 2007
Event18th International Symposium on Algorithms and Computation (ISAAC 2007) - Sendai, Japan
Duration: 17 Dec 200719 Dec 2007
Conference number: 18

Publication series

NameLecture Notes in Computer Science
Volume4835
ISSN (Print)0302-9743

Conference

Conference18th International Symposium on Algorithms and Computation (ISAAC 2007)
Abbreviated titleISAAC 2007
Country/TerritoryJapan
CitySendai
Period17/12/0719/12/07

Fingerprint

Dive into the research topics of 'Approximate range searching in external memory'. Together they form a unique fingerprint.

Cite this