Abstract
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)
Keywords
Computer scienceGrid fileGridTransformation (genetics)File formatPoint (geometry)Search engine indexingRange query (database)DatabaseGrid computingTheoretical computer scienceInformation retrievalWeb search querySargableSearch engineMathematics
Related Publications
Secure statistical databases with random sample queries
A new inference control, called random sample queries, is proposed for safeguarding confidential data in on-line statistical databases. The random sample queries control deals d...
The tracker
The query programs of certain databases report raw statistics for query sets, which are groups of records specified implicitly by a characteristic formula. The raw statistics in...
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects
The problem of indexing multidimensional objects is considered. First, a classification of existing methods is given along with a discussion of the major issues involved in mult...
Scalable object-tracking through unattended techniques (SCOUT)
A scalable object location service can enable users to search for various objects in an environment where many small, networked devices are attached to objects. We investigate t...
Querying Large Collections of Music for Similarity
We present a system capable of performing similarity queries against a large archive of digital music. Users are able to search for songs which "sound similar" to a given query ...
Publication Info
- Year
- 1983
- Type
- article
- Volume
- 54
- Citations
- 41
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
41
OpenAlex
Cite This
Klaus Hinrichs,
J. Nievergelt
(1983).
The Grid file: A data structure designed to support proximity queries on spatial objects.
Repository for Publications and Research Data (ETH Zurich)
, 54
.
https://doi.org/10.3929/ethz-a-005363208
Identifiers
- DOI
- 10.3929/ethz-a-005363208