Pattern-Preserving k-Anonymization of Sequences and its Application to Mobility Data Mining

Abstract

Sequential pattern mining is a major research ¯eld in knowledge discovery and data mining. Thanks to the increasing availability of transaction data, it is now possible to provide new and improved services based on users' and customers' behavior. However, this puts the citizen's privacy at risk. Thus, it is important to develop new privacy-preserving data mining techniques that do not alter the analysis results signi¯cantly. In this paper we propose a new approach for anonymizing sequential data by hiding infrequent, and thus potentially sensible, subsequences. Our approach guarantees that the disclosed data are k-anonymous and preserve the quality of extracted patterns. An application to a real-world moving object database is presented, which shows the e®ectiveness of our approach also in complex contexts.

-

In the last decade, many KDD techniques have been developed that provide new means for improving personalized services through the discovery of patterns and models which represent typical or unexpected customer's and user's behavior. The exponential growth of available personal data, as well as the re¯nement of data mining techniques, lead to new and intriguing possibilities. On the other hand, the collection and the disclosure of personal, often sensible, information increase the risk of citizen's privacy violation. For this reason, many recent research works have focused on privacy-preserving data mining [ 5, 24, 16, 18 ], proposing novel techniques that allow to extract knowledge while trying to protect the privacy of users and customers (or respondents) represented in the data3. This may involve techniques that return anonymized data mining results, or that provide anonymized datasets to the companies/research institution in charge of their analysis.

3 In statistics, the problem has been extensively studied in the ¯eld of statistical dis

closure control.

A major and rising ¯eld in data mining research concerns the analysis of sequence databases. User's actions as well as customer transactions are often stored together with their timestamps, making the temporal sequentiality of the events a powerful source of information. For instance, web logs provide the full activity of each website visitors during each browser session. Moreover, the spreading of mobile devices, such as mobile phone, GPS devices and RFIDs, has become a great source of spatio-temporal data. Companies and public institutions can now study the sequential behavior of their customers/citizens to improve their o®ers and services. A lot of advanced techniques have been investigated to extract patterns and models in databases of sequences [ 4, 27, 23 ], as well as in databases of moving objects (trajectories) [ 13 ]. For both legal and ethical reasons, the data owners (or custodians) should not compromise the privacy of their customers and users, and therefore should reveal as little as possible their personal sensible information. Hiding personal identi¯ers, such as personal IDs or quasi-identi¯ers (i.e., attributes that can be linked to external information to re-identify the individual to whom the information refers) may not be su±cient in the case of sequential data. If a small sequence of actions is easily referable to a few persons, an attacker may access to the whole action sequences involving these persons. For instance, if a malicious data user has access to the daylight city tra±c data, and he knows that John Smith often goes from the commercial zone A to the general hospital B, and the sequence A ) B appears few times in the dataset, he can easily identify the entire sequence of locations crossed by John Smith during the day, and guess his daily behavior. Existing k-Anonymity techniques do not take into consideration the intrinsic sensibility of sequential data. Some other approaches have been proposed that requires that sensible sequences have to be pre-de¯ned [ 2, 1 ]. Other approaches use collaborative data mining techniques [ 17 ], or propose to mine models instead of the data [ 15 ], but they do not ensure that sensible sequences can not be extracted.

In this paper, we propose a new technique that provides an anonymized dataset of sequences, while preserving sequential pattern mining results. We use a method which combines k-anonymity (the disclosed dataset is such that any sequence is undistinguishable with at least k ¡ 1 other sequences) and sequence hiding approaches. Our approach consists in a reformulation of the anonymization problem as the problem of hiding k-infrequent sequences, i.e., transforming the original sequence database in such way that the sequences with support less than k in the original dataset can not be mined any longer. In the hypothesis that an attacker knows part of the sequence belonging to a person, and that s/he also know that this person is present in the database, s/he has a probability of 1=k of reconstructing the entire sequence. Our approach is formally de¯ned in the general setting of sequences of items, or events. To illustrate its e®ectiveness and practicality in a realistic and complex domain, we put at work our anonymization technique in the scenario of moving object data analysis, and applied it to a large-scale, real-life dataset of GPS trajectories of vehicles with on-board GPS receivers, tracked in the city of Milan, Italy. The results of our experiments, where we compare the set of sequential patterns obtained before and after the application of our anonymization technique, show that we can substantially preserve such frequent sequential patterns, while guaranteeing that the disclosed data are k-anonymous.

