ACM Transactions on

Spatial Algorithms and Systems (TSAS)

Latest Articles

Efficient Computation of the Optimal Accessible Location for a Group of Mobile Agents

Nowadays, people can access location-based services (LBSs) as a group via mobile devices to plan their daily activities with friends and relatives. In... (more)

Geography and Routing in the Internet

The Internet is a network of networks consisting of tens of thousands of Autonomous Systems (ASes). These ASes connect to each other in different forms to enable the “global” Internet communication. In this study, we investigate the geographical characteristics of the visible Internet as well as examine the relation between... (more)

2D Vector Map Fragile Watermarking with Region Location

Locating the original region of tampered features is a challenging task for existing 2D vector map fragile watermarking methods. This article presents... (more)


 ACM Transactions on Spatial Algorithms and Systems (TSAS) is a scholarly journal that publishes high-quality papers on all aspects of spatial algorithms and systems and closely related disciplines. The journal welcomes articles on any of the above topics or closely related disciplines in the context of various computing architectures including parallel and distributed networks of computers, multiprocessing computers, or new mobile devices and sensors. READ MORE

Call-for-papers: ACM TSAS has issued a call for papers for a Special issue on Urban Mobility: Algorithms and Systems. Please use manuscriptcentral ( to submit articles, check the status of articles and for reviewing tasks.

Forthcoming Articles
Dictionary Compression in Point Cloud Data Management

Nowadays, massive amounts of point cloud data can be collected thanks to advances in data acquisition and processing technologies like dense image matching and airborne LiDAR scanning. With the increase in volume and precision, point cloud data offers a useful source of information for natural resource management, urban planning, self-driving cars and more. At the same time, the scale at which point cloud data is produced, introduces management challenges: it is important to achieve efficiency both in terms of querying performance and space requirements. Traditional file-based solutions to point cloud management offer space efficiency, however, cannot scale to such massive data and provide the declarative power of a DBMS. In this paper, we propose a time- and space-efficient solution to storing and managing point cloud data in main memory column-store DBMS. Our solution, Space-Filling Curve Dictionary-Based Compression (SFC-DBC), employs dictionary-based compression in the spatial data management domain and enhances it with indexing capabilities by using space-filling curves. SFC-DBC does so by constructing the space-filling curve over a compressed, artificially introduced dictionary space. Consequently, SFC-DBC significantly optimizes query execution, and yet does not require additional storage resources, compared to traditional dictionary-based compression. With respect to space-filling curve-based approaches, it minimizes storage footprint and increases resilience to skew. As a proof of concept, we develop and evaluate our approach as a research prototype in the context of SAP HANA. SFC-DBC outperforms other dictionary-based compression schemes by up to 61% in terms of space and up to 9.4x in terms of query performan

Flood Risk Analysis on Terrains

An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this paper we study the \emph{flooding query} problem: Preprocess a given terrain $\terrain$, represented as a triangulated $xy$-monotone surface with $n$ vertices, into a data structure so that for a query rain region $\varregion$ and a query point $q$ on $\terrain$, one can quickly determine how much rain has to fall in $\varregion$ so that $q$ is flooded. Available terrain data is often subject to uncertainty which must be incorporated into the terrain analysis. By representing the uncertainty in the terrain data explicitly, we can develop methods for flood risk analysis that properly incorporate terrain uncertainty when reporting what areas are at risk of flooding. We present two results. First, we present an $\BigO(n\log{n})$-time algorithm for preprocessing $\terrain$ with a linear-size data structure that can answer a flooding query in $\BigO(|\varregion|+\varrainpoints \log n)$ time, where $|\varregion|$ is the number of vertices in $\varregion$, $\varrainpoints$ is the number of minima of the terrain at which rain is falling, and $n$ is the number of vertices of the terrain. Next, we extend this data structure to handle ``uncertain'' terrains, using a standard Monte Carlo method. Given a probability distribution on terrain data, our data structure returns the probability of a query point being flooded if a specified amount of rain falls on a query region.

All ACM Journals | See Full Journal Index

Search TSAS
enter search term and/or author name