k-Nearest neighbor query processing algorithm for cloaking regions towards user privacy protection in location-based services

Due to the advancement of wireless internet and mobile positioning technology, the application of location-based services (LBSs) has become popular for mobile users. Since users have to send their exact locations to obtain the service, it may lead to several privacy threats. To solve this problem, a cloaking method has been proposed to blur users’ exact locations into a cloaked spatial region with a required privacy threshold (k). With the cloaked region, an LBS server can carry out a k-nearest neighbor (k-NN) search algorithm. Some recent studies have proposed methods to search k-nearest POIs while protecting a user’s privacy. However, they have at least one major problem, such as inefficiency on query processing or low precision of retrieved result. To resolve these problems, in this paper, we propose a novel k-NN query processing algorithm for a cloaking region to satisfy both requirements of fast query processing time and high precision of the retrieved result. To achieve fast query processing time, we propose a new pruning technique based on a 2D-coodinate scheme. In addition, we make use of a Voronoi diagram for retrieving the nearest POIs efficiently. To satisfy the requirement of high precision of the retrieved result, we guarantee that our k-NN query processing algorithm always contains the exact set of k nearest neighbors. Our performance analysis shows that our algorithm achieves better performance in terms of query processing time and the number of candidate POIs compared with other algorithms.     

Data management issues in mobile and peer-to-peer environments

Mobile computing is a revolutionary technology, born as a result of remarkable advance in the development of computer hardware and wireless communication. It enables us to access information anytime and anywhere even in the absence of physical network connection. More recently, there has been increasing interest in introducing ad hoc network into mobile computing, resulting in a new distributed computing style known as peer-to-peer (P2P) computing. In this paper, we discuss the data management issues in mobile and P2P environments. The use of wireless communication makes the data availability the most important problem here, so we focus on the problem of data availability and provide detailed discussion about replicating mobile databases. Not only that, we extend our discussion to mobile–P2P environment. At the end, we discuss the general data management issues in P2P environment.     

Spatial co-location pattern mining for location-based services in road networks

With the evolution of geographic information capture and the emergency of volunteered geographic information, it is getting more important to extract spatial knowledge automatically from large spatial datasets. Spatial co-location patterns represent the subsets of spatial features whose objects are often located in close geographic proximity. Such pattern is one of the most important concepts for geographic context awareness of location-based services (LBS). In the literature, most existing methods of co-location mining are used for events taking place in a homogeneous and isotropic space with distance expressed as Euclidean, while the physical movement in LBS is usually constrained by a road network. As a result, the interestingness value of co-location patterns involving network-constrained events cannot be accurately computed. In this paper, we propose a different method for co-location mining with network configurations of the geographical space considered. First, we define the network model with linear referencing and refine the neighborhood of traditional methods using network distances rather than Euclidean ones. Then, considering that the co-location mining in networks suffers from expensive spatial-join operation, we propose an efficient way to find all neighboring object pairs for generating clique instances. By comparison with the previous approaches based on Euclidean distance, this approach can be applied to accurately calculate the probability of occurrence of a spatial co-location on a network. Our experimental results from real and synthetic data sets show that the proposed approach is efficient and effective in identifying co-location patterns which actually rely on a network.     

Long-term location privacy protection for location-based services in mobile cloud computing

The popularity of mobile devices, especially intelligent mobile phones, significantly prompt various location-based services (LBSs) in cloud systems. These services not only greatly facilitate people’s daily lives, but also cause serious threats that users’ location information may be misused or leaked by service providers. The dummy-based privacy protection techniques have significant advantages over others because they neither rely on trusted servers nor need adequate number of trustworthy peers. Existing dummy-based location privacy protection schemes, however, cannot yet provide long-term privacy protection. In this paper, we propose four principles for the dummy-based long-term location privacy protection (LT-LPP). Based on the principles, we propose a set of long-term consistent dummy generation algorithms for the LT-LPP. Our approach is built on soft computing techniques and can balance the preferred privacy protection and computing cost. Comprehensive experimental results demonstrate that our approach is effective to both long-term privacy protection and fake path generation for LBSs in mobile clouds.     

