Mining of spatial data is an enabling technology for mobile services, Internet-connected cars and the Internet of Things. But the very distinctiveness of spatial data that drives utility can cost user privacy. Past work has focused upon points and trajectories for differentially private release. In this work, we continue the tradition of privacy-preserving spatial analytics, focusing not on point or path data, but on planar spatial regions. Such data represent the area of a user’s most frequent visitation—such as “around home and nearby shops”. Specifically we consider the differentially private release of data structures that support range queries for counting users’ spatial regions. Counting planar regions leads to unique challenges not faced in existing work. A user’s spatial region that straddles multiple data structure cells can lead to duplicate counting at query time. We provably avoid this pitfall by leveraging the Euler characteristic for the first time with differential privacy. To address the increased sensitivity of range queries to spatial region data, we calibrate privacy-preserving noise using bounded user region size and a constrained inference that uses robust least absolute deviations. Our novel constrained inference reduces noise and promotes covertness by (privately) imposing consistency. We provide a full end-to-end theoretical analysis of both differential privacy and high-probability utility for our approach using concentration bounds. A comprehensive experimental study on several real-world datasets establishes practical validity.
A key challenge in aggregation is the distinct counting @cite_14 @cite_7 @cite_20 @cite_3 @cite_53 or multiple-counting problem @cite_36 @cite_46 . In contrast to point objects, a spatial body can span more than one cell in a partitioned space, inhibiting the ability of regular histograms to form accurate counts. Euler histograms @cite_45 are designed to address this problem for convex bodies @cite_36 @cite_46 , by appealing to Euler's formula from graph theory @cite_39 . A variation of Euler histogram has been studied for trajectory data to address aggregate queries on moving objects @cite_19 . In that work, Euler histograms were used in a distributed setting (motivating a distributed Euler histogram), to tackle the duplicate (distinct) entry problem rather than duplicate (distinct) counting. The Euler-histogram tree @cite_23 has been studied as a tree-based data structure for counting vehicle trajectories using the approach first developed in @cite_52 to address the distinct counting problem for reducing storage requirements.
@cite_14 @cite_7 @cite_36 @cite_53 @cite_52 @cite_3 @cite_39 @cite_19 @cite_45 @cite_23 @cite_46 @cite_20
1546365363 2112128729 1851595508 2080393976 1002055276 2117010345 571207148 2019972606 1520033739 1978945372 2023578311
Spatial databases store information about the position of individual objects in space. In many applications however, such as traffic supervision or mobile communications, only summarized data, like the number of cars in an area or phones serviced by a cell, is required. Although this information can be obtained from transactional spatial databases, its computation is expensive, rendering online processing inapplicable. Driven by the non-spatial paradigm, spatial data warehouses can be constructed to accelerate spatial OLAP operations. In this paper we consider the star-schema and we focus on the spatial dimensions. Unlike the non-spatial case, the groupings and the hierarchies can be numerous and unknown at design time, therefore the well-known materialization techniques are not directly applicable. In order to address this problem, we construct an ad-hoc grouping hierarchy based on the spatial index at the finest spatial granularity. We incorporate this hierarchy in the lattice model and present efficient methods to process arbitrary aggregations. We finally extend our technique to moving objects by employing incremental update methods. Several spatio-temporal applications require the retrieval of summarized information about moving objects that lie in a query region during a query interval (e.g., the number of mobile users covered by a cell, traffic volume in a district, etc.). Existing solutions have the distinct counting problem: if an object remains in the query region for several timestamps during the query interval, it will be counted multiple times in the result. We solve this problem by integrating spatio-temporal indexes with sketches, traditionally used for approximate query processing. The proposed techniques can also be applied to reduce the space requirements of conventional spatio-temporal data and to mine spatio-temporal association rules. Spatial join is an expensive operation that is commonly used in spatial database systems. In order to generate efficient query plans for the queries involving spatial join operations, it is crucial to obtain accurate selectivity estimates for these operations. In this paper we introduce a framework for estimating the selectivity of spatial joins constrained by geometric selections. The center piece of the framework is Euler Histogram, which decomposes the estimation process into estimations on vertices, edges and faces. Based on the characteristics of different datasets, different probabilistic models can be plugged into the framework to provide better estimation results. To demonstrate the effectiveness of this framework, we implement it by incorporating two existing probabilistic models, and compare the performance with the Geometric Histogram [1] and the algorithm recently proposed by Mamoulis and Papadias. In this paper we present a formal framework for modelling a trajectory data warehouse (TDW), namely a data warehouse aimed at storing aggregate information on trajectories of moving objects, which also offers visual OLAP operations for data analysis. The data warehouse model includes both temporal and spatial dimensions, and it is flexible and general enough to deal with objects that are either completely free or constrained in their movements (e.g., they move along a road network). In particular, the spatial dimension and the associated concept hierarchy reflect the structure of the environment in which the objects travel. Moreover, we cope with some issues related to the efficient computation of aggregate measures, as needed for implementing roll-up operations. The TDW and its visual interface allow one to investigate the behaviour of objects inside a given area as well as the movements of objects between areas in the same neighbourhood. A user can easily navigate the aggregate measures obtained from OLAP queries at different granularities, and get overall views in time and in space of the measures, as well as a focused view on specific measures, spatial areas, or temporal intervals. We discuss two application scenarios of our TDW, namely road traffic and vessel movement analysis, for which we built prototype systems. They mainly differ in the kind of information available for the moving objects under observation and their movement constraints. Due to the high uptake of location-based services (LBSs), large spatio-temporal datasets of moving objects' trajectories are being created every day. An important task in spatial data analytics is to service range queries by returning trajectory counts within a queried region. The question of how to keep an individual user's data private whilst enabling spatial data analytics by third parties has become an urgent research direction. Indeed, it is increasingly becoming a concern for users. To preserve privacy we discard individual trajectories and aggregate counts over a spatial and temporal partition. However the privacy gained comes at a cost to utility: trajectories passing through multiple cells and re-entering a query region, lead to inaccurate query responses. This is known as the distinct counting problem. We propose the Connection Aware Spatial Euler (CASE) histogram to address this long-standing problem. The CASE histogram maintains the connectivity of a moving object path, but does not require the ID of an object to distinguish multiple entries into an arbitrary query region. Our approach is to process trajectories offline into aggregate counts which are sent to third parties, rather than the original trajectories. We also explore modifications of our aggregate counting approach that preserve differential privacy. Theoretically and experimentally we demonstrate that our method provides a high level of accuracy compared to the best known methods for the distinct counting problem, whilst preserving privacy. We conduct our experiments on both synthetic and real datasets over two competitive Euler histogram-based methods presented in the literature. Our methods enjoy improvements to accuracy from 10 up to 70 depending on trip data and query region size, with the greatest increase seen on the Microsoft T-Drive real dataset, representing a more than tripling of accuracy. In this paper we discuss how data warehousing technology can be used to store aggregate information about trajectories and perform OLAP operations over them. To this end, we define a data cube with spatial and temporal dimensions, discretized according to a regular grid. We investigate in depth some issues related to the computation of a holistic aggregate function, i.e, the presence, which returns the number of distinct trajectories occurring in a given spatio-temporal area. In particular, we introduce a novel way to compute an approximate, but nevertheless very accurate, presence aggregate function, which uses only a bounded amount of measures stored in the base cells of our cuboid. We also concentrate on the loading phase of our data warehouse, which has to deal with an unbounded stream of trajectory observations. We suggest how the complexity of this phase can be reduced, and we analyse the errors that this procedure induces at the level of the sub-aggregates stored in the base cells. These errors and the accuracy of our approximate aggregate functions are carefully evaluated by means of tests performed on synthetic trajectory datasets. For monitoring moving objects via wireless sensor networks, we introduce two aggregate query types: distinct entries to an area and the number of objects in that area. We present a new technique, Distributed Euler Histograms (DEHs), to store and query aggregated moving object data. Aggregate queries occur in a variety of applications ranging from wildlife monitoring to traffic management. We show that DEHs are significantly more efficient, in terms of communication and data storage costs, than techniques based on moving object identifiers and more accurate than techniques based on simple histograms. We present a geometric counting problem that arises in browsing and solve it in constant time per query using nonexhaustive tables. On the other hand, we prove that several closely related problems require exhaustive tables, no matter how much time we allow per query. This work addresses the problem of aggregation of trajectories data. Specifically, we propose a tree-based data structure for counting vehicle trajectories by mapping them into a set of spatial histograms with different granularities. We also present an approach for processing spatio-temporal range queries by aggregating the histograms in the query rectangles. The proposed methodology can be used for preserving the privacy of vehicle drivers by maintaining aggregated trajectory data. In addition, as we show, it can be used to handle the well-known distinct counting problem. Experimental results show that the new data structure achieves a high level of accuracy in query results and consistently outperforms the leading histogram-based approach. Spatiotemporal databases are becoming increasingly more common. Typically, applications modeling spatiotemporal objects need to process vast amounts of data. In such cases, generating aggregate information from the data set is more useful than individually analyzing every entry. In this paper, we study the most relevant techniques for the evaluation of aggregate queries on spatial, temporal, and spatiotemporal data. We also present a model that reduces the evaluation of aggregate queries to the problem of selecting qualifying tuples and the grouping of these tuples into collections on which an aggregate function is to be applied. This model gives us a framework that allows us to analyze and compare the different existing techniques for the evaluation of aggregate queries. At the same time, it allows us to identify opportunities for research on types of aggregate queries that have not been studied.