Suppose that the adversary learns that his/her neighbor Alice, whose QID value is {Female, 32}, suffered from some ADR in Q2. First, the adversary links to Table 1 (quarter 2) through the QID of Alice, learning that the record of Alice is in the first QID group (CaseIDs 1, 4, and 7). The adversary can then link to the previously published SRS data through the candidate CaseID set {1, 4, 7} and find the record with CaseID=1 and Sex=Male in Table 1 (quarter 1). Because Alice is female, the adversary can exclude CaseID 1 from the candidate CaseID set {1, 4, 7}, changing Table 1 (quarter 2) to 2-anonymous and lifting the confidence of the attacker to identify Alice.

Following the previous example, the adversary has known the candidate CaseID set of Alice {4, 7}. The adversary can now use this set to link to subsequently published SRS data and observe a record whose CaseID is 7 in Table 1 (quarter 3). Because the owner of that record is male, the adversary can exclude CaseID 7 from the candidate CaseID set, concluding that the CaseID of Alice in Table 1 (quarter 2) is 4.

Suppose that the adversary learns John’s QID value is {Male, 33} and the first time that John had an ADR is in Q3. This means that the CaseID of John’s event is a “new CaseID” in Q3 and shall not appear in any previously released data. First, the adversary links to Quarter 3 and learns that the record of John is within the second QID group (CaseIDs 7, 8, 18). The adversary can then connect to the 2 previously published SRS data sets through the candidate CaseID set of John {7, 8, 18}, observing 2 matching records whose CaseID are 7 and 8 in Quarter 2. The CaseID of John is neither 7 nor 8, so the adversary concludes that the CaseID of John is 18, ruining the privacy protection embedded by 3-anonymity.

Research on PPDP [4] aims to protect released microdata from 2 types of privacy attacks: record disclosure and attribute disclosure.

Record disclosure, also known as table linkage attack, refers to the situation in which the individual identity of a specific tuple that has been deidentified in the published data is reidentified. Although it is hard to prevent table linkage attacks, it is possible to reduce the possibility of identifying victims in a published data. Achievement is the invention of k-anonymity [6], which is the most influential privacy model that generalizes the values of QID to ensure that each record in published data contains at least k–1 other records with the same QID value.

Attribute disclosure, also known as attribute linkage attack, refers to the situation in which attackers can infer an individual’s sensitive information, even though they fail to perceive the exact record of the victim. Unfortunately, k-anonymity is not able to prevent attribute disclosure. Another renowned privacy model called l-diversity [8] was thus proposed. The main idea of l-diversity is to thwart the adversary’s belief on the probability of the sensitive value by ensuring that each QID group contains at least l “well-represented” sensitive values, that is, the probability of inferring the sensitive value of the victim will be at most 1/l.

Most real-world data are not static but dynamically changing, which means that data cannot be published simultaneously but have to be published incrementally [4]. Previously proposed privacy models such as k-anonymity and l-diversity only focus on single static data publishing, awkward to prevent privacy disclosure in incremental data publishing. Contemporary privacy models for incremental data publishing can be classified into continuous or dynamic data publishing [4].

This refers to the scenario in which all data collected so far have to be published even if some of the data have been released before. More precisely, suppose that the data holder had previously collected a set of records D₁ time stamped t₁ and published the anonymized version R₁ of D₁. After collecting a new set of records D₂ time stamped t₂, the data holder will publish R₂ as an anonymized version of all records collected so far, (ie, D₁ ∪ D₂). In general, the published release R_i (i≥1) shall be an anonymized version of D₁ ∪ D₂ ∪ ... D_i.

Byun et al [13] first identified the privacy threat under continuous data publishing. They demonstrated possible inference channels by comparing different l-diverse releases to explore the sensitive values of victims. They later enhanced their approach by considering both k-anonymity and l-diverse called (k, c)-anonymous and exploring more types of adversarial attacks named cross-version inferences [14].

Pei et al [15] illustrated that in the continuous data publishing scenario, the adversary can infer some privacy information from multiple releases that have been sanitized by k-anonymity. They also proposed an effective method called “monotonic incremental anonymization,” which would progressively and consistently reduce the generalization granularity as the updates arrive to maintain k-anonymity.

Fung et al [16] proposed a method to quantify the exact number of records that can be “cracked” by comparing the series of published k-anonymous data. The adversary can exclude the cracked records from published data, making the published data no longer satisfy k-anonymous. They also presented a privacy model, called BCF-anonymity, to measure the anonymous number in published data after excluding the cracked records, and proposed an algorithm to anonymize published data achieving BCF-anonymity.

