Progressive entity resolution techniques aim to allow linking vast amounts of records, coming from disparate data sources, in a way that provides early access to linkage results of high recall. However, existing methods suffer from serious limitations, as they either assume a nearly uniform distribution of record pairs in each block, or they use a sorted neighborhood approach which incurs a significant d elay i n t he r eporting of linkage results and can miss matching record pairs.In response, in this paper we introduce MULTIBLOCK, a progressive multi-iterative method that breaks down the matching step of entity resolution into a number of iterations, generating as many matching record pairs as possible upfront, to quickly resolve each block regardless of its size. MULTIBLOCK guarantees the formulation of each record pair with a fixed probability, and iteratively provides accurate estimates of the proportion of matching record pairs. It has linear complexity with the number of blocks and no dependence on the records of the data sets, which is important in large-scale settings. Additionally, MULTIBLOCK can adapt to any progressive algorithm that generates blocks of arbitrary sizes. Through experimental evaluation, using three real-world data sets consisting of millions of record pairs, we show that our approach outperforms four state-of-the-art methods in both accuracy and efficiency, b eing a t l east twice faster than its competitors.

Textual data, such as clinical notes, product or movie reviews in online stores, transcripts, chat records, and business documents, are widely collected nowadays and can be used to support a large spectrum of Big Data applications. At the same time, textual data, collected about individuals or from individuals, can be susceptible to inference attacks that may leak private and/or sensitive information about individuals.The increasing concerns of privacy risks in textual data preclude sharing or exchanging textual data across different parties/organizations for various applications such as record linkage, similar entity matching, natural language processing (NLP), or machine learning on large collections of textual data. This has led to the development of privacy preserving techniques for applying matching, machine learning or NLP techniques on textual data that contain personal and sensitive information about individuals. While cryptographic techniques are highly secure and accurate, they incur significant amount of computational cost for encoding and matching data – especially textual data – due to the complex nature of text.In this paper, we propose an efficient textual data encoding and matching algorithm using probabilistic techniques based on counting Bloom filters combined with Differential privacy. We apply our algorithm to a popular use case scenario that involves privacy preserving topic modeling – a widely used NLP technique – in order to identify common or collective topics in texts across multiple parties without learning the individual topics of each party, and show its effectiveness in supporting this application. Finally, through extensive experimental evaluation on three large text datasets against a state-of-the-art probabilistic encoding algorithm for privacy preserving LDA topic modelling, we show that our method provides a better privacy-utility trade-off at the cost of more computation complexity and memory space, while still being computationally efficient (log-linear complexity in the size of documents) for Big data compared to cryptographic techniques that have quadratic complexity.

Nowadays, a vast amount of information is collected in real-time on a daily basis via users' handheld devices, web-based applications, and customer service interactions (among many others). The sheer volume of this data and the unprecedented rate at which it becomes available for processing, potentially combined with other attributes that are commonly met in traditional data sets, calls for novel online record linkage1techniques that can handle streams of data to discover records that refer to the same real-world entity.This paper introduces UniBlock, an online record linkage approach, supported by a novel data structure, that can adapt to any blocking algorithm to separate the most frequently accessed blocks from the rest, and maintain these blocks in main memory. In UniBlock, this separation is performed in a randomized way, where the probability of eviction of a block is inversely proportional to its frequency of access, empowering our approach with simplicity and effectiveness. Additionally, UniBlock provides accurate estimations of the proportion of matching record pairs in the underlying data sets in sublinear running time. Through experimental evaluation, we show that our approach outperforms the state-of-the-art methods in both accuracy and efficiency, being able to scale well to data streams.

In privacy-preserving record linkage, a number of data custodians encode their records and submit them to a trusted third-party who is responsible for identifying those records that refer to the same real-world entity. In this paper, we propose FEDERAL, a novel record linkage framework that implements methods for anonymizing both string and numerical data values, which are typically present in data records. These methods rely on a strong theoretical foundation for rigorously specifying the dimensionality of the anonymization space, into which the original values are embedded, to provide accuracy and privacy guarantees under various models of privacy attacks. A key component of the applied embedding process is the threshold that is required by the distance computations, which we prove can be formally specified to guarantee accurate results. We evaluate our framework using three real-world data sets with varying characteristics. Our experimental findings show that FEDERAL offers a complete and effective solution for accurately identifying matching anonymized record pairs (with recall rates constantly above 93 percent) in large-scale privacy-preserving record linkage tasks.

In this work, we propose Bit Vectors (BV), an accurate, distance-preserving encoding scheme for representing numerical data values in privacy-preserving tasks. Although many methods have been proposed in the literature for encoding strings, the problem of encoding numerical values has not been effectively addressed yet. In Privacy-Preserving Record Linkage (PPRL), a number of data custodians encode their records and submit them to a trusted third-party that is responsible to identify those records that refer to the same real-world entity. BV is supported by a strong theoretical foundation for embedding numerical values into an anonymization space in a way that preserves the initial distances. Key components of this embedding process are (a) the employed hash functions which, by utilizing random intervals, they allow for approximate matching, and (b) the threshold that is required by the distance computations, which we prove that can be specified in a way that guarantees accurate results.

