Can I read Speeding up construction of PMR quadtree-based spatial indexes on EtoBox?

Speeding up construction of PMR quadtree-based spatial indexes by Gisli R. Hjaltason; Hanan Samet is a Computer Science article available to read on EtoBox.

What is Speeding up construction of PMR quadtree-based spatial indexes about?

Spatial indexes, such as those based on the quadtree, are important in spatial databases for efficient execution of queries involving spatial constraints, especially when the queries involve spatial joins. In this paper we present a number of techniques for speeding up the construction of quadtree-based spatial indexes, specifically the PMR quadtree, which can index arbitrary spatial data. We assume a quadtree implementation using the "linear quadtree", a disk-resident representation that stores objects contained in the leaf nodes of the quadtree in a linear index (e.g., a B-tree) ordered based on a space-filling curve. We present two complementary techniques: an improved insertion algorithm and a bulk-loading method. The bulk-loading method can be extended to handle bulk-insertions into an existing PMR quadtree. We make some analytical observations about the I/O cost and CPU cost of our PMR quadtree bulk-loading algorithm, and conduct an extensive empirical study of the techniques presented in the paper. Our techniques are found to yield significant speedup compared to traditional quadtree building methods, even when the size of a main memory buffer is very small compared to the s

Who reads Speeding up construction of PMR quadtree-based spatial indexes?

Author

Gisli R. Hjaltason; Hanan Samet

Publisher

Springer-Verlag; Springer Verlag; Springer Science and Business Media LLC (ISSN 1066-8888)

Published

2002

Language

EN

Field

Computer Science (Physical Sciences)