China
Africa
Explore chapters and articles related to this topic
Spatial Data Structures
Published in Suman Saha, Shailendra Shukla, Advanced Data Structures, 2019
The point of searching with a KD tree is analogous to searching in other types of trees. For searching a query point xq=(xq1,xiq,…,xqd) in a KD tree, we start the comparison of xq1 with the first coordinate of root, followed by the comparison of xq2 with the second coordinate of selected child of root and so on. Once the search process reaches the leaf, we decide whether the point exists in the tree or not based on an exact match or failure. The complexity of search process is O(log n) for a balanced KD tree consisting of n nodes.
Basic Data Structures
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
A kd tree is simply an extension of this binary tree to higher dimension space. It first partitions all the points into two groups of almost the same size along one dimension, and then recursively partitions the groups along other dimensions. It follows the same order of dimensions for further partitionings. Figure 4.3 shows a kd tree for a set of points on a plane (two-dimensional space) with a horizontal partitioning followed by a vertical one. The algorithm for building a kd tree is straightforward, based on recursive bipartitioning of the points along one dimension. Its runtime is in O(n log n). Given an orthogonal range, a query on a kd tree will give all the points within the range. The range query algorithm is just a simple extension of the interval query on binary trees and it is described in Figure 4.4. Theorem 2A kd tree for n points can be built in O(n log n) time; a query with an axis-parallel range can be performed in O(n1–1/d+ k) where d > 1 is the dimension and k is the number of points within the range. In a two-dimensional plane, a query takes O(n+k) time.
Local Methods for Dimension Reduction
Published in Yangsheng Xu, Ka Keung C. Lee, Human Behavior Learning and Transfer, 2005
The efficiency of this method is determined by the cost of building the kd-tree once and then doing n searches for the l closest points in the tree. Building the kd-tree is an O(n log n) operation [70]. The cost of the l-nearest-neighbor search depends on the intrinsic dimensionality of the set of points in the kd-tree. Generally, if the intrinsic dimensionality is approximately 8 or greater, the naïve O(n2) search is more efficient, and if the intrinsic dimension is much lower than 8, then building and searching the kd-tree to do the projection step is close to a cost of O(n log n). Since the points in the kd-tree are from a representative subset of a smooth one-dimensional curve, we can expect the kd-tree method to be much faster than the naïve search.
Spatially optimised retrieval of 3D point cloud data from a geospatial database for road median extraction
Published in Journal of Spatial Science, 2022
Pankaj Kumar, Paul Lewis, Conor Cahalane, Stefan Peters
The user explores the road polylines incorporated in the Google Maps interface of the GLIMPSE system and can click any point near the preferred road section for which the ALS data is required to be accessed. In Step 1 of our approach, the road polyline point nearest to the user-clicked location is selected using a kd-tree search approach. The kd tree is a data structure which is used to organise the points in a space with k-dimensions. Each node of a tree specifies an axis and splits the set of points based on whether their coordinates along that axis are greater or less than a node value (Maneewongvatana and Mount 1999). In our approach, all the road polyline points, representing the centre of the dual carriageway, are split into three dimensions and then the polyline point nearest to the user-clicked location is selected. The selected polyline point is used to further select the consecutive polyline points based on total length specified by the user.
A hierarchical indexing strategy for optimizing Apache Spark with HDFS to efficiently query big geospatial raster data
Published in International Journal of Digital Earth, 2020
Fei Hu, Chaowei Yang, Yongyao Jiang, Yun Li, Weiwei Song, Daniel Q. Duffy, John L. Schnase, Tsengdar Lee
For tree-like approaches, there are four common structures: multiple-key index, k-d tree, quad-tree and r-tree. The multiple-key index is an index of indexes, where nodes at each level are indexes for an attribute. A k-d tree (k-dimensional tree) is a main-memory binary search tree in which interior nodes use their attribute values to split their child nodes into two parts, and nodes at different tree levels have different attributes (Ooi, McDonell, and Sacks-Davis 1987; Zhou et al. 2008). A k-d tree is best at partial-match, range and nearest-neighbour queries (Robinson 1981). A Quad tree divides a space into a square two-dimensional region, and each interior node splits its region into four quadrants (Finkel and Bentley 1974; Eppstein, Goodrich, and Sun 2005). The r-tree is similar to b-tree, but its internal nodes represent the region in any shape (Beckmann et al. 1990). It is efficient for point location and overlapped region query but is complicated to insert/delete data.
A quantized approach for occupancy grids for autonomous vehicles: Q-Trees
Published in Advanced Robotics, 2018
K-d trees are suitable for space partitioning to use conveniently in nearest neighborhood search. Besides, partitioning the local search space unevenly with data occurrences is not suitable for efficient data clustering and associating the path allocation with the map. Octrees are designed to be used in 3D spaces and cannot be degraded into planar surfaces quickly. The proposed method uses separated trees for all dimensions to overcome the multi-dimensional-only problem. Quad-trees have a structure that divides the 2D surface into four regions/quadrants. Thus, this approach is diverged from the proposed method because x–y dimensions are always split in the same size (which is not always true in our case). Besides, the z-dimension is not aimed to be used in quad-trees. R-trees are useful in topological classification. However, they are not suitable to derive input signals for path planning stage because they are based on sparsely distributed bounding box methods. R-trees and derivative approaches are easy to implement, nevertheless, can only be useful after preprocessing the obstacle space first. RRT algorithms also consist of multiple line segments which are also not suitable for direct usage for kinematic planning.