China
Africa
Explore chapters and articles related to this topic
Spatial Data Structures
Published in Suman Saha, Shailendra Shukla, Advanced Data Structures, 2019
An R tree is a spatial data structure developed for indexing multi-dimensional batch processing such as geographical information or graphics design. The R tree was invented by Antonin Guttman in 1984 and is very popular for storing spatial objects, the data structure provides solid theoretical foundation as well as useful applications.
Efficiently identifying closed roads by integrating and indexing open data
Published in Journal of the Chinese Institute of Engineers, 2021
Ya-Hui Chang, Shu-Han He, Chih-Wei Tseng
Index structures are used to improve the querying efficiency. Many indices in addition to R-trees have been designed for spatial data, such as the Quadtree structure proposed by Finkel and Bentley (1974). The R-tree structure usually outperforms others in that it is a balanced tree and can provide stable accesses most of the time, but it is time consuming to build an optimal one. Beckmann et al. (1990) proposed the R*-tree to incorporate a combined optimization of areas, margins and overlaps of each enclosing rectangle of the inner node. Ang and Tan (1997) focused on the efficiency of the construction process and discussed a better linear algorithm to split the node. The R-tree index is currently widely applied in many spatial operations and for handling geographical data. To name a few, Schubert, Zimek, and Kriegel (2013) discussed how to apply it in geodetic distance queries. Chang, Lee, and Ke (2019) discussed how to represent flooded areas properly in the R-tree for future efficient querying. Since the flooded areas have irregular shapes due to geographical characteristics, the authors advocated the idea of partitioning the MBRs into smaller rectangles for better performance.
Constant-level spatio-temporal integrated search algorithm for repeating sun-synchronous orbit satellite images
Published in International Journal of Digital Earth, 2021
For remote sensing image data, catalogue services (Bai and Di 2011; Bai et al. 2012) are the major mechanism used to facilitate the query process on the web. Catalogue services support the ability to publish and search collections of descriptive information (metadata) in remote sensing image data and related information objects. When performing a spatio-temporal query, the spatial operations usually account for most of the duration of the query process. Therefore, many types of spatial indexes are developed to accelerate the retrieval process. R-tree (Nascimento and Silva 1998) is a common indexing scheme derived from the B-tree (Bayer and McCreight 2002). It was originally proposed for organizing spatial objects that use multi-dimensional indexes. The R-tree and its families, such as the R+-Tree (Sellis, Roussopoulos, and Faloutsos 1987), the R*-Tree (Beckmann, Kriegel, and Seeger 1990), and the Hilbert R-Tree (Kamel and Faloutsos 1993), have been extensively used by researchers to conduct efficient processing of queries in multi-dimensional data sets (Manolopoulos et al. 2010). The Quadtree (Finkel and Bentley 1974) was invented by Finkel and Bentley to express an extension of the Binary Search Tree in two dimensions, which was able to index points (Point Quadtree). Then, several Quadtree variations were developed for almost all types of spatial data (Klinger and Dyer 1976; Gargantini 1982; Samet 1990). The geohashes index is another important spatial indexing model. It was invented by Gustavo Niemeyer in 2008 to geocode specific points as a short string for use in web URLs (Uniform Resource Locators). All of these indexes have been extensively applied in most relational databases to index spatial data. However, most databases cannot directly support spatio-temporal data retrieval. To realize efficient spatio-temporal queries, several indexing mechanisms have been introduced for relational databases (Tao, Papadias, and Sun 2003 Zhu, Gong, and Zhang 2007;). For example, Carvalho, Ribeiro, and Augusto Sousa (2006) developed a spatio-temporal database system based on the temporal TimeDB and Oracle Spatial for temporal and spatial support. Zhao et al. (2011) developed the Spatio-Temporal Object Cartridge (STOC), which is an Oracle-based spatio-temporal information management system. Mahmood et al. (2017) introduced the spatio-temporal ontological concept using a relational data model for modeling spatio-temporal data. For non-relational databases, Fox et al. (2013) described a spatio-temporal index structure that leverages the horizontal scalability of NoSQL databases (Accumulo) (Cordova, Rinaldi, and Wall 2015), which is a sorted, distributed, and key/value store designed for non-relational databases built on Google’s BigTable database model (Chang et al. 2008), in order to achieve performant query and transformation semantics.