Location-based queries enable fundamental services for mobile users. While the benefits of location-based services (LBS) are numerous, exposure of mobile users’ locations to untrusted LBS providers may lead to privacy concerns. This article proposesStarCloak, a utility-aware and attack-resilient location anonymization service for privacy-preserving LBS usage.StarCloakcombines several desirable properties. First, unlike conventional approaches which are indifferent to underlying road network structure,StarCloakuses the concept ofstars and proposescloaking graphsfor effective location cloaking on road networks. Second,StarCloaksupports user-specified$k$-user anonymity and$l$-segment indistinguishability, for enabling personalized privacy protection and for serving users with varying privacy preferences. Third,StarCloakachieves strong attack-resilience against replay and query injection attacks through randomized star selection and pruning. Finally, to enable efficient query processing with high throughput and low bandwidth overhead,StarCloakmakes cost-aware star selection decisions by considering query evaluation and network communication costs. We evaluateStarCloakon two datasets using real-world road networks, under various privacy and utility constraints. Results show thatStarCloakachieves improved query success rate and throughput, reduced anonymization time and network usage, and higher attack-resilience in comparison toXStar, its most relevant competitor.

While location-based services and applications are increasing in popularity, there are growing concerns over users' location privacy. Although there exist general purpose mobile permission systems and cloaking techniques, these techniques suffer from several problems when applied to continuous location and GPS access, as they are often rigid, coarse-grained, not sufficiently personalizable, and unaware of road network semantics. This paper proposes PrivacyZone, a novel system for constructing personalized fine-grained privacy quarantine regions and protecting users' privacy within these regions. PrivacyZone allows users to seamlessly enter their privacy specifications under spatial, temporal, and semantic customization. Novel challenges arise from having to enforce privacy zones for large volume and variety of users with frequent location updates. We show that naive privacy zone processing techniques are inefficient and cause excessive energy consumption. We therefore develop advanced processing techniques based on the concept of safe hibernation. We empirically evaluate our techniques to demonstrate their trade-offs with respect to hibernation time, computation effort, and network bandwidth usage. Our results show that PrivacyZone is efficient, scalable, and flexible, while preserving users' location privacy.

Road network-aware spatial alarms extend the concept of time-based alarms to spatial dimension and remind us when we travel on spatially constrained road networks and enter some predefined locations of interest in the future. This paper argues that road network-aware spatial alarms need to be processed by taking into account spatial constraints on road networks and mobility patterns of mobile subscribers. We show that the Euclidian distance-based spatial alarm processing techniques tend to incur high client energy consumption due to unnecessarily frequent client wakeups. We design and develop a road network-aware spatial alarm processing system, called ROADALARM, with three unique features. First, we introduce the concept of road network-based spatial alarms using road network distance measures. Instead of using a rectangular region, a road network-aware spatial alarm is a star-like subgraph with an alarm target as the center of the star and border points as the scope of the alarm region. Second, we describe a baseline approach for spatial alarm processing by exploiting two types of filters. We use subscription filter and Euclidean lower bound filter to reduce the amount of shortest path computations required in both computing alarm hibernation time and performing alarm checks at the server. Last but not the least, we develop a suite of optimization techniques using motion-aware filters, which enable us to further increase the hibernation time of mobile clients and reduce the frequency of wakeups and alarm checks, while ensuring high accuracy of spatial alarm processing. Our experimental results show that the road network-aware spatial alarm processing significantly outperforms existing Euclidean space-based approaches, in terms of both the number of wakeups and the hibernation time at mobile clients and the number of alarm checks at the server.

Most existing solutions on location anonymization fail to address the issue of location privacy protection for mobile users traveling on road networks. In this paper, we present a road network-aware privacy model to handle the location privacy problem in mobile systems. We present third party supported anonymization which can be plugged into existing mobile systems without major modifications. As opposed to current road network specific solutions, our system has the following salient features. First, we argue that the graph density of a cloaked subgraph is an important location cloaking quality measure for road network-based location privacy protection. High graph density leads to high utility of the cloaked location with respect to spatial resolution. Second, we devise a suite of graph-based cloaking algorithms which guarantee reciprocity - an important location cloaking property that many existing approaches fail to support - under an enhanced privacy model. Further, we use controlled randomization in the cloaking process to provide higher privacy strength while maintaining the utility of the cloaked location. Last but not the least, our experimental evaluation shows the efficiency and robustness of the approach in terms of privacy, utility and performance of the model.

