Fieldtree
In computer science, a fieldtree is a hierarchical data structure that is used to index geometric objects. It groups these objects into rectangular regions called "fields", where the fields at a given level are regularly-spaced, have the same size, and may overlap. Contrary to its name, a fieldtree is not strictly speaking a tree, rather its fields form a directed acyclic graph.[1]
While PR quadtrees and PR octrees are technically fieldtrees, the term usually refers to either partition or cover fieldtrees. A partition fieldtree is a fieldtree where the fields at each level are offset from the fields at the previous level and they do not overlap. On the other hand, a cover fieldtree (better known as a loose quadtree or a loose octree[2][3]) is a fieldtree where the fields at each level are aligned with the fields at the previous level but they do overlap.[1][4]
Fieldtrees were originally designed for use in spatial databases, but they also have applications in multikey database indexes,[1] video games,[5] the Internet of Things[6] and simulations.[3]
History
[edit]Quadtrees have been used as database indexes since the 1970s.[7] A disadvantage of quadtrees, called "stickiness", is that when a small object lies across the line between two regions it must be stored at a higher level in order to fit entirely within a single region. This results in small objects being stored at unnecessarily high levels and it reduces the effectiveness of the partitioning.[5][1] Early attempts to solve this involved storing the sicky objects in both regions, either by duplicating them (which increases the amount of space required) or by using pointers (which requires extra disk accesses).
In 1983, Andrew U. Frank published a thesis[8] describing "the field tree" as a data structure for use in geographic information systems. It solved the stickiness problem by allowing adjacent regions to overlap. In 1990, Frank refined the fieldtree concept by describing both partition and cover fieldtrees.[1]
In the late 1990s, Thatcher Ulrich independently reinvented cover fieldtrees (which he calls "loose octrees") for use in video games. Ulrich noted that, as well as being effective at avoiding stickiness, they were more performant than octrees for handling moving objects.[9][5]
Description
[edit]A fieldtree has multiple "levels", and each level has several regularly-spaced square[a] "fields" (a.k.a. regions). Within each level there are no gaps between the fields (though they may overlap). The levels are usually listed in order of decreasing field size, with the largest fields at the top level and the smallest fields at the bottom level. Each object (e.g. point, line, polygon) is associated with exactly one of the fields that completely contain it. Smaller objects are placed in smaller fields.[1]
Fieldtrees are similar to quadtrees in that they start by assigning all objects to a single field. Then, when a field reaches its capacity, it is split into four smaller fields. These smaller fields form part of the next level of the data structure. This splitting process repeats until either all fields are below capacity or the fieldtree has reached a predefined maximum number of levels.
The main difference between fieldtrees and quadtrees is how the fields at each level are arranged. Depending on the type of fieldtree, the fields in each level may overlap or they may be offset from the fields in the previous level. In either case, a field in one level may intersect multiple fields in the levels below and above it.
One way of thinking about a fieldtree is as a directed acyclic graph, where each edge connects a field in one level (the "parent") with a field that intersects it in the next level (the "child"). This graph does not have any cycles because the edges always point from fields in higher levels to fields in lower levels. Contrary to what the name "fieldtree" might suggest, the data structure is not a true tree because a field may have multiple parents and multiple children. However, it is useful to systematically select a subset of the edges to form a tree (that is, to select a spanning tree) to allow for various optimizations.
Partition fieldtree
[edit]
A partition fieldtree is a type of fieldtree where each layer is slightly offset from the last, so that every corner of a field in one level lines up with the center of a field in the next level. This requires a shift in both the x and y directions of half of the smaller field's width, relative to where the fields would be in a quadtree. The fields in each level do not overlap.
This small shift ensures that an object never needs to be stored more than two levels up from the smallest level that could contain it, improving the efficiency of operations on the fieldtree.
A partition fieldtree is so called because, unlike a cover fieldtree, the fields at each level partition the space without overlapping.
Cover fieldtree
[edit]
A cover fieldtree (also known as a loose quadtree or loose octree[2]) is a type of fieldtree where the fields in each level are expanded so that they overlap. The centers of the fields remain in the same place as they would be in a quadtree.
The amount that the fields overlap is described by the expansion factor p,[2] which must be a positive real number. The width of each field can be found using (1 + p) × dc (where dc is the distance between the centers of adjacent fields[b]). A typical value for p is 1, which results in the fields being twice as wide as they would be in a quadtree. The overlap between adjacent fields ensures that any object of width p × dc can be stored in a given level. In the case of p = 1, an object never needs to be stored more than one level up from the smallest level that could contain it, improving the efficiency of operations on the fieldtree.
A cover fieldtree is so called because the fields at each level cover the space but, unlike with a partition fieldtree, there is some overlap (meaning that it cannot be considered a partition).
Importance attribute
[edit]Each object in a field tree may have an "importance" attribute attached to it that indicates the lowest level where the object may be stored. This allows insertion and querying to be optimized by not checking levels that are too low for that object if the object's importance is known.
See also
[edit]Notes
[edit]- ^ This article, like the original paper,[1] describes a fieldtree using squares in two dimensions. However, the data structure easily generalizes to rectangles and higher dimensions.
- ^ This is equal to the width that the fields would have if they were just touching.
References
[edit]- ^ a b c d e f g Frank, Andrew U.; Barrera, Renato (1990). "The Fieldtree: A Data Structure for Geographic Information Systems" (PDF). Symposium on the Design and Implementation of Large Spatial Databases: 29–44. Retrieved 19 November 2025.
- ^ a b c Samet, Hanan; Sankaranarayanan, Jagan; Auerbach, Michael (2013). "Indexing methods for moving object databases: games and other applications". Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data: 169–180. doi:10.1145/2463676.2465332. Retrieved 19 November 2025.
- ^ a b Deng, Ze; Wang, Lizhe; Han, Wei; Ranjan, Rajiv; Zomaya, Albert (2018). "G-ML-Octree: An Update-Efficient Index Structure for Simulating 3D Moving Objects Across GPUs". IEEE Transactions on Parallel and Distributed Systems. 29 (5): 1075-1088. doi:10.1109/TPDS.2017.2787747. Retrieved 19 November 2025.
- ^ Samet, Hanan (2006). Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. pp. 257–269. ISBN 978-0-12-369446-1. Retrieved 19 November 2025.
- ^ a b c Ulrich, Thatcher. "Loose Octrees". In DeLoura, Mark A. (ed.). Game Programming Gems. Retrieved 19 November 2025.
- ^ Chaudhry, Natalia; Yousaf, Muhammad Murtaza; Khan, Muhammad Taimoor (2020). "Indexing of real time geospatial data by IoT enabled devices: Opportunities, challenges and design considerations". Journal of Ambient Intelligence and Smart Environments. 12 (4): 281–312. doi:10.3233/AIS-200565. Retrieved 19 November 2025.
- ^ Finkel, Raphael; Bentley, Jon Louis (1974). "Quad Trees: A Data Structure for Retrieval on Composite Keys". Acta Informatica. 4 (1): 1–9. doi:10.1007/BF00288933. Retrieved 19 November 2025.
- ^ Frank, Andrew U. (1983). Storage Methods for Space Related data: The FIELD TREE (PDF) (Thesis). University of Maine. Swiss Federal Institute of Technology, Institute for Geodesy and Photogrammetry. Retrieved 19 November 2025.
- ^ Ulrich, Thatcher. "Spatial partitioning with "Loose" octrees". Retrieved 19 November 2025.