Nearest neighbor queries with peer-to-peer data sharing in mobile environments

Nearest neighbor queries, such as determining the proximity of stationary objects (e.g., restaurants and gas stations) are an important class of inquiries for supporting location-based services. We present a novel approach to support nearest neighbor queries from mobile hosts by leveraging the sharing capabilities of wireless ad-hoc networks. We illustrate how previous query results cached in the local storage of neighboring mobile users can be leveraged to either fully or partially compute and verify nearest neighbor queries at a local host. The feasibility and appeal of our technique is illustrated through extensive simulation results that indicate a considerable reduction of the query load on the remote database. Furthermore, the scalability of our approach is excellent because a higher density of mobile hosts increases its effectiveness.     

An adaptive secure communication framework for mobile peer-to-peer environments using Bayesian games

Peers in Mobile P2P (MP2P) networks exploit both the structured and unstructured styles to enable communication in a peer-to-peer fashion. Such networks involve the participation of two types of peers: benign peers and malicious peers. Complexities are witnessed in the determination of the identity of the peers because of the user mobility and the unrestricted switching (ON/OFF) of the mobile devices. MP2P networks require a scalable, distributed and light-weighted secure communication scheme. Nevertheless, existing communication approaches lack the capability to satisfy the requirements above. In this paper, we propose an Adaptive Trusted Request and Authorization model (ATRA) over MP2P networks, by exploiting the limited historical interaction information among the peers and a Bayesian game to ensure secure communication. The simulation results reveal that regardless of the peer’s ability to obtain the other such peer’s trust and risk data, the request peers always spontaneously connect the trusted resource peers and the resource peers always preferentially authorize the trusted request peers. Performance comparison of ATRA with state-of-the-art secure communication schemes over MP2P networks shows that ATRA can: (a) improve the success rate of node typing identification, (b) reduce time required for secure connections found, (c) provide efficient resource sharing, and (d) maintain the lower average cost.     

移动位置服务应用平台研究与开发

提出了一种移动位置服务的体系结构,开发、设计了其中的关键部件移动位置服务网关和位置服务应用平台,给出了实现位置服务的应用程序设计流程。经过实际测试表明,系统能够应用于移动通信网络为用户提供位置服务。     

Rational behavior in peer-to-peer profile obfuscation for anonymous keyword search

User profiling in web search has the advantage of enabling personalized web search: the quality of the results offered by the search engine to the user is increased by taking the user’s interests into account when presenting those results. The negative side is that the interests and the query history of users may contain information considered as private; hence, technology should be provided for users to avoid profiling if they wish so. There are several anti-profiling approaches in web search, from basic level countermeasures to private information retrieval and including profile obfuscation. Except private information retrieval (PIR), which hides the retrieved item from the database, the rest of approaches focus on anonymizing the user’s identity and fall into the category of anonymous keyword search (also named sometimes user-private information retrieval). Most current PIR protocols are ill-suited to provide PIR from a search engine or large database, due to their complexity and their assumption that the database actively cooperates in the PIR protocol. Peer-to-peer profile obfuscation protocols appear as a competitive option provided that peers are rationally interested in helping each other. We present a game-theoretic analysis of P2P profile obfuscation protocols which shows under which conditions helping each other is in the peers’ rational interest.     

A location-based policy-specification language for mobile devices

The dramatic rise in mobile applications has greatly increased threats to the security and privacy of users. Security mechanisms on mobile devices are currently limited, so users need more expressive ways to ensure that downloaded mobile applications do not act maliciously. Policy-specification languages were created for this purpose; they allow the enforcement of user-defined policies on third-party applications. We have implemented LoPSiL, a location-based policy-specification language for mobile devices. This article describes LoPSiL’s design and implementation, several example policies, and experiments that demonstrate LoPSiL’s viability for enforcing policies on mobile devices.     