The rest of the paper is organized as follows. Section 2 brie°y discusses the relevant related works on privacy-preserving data mining. Section 3 introduces and explains our Privacy-Preserving k-Anonymization (P2kA) framework. The algorithmic details are given in Section 4, together with explanations on a toy example consisting of a small set of sequences. The experimental results of our application to a moving object dataset are presented and discussed in Section 5. Finally, Section 6 concludes. 2

Related works

A lot of recent research works have focused on techniques for privacy-preserving data mining [ 5 ] and for privacy-preserving data publishing. Important techniques include perturbation, condensation, and data hiding with conceptual reconstruction. The ¯rst step before data publishing is to remove the personally identifying information. In [ 24 ] (and much earlier in statistics by T. Dalenius [ 9 ]), it has been shown that removing personally identifying information is not enough to protect privacy. In this work, Samarati and Sweeney propose a classi¯cation of the attributes in quasi-identi¯ers (i.e., attributes that can be linked to external information to re-identify the individual to whom the information refers, a concept that was already present in [ 10 ]), and sensitive attributes. Moreover, they propose the k-anonymity to generalize the values of quasi-identi¯er attributes in each record so that it is indistinguishable with at least k ¡ 1 other records with respect to the quasi-identi¯er, Recently, privacy-preserving data mining has been studied in conjunction with spatio-temporal data and trajectory mining [ 12, 8 ]. In the work presented in [ 3 ], the authors study the problem of anonymity preserving data publishing in moving objects databases. They propose the notion of (k; ±) ¡ anonymity for moving objects databases. In particular, this is a novel concept of k-anonymity based on co-localization that exploits the inherent uncertainty of the moving objects whereabouts. The k-anonymity notion is also used in [ 22 ], where authors address privacy issues regarding the identi¯cation of individuals in static trajectory datasets. They provide privacy protection by: (1) ¯rst enforcing k-anonymity, meaning every released information refers to at least k users/trajectories, (2) then reconstructing randomly a representation of the original dataset from the anonymization. Although it has been shown that the k-anonymity framework presents some °aws and limitations [ 20 ], and that ¯nding an optimal k-anonymization is NP-hard [ 6 ], the k-anonymity model is still practically relevant and in recent years a large research e®ort has been devoted to develop algorithms for k-anonymity [ 16, 18 ].

Existing work about anonymity of spatio-temporal moving points has been mainly developed in the context of location based services (LBS) [ 21, 26, 14, 7 ]. Works in [ 21, 26 ] use perturbation and obfuscation techniques to de-identify a given request or a location. In [ 14 ], anonymity is enforced on sensitive locations other than user location points or trajectories. In [ 7 ], anonymization process enforces points referring to same set of users to be anonymized together. However this work considers the anonymization of a request rather than the whole trajectory anonymization. In order to preserve the privacy for moving object data in [ 1 ] the authors propose a hiding technique. In particular, they address the problem of hiding sensitive trajectory patterns from a database of moving objects. A similar technique is used in [ 2 ], where Abul et al. address ¯rst the problem of hiding patterns that are a simple sequence of symbols and then they extend the proposed framework to the case of sequential patterns according to the classical de¯nition [ 5 ]. A ¯rst work attacking the problem of limiting disclosure of sensitive rules by reducing their signi¯cance, while leaving unaltered or minimally a®ecting the signi¯cance of others, non-sensitive rules is [ 6 ]. One of the most important contributions of this paper is the proof that ¯nding an optimal sanitization of a dataset is NP-hard. A heuristic using greedy search is thus proposed. In the work [ 11 ] the objective is to hide individual sensitive rules instead of all rules produced by some sensitive itemsets. The work in [ 25 ] proposes two distortion-based heuristic techniques for selectively hiding sensitive rules. An interesting work is presented in [ 15 ], where Jacquemont et al. propose a costless solution to privacy preserving for problems that may be stated as °ow control problems, that is the case of frequent path discovery in Web sites and frequent route discovery in towns. They propose to model this °ow of data in the form of a weighted automaton, for which they provide a probabilistic solution to discover frequent patterns (potentially with gaps) under constraints, without any information about the original data.

