Maintaining range trees in secondary memory. Part I: Partitions
type: Item
instance of: scholarly article
title: Maintaining range trees in secondary memory. Part I: Partitions
zbMATH Open document ID: 0672.68007
DOI: 10.1007/BF00289018
author: Mark H. Overmars
author: Michiel Smid
author: Mark de Berg
author: Marc Van Kreveld
published in: Acta Informatica
publication date: 1990-01-01T00:00:00Z
review text: Range trees are used for solving the orthogonal range searching problem, a problem that has applications in e.g. databases and computer graphics. We study the problem of storing range trees in secondary memory. To this end, we partition range trees into parts that are stored in consecutive blocks in secondary memory. This paper gives a number of partition schemes that limit the part-sizes and the number of disk accesses necessary to perform updates and queries. We show e.g., that for each fixed positive integer k, there is a partition of a two-dimensional range tree into parts of size \(O(n^{1/k})\), such that each update requires at most \(k(2k+1)\) disk accesses, and each query requires at most \(8k^ 2+2k+2t\) disk accesses, where t is the number of answers to the range query.
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4100597
zbMATH Keywords: partition of range tree
zbMATH Keywords: partition schemes
zbMATH Keywords: range trees
zbMATH Keywords: orthogonal range searching problem
zbMATH Keywords: databases
zbMATH Keywords: computer graphics
MaRDI profile type: Publication
cites work: Organization and maintenance of large ordered indexes
cites work: Decomposable searching problems
cites work: On the average number of rebalancing operations in weight-balanced trees
cites work: Q3853109
cites work: Q4040797
cites work: Implementation of the grid file: Design concepts and experience
cites work: Binary Search Trees of Bounded Balance
cites work: The design of dynamic data structures
cites work: Q3694703
cites work: Q4729324
cites work: Adding range restriction capability to dynamic data structures
full work available at URL: https://doi.org/10.1007/bf00289018
OpenAlex ID: W1999166624
description: scientific article; zbMATH DE number 4100597