Many popular web service networks are content-rich in terms of heterogeneous types of entities and links, associated with incomplete attributes. Clustering such heterogeneous service networks demands new clustering techniques that can handle two heterogeneity challenges: (1) multiple types of entities co-exist in the same service network with multiple attributes, and (2) links between entities have diverse types and carry different semantics. Existing heterogeneous graph clustering techniques tend to pick initial centroids uniformly at random, specify the number k of clusters in advance, and fix k during the clustering process. In this paper, we propose Service Cluster, a novel heterogeneous service network clustering algorithm with four unique features. First, we incorporate various types of entity, attribute and link information into a unified distance measure. Second, we design a Discrete Steepest Descent method to naturally produce initial k and initial centroids simultaneously. Third, we propose a dynamic learning method to automatically adjust the link weights towards clustering convergence. Fourth, we develop an effective optimization strategy to identify new suitable k and k well-chosen centroids at each clustering iteration. Extensive evaluation on real datasets demonstrates that Service Cluster outperforms existing representative methods in terms of both effectiveness and efficiency.

In recent years, systems researchers have devoted considerable effort to the study of large-scale graph processing. Existing distributed graph processing systems such as Pregel, based solely on distributed memory for their computations, fail to provide seamless scalability when the graph data and their intermediate computational results no longer fit into the memory; and most distributed approaches for iterative graph computations do not consider utilizing secondary storage a viable solution. This paper presents GraphMap, a distributed iterative graph computation framework that maximizes access locality and speeds up distributed iterative graph computations by effectively utilizing secondary storage. GraphMap has three salient features: (1) It distinguishes data states that are mutable during iterative computations from those that are read-only in all iterations to maximize sequential access and minimize random access. (2) It entails a two-level graph partitioning algorithm that enables balanced workloads and locality-optimized data placement. (3) It contains a proposed suite of locality-based optimizations that improve computational efficiency. Extensive experiments on several real-world graphs show that GraphMap outperforms existing distributed memory-based systems for various iterative graph algorithms.

Spatial alarms are one of the fundamental functionalities for many LBSs. We argue that spatial alarms should be road network aware as mobile objects travel on spatially constrained road networks or walk paths. In this software system demonstration, we will present the first prototype system of ROADALARM - a spatial alarm processing system for moving objects on road networks. The demonstration system of ROAD-ALARM focuses on the three unique features of ROADALARM system design. First, we will show that the road network distance-based spatial alarm is best modeled using road network distance such as segment length-based and travel time-based distance. Thus, a road network spatial alarm is a star-like subgraph centered at the alarm target. Second, we will show the suite of ROADALARM optimization techniques to scale spatial alarm processing by taking into account spatial constraints on road networks and mobility patterns of mobile subscribers. Third, we will show that, by equipping the ROADALARM system with an activity monitoring-based control panel, we are able to enable the system administrator and the end users to visualize road network-based spatial alarms, mobility traces of moving objects and dynamically make selection or customization of the ROADALARM techniques for spatial alarm processing through graphical user interface. We show that the ROADALARM system provides both the general system architecture and the essential building blocks for location-based advertisements and location-based reminders.

Location based queries are increasingly common in mobile applications, and the associated privacy issues have become a hot research topic in the last years. Most of the current approaches, however, do not account for the location of potentially sensitive places and for constraints on the movement of users, such as speed limits or network contraints. In this demo we present different deployment scenarios of a privacy-preserving framework for the protection of sensitive positions in real time trajectories. We assume that the sensitivity of users' positions depends on the spatial context, while the users' movement is confined to road networks and places. Further, the users are non-anonymous, as in the case of geo-social network members who agree to share their exact position whenever it does not fall within a sensitive place, e.g. a hospital. We will show that our proposal is suitable for different classes of devices and can be integrated in different kind of location based applications.

This paper presents a privacy-preserving framework for the protection of sensitive positions in real time trajectories. We assume a scenario in which the sensitivity of user's positions is space-varying, and so depends on the spatial context, while the user's movement is confined to road networks and places. Typical users are the non-anonymous members of a geo-social network who agree to share their exact position whenever such position does not fall within a sensitive place, e.g. a hospital. Suspending location sharing while the user is inside a sensitive place is not an appropriate solution because the user's stopovers can be easily inferred from the user's trace. In this paper we present an extension of the semantic location cloaking model [1] originally developed for the cloaking of non-correlated positions in an unconstrained space. We investigate different algorithms for the generation of cloaked regions over the graph representing the urban setting. We also integrate methods to prevent velocity-based linkage attacks. Finally we evaluate experimentally the algorithms using a real data set.