Publishing data about individuals, in a privacy-preserving way, has led to a large body of research. Meanwhile, algo-rithms for anonymizing datasets, with relational or trans-action attributes, that preserve data truthfulness, have at-tracted significant interest from organizations. However, se-lecting the most appropriate algorithm is still far from triv-ial, and tools that assist data publishers in this task are needed. In response, we develop SECRETA, a system for analyzing the effectiveness and efficiency of anonymization algorithms. Our system allows data publishers to evalu-ate a specific algorithm, compare multiple algorithms, and combine algorithms for anonymizing datasets with both re-lational and transaction attributes. The analysis of the algo-rithm(s) is performed, in an interactive and progressive way, and results, including attribute statistics and various data utility indicators, are summarized and presented graphically. 1.

Sequence data are increasingly shared to enable mining applications, in various domains such as marketing, telecommunications, and healthcare. This, however, may expose sensitive sequential patterns, which lead to intrusive inferences about individuals or leak confidential information about organizations. This paper presents the first permutation-based approach to prevent this threat. Our approach hides sensitive patterns by replacing them with carefully selected permutations that avoid changes in the set of frequent nonsensitive patterns (side-effects) and in the ordering information of sequences (distortion). By doing so, it retains data utility in sequence mining and tasks based on item set properties, as permutation preserves the support of items, unlike deletion, which is used in existing works. To realize our approach, we develop an efficient and effective algorithm for generating permutations with minimal side-effects and distortion. This algorithm also avoids implausible symbol orderings that may exist in certain applications. In addition, we propose a method to hide sensitive patterns from a sequence dataset. Extensive experiments verify that our method allows significantly more accurate data analysis than the state-of the-art approach.

Sequence data are encountered in a plethora of applications, spanning from telecommunications to web usage analysis, marketing and healthcare. Disseminating these data offers remarkable opportunities for discovering interesting patterns, but it is challenging to perform in a privacy-preserving way. Although there is a large gamut of techniques to anonymizing sequential data, the discovery of sensitive sequential patterns through data mining algorithms may still lead to serious privacy violations. This is because the mining of such patterns enables intrusive inferences about the habits of a portion of the population, or provides the means for unsolicited advertisement and user profiling. In this paper, we present the problem of hiding sensitive sequential patterns, and survey existing works that attempt to address it. In addition, we discuss the important research challenges that pertain to solving this problem, and present a roadmap for future work.

The publication of trajectory data opens up new directions in studying human behavior, but it is challenging to perform in a privacy-preserving way. This is mainly because, the identities of individuals, whose movement is recorded in the data, can be disclosed, even after removing identifying information. Existing works to anonymize trajectory data offer privacy, but at a high data utility cost. This is because, they either do not produce truthful data, which is important in many applications, or are limited in their privacy specification component. This paper proposes an approach that overcomes these shortcomings by adapting km-anonymity to trajectory data and by using distance-based generalization. We also develop an effective and efficient anonymization algorithm, which is based on the apriori principle. Our experiments verify that this algorithm preserves data utility well, and it is fast and scalable.

Mobility data sources feed larger and larger trajectory databases nowadays. Due to the need of extracting useful knowledge patterns that improve services based on users' and customers' behavior, querying and mining such databases has gained significant attention in recent years. However, publishing mobility data may lead to severe privacy violations. In this paper, we present Private-HERMES, an integrated platform for applying data mining and privacy-preserving querying over mobility data. The presented platform provides a two-dimension benchmark framework that includes: (i) a query engine that provides privacy-aware data management functionality of the in-house data via a set of auditing mechanisms that protect the sensitive information against several types of attacks, and (ii) a progressive analysis framework, which, apart from anonymization methods for data publishing, includes various well-known mobility data mining techniques to evaluate the effect of anonymization in the querying and mining results. The demonstration of Private-HERMES via a real-world case study, illustrates the flexibility and usefulness of the platform for supporting privacy-aware data analysis, as well as for providing an extensible blueprint benchmark architecture for privacy-preservation related methods in mobility data.

Existing approaches for privacy-aware mobility data sharing aim at publishing an anonymized version of the mobility dataset, operating under the assumption that most of the information in the original dataset can be disclosed without causing any privacy violations. In this paper, we assume that the majority of the information that exists in the mobility dataset must remain private and the data has to stay in-house to the hosting organization. To facilitate privacy-aware sharing of the mobility data we develop a trajectory query engine that allows subscribed users to gain restricted access to the database to accomplish various analysis tasks. The proposed engine (i) audits queries for trajectory data to block potential attacks to user privacy, (ii) supports range, distance, and k-nearest neighbors spatial and spatiotemporal queries, and (iii) preserves user anonymity in answers to queries by (a) augmenting the real trajectories with a set of carefully crafted, realistic fake trajectories, and (b) ensuring that no user-specific sensitive locations are reported as part of the returned trajectories.

