The Grid File: A Data Structure Designed to Support Proximity Queries on Spatial Objects.
Abstract
This document describes a technique for storing large sets of spatial objects so that proximity queries are handled efficiently as part of the accessing mechanism. This technique is based on a transformation of spatial objects into points in higher-dimensional spaces and on a data structure called the grid file. The grid file was designed to store highly dynamic sets of multi-dimensional data in such a way that it can be accessed using few disk accesses: a point query requires two disk accesses, a range query requires at most two disk accesses per data bucket retrieved. The efficiency of our technique is based on two facts: (1) many types of proximity queries lead to cone-shaped regions of the search space; and (2) the grid file allows an efficient enumeration of all the points in such a cone. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1983
- Accession Number
- ADA144385
Entities
People
- J. Nievergelt
- K. Hinrichs