This refers to the scenario in which the data holder can insert records into or delete records, or perform both actions, from raw data sets. Suppose that the data holder had collected an initial set of records D₁ in time t₁ and published its anonymized version R₁. During the period [t₁, t₂), the data holder kept collecting new records and inserted them into D₁. Further, the data holder might delete and update some records from D₁, finally obtaining the updated version D₂ of D₁ in t₂. Then, the published release R₂ in t₂ is an anonymized version of D₂. In general, a published release R_i in time t_i shall be an anonymized version of D_i.

Xiao and Tao [17] identified a kind of privacy disclosure called critical absence. The adversary can infer victims’ sensitive information by comparing the series of published l-diverse data in dynamic data publishing scenarios (only considered insertion and deletion). They proposed a privacy model, called m-invariance, to ensure the certain “invariance” of the “signature” of QID groups, and an effective method called counterfeited generalization to anonymize published data achieving m-invariance.

Bu et al [18] noticed that some sensitive values would be permanent, such as criminal record and some incurable diseases, such as HIV. They showed that m-invariance is unable to prevent privacy disclosure when permanent sensitive values are present. Therefore, they proposed an anonymization approach, called HD-composition [18], to limit the probability of linkage between individuals and sensitive values not over a given threshold.

On observing m-invariance only considers data evolution caused by insertion and deletion, Li and Zhou [19] further presented a counterfeit generalization model named m-distinct to support full data evolution (ie, insertion, update, and deletion). Moreover, they observed that attribute updates are seldom arbitrary, with some correlations often existing between the old and the new values. Based on this observation, they assumed that all updates on sensitive values are nonarbitrary. Therefore, m-distinct applies the concept of the candidate update set, which is a set of specific sensitive values that can be updated.

Following the work in [19], Anjum et al [20] further assumed that the updates in fully dynamic data publishing are arbitrary, meaning the old values of attributes may not correlate with the new values. They presented a new kind of attack named τ-attack by exploiting the “event list” of an individual. They also proposed a method called τ-safety, an extension of m-invariance, to solve the privacy disclosure caused by τ-attack.

He et al [21] presented a new type of attack named value equivalence attack, which can exploit the partitioned structure of published data, such as m-invariant releases, to obtain sensitive information of individuals. Once the adversary knows the actual sensitive value of an individual, he/she can disclose the sensitive information of the remaining individuals within the same equivalence class. They proposed a graph-based anonymization algorithm, which leverages a min-cut algorithm to prevent the old “value association attack” and the new “equivalence attack.”

Specifically, Bewong et al [22] focused on transactional data. They proposed a new privacy model called serially preserving, which requires the posterior probability of any sensitive term to its corresponding population rate bounded by a given threshold. A novel anonymization method (Sanony, which counts on adding counterfeits) was presented to guarantee a new published transactional data set satisfying the required privacy model.

There is another scenario of nonstatic data publishing called sequential data publishing. Different vertical projections of the same table on different subsets of attributes are published consecutively in this scenario. Anonymization models and methods for this scenario were first studied in [23] and then further investigated in [24] and [25].

In summary, no contemporary work notices the scenario of periodical data publishing, and no work has been conducted for SRS data anonymization, considering the privacy threat caused by follow-up cases. In this paper, we investigate the privacy threat caused by periodical releases of SRS data and propose anonymization methods to prevent the disclosure of personal privacy information while maintaining the utility of published data.

Backward-Attack (B-attack) focuses on excluding records from the specific release by exploiting some previous ones (Textbox 2). Scenario I is an example, which occurs when the QID value of the old case differs from the background learned by the attacker. As the QID values would have been generalized in all published releases, the only way by which B-attack can succeed is when the QID value of old CaseID fails to cover that of the current CaseID. More precisely, for every target v, if in any previous release there exists an old CaseID i_old corresponding to the candidate CaseID set of v such that the QID value of i_old does not cover the QID value of v, then i_old would be excluded from the candidate CaseID set of v.

Analogous to B-attack, Forward-Attack (F-attack) occurs when the QID value of the following CaseID differs from the background learned by the attacker (Textbox 3). That is, the QID value of a following CaseID in some subsequent releases fails to cover that of the current CaseID. An example is shown in Scenario II. More precisely, for every target v, if in any subsequent release there exists a following CaseID i_new corresponding to the candidate CaseID set of v such that the QID value of i_new does not cover the QID value of v, then i_new would be excluded from the candidate CaseID set of v.

This attack is illustrated in Scenario III. In this example, the attacker knows that the event for the target (John) first appears in Quarter 3. It follows that John’s case (CaseID) is definitely absent in all previously published releases. In general, for every target v whose CaseID is first present in some release known by the attacker, Latest Attack (L-attack) would occur if the candidate CaseID set of v contains some old CaseIDs appearing in previous releases (Textbox 4).