Essentially, in our work we present a new anonymization technique for preserving privacy and at same time, preserving also frequent sequential patterns (FSP) obtained by mining the anonymized data. The basic frequent sequential pattern problem, originally introduced in [ 4 ], is de¯ned over a database of sequences D, where each element of each sequence is a time-stamped set of items | i.e., an itemset. Time-stamps determine the order of elements in the sequence. Then, the FSP problem consists in ¯nding all the sequences that are frequent in the database, i.e., appear as subsequence of a large percentage of sequences of the database. Since its ¯rst de¯nition, many algorithms for sequential patterns have been proposed, from the earliest in [ 4 ], to the more recent Pre¯xSpan [ 23 ] and SPADE [ 27 ]. 3

Problem De¯nition

Let L = fl1; l2; : : : ; lng denote a set of items (e.g, spatial locations or regions). A sequence S = s1s2 : : : sm (si 2 L) is an ordered list of items, and an item can occur multiple times in a sequence. A sequence T = t1t2 : : : tw is a subsequence of S (T ¹ S) if there exist integers 1 · i1 < : : : < iw · m such that 81 · j · w tj = sij . A sequence database D is a set of sequences D = fS1; S2; : : : ; SN g. The support of a sequence T in a database D is the number of sequences in the database containing T , i.e.:

suppD(T ) = jfS s:t: S 2 D ^ T ¹ Sgj Given a support threshold ¾, a sequence T is called a ¾-frequent sequential pattern in a sequence database D if suppD(T ) ¸ ¾. The collection of all ¾-frequent (sequential) patterns in D is denoted by S(D; ¾). The set of all subsequences supported by D is denoted by S(D).

Our goal is to provide an anomymized version of D that preserves as much as possible the collection of frequent patterns. We use a method which combines kanonymity and sequence hiding approaches. Put in other words, we reformulate the anonymization problem | in the case of sequential data | as the problem of hiding k-infrequent sequences, i.e., transforming the original sequence database in such way that the sequences with support less than k in the original dataset can not be mined any longer. The disclosed dataset is such that any sequence is undistinguishable with at least k ¡ 1 other sequences. This goal is achieved by hiding all the subsequences which are not supported by at least k sequences in the database. Let D0 denote the disclosed dataset. Given a positive integer k, the disclosed dataset D0 is such that where ±[condition] is the Dirichlet function (which is equal to 1 if condition is true, 0 otherwise). In this paper we consider that any infrequent subsequence of items can potentially lead to the identi¯cation of the user (respondent). Thus, we do not need to specify any sensible subsequence preliminarily, as in [ 2, 1 ]. Moreover, we want to preserve frequent pattern mining results, in order to let the analysts investigate over frequent and interesting/unexpected behavior. The optimal pattern-preserving k-anonymization problem can be formulated as follows: De¯nition 1 (optimal P2kA problem). Given a sequence database D, and a positive integer k, ¯nd a database D0 such that

1. D0 is k-anonymous, i.e.: 2. the collection of all k-frequent pattern in D is preserved, i.e.:

X

In this paper we present an algorithm which assures that (i) D0 is k-anonymous and (ii) S(D0; k) and S(D; k) are "similar". In particular the second condition of De¯nition 1 becomes:

S(D0; k) µ S(D; k) 8T 2 S(D0; k) suppD0 (T ) ' suppD0 (T ) Algorithm 1: BF-P2kA(D, k)

Input: A sequence database D, a minimum support threshold k Output: A k-anonymous sequence database D0 PT = P ref ixT reeConstruction(D); PT 0 = P T Anonymization(PT ; k) D0 = SequenceGeneration(PT 0); return D0 Algorithm 2: PTAnonymization(PT , k)

Input: A pre¯x tree PT , a minimum support threshold k Output: A k-anonymous pre¯x tree PT 0 Lcut = ;; foreach n in Root(PT ):children do