Multidimensional data modeling for location-based services

With the recent and continuing advances in areas such as wireless communications and positioning technologies, mobile, location-based services are becoming possible.Such services deliver location-dependent content to their users. More specifically, these services may capture the movements and requests of their users in multidimensional databases, i.e., data warehouses, and content delivery may be based on the results of complex queries on these data warehouses. Such queries aggregate detailed data in order to find useful patterns, e.g., in the interaction of a particular user with the services.The application of multidimensional technology in this context poses a range of new challenges. The specific challenge addressed here concerns the provision of an appropriate multidimensional data model. In particular, the paper extends an existing multidimensional data model and algebraic query language to accommodate spatial values that exhibit partial containment relationships instead of the total containment relationships normally assumed in multidimensional data models. Partial containment introduces imprecision in aggregation paths. The paper proposes a method for evaluating the imprecision of such paths. The paper also offers transformations of dimension hierarchies with partial containment relationships to simple hierarchies, to which existing precomputation techniques are applicable.Received: 28 September 2002, Accepted: 5 April 2003, Published online: 12 August 2003Edited by: J. Veijalainen Correspondence to: I. Timko     

A context-aware scheme for privacy-preserving location-based services

We address issues related to privacy protection in location-based services (LBSs). Most existing privacy-preserving LBS techniques either require a trusted third-party (anonymizer) or use cryptographic protocols that are computationally and communicationally expensive. Our design of privacy-preserving techniques is principled on not requiring a trusted third-party while being highly efficient in terms of time and space complexities. The problem has two interesting and challenging characteristics: First, the degree of privacy protection and LBS accuracy depends on the context, such as population and road density, around a user’s location. Second, an adversary may violate a user’s location privacy in two ways: (i) based on the user’s location information contained in the LBS query payload and (ii) by inferring a user’s geographical location based on the device’s IP address. To address these challenges, we introduce CAP, a context-aware privacy-preserving LBS system with integrated protection for both data privacy and communication anonymity. We have implemented CAP and integrated it with Google Maps, a popular LBS system. Theoretical analysis and experimental results validate CAP’s effectiveness on privacy protection, LBS accuracy, and communication QoS (Quality-of-Service).     

Protecting query privacy in location-based services

The popularity of location-based services (LBSs) leads to severe concerns on users’ privacy. With the fast growth of Internet applications such as online social networks, more user information becomes available to the attackers, which allows them to construct new contextual information. This gives rise to new challenges for user privacy protection and often requires improvements on the existing privacy-preserving methods. In this paper, we classify contextual information related to LBS query privacy and focus on two types of contexts—user profiles and query dependency: user profiles have not been deeply studied in LBS query privacy protection, while we are the first to show the impact of query dependency on users’ query privacy. More specifically, we present a general framework to enable the attackers to compute a distribution on users with respect to issuing an observed request. The framework can model attackers with different contextual information. We take user profiles and query dependency as examples to illustrate the implementation of the framework and their impact on users’ query privacy. Our framework subsequently allows us to show the insufficiency of existing query privacy metrics, e.g., k-anonymity, and propose several new metrics. In the end, we develop new generalisation algorithms to compute regions satisfying users’ privacy requirements expressed in these metrics. By experiments, our metrics and algorithms are shown to be effective and efficient for practical usage.     

Preserving privacy in environments with location-based applications

The increase in location-based applications makes protecting personal location information a major challenge. Addressing this challenge requires a mechanism that lets users automate control of their location information, thereby minimizing the extent to which the system intrudes on their lives.     

A location-based personal task reminder for mobile users