Our algorithm can be summarized as a greedy and clustering approach to divide records into QID groups. Viewing each QID group as a cluster, we adopted a clustering-based method [26] to build QID groups, each of which starts from a randomly chosen record and grows gradually by adding a solo record exhibiting the best characteristic among all candidates. This process repeats until the QID group satisfies the “k” requirement. Finally, we generalize the QID values of all records within the same cluster to the same value.

We adopted 2 metrics, information loss [26] (Textbox 7) and privacy risk (PR) [9] (Textbox 8), to choose the best isolated record. For each evolving QID group, the former favors the new record contributing minimal impact to the data utility while the latter quantifies the ratio of sensitive values within the QID group to meet the privacy requirement in Definition 6(2).

The NC-bounding strategy aims to maintain at least “k” new CaseID records in each group after excluding all old CaseID records. This is because all old CaseID records may become excludable by exploiting the previous releases, such as B-attack and L-attack. QID-covering is to generalize the QID value of records to prevent them from being excluded by B-attack and F-attack. NC-bounding allows the adversary to discover and exclude records not belonging to the target, but enforces the privacy requirement met by the remaining records. QID-covering, by contrast, perplexes the adversary to find out excludable records.

Multimedia Appendix 4 presents our algorithm PPMS-Anonymization, which is composed of 3 stages. The first stage aims at finding out old CaseID records and generalizing their QID values in advance to achieve QID-covering against F-attack. Because there may exist multiple individual records [9] in ADE data sets, we follow the combined record (or super record) concept in [9] to deal with this issue. All records with the same CaseID are combined into a super record before starting to form QID groups. Without this process, the records with identical CaseIDs may be divided into different QID groups, leading to more substantial deviation in the data quality and perplexing the process of identifying duplicate records while detecting ADR signals.

To find out old CaseID records in D_i and generalize their QID values in advance, we check previous releases R_pre from R_i–1 to R_i–x (if i=1, R_pre=null). Because CaseID is used to trace an event’s follow-ups, there is typically a life span of CaseID, denoted by x. The generalization of old CaseID records aims at achieving QID-covering against F-attack. Because of the transitive property of QID value shown in Lemma 1, once we discover an old CaseID record r' in any one of the previous releases, we stop checking the remaining earlier releases by using “break” (line 13 in Multimedia Appendix 4) to end the “while loop” (line 8 in Multimedia Appendix 4).

The second stage shown in Multimedia Appendix 5 is activated by calling the procedure Grouping, forming as many QID groups satisfying PPMS(k, θ*)-bounding as possible. Each group begins with a randomly chosen seed record, gradually growing by adding a record with the least ΔIL' (defined in Equation 7) until there are at least k new CaseID records to achieve the NC-bounding strategy. The OldCaseNum function returns the number of old CaseID records in a group. A new group then begins with the new record most distinguished from the one just added into the latest group. The above steps are repeated until the remaining records fail to form a group, for example, the number of new CaseID records is less than k or the ratio of all sensitive values within the remaining records is higher than the associated threshold (see line 10 in Multimedia Appendix 5).

The last stage is activated by calling the function Generalization (Multimedia Appendix 6), which processes the remaining ungrouped records by assigning each of them into the most feasible group that produces the minimal ΔIL' to sustain the data utility and satisfy the privacy requirement. Next, the super records will be split back to the original records (the group they belong to remains unchanged). Finally, all records within the same group are generalized into the same QID value to satisfy PPMS(k, θ*)-bounding.

In this section, we propose an improvement of our PPMS-Anonymization algorithm: PPMS⁺-Anonymization. The idea is to neglect the QID covering derived in Lemma 1.

Let r be a record in D_i whose CaseID is c, q^r the QID value of r, and r₁, r₂, ..., r_p be the older versions of r in the previous releases R₁, R₂, ..., R_i–1. To prevent F-attack, we have to make q^r cover {q^r1, q^r2, ..., q^rp}. Although we have exploited the transitivity property in Lemma 1 to avoid checking out all of the old CaseID records in releases R₁, R₂, ..., R_i–1, the QID value suffers from accumulated generalization. That is, the later the record r is published, the more information loss will be caused by generalization. Fortunately, we can limit the accumulated generalization by neglecting all subsequent QID coverings.

The fact is that some of the records protected by QID-covering against F-attack still can be eliminated by BL-attacks. Following the previous discussion, let r₁ be the earliest record with CaseID=c. Without loss of generality, assume r₁ resides in R₁. Then clearly, c is a new case in R₁, that is, c ∈ NC(R₁), and will be an old case in all subsequent releases, that is, c ∈ OC(R_j), 2 ≤ j ≤ i–1. Remember that all old CaseIDs have the potential to be excluded by BL-attacks. So even if we make q^r cover {q^r2, q^r3, ..., q^ri-1} to prevent {r₂, r₃, ..., r_i-1} from being excluded by F-attack, they can still be excluded by BL-attack. This means that generalizing q^r to cover {q^r2, q^r3, ..., q^ri-1} is useless. It suffices to generalize q^r to cover q^r1. Figure 1 illustrates this concept.

