Nowadays people can access LBSs as a group via mobile devices to plan their daily activities with friends and relatives. In this paper, we introduce an important class of group oriented LBSs, group optimal accessible location (GOAL) queries that enable users to identify the location of a point of interest (POI) that has the minimum total distance to a given set of paths. GOAL queries have many applications such as the selection of an optimal location for group meet-ups or for a mobile facility such as a food truck. In a GOAL query, each trip or path is represented as a set of line segments and the distance of a POI from a path is computed as the minimum distance of the POI to any line segment of the path. We develop an efficient approach to evaluate GOAL queries. The novelty of our GOAL query processing algorithm in contrast to other spatial query processing algorithms is the reformulation of a GOAL query by considering only a subset of path segments from the given set of paths, which is also the key ingredient behind the efficiency of our proposed algorithm. We exploit geometric properties and develop pruning techniques to eliminate both POIs and path segments that cannot provide the optimal solution for a GOAL query. Our experimental results demonstrate that we provide a readily deployable solution for real-life applications.
Road networks are essential nowadays, especially for people travelling to large, unfamiliar cities. Moreover, cities are constantly growing and road networks need periodical updates to provide reliable information. We propose an automatic method to generate the road network using a GPS trajectory dataset. The method, titled CellNet, works by first detecting the intersections (junctions) using a clustering-based technique and then creating the road segments in-between. We compare CellNet against three conceptually different state-of-the-art alternatives. The results show that CellNet provides better accuracy and is less sensitive to parameter setup. The generated road network occupies only 25% of the memory required for the networks produced by other methods.
The plethora of location-aware devices has led to countless location-based services in which huge amounts of spatio-temporal data get created every day. Several applications require efficient processing of queries on the locations of moving objects over time, i.e., the moving object trajectories. This calls for efficient trajectory-based indexing methods that capture both the spatial and temporal dimensions of the data in a way that minimizes the number of disk I/Os required for both updating and querying. Most existing spatio-temporal index structures capture either the current locations of the moving objects or the entire history of the moving objects. Historical spatio-temporal indexing methods require multiple disk I/Os to process new updates, and use a discrete trajectory representation that may result in incomplete query results. In this paper, we introduce the trails-tree, a disk-based data structure for indexing recent trajectories. The trails-tree requires half the number of disk I/Os needed by other historical spatio-temporal indexing methods. We give a detailed description of the trails-tree, and we mathematically analyze its performance. Moreover, we present a novel query processing algorithm that ensures the completeness of the query resultset. We experimentally verify the performance of the trails-tree using various real and synthetic datasets.
The visualization of georeferenced thematic data by virtual environments represents a key functional requirement in a large number of geo-information applications and systems. The perception of large, detailed thematic data sets, however, can be inhibited by visual clutter and information overload, especially in case of three-dimensional data. Level-of-detail visualization techniques can mitigate these issues and guide the viewers in their analyses. While the commonly used geometric level-of-detail techniques can reduce the complexity of the data's reference geometry, they generally do not take into account thematic data. This article presents two spatial aggregation techniques for generating level-of-detail representations for thematic data: The scene-based technique aggregates data solely based on spatial locations, thus supporting visual analysis of data with arbitrary reference geometry. The object-based technique performs aggregation based on scene-specific objects and their hierarchy to facilitate per-object analysis. Both techniques operate in real-time during rendering to support on-the-fly and on-demand level-of-detail generation for the visualization of spatiotemporal data sets. We demonstrate the application of both techniques using real-world data sets, including solar potential analyses and the propagation of pressure waves in a virtual city model.
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 empirical study, we investigate the geographical characteristics of the Internet as well as examine the relation between geography and intra-AS and inter-AS routing policies. We show that the ingress-to-egress subpaths have lower circuitousness compared to the end-to-end paths. Our findings not only demonstrate the efficient backbone infrastructures deployed by ASes but also show the consequences of economical incentives on the adoption of inter-AS paths. We present and examine the existence of a strong correlation between the geographical distance and round trip delay time as well as the lack of a correlation between the geographical distance and hop length in the Internet. We investigate the relation between the geographical distance and intra-AS routing policies by employing cross-AS Internet topology maps. Our results show that more than two thirds of the intra-AS subpaths are congruent with the shortest geographical distance whether or not the geographical distance is employed as a parameter in routing decisions. Our results provide new insights into the relations between geography and Internet routing which allow the network researchers and practitioners to improve their networking infrastructures, reevaluate their routing policies, deploy geography-aware network overlays and develop more realistic network simulation processes.
Several existing 2D vector map fragile watermarking methods cannot locate all the regions affected by tampering. Once these tampered regions are detected as untampered, some misuses of the vector map data may be caused. In this paper, we propose a fragile watermarking framework that locates regions of tampered spatial features. In particular, we propose dividing the features of the host vector map into groups, and embedding a watermark consisting of location-bits and check-bits into each group. On the receiver side, by comparing the extracted and calculated check-bits, one can identify the tampered groups and their current regions. Then the location-bits extracted from the mapping groups are used to indicate the original regions of the tampered groups. We demonstrate and analyze the applicability of this framework by instantiating it with a simulated annealing (SA) based group division method, a minimum encasing rectangle (MER) based location-bits generation method and an existing reversible data hiding method. The experimental results show that the proposed framework can locate the regions influenced by tampering, and the SA based group division method can get a better region location accuracy.