Spatial co-location pattern discovery without thresholds

Spatial co-location pattern mining discovers the subsets of features whose events are frequently located together in geographic space. The current research on this topic adopts a threshold-based approach that requires users to specify in advance the thresholds of distance and prevalence. However, in practice, it is not easy to specify suitable thresholds. In this article, we propose a novel iterative mining framework that discovers spatial co-location patterns without predefined thresholds. With the absolute and relative prevalence of spatial co-locations, our method allows users to iteratively select informative edges to construct the neighborhood relationship graph until every significant co-location has enough confidence and eventually to discover all spatial co-location patterns. The experimental results on real world data sets indicate that our framework is effective for prevalent co-locations discovery.     

领域驱动的高效用co-location模式挖掘方法

空间并置（co-location）模式是指其实例在空间邻域内频繁共现的空间特征集的子集。现有的空间co-location模式挖掘的有趣性度量指标,没有充分地考虑特征之间以及同一特征的不同实例之间的差异;另外,传统的基于数据驱动的空间co-location模式挖掘方法的结果常常包含大量无用或是用户不感兴趣的知识。针对上述问题,提出一种更为一般的研究对象--带效用值的空间实例,并定义了新的效用参与度（UPI）作为高效用co-location模式的有趣性度量指标;将领域知识形式化为三种语义规则并应用于挖掘过程中,提出一种领域驱动的多次迭代挖掘框架;最后通过大量实验对比分析不同有趣性度量指标下的挖掘结果在效用占比和频繁性两方面的差异,以及引入基于领域知识的语义规则前后挖掘结果的变化情况。实验结果表明所提出的UPI度量是一种兼顾频繁和效用的更为合理的度量指标;同时,领域驱动的挖掘方法能有效地挖掘到用户真正感兴趣的模式。     

A fast space-saving algorithm for maximal co-location pattern mining

Real space teems with potential feature patterns with instances that frequently appear in the same locations. As a member of the data-mining family, co-location can effectively find such feature patterns in space. However, given the constant expansion of data, efficiency and storage problems become difficult issues to address. Here, we propose a maximal-framework algorithm based on two improved strategies. First, we adopt a degeneracy-based maximal clique mining method to yield candidate maximal co-locations to achieve high-speed performance. Motivated by graph theory with parameterized complexity, we regard the prevalent size-2 co-locations as a sparse undirected graph and subsequently find all maximal cliques in this graph. Second, we introduce a hierarchical verification approach to construct a condensed instance tree for storing large instance cliques. This strategy further reduces computing and storage complexities. We use both synthetic and real facility data to compare the computational time and storage requirements of our algorithm with those of two other competitive maximal algorithms: “order-clique-based” and “MAXColoc”. The results show that our algorithm is both more efficient and requires less storage space than the other two algorithms.     

A framework of spatial co-location pattern mining for ubiquitous GIS

A spatial co-location pattern represents relationships between spatial features that are frequently located in close proximity to one another. Such a pattern is one of the most important concepts for geographic context awareness of ubiquitous Geographic Information System (GIS). We constructed a framework for co-location pattern mining using the transaction-based approach, which employs maximal cliques as a transaction-type dataset; we first define transaction-type data and verify that the definition satisfies the requirements, and we also propose an efficient way to generate all transaction-type data. The constructed framework can play a role as a theoretical methodology of co-location pattern mining, which supports geographic context awareness of ubiquitous GIS.     

基于改进列计算的空间并置模式挖掘方法

空间并置（co-location）模式挖掘旨在发现空间特征间的关联关系,是空间数据挖掘的重要研究方向。基于列计算的空间并置模式挖掘方法（CPM-Col算法）避开挖掘过程中最耗时的表实例生成操作,直接搜索模式的参与实例,成为当前高效的方法之一。然而,回溯法搜索参与实例仍是该方法的瓶颈,尤其在稠密数据和长模式下。为加速参与实例的搜索,充分利用CPM-Col算法搜索参与实例时得到的行实例,在不增加额外计算的前提下对CPM-Col算法进行两点改进。首先,将CPM-Col算法搜索到的行实例存储为部分表实例,利用子模式的部分表实例快速确定参与实例,避免了大量实例的回溯计算。其次,在CPM-Col算法获得一条行实例后,利用行实例的子团反作用于第一个特征,得到第一个特征的参与实例,避免了这些实例的回溯搜索。由此,提出了基于改进列计算的空间并置模式挖掘算法（CPM-iCol算法）,并讨论了算法的复杂度、正确性和完备性。在合成数据和真实数据集上进行了实验,与经典的传统算法join-less和CPM-Col算法对比,CPM-iCol算法明显降低了挖掘的时间,减少了回溯的次数。实验结果表明,该算法比CPM-Col具有更好的性能和可扩展性,特别在稠密数据集中效果更加明显。     

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.     

From location to location pattern privacy in location-based services

Location privacy is extensively studied in the context of location-based services (LBSs). Typically, users are assigned a location privacy profile and the precise locations are cloaked so that the privacy profile is not compromised. Though being well-defined for snapshot location privacy, these solutions require additional precautions and patches in case of consecutive LBS requests on the user trajectory. The attacker can exploit some background knowledge like maximum velocity to compromise the privacy profile. To protect against this kind of location privacy attacks, PROBE (Damiani et al. in Trans Data Priv 3(2):123–148, 2010)-like systems constantly check location privacy violations and alter requests as necessary. Clearly, the location privacy is defined in terms of snapshot locations. Observing that there are usually user-specific movement patterns existing in the shared LBS requests, this work extends location privacy to location pattern privacy. We present a framework where user-specific sensitive movement patterns are defined and sanitized in offline and online fashions, respectively. Our solution uses an efficient dynamic programming approach to decide on and to prevent sensitive pattern disclosure. An extensive experimental evaluation has been carried out too.     