Multimedia Appendix 7 shows PPMS⁺-Anonymization, the improved version of PPMS-Anonymization in Multimedia Appendix 4 (lines 5-18). For the given record r, the modified version seeks R_i–x to R_i–1 to find the earliest release in which r occurs. Once we find out the earliest old CaseID record r', we stop checking the remaining releases.

In this evaluation, we set a uniform threshold (θ*=0.2 and 0.4) to each symptom, that is, the sensitivity of each symptom is the same, and 2 settings of k (k=5, 10).

Two different settings of k (5 or 10) are considered. The results on DIR are omitted because they are similar to those generated by uniform setting, that is, MS-Anonymization generates large DIRs while our PPMS-Anonymization yields zero DIR.

Again, 2 different k (5 and 10) settings are considered, and for the same reason, we omit the results on DIR.

In this experiment, we inspected variation on the strength of observed ADR signals shown in Table 4 between before and after anonymization. Because some signals exhibit similar performance, we only show 3 representatives with different demographic conditions, that is, the signals related to Avandia, Zelnorm, and Warfarin, which are shown as follows:

R1: Avandia, Age>18 → Myocardial infarction

R2: Zelnorm, Sex=Female → Cerebrovascular accident

R3: Warfarin, Age>60 → Myocardial infarction

We calculated its occurrences, PRRs, and compared the values with the original values for each signal. We omit the results for uniform setting θ*=0.4 and level-wise setting because similar results were observed for uniform setting θ*=0.2 and frequency-based setting, respectively.

To highlight the impact of anonymization on rare events, we set PRR=0 when a<3, where a denotes the number of reports that satisfy the specific ADR rule. The threshold a≥3 follows Evans et al [29], who investigated a group of newly marketed drugs and suggested that the minimum criteria for a signal are a≥3 and PRR>2.

The original count and PRR of these 3 rules are shown in Figure 5. Rule R1 is a signal with an extremely high occurrence and significant strength, rule R2 is the one with the relatively small occurrence and medium strength, while R3 represents medium occurrence and relatively little strength.

We first evaluated the variation of signal occurrence (count) caused by anonymization. The results are shown in Figure 6. Notice that there is no result for several quarters (eg, 2007Q1, 2010Q3) under the uniform setting. The reason is the same as that for information loss. Generally, the variation yielded by frequency-based setting is much less than that by uniform setting, and a larger k causes more missing counts. For signals with extremely high occurrence like R1, the variation can be substantial; for example, it reaches 180 for PPMS with k=10 and uniform confidence setting. In the same case, our PPMS⁺⁺ exhibits outstanding performance, only causing variation of less than 10. We also note that some quarters are suffering significant count variation for rule R2 (Figure 6E-H). This is because the taxonomy of Gender is relatively flat, composed of only 2 levels. Once the gender of a report satisfying this rule is generalized, it will become “Any” and increase the missing count of this rule. For example, in Figure 6F, when k=10, 7 of 11 counts are missing in 2007Q2 for PPMS. In fact, when k=10, the ratio of reports with Gender=Any is at least 25% and 45% from 2010Q4 to 2011Q4 for PPMS⁺ and PPMS, respectively, which causes serious bias on the count of ADR rule. By contrast, as shown in Figure 6G and H, the frequency-based setting exhibits lower missing count. The overall situation shows that PPMS⁺⁺ significantly outperforms PPMS and PPMS⁺, and demonstrates comparable results with MS-Anonymization.

Figure 7 shows the results on the PRR difference. Similar to that observed for occurrence variation, the frequency-based setting yields more negligible PRR difference than that by uniform setting. For rule R1 with enormous strength, the PRR variation is significantly higher than those for rules R2 and R3. The variations caused by PPMS and PPMS⁺ fluctuate seriously, sometimes much higher, reaching 5 for k=10 and uniform setting of θ*; PPMS⁺⁺ exhibits relatively small variation under the same situation. For rule R2 with attributes of flat taxonomy, we observe a similar phenomenon. Specifically, a sharply significant variation, reaching –14 (Figure 7E, F, and H), is observed in 2007Q4 for PPMS and PPMS⁺. This is because the a value for computing PRR is less than 3. We observe that the original count of this rule in 2007Q4 (Figure 5B) is 3 and its original PRR (Figure 5E) is 13.39. This means that this rule is a rare event with high strength. Any missing count of this rule causes value a to be less than 3 and the PRR will become 0, invalidating this rule. This situation demonstrates the impact of generalization on rare but significant ADR rule, especially for attributes with shallow generalization levels such as Gender, which will hinder or delay the discovery of ADR signals.