Abstract: With the development of Location-Based Services (LBS), privacy protection associated with LBS is becoming a challenge in terms of research and industrial concerns. Among the available privacy protection techniques for LBS users, spatial-temporal K-anonymity has become a prominent method because of its easy implementation and broad applicability. However, this method and its variants suffer from a common drawback: They decrease the use of LBS anonymity datasets due to a reduction of the spatial and temporal resolution of an LBS query. Today, the utilization of LBS anonymity datasets is very important for LBS providers because the datasets benefit many LBS applications. In this study, we propose a method for the implementation of LBS anonymity using mining spatial association rules among the topological relationships between LBS anonymity datasets and the related geographic background datasets. First, we define the basic concepts of the proposed approach, subsequently, we present the corresponding implementation. In phase 1, the LBS anonymity datasets are preprocessed by spatially comparing them to the related geographic background datasets to obtain a spatial transaction database. In phase 2, the traditional Boolean association rules for mining algorithms are adopted to obtain spatial association rules from the spatial transaction database generated in the phase 1. Finally, we present an experimental application of the proposed approach to large-scale LBS anonymity datasets which were simulated from real GPS trajectories. The experimental results indicate that based on the analysis of the spatial association rules generated by the approach, LBS anonymity datasets can be utilized by LBS providers and other third parties.
INTRODUCTION
With the rapid advancement in mobile communication and proliferation of location tracking devices (e.g., GPS), Location-Based Services (LBS) are widely recognized as an important feature of the future computing environment (Ali et al., 2006; Baldauf et al., 2007). However, without strict safeguards, the deployment of LBS poses a severe threat to user privacy (e.g., with untrustworthy servers, location-based services may lead to several privacy threats ranging from worries over employers snooping on their workers’ whereabouts to fears of tracking by potential stalkers (Chow and Mokbel, 2007) which has gained attention from academia and industry (Kulik, 2009; Krumm, 2009).
There are mainly four primitives that make up user privacy in LBS applications: identity, issuer, location and time (Baugh and Gao, 2006; Bettini et al., 2007). Identity is the unique information about an individual that would allow the individual to be recognized as a separate entity from a set of individuals (i.e., security identifier: SID). Issuer is the identity of the user that issues the query request. Location deals specifically with the whereabouts of an individual or group which may include coordinates, landmarks, or other information. Time points out when the query is requested. Additionally, based on the composite of the three primitives, attackers can reach a greater threat to user privacy.
Initial research on the privacy protection LBS users mainly focused on establishing specifications and laws. However, this research lacked flexibility and lagged behind attack technologies. Several algorithms for protecting LBS user privacy have been proposed, such as the use of dummies (Kido et al., 2005), spatial transformation based on the Hilbert curve (Um et al., 2010) and Private Information Retrieval (PIR) protocols (Shang et al., 2010). Spatial-temporal K-anonymity (Gruteser and Grunwald, 2003) has become a prominent privacy protection technique for LBS users because it is easy to implement and widely applicable.
| Fig. 1: | Centralized cloaking architecture |
Spatial-temporal K-anonymity is an extension of K-anonymity and is based on the use of obfuscation. Specifically, a query request submitted to an LBS server does not consist of the requestor’s identifier and accurate location but rather the pseudonyms of the requestor, at least K-1 others nearby and a cloaking area that encloses at least K-1 locations of others. If the resolution of the cloaking area is too coarse for service quality, temporal cloaking is applied (i.e., the user’s service request is delayed). Finally, at least K pseudonyms, a cloaking area and temporal cloaking comprise an LBS anonymity dataset (hereafter referred to as an anonymity dataset) corresponding to the query request that is processed by spatial-temporal K-anonymity. Currently, the general architecture for the implementation of spatial-temporal K-anonymity consists of one trusted server (Um et al., 2009) (Fig. 1).
The components of the centralized cloaking system can be broadly classified into four subsystems: Mobile clients, base stations, an anonymizer and an LBS server. In this architecture, mobile clients act as query users and send requests to an anonymizer via base stations. According to the requests of the mobile clients, the anonymizer forms an anonymity dataset and sends it to the LBS server. The LBS server processes the anonymity dataset and returns a candidate result to the anonymizer. The anonymizer then creates an actual result from the candidate result by filtering out undesired information and returns the actual result to the mobile clients.
As mentioned above, by using pseudonyms instead of identities of users, the identity privacy is protected. Furthermore, because any pseudonym within the anonymity dataset may be requesting the service, the issuer privacy is protected from disclosure with a certain level of assurance. Likewise, the cloaking area and temporal cloaking of the anonymity dataset reduce the accuracy of the requester’s location and time information in the spatial and temporal dimensions. Specifically, the requestor’s location and time information are indistinguishable from those of at least k-1 other subjects, thus, the location and time privacy is protected to a certain extent. Generally, spatial-temporal K-anonymity can guarantee the protection of the four primitives of LBS users.
The basic concept of spatial-temporal K-anonymity has inspired a series of variants in research publications. These variants are mainly applied in LBS snapshot queries, such as “Where is the nearest gas station?” and “What restaurants are within one mile of my location?” and in continuous queries, such as “Continuously report the nearest police car” and “Continuously report the gas stations within one mile of my car”. Previously developed variant methods include enhanced privacy protection of query identification (Gedik and Liu, 2005), privacy protection in multi-mode query (Mokbel et al., 2006), flexibility in setting the privacy protection level (Xu and Cai, 2009), privacy protection within the spatial network (Ku et al., 2007) and the use of a distributed sensing network (Chow et al., 2006). Later variant methods included the robust spatial cloaking technique (Chow and Mokbel, 2007) and the prediction method based on movement characters (e.g., speed or direction) (Pan et al., 2009).
However, spatial-temporal K-anonymity and its variants suffer from a common drawback: They reduce the resolution of location information. Hence, the use of anonymity datasets may decrease or even cease in future applications. To our knowledge, studies on the successful use of LBS anonymity datasets have not been published, although this information is important for LBS providers (Zhang et al., 2013). In this study, we attempt to solve this problem by introducing an approach that successfully implements an anonymity dataset. The principle of our approach is to mine spatial association rules among spatial relationships between LBS anonymity datasets and related geographic background datasets.
PRELIMINARIES
Here, the typical method used to implement spatial-temporal K-anonymity in LBS snapshot queries is introduced.
| Fig. 2: | Example of adaptive-interval cloaking algorithm |
The basic units of an anonymity dataset are then presented together with a hierarchy expressing their relationships. Finally, the basic concepts of spatial association rules are described.
Spatial-temporal K-anonymity: The representative implementation of spatial-temporal K-anonymity in LBS snapshot queries is based on the adaptive-interval cloaking algorithm introduced by Gruteser and Grunwald (2003). This algorithm uses grid-based schemes which recursively partition the spatial domain into grid cells in a quad-tree style. The partitioning stops when the size of any grid cell becomes less than the threshold set by the users. All of the grid cells generated during the partitioning form a pyramid structure which is depicted in Fig. 2.
The top level of the pyramid (level 0) has only one grid cell that covers the entire spatial domain. Each grid cell, except those at the bottom level, is composed of four grid cells at the next lower level (referred to as “child grid cells”). After a query is received from user U, it traverses the quad-tree (top down) until it finds the grid cell that contains U and fewer than K-1 users. Then, the query returns the parent of the grid cell as the cloaking region. For example, U1 issues a query where K = 2, grid cells <(0, 2), (1, 3)> contain only U1 and thus, the parent grid cells <(0, 2), (2, 4)> are the cloaking region.
The result using the adaptive-interval cloaking algorithm consists of users’ pseudonyms (UPs), a Cloaking Region (CR) and Temporal Cloaking (TC). If we assume that the LBS server knows the spatial and temporal resolution of the anonymity datasets, i.e., the grid cell (Celli) and Time Interval (TIi) of the adaptive-interval cloaking, then the anonymity dataset can be formalized as:
AS = <UPs, CR, TC>, UPs = <U1, U2,...,
Uk>,
CR = <Cell1, Cell2,... Cellm>, TC
= <TI1, TI2,..., TIn>
The three-level hierarchy that expresses the relationship of the units of an anonymity dataset is presented in Fig. 3 (Zhang et al., 2013).
| Fig. 3: | Three-level hierarchy expressing the relationship of the units of an anonymity dataset |
In this study, we focus on the spatial properties of LBS anonymity datasets and the temporary equivalence of the anonymity dataset (i.e., AS = CR = <Cell1, Cell2,..., Cellk>).
Spatial association rules: Inspired by the approach of mining association rules from the transactional dataset introduced by Koperski and Han (1995) first investigated spatial association rules among a set of spatial and (possibly) non-spatial predicates. Specifically, P1∧...Pm⇒Q1∧Qn.(S%, C%), where (P1,..., Pm, Q1,..., Qn) are predicates, (P1,..., Pm) are antecedent predicates, (Q1,..., Qn) are consequent predicates and at least one of the predicates (P1,..., Pm, Q1,..., Qn) is a spatial predicate (Koperski and Han, 1995).
In fact, spatial predicates (P1,..., Pm, Q1,..., Qn) describe the spatial relationships of objects in spatial datasets. Different from the traditional relationships in DBMS, spatial relationships are implicit and methods for materializing this implicit information are specifically required. Three spatial relationships are considered: The direction, distance and topology (Guting, 1994). Due to the space limitation of this study, we primarily consider topological relationships to be the spatial predicates.
Topological relationships characterize the type of intersection between two spatial objects. The formal definition of topological relationships is usually given by the nine-intersection model. In this model, each spatial object is represented as a set of points in the Euclidean plane R2. For a given point set A, it is distinguished between its interior A0, its boundary δA and its exterior (or complement)A-1. The point sets of two spatial objects A and B are then interrelated by building all nine intersections between these point sets to determine how they are topologically related. The model is usually represented by the following nine-intersection matrix:
| (1) |
Each intersection described by these matrix elements is distinguished between the empty set ø and the nonempty set ¬ø which results in 29 = 512 possible combinations. In this study, we focus on the topological relationships between anonymity datasets and related geographic background datasets which are composed of two-dimensional, coherent and simple spatial objects (i.e., a point, line and polygon), therefore, the exterior does not need to be considered. The result is a four-intersection matrix:
| (2) |
This matrix reduces the possible combinations to 24 = 16. Some combinations are not logical because they do not describe any possible topological relationship. Furthermore, the geometry types of one or more cells of anonymity datasets are polygons. Removing the contradictory combinations and constraining the topological relationships between polygons and other geometric types (point, line and polygon) leads to the topological relationships illustrated in Fig. 4.
S% and C% are the support and confidence, respectively, of the rule P1∧Pm⇒Q1∧Qn.(S%, C%). For example, let D = <T1, T2,..., Tn> be a spatial transaction database and I = <I1, I2,..., Im> is the spatial itemsets (another term for a spatial relationship or a spatial predicate) of all of the spatial transactions in D. Any subset X of I is included in D. If XεTi, then Ti contains X. The count transactions which are in D and contain X, are defined as the support counts of X and denoted as ∂x. Accordingly, the support of X is denoted as support(X) and formulated as follows:
| (3) |
If support(X) is greater than the threshold specified by the users, then X is called a frequent spatial itemset.
For any spatial itemsets X and Y, if X∩Y = ø, then the equation X→Y is called a spatial association rule of X (antecedent) and Y (consequent). The support of X→Y is that of X∪Y which is denoted as support(X→Y) and formulated as follows:
Support(X→Y) = support(X∪Y) |
(4) |
The confidence degree of X∪Y is denoted as confidence(X∪Y) and formulated as follows:
| (5) |
If support(X→Y)≥supmin and confidence(X→Y)≥ confmin, X→Y is called an association rule.
APPROACH OF MINING SPATIA ASSOCIATION RULES AMONG TOPOLOGICAL RELATIONSHIPS
An approach used to mine spatial association rules is applied to determine the topological relationships between anonymity datasets and related geographic background datasets.
| Fig. 4: | Topological relationships between simple spatial objects in Euclidean plane R2 |
First, we format the basic definitions of the spatial association mining rules for the anonymity datasets and we then design the implementation process.
Basic definitions
Definition 1: Ltar = <Otar1, Otar2,...,
Otarm> represents a target layer, where Otar1, Otar2,...,
Otarm are instances in the target layer Ltar and each
instance holds a Cloaking Region (CR) of an anonymity dataset.
Definition 2: Lrel = <Orel1, Orel2, Orelm> represents a relevant layer, where Orel1, Orel2,..., Orelm are instances in the relevant layer Lrel and Lrels = <Lrel1, Lrel2,..., Lrels> represents a set of relevant layers.
Definition 3: R = (Otar1-Orel1), Otar1εLtar, Orel1εLrel, LrelεLrels represents a topological relationship between the instance Otar1 in the target layer Ltar and the instance Orel1 in the relevant layer Lrel, where Lrel is a member of Lrels.
Definition 4: Rr_I = <Otar1, R = (Otar1-Orel1), Orel1> and Rr_L = <Otar1, R = (Otar1-Orel1), Orel1>, where Otar1εLtar, OreliεLrel, LrelεLrels represent topological relationships stored in a relational table at the instances level and at the relevant layers level, respectively.
Definition 5: Rt_I = <Otar1, (Otar1-Orel1)_Orel1> and Rt_L = <Otar1, (Otar1-Orel1)_Lrel>, where Otar1εLtar, Orel1εLrel, LrelεLrels represent topological relationships stored in a transactional table at the instances level and relevant layers level, respectively.
Definition 6: Let SD = <Rt1, Rt2,..., Rtn> be a spatial transaction database, where Rt1, Rt2,..., Rtn are a set of topological relationships that are stored in transactional tables at the instances level or relevant layers level.
Preprocessing anonymity datasets: Three basic steps are used to preprocess the anonymity datasets:
| • | Selection of a target layer and a set of relevant layers: A series of anonymity datasets and a set of geographic background datasets are organized and chosen as the target layer and the relevant layers, respectively. An example is illustrated in Fig. 5. The target layer includes five anonymity datasets: AS1 = <Cell1(2x2), Cell2(2x3), Cell3(3x2)>, AS2 = <Cell1(3x5), Cell2(4x4), Cell3(4x5), Cell4(4x6)>, AS3 = <Cell1(1x9), Cell2(2x8), Cell3(2x9), Cell4(3x8)>, AS4 = <Cell1(4x9), Cell2(5x8), Cell3(5x9), Cell4(6x8)>, AS5 = <Cell1(8x7), Cell2(8x8), Cell3(8x9), Cell4(8x10), Cell5(9x7), Cell6(9x8), Cell7(9x9), Cell8(10x8), Cell9(10x9)>, AS6 = <Cell1(7x2), Cell2(7x3), Cell3(7x4), Cell4(8x3), Cell5(9x3), Cell6(10x2), Cell7(10x3)>. The relevant layers include 4 layers: “Main residential area”, “Bridge”, “First class road” and “Road networks”. The geometry type of the instances of the relevant layer “Main residential area” is a polygon, whereas the geometry type of the instances of the other relevant layers is a line |
| • | Computation of the topological relationships and storage in a relational table: The relevant layer “Main residential area” includes three instances (Fig. 5). According to the computation method for topological relationships mentioned in preliminaries section and definition 3 in section, we can obtain three topological relationships: “WITHIN” between the anonymity dataset AS1 and instance 1, “OVERLAPS” between the anonymity dataset AS2 and instance 2 and “OVERLAPS” between the anonymity dataset AS5 and instance 3 |
| Fig. 5: | Illustration of target layer and relevant layers |
Applying the same logic, other topological relationships can be defined. According to definition 4 in basic definition section, all topological relationships between anonymity datasets and geographic background datasets illustrated in Fig. 5 can be organized at the instances level in a relational table (Table 1), where ID1 and ID2 are unique identifiers of the instances in the target layer and the relevant layer, respectively.
However, to improve the efficiency of the subsequent algorithms, it is best to store the topological relationships at the relevant layers level (Bogorny et al., 2005). This method is used here (i.e., ID2 attributes in Table 1 are discarded).
| Table 1: | An example of topological relationships stored in a relational table |
Transforming the topological relationships to a transactions table: For the purpose of adopting traditional Boolean association rules while mining algorithms to obtain spatial association rules, the topological relationships generated in the previous process should be transformed into a transactional table. The principle of the transformation is that all of the topological relationships of tuples with the same ID1 attribute are combined to form a transaction, as for the tuples with ID1 = AS5 and ID1 = AS6. However, the same topological relationships are not allowed in a transaction, for example, instance ID1 = AS5 has the same topological relationship “CROSSES” with the relevant layers “first class road” and “road networks”. The suffix “name of relevant layers” of the tuples is added to the topological relationships to form new types, such as “CROSSES_first class road” and “CROSSES_road networks”. The final results are shown in Table 2.
Mining spatial association rules from spatial transactions database: The typical mining spatial data association rules are generally classified into three types of methods: Methods based on clustering over layers, methods based on spatial transactions and methods without spatial transactions. Among these methods, the third type is the most popular (Zhang et al., 2007) and adopts traditional Boolean association rules mining algorithms. The process can be split into two phases: The extraction of the frequent spatial itemsets (spatial relationships or spatial predicates) and the generation of the spatial association rules from the frequent spatial itemsets. The extraction of the frequent spatial itemsets phase follows the paradigm of candidate generation-and-test to combine frequent K-1 spatial itemsets to obtain candidate K spatial itemsets which iteratively meet the supmin threshold. The candidates are pruned according to the Apriori pruning principle: if there are any spatial itemsets that are infrequent, then their super spatial itemsets should not be generated or tested.
The generation of spatial association rules can be performed by partitioning the frequent spatial itemsets X into two non-empty subsets, X and Y-X, such that (X→Y-X) satisfies the confmin threshold.
| Table 2: | An example of topological relationships stored in a transactional table |
Being limited by the manuscript length, we do not describe the details of the algorithm. For more details, see the literature by Koperski and Han (1995).
EXPERIMENT AND RESULTS ANALYSIS
Experiment datasets: In the experiment, we adopt the adaptive-interval cloaking algorithm for GPS trajectories to simulate the anonymity datasets. The GPS trajectories were collected from 2,612 taxis in Nanjing city on July 15, 2007. An outline of this process is as follows.
Preprocessing of the GPS trajectories:
| • | Based on the spatial-temporal distribution of the 2,612 taxi GPS trajectories, we configure the spatial and temporal resolution parameters which are shown in Table 3. We partition the spatial-temporal domains into 12 periods and 10,000 (100x100 m) spatial-temporal grids for every period. The discrete spatial-temporal grids are illustrated in Fig. 6a |
| • | For each period, we randomly sample 500 spatial-temporal grids which are simulated as the location and time of each anonymous request. The sampled spatial-temporal grids are illustrated in Fig. 6b |
| Table 3: | Parameters of adaptive-interval cloaking algorithm |
| The parameters in the table can be adjusted according to the privacy protection level required by users. For example, if some users argue that the value of the “Grid Cell” parameter is set too small, not enough to protect their location privacy. There are two methods to adjust the parameters. The first method is to only set a larger value (e.g., 5 or 10 km) for the “Grid Cell” parameter, and the second method is to set both the “K” parameter and “Spatial delay” to larger values. Because the “Grid Cell” parameter is the basic unit of our mining association rules algorithm, the larger value of the “Grid Cell” parameter will result in the spatiotemporal distribution which is reflected by the mined association rules, more rough. On the contrary, the second method does not involve the “Grid Cell” parameter. Therefore, we recommend using the second method | |
Generation of the anonymity datasets:
| • | For each sampled spatial-temporal grid, we adopt the adaptive-interval cloaking algorithm to generate an anonymous dataset. The parameters of the algorithm are shown in Table 3 and the anonymity datasets generated for one period are illustrated in Fig. 6c |
All of the anonymity datasets generated from the 12 periods are translated to a layer as the target layer which stores the Cloaking Region (CR) as the geometry attribute and Users’ Pseudonyms (UPs) and Temporal Cloaking (TC) as the categorical attributes. The generated layers are illustrated in Fig. 6d.
We select 10 geographic background dataset as the relevant layers which are shown in Table 4. The overlying mapping of the target layer and the relevant layers are shown as Fig. 7.
As observed in Fig. 7, the target layer is mainly distributed in the Gulou district in Nanjing which is located west of the Qinhuai River, east of Xuanwu Lake, south of Xinjiekou and north of Xinmofan Road, the area is one of the busiest traffic areas in Nanjing city. In addition, the basic space-time variance distribution of the target layer can be observed based on the colors of the anonymity datasets which change gradually over time, however, the interpretation is not straightforward or accurate because of the tremendous amount of overlap within the cloaking region of the anonymity datasets. The outcome is that the patterns of the space-time variance distribution are too rough to aid city traffic guidance.
By preprocessing the target layer and the relevant layers according to steps 2 and 3 of preprocessing anonymity dataset section, we obtain a spatial transactions database with 8,873 records.
| Table 4: | Basic information of geographic background datasets |
| Fig. 6(a-d): | Workflow of generating anonymity datasets from GPS trajectories |
| Fig. 7(a-l): | Overlaying mapping of the target layer and the relevant layers (a) 0:00~2:00, (b) 2:00~4:00, (c) 4:00~6:00, (d) 6:00~8:00, (e) 8:00~10:00, (f) 10:00~12:00, (g) 12:00~14:00, (h) 14:00~16:00, (i) 16:00~18:00, (j) 18:00~20:00, (k) 20:00~22:00 and (l) 22:00~24:00 | |
Of those records, 16 new topological relationships are defined (Table 5). The “Count” attribute represents the count of records supporting those topological relationships.
Experiment result and analysis: We adopt two algorithms that are implemented in SPMF which is an open-source data mining framework written in Java, to mine the spatial association rules. The algorithms are Eq. 1 mining all association rules and Eq. 2 mining perfectly sporadic association rules:
| • | Mining all association rules: In this algorithm, the thresholds for support (S%) and confidence (C%) of the rules to be mined (Supmin and confmin) are set at 65 and 80%, respectively. The mined results include six rules listed in Table 6. These rules include three topological relationships, “CROSSES_road networks”, “CROSSES_first class road” and “OVERLAPS_main residential area”, between the target layer and the three relevant layers (i.e., “road networks”, “first class road” and “main residential area”) |
It is well known that Supmin represents the minimum amount of evidence and that confmin specifies the strength of a spatial association rule’s implications.
| Table 5: | Information of coding of topological relationships |
Here, the confidences of those six rules have large values that are equal to or greater than 80%. The associations reflected by the confidence values are very strong and can be visually expressed by overlaying the anonymous datasets and the geographic background datasets, among which the topological relationships constitute the transaction supporting those six rules (Fig. 8).
Subsequently, those six rules can be interpreted as conditional expressions, as shown in Fig. 8. For example, rule 5 in Table 6 can be expressed as a conditional expression with an anonymity dataset that overlaps the main residential areas and crosses road networks has (with 99% confidence) a high percentage of crossing first class roads. Likewise, other rules can be interpreted as similar conditional expressions.
Based on the visual conditional expressions of the mined rules, patterns of popular public activities can be predicted because the rules also have a large support value (equal to 68.1%). For example, based on the rules in Table 6, we can infer that most users will prefer to anonymously request LBS services in areas where the road networks and first class roads are crossed and the main residential area is overlapped. Based on this prediction, the department of urban traffic management can make decisions regarding the urban traffic flow guidance system.
Mining perfectly sporadic association rules: Sporadic rules represent rare cases that are scattered sporadically through the database but with a high confidence of occurring together, this can indicate a rare but fatal pattern. To identify the sporadic rules based on the anonymity datasets, the support (C%) threshold is constricted to an interval range (i.e., [Supmin, Supmax]). In this experiment, we set the interval range to [0.10, 0.20%]. Similar to previous rules, the confidence threshold confmin of the rules to be mined is set to a large value of 60%.
Based on the results in Table 7, we observe that “CONTAINS” between the anonymity datasets and the relevant layers of “vegetation” and “main residential area” exists in the mined rules. Similarly, according to Fig. 9 which visualizes the topological relationship associations related to the rules, we can make predictions using the conditional expressions of the mined rules.
| Table 6: | Basic information of mined spatial association rules |
| Table 7: | Basic information of mining sporadic spatial association rules |
| Fig. 8(a-l): | Mapping display of spatial association rules (a) 0:00~2:00, (b) 2:00~4:00, (c) 4:00~6:00, (d) 6:00~8:00, (e) 8:00~10:00, (f) 10:00~12:00, (g) 12:00~14:00, (h) 14:00~16:00, (i) 16:00~18:00, (j) 18:00~20:00, (k) 20:00~22:00 and (l) 22:00~24:00 | |
| Fig. 9: | Mapping display of mining sporadic spatial association rules |
According to rule 1, a condition states that the anonymity datasets spatially containing “vegetation” will have (with 63% confidence) a high percentage of space containing “main residential area”. In contrast, according to rule 2, if the places where the anonymous requests spatially occur contain “main residential area”, then they will spatially contain “vegetation” (with 100% confidence).
However, the meanings of the prediction based on the sporadic spatial association rules are different from those based on the previous rule. The reason for this difference is that the support threshold of the mined spatial association rules is very small, the patterns implied by the spatial association rules may belong to a few specific users (Fig. 9). For example, a few specific users habituated to anonymously request LBS services near “zifeng plaza”, a landmark in Nanjing City that lies in a main residential area and a vegetated region, can be ascertained. With an accurate prediction from the pattern, the LBS server can provide its users with personalized services in an efficient manner.
CONCLUSION
In this study, we first suggested that spatial-temporal K-anonymity and its variants suffer from a common drawback in that they severely decrease the utilization of anonymity datasets. Then, we proposed a method to solve this problem by mining spatial association rules among the topological relationships between LBS anonymity datasets and related geographic background datasets. Finally, we conducted experiments by applying the proposed approach to large-scale LBS anonymity datasets to mine association rules and the experimental results demonstrate that the spatiotemporal distribution of LBS anonymity datasets can be clearly expressed and be utilized by LBS providers and third parties.
Many remaining issues must be addressed to successfully implement LBS anonymity datasets, including issues regarding classification, cluster analysis and outlier analysis. Alternative data mining technologies should also be explored. Furthermore, the implementation of LBS anonymity datasets may pose a challenge for protecting the privacy of anonymous users.
ACKNOWLEDGMENTS
This research is supported by Jiangsu Government Scholarship for Overseas Studies, the grants from the Natural Science Foundation of China under Grant No. (41201465) and the grants from the Natural Science Foundation of Jiangsu province under Grant No. (BK2012439). The authors thank the Institute of Cartography and Geoinformatics, Leibniz University Hannover for providing us with a good work environment.