# Quad trees a data structure for retrieval on composite keys

@article{Finkel2004QuadTA, title={Quad trees a data structure for retrieval on composite keys}, author={Raphael A. Finkel and Jon Louis Bentley}, journal={Acta Informatica}, year={2004}, volume={4}, pages={1-9} }

SummaryThe quad tree is a data structure appropriate for storing information to be retrieved on composite keys. We discuss the specific case of two-dimensional retrieval, although the structure is easily generalised to arbitrary dimensions. Algorithms are given both for staightforward insertion and for a type of balanced insertion into quad trees. Empirical analyses show that the average time for insertion is logarithmic with the tree size. An algorithm for retrieval within regions is presented… Expand

#### 1,681 Citations

Dynamic multi-dimensional data structures based on quad- and k—d trees

- Mathematics, Computer Science
- Acta Informatica
- 2004

A method to insert points in a quad-tree while keeping the tree balanced that achieves an average time complexity of O(log2 N) per insertion, where N is the number of updates performed on the quad- tree. Expand

An Investigation of Grid-enabled Tree Indexes for Spatial Query Processing

- Computer Science
- SIGSPATIAL/GIS
- 2019

The Grid-Enabled Tree index is introduced; a hybrid spatial index that augments a grid into tree-based indexing for spatial query processing and achieves constant-time tree search, insert, update, and leaf node neighbor finding operations, in contrast to the log time in conventional two-dimensional trees. Expand

Quad-kd trees: A general framework for kd trees and quad trees

- Computer Science
- Theor. Comput. Sci.
- 2016

It is suggested that the quad-kd tree is a flexible data structure that can be tailored to the resource requirements of a given application. Expand

Dynamic Data Structures for Geometric Search and Retrieval

- Computer Science
- 2013

This dissertation introduces two dynamic quadtree-based data structures for storing a set of points in space, called the quadtreap and the splay quadtree, and presents the first output sensitive algorithm for maintaining a well-separated pair decomposition (WSPD) for a dynamic point set. Expand

A Novel Spatial Indexing Mechanism Leveraging Dynamic Quad-Tree Regional Division

- Computer Science
- 2013

A new spatial index based on dynamic quad-tree regional division is proposed in this paper, which will first carry on clustering in the queried region, and then chose the biggest covering area to carry on quad- tree partition for each cluster. Expand

SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees

- Computer Science
- Journal of Intelligent Information Systems
- 2004

A new extensible index structure, termed SP-GiST is presented that supports this class of data structures, mainly the class of space partitioning unbalanced Trees, and issues related to clustering tree nodes into pages as well as concurrency control are addressed. Expand

Efficient Data Storage and Searching for Location Based Services using Quadtrees and H-ordering

- 2014

Data is always stored in secondary storage Devices due to its volume. When it is stored in secondary storage devices, it is required that the access time is as minimal as possible. Most of the… Expand

External segment trees

- Computer Science
- Algorithmica
- 2005

This paper transfers the underlying principle of the segment tree in a nontrivial way to secondary storage and arrives at the EST-an external file structure with the same functionality and the following properties: the EST is balanced and the update algorithms are efficient. Expand

FRINGED-QUADTREES: A NEW KIND OF DATA STRUCTURE

- Mathematics
- 2002

In our everyday life we have to deal with dierent problems that, in most cases, need new data structures. At first sight, these structures do not look like any known data structure. This paper… Expand

Hierarchical Data Structures for Accessing Spatial Data

- Computer Science
- FGIT-SIP/MulGraB
- 2010

This paper has described an algorithm for insertion of points in a Quad tree based structure, known as PR Quad Tree, and another data structure called K-D Tree is also described and the insertion procedure is defined. Expand

#### References

SHOWING 1-2 OF 2 REFERENCES

The Art of Computer Programming

- Computer Science
- 1968

The arrangement of this invention provides a strong vibration free hold-down mechanism while avoiding a large pressure drop to the flow of coolant fluid. Expand

The Art of Computer Programming, Vol. 3: Sorting and Searching

- Computer Science, Mathematics
- 1973