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.
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.