Personal task reminders have been indispensable for modern people, in order to remind them of their tasks at specific circumstances. Traditional paper-based reminders are still useful, but they cannot be organized efficiently. Electronic reminders based on the calendar in cell phones are more efficient and gaining popularity, but such reminders are mostly triggered by time. In many situations, tasks are only meaningful to be performed at a specific location, so it would be useful if reminders for those tasks can be triggered only when the person to be reminded is physically near or located at that location. Therefore, in this research, we develop a location-based personal task reminder for Android-based smartphones and tablets. To distinguish our work from existing ones that rely solely on the GPS technology, we take advantage of the ubiquity of IEEE 802.11 WLAN infrastructure to compliment the “blind spots” of GPS location sensing. Combining the two technologies makes it possible for the personal task reminder to be effective in both indoor and outdoor environments. We also propose two operating models for the personal task reminder to boost the usability of the application. Furthermore, as long as the WLAN infrastructure is available, our work as a foundation of location-based services can easily be extended to be used in many other scenarios, such as guiding in public transportation systems or tourist attractions, location-based learning, and even caring of the Dementia residents.     

Landscape-aware location-privacy protection in location-based services

Mobile network providers have developed a variety of location-based services (LBSs), such as friend-finder, point of interest services, emergency rescue and many other safety and security services. The protection of location-privacy has consequently become a key aspect to the success of LBSs, since users consider their own physical location and movements highly privacy-sensitive, and demand for solutions able to protect such an information in a variety of environments. The idea behind location-privacy protection is that the individual should be able to set the level at which the location information is released to avoid undesired exploitation by a potential attacker: one of the approaches to this problem is given by the application of spatial obfuscation techniques, actuated by a trusted agent, and consisting in artificial perturbations of the location information collected by sensing technologies, before its disclosure to third parties. In many situations, however, landscape/map information can help a third party to perform Bayesian inference over spatially obfuscated data and to refine the user’s location estimate up to a violation of the original user’s location-privacy requirements. The goal of this paper is to provide a map-dependent obfuscation procedure that enables the release of the maximum possible user’s location information, that does not lead to a violation of the original user’s location-privacy requirements, even when refined through map-based inference.     

Overlay construction for mobile peer-to-peer video broadcasting

An efficient overlay is a crucial component of wireless cooperative live video streaming networks—an emerging wireless streaming solution with ever-increasing storage and computation capabilities, and provides scalability, autonomy, carrier-billing network bandwidth conservation, service coverage extension, etc. Based on whether routes are pre-calculated and maintained, or determined per-hop in reactive to each data piece, the streaming overlay can be classified as either unstructured, structured, or hybrid. We discuss issues, properties and example approaches of each category in detail, and present quantitative and qualitative comparisons on their strengths and weaknesses in terms of system robustness, overlay maintenance complexity, delivery ratio, end-to-end delay, etc. Finally we discuss some open issues and emerging areas regarding overlay construction.     

Clustering distributed data streams in peer-to-peer environments

This paper describes a technique for clustering homogeneously distributed data in a peer-to-peer environment like sensor networks. The proposed technique is based on the principles of the K-Means algorithm. It works in a localized asynchronous manner by communicating with the neighboring nodes. The paper offers extensive theoretical analysis of the algorithm that bounds the error in the distributed clustering process compared to the centralized approach that requires downloading all the observed data to a single site. Experimental results show that, in contrast to the case when all the data is transmitted to a central location for application of the conventional clustering algorithm, the communication cost (an important consideration in sensor networks which are typically equipped with limited battery power) of the proposed approach is significantly smaller. At the same time, the accuracy of the obtained centroids is high and the number of samples which are incorrectly labeled is also small.     

LBS的一种隐私保护模型

移动位置服务(LBS)是一个分布式多方参与的系统,给移动商业应用带来了一个快速发展的时机,但由于其拥有访问私人信息的权利,以至于也给它们的用户隐私带来很大的风险.为此,通过对能够有效保护用户隐私的模型进行了研究,提出了一个体系结构和一个协议,协议中使用一个位置中间件把来自LBS供应商提供的用户关心的区域信息和来自移动运营商的用户位置信息进行匹配.结果表明,该协议使得隐私友好的服务成为可能,而且仍然是高效率.