Lcut = Lcut [ T reeP runing(n; PT ; k); end PT 0 = T reeReconstruction(PT ; Lcut); return PT 0 In the experimental section (see Section 5) we will express this similarity in terms of two measures which quantify how much the pattern support changes, and how many frequent pattern we miss. As a preliminary step towards an "optimal" algorithm, we will show that our algorithm provides good results in term of pattern similarity (see Section 5), and guarantees that the disclosed dataset is k-anonymous. 4

The BF-P2kA algorithm

In this section we present our BF-P2kA (Brute Force Pattern-Preserving kAnonymization) algorithm (Algorithm 1), which allows to anonymize a dataset of sequences D. Our approach consists of three steps. During the ¯rst step, the sequences in the input dataset D are used to build a pre¯x tree PT . The second step, given a minimum support threshold k, anonymizes the pre¯x tree. This means that sequences whose support is less than k are pruned from the pre¯x tree. Then part of these infrequent sequences is re-appended in the pre¯x tree. The third and last step post-process the anonymized pre¯x tree, as obtained in the previous step, to generate the anonymized dataset of sequences D0. Step I: Pre¯x Tree Construction The ¯rst step of the BF-P2kA algorithm (Algorithm 1) is the construction of a pre¯x tree PT , given a list of sequences D. The created pre¯x tree is a more compact structure than a list of sequences. It is de¯ned as a triplet PT = (N ; E; Root(PT )), where N is a ¯nite set of labeled nodes, E is a set of edges and Root(PT ) 2 N is a ¯ctitious node and represents the root of the tree. Each node of the tree (except the root) has exactly one parent and it can be reached through a path, which is a sequence of Algorithm 3: Pre¯xTreeConstruction(D)

Input: A sequence database D Output: A pre¯x tree PT foreach T in D do

LP = LongestP ref ixSearch(Root(PT ); T ); Append T to LP ; foreach v in LP do

v:support = v:support + suppD(T ); end foreach v in T n LP do

v:support = suppD(T ); end end return PT edges starting with the root node. An example of path for the node d (denoted P(d; PT )) is the following:

P(d; PT ) = (Root(PT ); a); (a; b); (b; c); (c; d):

Each node v 2 N , except Root(PT ), has entries in the form hid; item; support; childreni where: { id is the identi¯er of the node v { item represents an item of a sequence { support is the support of the sequence represented by the path from Root(PT ) to v { children is the list of child nodes of v.

The Pre¯xTreeConstruction algorithm (see Algorithm 3) for each sequence of items T searches in PT the path which corresponds to the longest pre¯x of the sequence T . Next, it appends, to the last node of the longest pre¯x found, a branch which represents the remaining elements of T , updating the involved node attributes accordingly. In particular, it updates the support of each node belonging to the common pre¯x by adding the support of the sequence T in D, and sets the support of the remaining nodes to suppD(T ).

Step II: Pre¯x Tree Anonymization The main phase of our approach is the second one. This phase is described by the Tree Anonymization Algorithm (Algorithm 2). Before describing this algorithm we introduce some notions which are needed to better explain our method.

De¯nition 2 (minimum pre¯x). Let S = s1s2 : : : sn and T = t1t2 : : : tk be two sequences such that T is a subsequences of S and sp is the ¯rst item of S such that T ¹ s1s2 : : : sp. The sequence S0 = s1 : : : sp is the minimum pre¯x of S containing the sub-sequence T .

Algorithm 4: TreePruning(n, PT , k)

Input: A node n, a pre¯x tree PT , a minimum support threshold k Output: A list of infrequent sequences Lcut Lcut = ;; if n:support < k then

Lcut = the set of all sequences in P athT ree(PT ; n); foreach j 2 P(n; PT ) do

j:support = j:support ¡ n:support; else end return Lcut end PT = PT n the subtree induced by n; end foreach j 2 n:children do

Lcut [ T reeP runing(j; PT ; k); Example 1. Let us consider the sequences

S = ABCDECDF

T = ACD The sequence S0 = ABCD is the minimum pre¯x of S containing the subsequence T .

De¯nition 3 (path tree). Let PT be a pre¯x tree, let n be a node in the pre¯x tree PT . The path tree of n in PT (denoted by P athT ree(PT ; n)) is the subtree induced by the set of nodes belonging to P(n; PT ) plus the subtree induced by n.

We recall now the well-known notions of Levenshtein distance [ 19 ] and Longest Common Subsequence, which are used in our algorithm.

De¯nition 4 (Levenshtein distance). Let S and T be two sequences. The Levenshtein (edit) distance between S and T is given by the minimum number of operations needed to transform a sequences into the other, where an operation is an insertion, deletion, or substitution of a single element. De¯nition 5. Let T be a set of sequences. The Longest Common Subsequence (LCS) is the longest subsequence common to all sequences in T .

The ¯rst step of the Algorithm 2 is the pruning of the pre¯x tree with respect to the minimum support threshold given in input. This operation is executed thanks to the TreePruning function (see Algorithm 4). Indeed, this function modi¯es the tree by pruning all the infrequent subtrees and updating the support of the path to the last frequent node. In particular, it visits the tree and, when the support of a given node n is less than the minimum support threshold k, it computes all the sequences represented by the paths which contain Algorithm 5: TreeReconstruction(PT , Lcut)

end Input: A pre¯x tree PT , a list of infrequent sequences Lcut Output: An anonymized reconstructed pre¯x tree PT 0 foreach distinct S 2 Lcut do cand = ClosestLCS(S; PT ); L = the set of nodes in PT belonging to the ¯rst minimum pre¯x containing cand; if L is not empty then foreach node 2 L do

node:support = node:support + suppLcut (S); end end return PT the node n and which start from the root and reach the leaves of the sub-tree with root n. Note that for construction each node of this sub-tree has support less than k. All the computed sequences and their supports are inserted in to the list Lcut. Next, the subtree with root n is cut from the tree. Therefore, the procedure TreePruning returns a pruned pre¯x tree and the list Lcut. After the pruning step, the algorithm redistributes the infrequent sequences in Lcut into the pruned tree, using the TreeReconstruction function (see Algorithm 5). In particular, for each infrequent sequence S in Lcut, it computes the LCS between S and every sequence represented by the tree. Suppose that T is the sequence such that the computed LCS is subsequence of T . Thus, the TreeReconstruction function selects the path of the tree that represents the minimum pre¯x of T containing the LCS, and increases the support of the related nodes by adding the support of S in Lcut. If there are more LCSs having the same length, the function ClosestLCS function returns the LCS and the sequence in PT such that the Levenshtein distance between them is minimum. This choice allows to increase the support of a limited set of nodes not belonging to the LCS, thus reducing the noise.

Step III: Generation of anonymized sequences PTAnonymization algorithm returns an anonymized pre¯x tree, i.e., a pre¯x tree where only k-frequent subsequences are represented. The third step our method allows to generate the anonymized dataset D0. This phase is performed by the SequenceGeneration procedure, which visits the anonymized pre¯x tree and generates all the represented sequences. Of course, while a sequence is generated the SequencesGeneration procedure considers the support of this sequence.

We show now that (i) our approach guarantees that the disclosed dataset D0 is k-anonymous (i.e., patterns whose support is less than k in the original dataset D are not represented in D0) and (ii) the set of sequential patterns in D0 is a subset of those in D. Theorem 1. Let D be a dataset of sequences. Given a minimum support threshold k, the dataset D0 returned by Algorithm 1 satis¯es the following conditions:

1. D0 is k-anonymous, i.e.:

2. S(D0; k) µ S(D; k)

X where S(D; k) and S(D0; k) are the collections of k-frequent patterns respectively in D and D0 Proof. (sketch) 1. By construction, the pruning step in Algorithm 2 prunes all the subtrees with support less than k, then the pre¯x tree PT only contains k-frequent sequences. Nevertheless, the reconstruction step (see Algorithm 5) does not change the tree structure of PT , it only increases the support of existing sequences which are already k-frequent in D. In conclusion, at the end of the second step of Algorithm 1, the sequential patterns which are represented in PT 0 are at least k-frequent in D. 2. At the end of the pruning step in Algorithm 2, all infrequent branches in PT are cut o®. However, this could also imply that some k-frequent sequential patterns are pruned out, if they are only supported by multiple infrequent paths in the pre¯x tree PT . Then, the pre¯x tree PT contains a subset of the S(D; k). Moreover, as already stated, during the reconstruction step the tree structure of PT is unchanged, i.e., patterns represented in PT 0 were still represented in PT after the pruning step. Finally, the set of sequential patterns supported by D0 is a subset of those supported by D.

Even if our approach does not assure that S(D0; k) = S(D; k), we will show in Section 5 that the di®erence between the two sets can be very small in practice. We present now an example which shows how our approach works. We consider the dataset of sequences in Figure 1(a) and a minimum support threshold equal to 2. During the ¯rst phase of our method the Pre¯xTreeConstruction algorithm builds the pre¯x tree depicted in Figure 2(a), which represents the sequences in a more compact way.

During the anonymization step, the pre¯x tree is modi¯ed by the TreePruning procedure with respect to the minimum support threshold. In particular, this procedure searches the tree for all nodes with support less than 2: <12, S, 1>

<13, D, 1>.

Next, it selects the paths that contain these nodes and which start from the root and reach each leaves belonging to the subtrees of these nodes. Then, it generates all the sequences represented by these paths and inserts them into the list Lcut: (B K S, 1)

(D E J F, 1).

Finally, the TreePruning procedure eliminates from the tree the subtrees induced by the infrequent nodes listed above and updates the support of the remaining nodes. The pre¯x tree obtained after the pruning step is shown in the Figure 2(b).

The infrequent sequences within Lcut are then redistributed in this way: 1. (B K S, 1) increases the support of the following nodes

<10, B, 2> <11, K, 2> and thus we obtain

<10, B, 3> <11, K, 3> 2. (D E J F, 1) increases the support of the following nodes of the tree <1, A, 6> <7, D, 3> <8, E, 3> <9, F, 3> therefore we obtain

<1, A, 7> <7, D, 4> <8, E, 4> <9, F, 4>.

The pre¯x tree obtained after the anonymization step is shown in Figure 2(c). Finally, the SequencesGeneration procedure provides the anonymized sequence dataset shown in Figure 1(b). 5

Experiments & Results

In this section, we present an application to a moving objects dataset. Object trajectories are ¯rst transformed into sequences of crossed locations, and then processed with our anonymization approach. In the following, we discuss the results over multiple instances of the original data, for di®erent anonymization degrees. 5.1

Data Preparation In this section, we explain the procedure used to obtain the input datasets. We got a set of GPS trajectories of cars from the european project GeoPKDD 4 that cover a week of tra±c in Milan. Essentially, each trajectory is a sequence of pairs of coordinates x and y with relative timestamp. Obviously, performing our algorithm over sequences of points is practically useless because it is impossible to ¯nd a set of points that exactly matches enough times for being considered frequent with respect to any values of k. Thus, to overcome this problem, we use the de¯nition of Regions of Interest given in [ 13 ], where the authors discretize the working space through a regular grid with cells of small size. Then the density of each cell is computed by considering each single trajectory and incrementing the density of all the cells that contain any of its points. Finally a set of RoI's is extracted by means of a simple heuristics using a density threshold.

As a result, a set of Roi's provides a coverage of dense cells through di®erent sized, disjoint, rectangular regions with some form of local maximality. In particular, for each region they consider the average density of its cells, instead of its overall density (which is generally higher), and larger rectangles are preferred only if they add dense regions.

4 http://www.geopkdd.eu

(a)

(b)

Once the set of RoI's has been extracted, we preprocess all the input trajectories translating each one from a sequence of points to a sequence of RoI's. The order of visit is maintained by means of timestamps. An example of this simple procedure of translation is shown in Fig. 3 | on the left we can see all the trajectories and a set of RoI's extracted; on the right we show a trajectory and we evidence which RoI's it crosses. This new dataset represents the input dataset for the anonymization algorithm.

The datasets used in our experiments are built using all the trajectories in the dataset described above with di®erent density thresholds. These values have been chosen in order to obtain an adequate number of RoI's, since low density values correspond to few big regions, and higher values produce few small regions. In that way, we obtain di®erent sets of RoI's meaning di®erent sets of items in the input sequences. Table 1 summarizes the datasets used in our experiments. Notice that the number of trajectories is di®erent among the datasets because we lose those trajectories that do not cross any region. 5.2

Results and discussion Since our goal is to preserve local patterns (i.e., local subsequences) as much as possible, we compare the collections of pattern extracted before and after the anonymization process. To measure the similarity between two collection of patterns, we de¯ne two metrics:

1 X minffreq (s; D0); freq (s; D)g jS(D0; ¾)j s2S(D0;¾) maxffreq (s; D0); freq (s; D)g { SIM2 (Frequent Pattern Collection Size Similarity): de¯ned as minfjS(D0; ¾)j; jS(D; ¾)jg maxfjS(D0; ¾)j; jS(D; ¾)jg All these measures are de¯ned between 0 and 1. When two collections of subsequences are identical, the two measures are all equal to 1.

Our experiments were conducted as follows: we ¯rst anonymized the six datasets using values of k between 10 and 1000. Then, for each value of k we compared the collection of frequent patterns extracted from the original dataset and the collection extracted from the k-anonymized dataset. In all these experiments, we used PrefixSpan [ 23 ] and the minimum support threshold was set to k.

In Figure 4 we report the results of all the experiments. We were unable to compare results for k < 50 and k < 200 for the two ¯rst datasets, since the related pattern collections are too huge and then untractable. As expected, some frequent patterns in D are missing in D0. This is more evident in the ¯rst two datasets (see Figure 4(a) and 4(b)), while for higher density thresholds (Figure 4(c) to 4(f)) the value of SIM2 is closer to the maximum. This is in part due to the fact that when data are sparser, the anonymization algorithm tends to prune more sequences. Concerning the e®ective support similarity (SIM1), the results show that the higher the k threshold, the more similar the relative frequencies. Moreover, the SIM1 measure is quite high in general (the only exception is for the 0.035 dataset).

It is interesting to notice that, for some datasets, it is possible to identify an "optimum" minimum value of k. For instance, if we look at the similarity measures for the last dataset (see Figure 4(f)), k = 300 that preserves the number of frequent patterns, as well as their support. For the ¯rst dataset (see Figure 4(a)), two good choices are k = 100 and k = 500. This may possibly help the data publisher in deciding of a suitable value of k. A possible methodology would consist in ¯nding the best tradeo® (w.r.t. the application) between the anonymization degree and the number of preserved patterns.

300 400 K v5a0lu0es 600 700 800 900 1000 100 200 300 400 K v5a0lu0es 600 700 (e) 0.039 dataset (f ) 0.04 dataset Fig. 4. Values of SIM1 and SIM2 for di®erent location datasets 0.01 dataset 100 200 700 800 900 1000 300 800 900 1000 SIM1 SIM2 SIM1 SIM2 SIM1 SIM2 SIM1

SIM2

Conclusion and future work

In this paper, we introduced a new approach for anonymizing sequential datasets. Our approach provides k-anonymous data generalizing the sequence hiding approach. Through an experiment of application to a real-life mobility dataset, we showed that the proposed technique preserves sequential pattern mining results both in terms of number of extracted patterns and their support.

Further research will investigate over new approaches to preserve pattern mining results also in other hard contexts, such as sparse datasets or long sequences. One possible strategy might require the usage of a di®erent and more compact data structure, instead of the pre¯x tree which is used here. Moreover, another investigation possibility could be oriented to a relaxed privacy constraint. Instead of guaranteeing the full satisfaction of k-anonymity, we could enable better pattern mining results despite of a less aggressive (and slightly more risky) pruning step. Concerning the application to mobility data, our approach does not consider yet the precious information carried by temporal annotations as well as the geographical proximity of locations/regions. A deep research effort will be undertaken to investigate on the possible extension of our approach towards a comprehensive privacy-preserving spatio-temporal framework. Acknowledgements The authors wish to thank the anonymous reviewers for their precious comments, and Roberto Trasarti for his technical support. This work has been carried out within the European project GeoPKDD, which acknowledges the ¯nancial support of the Future and Emerging Technologies (FET) programme within the Sixth Framework Programme for Research of the European Commission, under FET-Open contract number 014915.

References

1. Osman Abul , Maurizio Atzori, Francesco Bonchi, and Fosca Giannotti . Hiding sensitive trajectory patterns . In ICDM Workshops , pages 693 { 698 . IEEE Computer Society, 2007 .

2. Osman Abul , Maurizio Atzori, Francesco Bonchi, and Fosca Giannotti . Hiding sequences . In ICDE Workshops , pages 147 { 156 . IEEE Computer Society, 2007 .

3. Osman Abul , Francesco Bonchi, and Mirco Nanni . Never walk alone: Uncertainty for anonymity in moving objects databases . In ICDE , pages 376 { 385 . IEEE, 2008 .

4. R. Agrawal and R. Srikant . Mining sequential patterns . In Proceedings of ICDE , 1995 .

5. R. Agrawal and R. Srikant . Privacy-preserving data mining . In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (SIGMOD 2000 ), pages 439 { 450 , 2000 .

6. M. Atallah , E. Bertino , A. Elmagarmid , M. Ibrahim , and V. S. Verykios . Disclosure limitation of sensitive rules . In Proceedings of the 1999 IEEE Knowledge and Data Engineering Exchange Workshop (KDEX'99) , pages 45 { 52 , 1999 .

7. Claudio Bettini , Xiaoyang Sean Wang, and Sushil Jajodia . Protecting privacy against location-based personal identi¯cation . In Proceedings VLDB Workshop SDM 2005 , volume 3674 of LNCS , pages 185 { 199 . Springer, 2005 .

8. Francesco Bonchi , YuÄcel Saygin, Vassilios S. Verykios, Maurizio Atzori, Aris Gkoulalas-Divanis, Selim. V. Kaya , and Erkay Savas . Privacy in Spatiotemporal Data Mining , pages 297 { 329 . Springer Verlang, 2008 .

9. Tore Dalenius . The invasion of privacy problem and statistics production | an overview . Statistik Tidskrift , 12 : 213 { 225 , 1974 .

10. Tore Dalenius. inding a needle in a haystack | or identifying anonymous census record . Journal of O±cial Statistics , 2 ( 3 ): 329 { 336 , 1986 .

11. Elena Dasseni , Vassilios S. Verykios, Ahmed K. Elmagarmid , and Elisa Bertino . Hiding association rules by using con¯dence and support . In Ira S. Moskowitz, editor, Information Hiding , volume 2137 of LNCS , pages 369 { 383 . Springer, 2001 .

12. Dino Pedreschi Fosca Giannotti, editor. Mobility Data Mining and Privacy: Geographic Knowledge Discovery . Springer Verlang, 2008 .

13. Fosca Giannotti , Mirco Nanni, Fabio Pinelli, and Dino Pedreschi . Trajectory pattern mining . In Pavel Berkhin, Rich Caruana, and Xindong Wu, editors, KDD , pages 330 { 339 . ACM, 2007 .

14. M. Gruteser and X. Liu . Protecting privacy in continuous location-tracking applications . IEEE Security & Privacy Magazine , 2 ( 2 ): 28 { 34 , 2004 .

15. St ¶ephanie Jacquemont, Fran»cois Jacquenet, and Marc Sebban. Sequence mining without sequences: A new way for privacy preserving . In ICTAI , pages 347 { 354 . IEEE Computer Society, 2006 .

16. Roberto J. Bayardo Jr . and Rakesh Agrawal . Data privacy through optimal kanonymization . In ICDE , pages 217 { 228 . IEEE Computer Society, 2005 .

17. Seung-Woo Kim , Sanghyun Park, Jung-Im Won , and Sang-Wook Kim . Privacy preserving data mining of sequential patterns for network tra±c data . Inf. Sci. , 178 ( 3 ): 694 { 713 , 2008 .

18. Kristen LeFevre , David J. DeWitt, and Raghu Ramakrishnan. Mondrian multidimensional k-anonymity . In Ling Liu, Andreas Reuter, Kyu-Young Whang , and Jianjun Zhang, editors, ICDE, page 25. IEEE Computer Society , 2006 .

19. Vladimir I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals . Soviet Physics Doklady , 10 ( 8 ): 707 { 710 , 1966 .

20. Ashwin Machanavajjhala , Daniel Kifer, Johannes Gehrke, and Muthuramakrishnan Venkitasubramaniam . L-diversity: Privacy beyond k-anonymity . TKDD , 1 ( 1 ), 2007 .

21. S. Menon , S. Sarkar , and S. Mukherjee . Maximizing accuracy of shared databases when concealing sensitive patterns . Information Systems Research , 16 ( 3 ): 256 { 270 , 2005 .

22. Mehmet Ercan Nergiz, Maurizio Atzori, and Yucel Saygin . Perturbation-driven anonymization of trajectories . Technical Report 2007-TR-017 , ISTI-CNR, Pisa, Italy, 2007 . 10 pages.

23. J. Pei et al. Pre¯xspan: Mining sequential patterns by pre¯x-projected growth . In ICDE , pages 215 { 225 , 2001 .

24. P. Samarati and L. Sweeney . Protecting privacy when disclosing information: kanonymity and its enforcement through generalization and suppression . Technical report , SRI International, March 1998 .

25. YuÄcel Saygin, Vassilios S. Verykios, and Chris Clifton . Using unknowns to prevent discovery of association rules . SIGMOD Record , 30 ( 4 ): 45 { 54 , 2001 .

26. V. S. Verykios , E. Bertino , I. N. Fovino , L. P. Provenza , Y. Saygin , and Y. Theodoridis . State-of-the-art in privacy preserving data mining . ACM SIGMOD Record , 33 ( 1 ): 50 { 57 , 2004 .

27. M. J. Zaki . Spade: An e±cient algorithm for mining frequent sequences . Machine Learning , 42 ( 1 /2): 31 { 60 , 2001 .