Sequence datasets are encountered in a plethora of applications spanning from web usage analysis to healthcare studies and ubiquitous computing. Disseminating such datasets offers remarkable opportunities for discovering interesting knowledge patterns, but may lead to serious privacy violations if sensitive patterns, such as business secrets, are disclosed. In this work, we consider how to sanitize data to prevent the disclosure of sensitive patterns during sequential pattern mining, while ensuring that the nonsensitive patterns can still be discovered. First, we re-define the problem of sequential pattern hiding to capture the information loss incurred by sanitization in terms of both events' modification (distortion) and lost nonsensitive knowledge patterns (side-effects). Second, we model sequences as graphs and propose two algorithms to solve the problem by operating on the graphs. The first algorithm attempts to sanitize data with minimal distortion, whereas the second focuses on reducing the side-effects. Extensive experiments show that our algorithms outperform the existing solution in terms of data distortion and side-effects and are more efficient.

The widespread adoption of location based services (LBSs) coupled with recent advances in location tracking technologies, pose serious concerns to user privacy. As a consequence, privacy preserving approaches have been proposed to protect the location information which is communicated during a request for an LBS. Most existing approaches are centralized as they rely on a trusted server to protect the real location of the user. Although the centralized approaches are commonplace, so far no attempt has been made to integrate them in a unified framework. Such an integration would provide the means for easily implementing and testing new techniques by offering ready-made vanilla system components and allow for both the experimental and analytical evaluation of the implemented techniques.In this paper we propose PLOT, an open-ended toolbox that allows the implementation and the evaluation of privacy-enhancing algorithms for LBSs. PLOT offers a variety of interesting features: (i) it supports both real and synthetic movement data, (ii) it relies on spatial DBMSs to efficiently handle movement data as well as the underlying model of user movement, (iii) it offers tools for mobile data preprocessing, movement reconstruction and segmentation, (iv) it allows the implementation of both network-based and free-terrain solutions to location privacy, (v) it provides the infrastructure for second-chance approaches when the main location privacy approach fails, (vi) it implements strategies for the identification of frequent patterns in user movement, and finally (vii) it offers an extended set of visualization tools that both provide insight on the workings of the implemented solutions and facilitate the qualitative and quantitative evaluation of their behavior.

In this paper, we propose a privacy model that offers trajectory privacy to the requesters of Location-Based Services (LBSs), by utilizing an underlying network of user movement. The privacy model has been implemented as a framework that (i) reconstructs the user movement from a series of independent location updates, (ii) identifies routes where user privacy is at risk, and (iii) anonymizes online user requests for LBSs to protect the requester for as long as the service withstands completion. In order to achieve (iii), we propose two anonymization techniques, the K–present (weak) and the K–frequent (strong) trajectory anonymity, and a second chance approach that takes over when anonymization fails to ensure that the privacy of the user is preserved. To the best of our knowledge, this is the first work to propose a trajectory privacy model that utilizes an underlying network of user movement to offer in an interactive way personalized privacy to online user requests on trajectory data.

In this paper, we propose a novel, exact border-based approach that provides an optimal solution for the hiding of sensitive frequent itemsets by (i) minimally extending the original database by a synthetically generated database part - the database extension, (ii) formulating the creation of the database extension as a constraint satisfaction problem, (iii) mapping the constraint satisfaction problem to an equivalent binary integer programming problem, (iv) exploiting underutilized synthetic transactions to proportionally increase the support of non-sensitive itemsets, (v) minimally relaxing the constraint satisfaction problem to provide an approximate solution close to the optimal one when an ideal solution does not exist, and (vi) by using a partitioning in the universe of the items to increase the efficiency of the proposed hiding algorithm. Extending the original database for sensitive itemset hiding is proved to provide optimal solutions to an extended set of hiding problems compared to previous approaches and to provide solutions of higher quality. Moreover, the application of binary integer programming enables the simultaneous hiding of the sensitive itemsets and thus allows for the identification of globally optimal solutions.

The rapid growth of transactional data brought, soon enough, into attention the need of its further exploitation. In this paper, we investigate the problem of securing sensitive knowledge from being exposed in patterns extracted during association rule mining. Instead of hiding the produced rules directly, we decide to hide the sensitive frequent itemsets that may lead to the production of these rules. As a first step, we introduce the notion of distance between two databases and a measure for quantifying it. By trying to minimize the distance between the original database and its sanitized version (that can safely be released), we propose a novel, exact algorithm for association rule hiding and evaluate it on real world datasets demonstrating its effectiveness towards solving the problem. Copyright 2006 ACM.