Building a scalable geo-spatial dbms: technology, implementation, and evaluation (1997)
by J Patel, J B Yu, N Kabra, K Tufte, B Nag, J Burger, N Hall, K Ramasamy, R Lueder, C Ellmann, J Kupsch, S Guo, J Larson, D DeWitt, J Naughton
Venue: Proceedings of the ACM SIGMOD Conference, AZ
The DEDALE System for Complex Spatial Queries
by Stéphane Grumbach, Philippe Rigaux, Luc Segoufin , 1998
"... This paper presents dedale, a spatial database system intended to overcome some limitations of current systems by providing an abstract and non-specialized data model and query language for the representation and manipulation of spatial objects. dedale relies on a logical model based on linear const ..."
This paper presents dedale, a spatial database system intended to overcome some limitations of current systems by providing an abstract and non-specialized data model and query language for the representation and manipulation of spatial objects. dedale relies on a logical model based on linear constraints, which generalizes the constraint database model of [KKR90]. While in the classical constraint model, spatial data is always decomposed into its convex components, in dedale holes are allowed to fit the need of practical applications. The logical representation of spatial data although slightly more costly in memory, has the advantage of simplifying the algorithms. dedale relies on nested relations, in which all sorts of data (thematic, spatial, etc.) are stored in a uniform fashion. This new data model supports declarative query languages, which allow an intuitive and efficient manipulation of spatial objects. Their formal foundation constitutes a basis for practical query optimizati...
Multiway Spatial Joins
by Nikos Mamoulis - ACM Transactions on Database Systems (TODS , 2001
"... Due to the evolution of Geographical Information Systems, large collections of spatial data having various thematic contents are currently available. As a result, the interest of users is not limited to simple spatial selections and joins, but complex query types that implicate numerous spatial inpu ..."
Due to the evolution of Geographical Information Systems, large collections of spatial data having various thematic contents are currently available. As a result, the interest of users is not limited to simple spatial selections and joins, but complex query types that implicate numerous spatial inputs become more common. Although several algorithms have been proposed for computing the result of pairwise spatial joins, limited work exists on processing and optimization of multiway spatial joins. In this article, we review pairwise spatial join algorithms and show how they can be combined for multiple inputs. In addition, we explore the application of synchronous traversal (ST), a methodology that processes synchronously all inputs without producing intermediate results. Then, we integrate the two approaches in an engine that includes ST and pairwise algorithms, using dynamic programming to determine the optimal execution plan. The results show that, in most cases, multiway spatial joins are best processed by combining ST with pairwise methods. Finally, we study the optimization of very large queries by employing randomized search algorithms.
Experience with SAND-Tcl: A Scripting Tool for Spatial Databases
by Claudio Esperança, Hanan Samet
"... The use of scripting makes it possible to overcome many important difficulties in the development of database applications. By extending a general-purpose scripting language with constructs derived both from the database kernel and from the intended application domain, issues such as query processin ..."
Abstract - Cited by 15 (12 self) - Add to MetaCart
The use of scripting makes it possible to overcome many important difficulties in the development of database applications. By extending a general-purpose scripting language with constructs derived both from the database kernel and from the intended application domain, issues such as query processing and user interfacing can be approached in an economical and flexible way. This is illustrated by describing our experience with SAND-Tcl, a scripting tool developed by us for building spatial database applications. SAND-Tcl is an extension of the Tcl embedded scripting language with the constructs of the SAND environment for developing applications involving both spatial and non-spatial data. SANDTcl acts as a "glue" to hold together all the subsystems of SAND. In fact, query evaluation plans are SAND-Tcl programs (or scripts) which are written on-the-fly by SAND in response to a query defined by the user. This permits the rapid prototyping of algorithms and makes SAND a useful tool both f...
Efficient spatial sampling of large geographical tables
by Anish Das Sarma, Hongrae Lee, Hector Gonzalez, Jayant Madhavan, Alon Halevy - In SIGMOD , 2012
"... Large-scale map visualization systems play an increasingly important role in presenting geographic datasets to end users. Since these datasets can be extremely large, a map rendering system often needs to select a small fraction of the data to visualize them in a limited space. This paper addresses ..."
Large-scale map visualization systems play an increasingly important role in presenting geographic datasets to end users. Since these datasets can be extremely large, a map rendering system often needs to select a small fraction of the data to visualize them in a limited space. This paper addresses the fundamental challenge of thinning: determining appropriate samples of data to be shown on specific geographical regions and zoom levels. Other than the sheer scale of the data, the thinning problem is challenging because of a number of other reasons: (1) data can consist of complex geographical shapes, (2) rendering of data needs to satisfy certain constraints, such as data being preserved across zoom levels and adjacent regions, and (3) after satisfying the constraints, an optimal solution needs to be chosen based on objectives such as maximality, fairness, and importance of data. This paper formally defines and presents a complete solution to the thinning problem. First, we express the problem as an integer programming formulation that efficiently solves thinning for desired objectives. Second, we present more efficient solutions for maximality, based on DFS traversal of a spatial tree. Third, we consider the common special case of point datasets, and present an even more efficient randomized algorithm. Finally, we have implemented all techniques from this paper in Google Maps [6] visualizations of Fusion Tables [14], and we describe a set of experiments that demonstrate the tradeoffs among the algorithms.
...xtensively in the database community as well. However, the main focus has been on data structures, e.g. [16, 27], query processing, e.g. [15, 20], spatial data mining, e.g. [17] and scalability, e.g. =-=[23]-=-; these are all largely orthogonal to our contributions. The spatial index in Section 2 can be implemented with various data structures studied, e.g. [16, 19].(a) Flu with Fmax (b) Flu with Fimp Figu...
Ten benchmark database queries for location-based services
by Yannis Theodoridis - The Computer Journal , 2003
...e benchmark queries, both in natural language and in an 'imaginary' SQL-like language, supporting ADTs for l-service applications. 5 Following the examples of Stonebraker et al. [18] and Patel et al. =-=[19]-=-, the first operation to be supported is the loading of the benchmark database and the building of appropriate indices (the indices required are discussed later). OPERATION 0A. (Initialization) Load t...
A performance benchmark for spatiotemporal databases
by Paul Werstein - In: Proc. of the 10th Annual Colloquium of the Spatial Information Research Centre , 1998
"... In the course of developing a spatiotemporal database to serve as a research tool, it became apparent that existing benchmarks were inadequate for our needs. This paper describes the benchmark I created to fill the void. The benchmark is unique in two ways. First it requires significant temporal pro ..."
In the course of developing a spatiotemporal database to serve as a research tool, it became apparent that existing benchmarks were inadequate for our needs. This paper describes the benchmark I created to fill the void. The benchmark is unique in two ways. First it requires significant temporal processing and storage capabilities. Second it has provisions for evaluating the ability of a spatiotemporal database to handle three dimensional data.
Multi-level Indexing and GIS Enhanced Learning for Satellite Imageries
by Krzysztof Koperski , 2000
"... Satellite technology produces data at an enormous rate. Most of the database research on the analysis of remotely sensed images concentrated on data retrieval and simple queries that involved spatial joins and spatial selections. For example, the Sequoia 2000 project [13] aimed at the retrieval of r ..."
Satellite technology produces data at an enormous rate. Most of the database research on the analysis of remotely sensed images concentrated on data retrieval and simple queries that involved spatial joins and spatial selections. For example, the Sequoia 2000 project [13] aimed at the retrieval of raster data, while the Sloan Digital Sky Survey [14] poses the need for the creation of multiterabyte astronomy archive. The large scale systems for the analysis of remotely sensed images were specialized toward the detection of particular features like volcanoes [2], or proposed distributed and parallel data storage and query processing systems for handling of geo-scientific data retrieval queries [11]. The GeoBrowse project aims to provide infrastructure that would enable the analysis of large databases containing satellite images. Our work addresses two issues. One is the extraction of information that enables reduction of the data from multi-spectral images into a number of features. Seco...
Data Models and Query Languages of Spatio-Temporal Information
by Cindy Xinmin Chen , 2001
by unknown authors
"... The use of scripting makes it possible to overcome many important difficulties in the development of database applications. By extending a general-purpose scripting lan-guage with constructs derived both from the database kernel and from the intended application domain, issues such as query processi ..."
The use of scripting makes it possible to overcome many important difficulties in the development of database applications. By extending a general-purpose scripting lan-guage with constructs derived both from the database kernel and from the intended application domain, issues such as query processing and user interfacing can be approached in an economical and flexible way. This is illustrated by describing our experience with SAND-Tcl, a scripting tool developed by us for building spatial database applications. SAND-Tcl is an extension of the Tcl-embedded scripting language with the constructs of the SAND environment for developing applications involving both spatial and non-spatial data. SAND-Tcl acts as a 'glue ' to hold together all the subsystems of SAND. In fact, query evaluation plans are SAND-Tcl programs (or scripts) which are written on-the-fly by SAND in response to a query defined by the user. This permits the rapid prototyping of algorithms and makes SAND a useful tool both for applications and research. The focus is on data storage, retrieval operations, and spatial indexing. Implementations of operations such as spatial selection, ranking and spatial join are given. In addition, tools are described to make possible the construction of graphical user interfaces to a spatial database as well as providing users the ability to view and interact with spatial objects in a graphical manner. This is achieved through the use of SAND-Tcl scripts and the Tk graphical user interface toolkit which is tightly coupled to Tcl. 2002 Elsevier Science Ltd. All rights reserved. 1.
...ed and operated upon in the same way as integers or strings. Similarly, spatial access methods are viewed as analogs to linear indices such as B-trees. Among others, the Gral [6], GEO## [3], PARADISE =-=[7]-=- and SAND systems [8] all follow this approach. From the above, it is fairly clear that the integrated approach is the most flexible. The SAND system, built by us, is a prototype environment for devel...
A Consistent Thinning of Large Geographical Data for Map
by Anish Das Sarma, Hongrae Lee, Hector Gonzalez, Jayant Madhavan, Alon Halevy
Large-scale map visualization systems play an increasingly important role in presenting geographic datasets to end users. Since these datasets can be extremely large, a map rendering system often needs to select a small fraction of the data to visualize them in a limited space. This paper addresses the fundamental challenge of thinning: determining appropriate samples of data to be shown on specific geographical regions and zoom levels. Other than the sheer scale of the data, the thinning problem is challenging because of a number of other reasons: (1) data can consist of complex geographical shapes, (2) rendering of data needs to satisfy certain constraints, such as data being preserved across zoom levels and adjacent regions, and (3) after satisfying the constraints, an optimal solution needs to be chosen based on objectives such as maximality, fairness, and importance of data. This paper formally defines and presents a complete solution to the thinning problem. First, we express the problem as an integer programming formulation that efficiently solves thinning for desired objectives. Second, we present more efficient solutions for maximality, based on DFS traversal of a spatial tree. Third, we consider the common special case of point datasets, and present an even more efficient randomized algorithm. Fourth, we show that contiguous regions are tractable for a general version of maximality, for which arbitrary regions are intractable. Fifth, we examine the structure of our integer programming formulation and show that for point datasets, our program is integral. Finally, we have implemented all techniques from this paper in Google Maps [Google 2005] visualizations of Fusion Tables [Gonzalez et al. 2010], and we describe a set of experiments that demonstrate the tradeoffs among the algorithms.