不均匀模糊空间对象的分层次co-location模式挖掘方法

针对现有的co-location模式挖掘算法无法有效处理不均匀分布空间对象的问题,提出一种不均匀模糊空间对象的分层次co-location模式挖掘方法。首先提出一种不均匀数据集的生成方法;然后对不均匀分布的数据集进行层次划分,使每个区域具有均匀的空间分布;再基于改进的PO_RI_PC算法对划分后的模糊对象进行空间数据挖掘。该方法基于距离变化系数构建每个子区域的邻域关系图,进而完成区域融合,实现co-location模式挖掘。实验结果表明,与传统方法相比,所提方法的执行效率更高,随实例个数和不均匀度的变化获得的co-location集个数更多,同比情况下平均提高约25%,获得了更精确的挖掘结果。     

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     

Preference-oriented mining techniques for location-based store search

With the development of wireless telecommunication technologies, a number of studies have been done on the issues of location-based services due to wide applications. Among them, one of the active topics is the location-based search. Most of previous studies focused on the search of nearby stores, such as restaurants, hotels, or shopping malls, based on the user’s location. However, such search results may not satisfy the users well for their preferences. In this paper, we propose a novel data mining-based approach, named preference-oriented location-based search (POLS), to efficiently search for k nearby stores that are most preferred by the user based on the user’s location, preference, and query time. In POLS, we propose two preference learning algorithms to automatically learn user’s preference. In addition, we propose a ranking algorithm to rank the nearby stores based on user’s location, preference, and query time. To the best of our knowledge, this is the first work on taking temporal location-based search with automatic user preference learning into account simultaneously. Through experimental evaluations on the real dataset, the proposed approach is shown to deliver excellent performance.     

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.     

Search on transportation networks for location-based service

The issue of how to provide location-based service (LBS) attracted many researchers. In this paper, we focus on a typical situation of LBS which is to provide services for users in cars that move in a road network. To provide such kind of services, an integration method for representing transportation information with a road map is proposed. By using our integration method, since the transportation information of road networks is managed under the spatial index structure created for road networks, spatial queries on them can take advantages of the spatial index structure and achieve an efficient process. Moreover, we discuss path search, region search, nearest neighbor search and continuous nearest neighbor search in this paper, which are based on transportation networks with (or without) considering the static spatial objects outside the transportation networks. Using transportation information and the corresponding real road network, the paper offers evaluations by comparing our representation method and query method with those in related works. The results show a good performance of our methods.     

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.     

Supergraph based periodic pattern mining in dynamic social networks

In dynamic networks, periodically occurring interactions express especially significant meaning. However, these patterns also could occur infrequently, which is why it is difficult to detect while working with mass data. To identify such periodic patterns in dynamic networks, we propose single pass supergraph based periodic pattern mining SPPMiner technique that is polynomial unlike most graph mining problems. The proposed technique stores all entities in dynamic networks only once and calculate common sub-patterns once at each timestamps. In this way, it works faster. The performance study shows that SPPMiner method is time and memory efficient compared to others. In fact, the memory efficiency of our approach does not depend on dynamic network’s lifetime. By studying the growth of periodic patterns in social networks, the proposed research has potential implications for behavior prediction of intellectual communities.     

LBS的一种隐私保护模型

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

A knowledge infrastructure for intelligent query answering in location-based services

Intelligent query answering in Location-based Services refers to their capability to provide mobile users with personalized and contextualized answers. Personalization is expected to lead to answers that better match user’s interests, as inferable from the user’s profile. Contextualization aims at not selecting answers that for some reason would not be appropriate at the time and place of the user query. These goals are beyond the current state of art in LBS, or are provided based on ad hoc solutions specific to the application at hand. This paper reports on the results of an investigation aiming at defining the knowledge infrastructure that should be developed within the LBS to make it capable of returning intelligent answers. We first discuss the data management features that make LBS different from other query answering systems. Next we propose a data infrastructure that builds on the idea of modular ontologies. We explain how the relevant knowledge may be incrementally set up and dynamically maintained based on an application-independent approach. Last we show how this knowledge is used to reformulate user’s queries via personalized and contextualized rewriting.     

A location-based mobility tracking scheme for PCS networks

This paper introduces a location-based locating strategy for Personal Communication Services (PCS) systems. In the proposed scheme, location updates are based on the value of a movement counter. The update of the movement counter is based on information on the locations visited by a mobile terminal (MT) since the last location update. In particular, the cell identifiers and the corresponding movement counter values are maintained in the MT for a part of the visited cells since the last location update. When the MT enters a cell whose identifier is not stored in the MT, the movement counter increases by one. If the movement counter reaches the update threshold, a location update is triggered; otherwise, the cell identifier and the corresponding movement counter value are stored in the MT. When the MT enters a cell whose identifier is in the MT, the movement counter is assigned with the counter value kept in the MT for this cell, and all cells with greater counter values in the MT are removed. The proposed scheme allows the dynamic selection of the update threshold according to each user's calling and mobility patterns. Analytical and simulation models have been developed to compare the proposed scheme with both the movement-based scheme and the distance-based scheme. Results demonstrate that when the call-to-mobility ratio (CMR) is low, the proposed scheme can achieve a significant cost reduction compared to the movement-based scheme. For example, when the CMR is 0.01, a savings of around 25% in the optimal total cost per call arrival is achieved with the proposed scheme. Moreover, the proposed scheme is easier to implement than the distance-based scheme.