Using B-trees to Solve Geographic Range Queries
Open Access
- 1 January 1986
- journal article
- research article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 29 (2) , 176-180
- https://doi.org/10.1093/comjnl/29.2.176
Abstract
We present an algorithm to solve range queries in an interactive Geographic Information System. The algorithm uses a quadtree as logical data structure implemented in a two-level memory environment as an inverted file (B-Tree) and accesses points using a search key built from the coordinates of the point itself. This data structure is easily maintained by any file system, which also resolves problems pertaining to concurrency control and recovery. The method is shown to have O(√F) expected running time, where F is the total number of points belonging to the requested region.Keywords
This publication has 0 references indexed in Scilit: