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.     

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.     

Anonymous Query Processing in Road Networks

The increasing availability of location-aware mobile devices has given rise to a flurry of location-based services (LBSs). Due to the nature of spatial queries, an LBS needs the user position in order to process her requests. On the other hand, revealing exact user locations to a (potentially untrusted) LBS may pinpoint their identities and breach their privacy. To address this issue, spatial anonymity techniques obfuscate user locations, forwarding to the LBS a sufficiently large region instead. Existing methods explicitly target processing in the euclidean space and do not apply when proximity to the users is defined according to network distance (e.g., driving time through the roads of a city). In this paper, we propose a framework for anonymous query processing in road networks. We design location obfuscation techniques that: 1) provide anonymous LBS access to the users and 2) allow efficient query processing at the LBS side. Our techniques exploit existing network database infrastructure, requiring no specialized storage schemes or functionalities. We experimentally compare alternative designs in real road networks and demonstrate the effectiveness of our techniques.     

L2P2: A location-label based approach for privacy preserving in LBS

The developments in positioning and mobile communication technology have made the location-based service (LBS) applications more and more popular. For privacy reasons and due to lack of trust in the LBS providers, k-anonymity and l-diversity techniques have been widely used to preserve privacy of users in distributed LBS architectures in Internet of Things (IoT). However, in reality, there are scenarios where the locations of users are identical or similar/near each other in IoT. In such scenarios the k locations selected by k-anonymity technique are the same and location privacy can be easily compromised or leaked. To address the issue of privacy preservation, in this paper, we introduce the location labels to distinguish locations of mobile users to sensitive and ordinary locations. We design a location-label based (LLB) algorithm for protecting location privacy of users while minimizing the response time for LBS requests. We also evaluate the performance and validate the correctness of the proposed algorithm through extensive simulations.     

SMashQ: spatial mashup framework for k-NN queries in time-dependent road networks

The k-nearest-neighbor (k-NN) query is one of the most popular spatial query types for location-based services (LBS). In this paper, we focus on k-NN queries in time-dependent road networks, where the travel time between two locations may vary significantly at different time of the day. In practice, it is costly for a LBS provider to collect real-time traffic data from vehicles or roadside sensors to compute the best route from a user to a spatial object of interest in terms of the travel time. Thus, we design SMashQ, a server-side spatial mashup framework that enables a database server to efficiently evaluate k-NN queries using the route information and travel time accessed from an external Web mapping service, e.g., Microsoft Bing Maps. Due to the expensive cost and limitations of retrieving such external information, we propose three shared execution optimizations for SMashQ, namely, object grouping, direction sharing, and user grouping, to reduce the number of external Web mapping requests and provide highly accurate query answers. We evaluate SMashQ using Microsoft Bing Maps, a real road network, real data sets, and a synthetic data set. Experimental results show that SMashQ is efficient and capable of producing highly accurate query answers.     

Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments

This paper tackles a privacy breach in current location-based services (LBS) where mobile users have to report their exact location information to an LBS provider in order to obtain their desired services. For example, a user who wants to issue a query asking about her nearest gas station has to report her exact location to an LBS provider. However, many recent research efforts have indicated that revealing private location information to potentially untrusted LBS providers may lead to major privacy breaches. To preserve user location privacy, spatial cloaking is the most commonly used privacy-enhancing technique in LBS. The basic idea of the spatial cloaking technique is to blur a user’s exact location into a cloaked area that satisfies the user specified privacy requirements. Unfortunately, existing spatial cloaking algorithms designed for LBS rely on fixed communication infrastructure, e.g., base stations, and centralized/distributed servers. Thus, these algorithms cannot be applied to a mobile peer-to-peer (P2P) environment where mobile users can only communicate with other peers through P2P multi-hop routing without any support of fixed communication infrastructure or servers. In this paper, we propose a spatial cloaking algorithm for mobile P2P environments. As mobile P2P environments have many unique limitations, e.g., user mobility, limited transmission range, multi-hop communication, scarce communication resources, and network partitions, we propose three key features to enhance our algorithm: (1) An information sharing scheme enables mobile users to share their gathered peer location information to reduce communication overhead; (2) A historical location scheme allows mobile users to utilize stale peer location information to overcome the network partition problem; and (3) A cloaked area adjustment scheme guarantees that our spatial cloaking algorithm is free from a “center-of-cloaked-area” privacy attack. Experimental results show that our P2P spatial cloaking algorithm is scalable while guaranteeing the user’s location privacy protection.     

基于轨迹聚类的连续查询隐私保护方法

在LBS连续查询的应用场景下,攻击者易利用查询时间序列、区域位置、移动趋势等背景知识发起有效的攻击,以获取用户的真实位置或轨迹,进而可推断出用户生活习惯等各类隐私信息。针对此,提出了一种基于轨迹聚类的连续查询隐私保护方法。该方法基于邻近用户的信息共享与协作,设计了一种匿名区域构造机制,用户在查询过程中,首先通过被共享缓存获取所需服务结果,如未命中,再向LBS服务器发起查询请求。同时,提出了一种邻近用户位置更新算法,提高用户的协作效率并保证缓存的有效性,对于由命中缓存完成的查询,采用提出的基于密度聚类的兴趣区提取算法,生成高混淆度的假查询扰乱整体查询序列顺序,以此增强轨迹隐私的保护效果。实验结果表明,该方法降低了连续查询中的时间代价,提高了位置混淆程度。     

Slicing the metric space to provide quick indexing of complex data in the main memory

Searching in a dataset for elements that are similar to a given query element is a core problem in applications that manage complex data, and has been aided by metric access methods (MAMs). A growing number of applications require indices that must be built faster and repeatedly, also providing faster response for similarity queries. The increase in the main memory capacity and its lowering costs also motivate using memory-based MAMs. In this paper, we propose the Onion-tree, a new and robust dynamic memory-based MAM that slices the metric space into disjoint subspaces to provide quick indexing of complex data. It introduces three major characteristics: (i) a partitioning method that controls the number of disjoint subspaces generated at each node; (ii) a replacement technique that can change the leaf node pivots in insertion operations; and (iii) range and k-NN extended query algorithms to support the new partitioning method, including a new visit order of the subspaces in k-NN queries. Performance tests with both real-world and synthetic datasets showed that the Onion-tree is very compact. Comparisons of the Onion-tree with the MM-tree and a memory-based version of the Slim-tree showed that the Onion-tree was always faster to build the index. The experiments also showed that the Onion-tree significantly improved range and k-NN query processing performance and was the most efficient MAM, followed by the MM-tree, which in turn outperformed the Slim-tree in almost all the tests.     

基于图压缩的k可达查询处理

研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45%,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75%和67%;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.     

支持区间查询的基于位置服务外包数据隐私保护方案

随着云计算技术的迅猛发展,越来越多的LBS服务被外包到云上运行以减少本地的计算和存储成本。然而,外包环境下的云服务器通常被认为是一个半可信的实体,LBS提供商的数据安全和用户的个人隐私将会面临新的安全挑战。针对现有基于位置服务数据外包方案中不支持区间查询和隐私保护不足等问题,文章提出一种支持区间查询的LBS外包数据隐私保护方案,利用非对称向量积保值加密和公钥可搜索加密对LBS坐标和关键词进行加密,实现LBS数据的机密性和用户查询模式的隐私性;利用轻量级的矩阵运算使用户在不泄露查询区间的前提下准确获得所需LBS数据。在新用户注册方面,采用基于双线性配对运算实现用户身份认证。安全性和性能分析表明,文章方案较同类方案具有一定优势。     

Manifold-ranking based retrieval using k-regular nearest neighbor graph

Manifold-ranking is a powerful method in semi-supervised learning, and its performance heavily depends on the quality of the constructed graph. In this paper, we propose a novel graph structure named k-regular nearest neighbor (k-RNN) graph as well as its constructing algorithm, and apply the new graph structure in the framework of manifold-ranking based retrieval. We show that the manifold-ranking algorithm based on our proposed graph structure performs better than that of the existing graph structures such as k-nearest neighbor (k-NN) graph and connected graph in image retrieval, 2D data clustering as well as 3D model retrieval. In addition, the automatic sample reweighting and graph updating algorithms are presented for the relevance feedback of our algorithm. Experiments demonstrate that the proposed algorithm outperforms the state-of-the-art algorithms.     

Blind evaluation of location based queries using space transformation to preserve location privacy

In this paper we propose a fundamental approach to perform the class of Range and Nearest Neighbor (NN) queries, the core class of spatial queries used in location-based services, without revealing any location information about the query in order to preserve users’ private location information. The idea behind our approach is to utilize the power of one-way transformations to map the space of all objects and queries to another space and resolve spatial queries blindly in the transformed space. Traditional encryption based techniques, solutions based on the theory of private information retrieval, or the recently proposed anonymity and cloaking based approaches cannot provide stringent privacy guarantees without incurring costly computation and/or communication overhead. In contrast, we propose efficient algorithms to evaluate KNN and range queries privately in the Hilbert transformed space. We also propose a dual curve query resolution technique which further reduces the costs of performing range and KNN queries using a single Hilbert curve. We experimentally evaluate the performance of our proposed range and KNN query processing techniques and verify the strong level of privacy achieved with acceptable computation and communication overhead.     

路网环境下兴趣点查询的隐私保护方法

近年来,随着无线通信技术的迅猛发展,推动了基于位置服务（Location-based services,LBS）的发展进程.而其中兴趣点（Point of Interest,POI）查询是基于位置服务最重要的应用之一.针对在路网环境下,用户查询过程中位置隐私泄露的问题,提出了一种新的位置k匿名隐私保护方法.首先,匿名服务器将兴趣点作为种子节点生成网络Voronoi图,将整个路网划分为相互独立且不重叠的网络Voronoi单元（Network Voronoi Cell,NVC）;其次,利用Hilbert曲线遍历路网空间,并按照Hilbert顺序,对路网上所有的兴趣点进行排序.当用户发起查询时,提出的匿名算法通过查找与用户所在NVC的查询频率相同且位置分散的k-1个NVC,并根据用户的相对位置在NVC内生成匿名位置,从而保证了生成的匿名集中位置之间的相互性,克服了传统k-匿名不能抵御推断攻击的缺陷.最后,理论分析和实验结果表明本文提出的隐私保护方案,能有效保护用户位置隐私.     

保护位置隐私和查询内容隐私的路网K近邻查询方法

位置隐私和查询内容隐私是LBS兴趣点（point of interest,简称POI）查询服务中需要保护的两个重要内容,同时,在路网连续查询过程中,位置频繁变化会给LBS服务器带来巨大的查询处理负担,如何在保护用户隐私的同时,高效地获取精确查询结果,是目前研究的难题.以私有信息检索中除用户自身外其他实体均不可信的思想为基本假设,基于Paillier密码系统的同态特性,提出了无需用户提供真实位置及查询内容的K近邻兴趣点查询方法,实现了对用户位置、查询内容隐私的保护及兴趣点的精确检索;同时,以路网顶点为生成元组织兴趣点分布信息,进一步解决了高强度密码方案在路网连续查询中因用户位置变化频繁导致的实用效率低的问题,减少了用户的查询次数,并能确保查询结果的准确性.最后从准确性、安全性及查询效率方面对本方法进行了分析,并通过仿真实验验证了理论分析结果的正确性.     

DART+: Direction-aware bichromatic reverse k nearest neighbor query processing in spatial databases

This article presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor(DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBRkNN query returns a subset P′ of P such that k nearest neighbors of each object in P′ include q and each object in P′ has a direction toward q within a pre-defined distance. We formally define the DBRkNN query, and then propose an efficient algorithm, called DART, for processing the DBRkNN query. Our method utilizes a grid-based index to cluster the spatial objects, and the B⁺-tree to index the direction angle. We adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than a pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. As a major extension of DART, we also present an improved algorithm, called DART+, for DBRkNN queries. From extensive experiments with several datasets, we show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time. In addition, our extension algorithm, DART+, also shows significantly better performance than DART.     

An efficient continuous k-nearest neighbor query processing scheme for multimedia data sharing and transmission in location based services

The continuous k-nearest neighbor query is one of the most important query types to share multimedia data or to continuously identify transportable users in LBS. Various methods have been proposed to efficiently process the continuous k-NN query. However, most of the existing methods suffer from high computation time and larger memory requirement because they unnecessarily access cells to find the nearest cells on a grid index. Furthermore, most methods do not consider the movement of a query. In this paper, we propose a new processing scheme to process the continuous k nearest neighbor query for efficiently support multimedia data sharing and transmission in LBS. The proposed method uses the patterns of the distance relationships among the cells in a grid index. The basic idea is to normalize the distance relationships as certain patterns. Using this approach, the proposed scheme significantly improves the overall performance of the query processing. It is shown through various experiments that our proposed method outperforms the existing methods in terms of query processing time and storage overhead.

     

Query-aware location anonymization for road networks

Recently, several techniques have been proposed to protect the user location privacy for location-based services in the Euclidean space. Applying these techniques directly to the road network environment would lead to privacy leakage and inefficient query processing. In this paper, we propose a new location anonymization algorithm that is designed specifically for the road network environment. Our algorithm relies on the commonly used concept of spatial cloaking, where a user location is cloaked into a set of connected road segments of a minimum total length L{\cal L} including at least K{\cal K} users. Our algorithm is “query-aware” as it takes into account the query execution cost at a database server and the query quality, i.e., the number of objects returned to users by the database server, during the location anonymization process. In particular, we develop a new cost function that balances between the query execution cost and the query quality. Then, we introduce two versions of our algorithm, namely, pure greedy and randomized greedy, that aim to minimize the developed cost function and satisfy the user specified privacy requirements. To accommodate intervals with a high workload, we introduce a shared execution paradigm that boosts the scalability of our location anonymization algorithm and the database server to support large numbers of queries received in a short time period. Extensive experimental results show that our algorithms are more efficient and scalable than the state-of-the-art technique, in terms of both query execution cost and query quality. The results also show that our algorithms have very strong resilience to two privacy attacks, namely, the replay attack and the center-of-cloaked-area attack.     

A query integrity assurance scheme for accessing outsourced spatial databases

With the trend of cloud computing, outsourcing databases to third party service providers is becoming a common practice for data owners to decrease the cost of managing and maintaining databases in-house. In conjunction, due to the popularity of location-based-services (LBS), the need for spatial data (e.g., gazetteers, vector data) is increasing dramatically. Consequently, there is a noticeably new tendency of outsourcing spatial datasets by data collectors. Two main challenges with outsourcing datasets are to keep the data private (from the data provider) and to ensure the integrity of the query result (for the clients). Unfortunately, most of the techniques proposed for privacy and integrity do not extend to spatial data in a straightforward manner. Hence, recent studies proposed various techniques to support either privacy or integrity (but not both) on spatial datasets. In this paper, for the first time, we propose a technique that can ensure both privacy and integrity for outsourced spatial data. In particular, we first use a one-way spatial transformation method based on Hilbert curves, which encrypts the spatial data before outsourcing and, hence, ensures its privacy. Next, by probabilistically replicating a portion of the data and encrypting it with a different encryption key, we devise a technique for the client to audit the trustworthiness of the query results. We show the applicability of our approach for both k-nearest-neighbor queries and spatial range queries, which are the building blocks of any LBS application. We also design solutions to guarantee the freshness of outsourced spatial databases. Finally, we evaluate the validity and performance of our algorithms with security analyses and extensive simulations.     

k-Nearest neighbor searching in hybrid spaces

Little work has been reported in the literature to support k-nearest neighbor (k-NN) searches/queries in hybrid data spaces (HDS). An HDS is composed of a combination of continuous and non-ordered discrete dimensions. This combination presents new challenges in data organization and search ordering. In this paper, we present an algorithm for k-NN searches using a multidimensional index structure in hybrid data spaces. We examine the concept of search stages and use the properties of an HDS to derive a new search heuristic that greatly reduces the number of disk accesses in the initial stage of searching. Further, we present a performance model for our algorithm that estimates the cost of performing such searches. Our experimental results demonstrate the effectiveness of our algorithm and the accuracy of our performance estimation model.