Catálogo de publicaciones - libros

Electronic privacy is drawing more and more attention nowadays, as evidenced by cover stories in media 1311 and initiatives of governments [70]. Public surveys also reflect strong concerns about potential privacy breaches. The results of recent public opinion polls show that 86% of respondents want a web site to obtain opt-in consent before collecting personal information, and 81% of respondents worry that companies may misuse the collected private data [lo]. Privacy is relevant to the business, too. Privacy concerns cause consumers to routinely abandon their shopping carts when too much personal information is being demanded. The estimated loss of internet sales due to such privacy concerns is as much as $18 billion according to analysts [36]. A failure to protect customers7 privacy will eventually become the breach of laws due to upcoming privacy legislation, such as the Health Insurance Portability and Accountability Act (HIPAA) enacted by the US. Congress in 1996.

This chapter reviews On-line Analytical Processing (OLAP) in Section 2.1 and data cubes in Section 2.2.

Inference control has been extensively studied in statistical databases and census data for more than thirty years, as surveyed in [I, 28, 801. The proposed methods can roughly be classified into techniques and perturbation-based techniques. Restriction-based inference control methods prevent malicious inferences by denying some unsafe queries. The metric used to determine the safety of queries includes the minimal number of values aggregated by a query [28], the maximal number of common values aggregated by different queries [29], the approximate intervals that can be guessed from query results [47, 46, 50, 48, 49, 52, 53, 51], and the maximal rank of a matrix representing all answered queries [16]. Perturbation-based techniques add random noises to sensitive data [69], to answers of queries [7], or to database structures [64]

As discussed in Chapter 2, the characteristics that distinguish OLAP systems from general-purpose databases include restricted forms of queries, high efficiency in answering such queries, and relatively less frequent updates of data. OLAP users are more interested in well-formed queries, such as multidimensional range query [41]. These queries usually convey information about general properties. Hence, they better serve the needs of OLAP users in discovering universally applicable knowledge. Although OLAP queries usually involve the aggregation of a large amount of data, they are to be answered in merely a few seconds. Such a fast response is achieved through comprehensive pre-processing and the materialization of multi-dimensional views from which the answer to queries can be more easily derived. Although initially proposed as a relational operator, data cubes can serve as a popular model for organizing multi-dimensional aggregates to facilitate the fast computation of OLAP queries.

As described in previous chapters, inference problem may lead to inappropriate disclosures of sensitive data and consequently cause privacy breaches in OLAP systems. Although the restricted form of OLAP queries makes inferences more difficult, it does not completely remove the threat. Most inferences remain possible using OLAP queries, and exploiting these inferences is usually fairly easy. Although inference control has been investigated for more than thirty years with abundant results, most of the methods are computationally infeasible if directly applied to OLAP systems. This is due to two facts. First, the interactive nature of OLAP systems requires instant responses to most queries. Such a stringent requirement on performance prevents many off-line inference control methods, which have been successful in applications like releasing census data, from being applied to OLAP systems. Second, OLAP queries usually aggregate a large amount of data. Many existing inference control algorithms have run times proportional to the size of the query sets, and their performance decrease quickly when applied to queries with large query sets. Furthermore, these algorithms are enforced after queries arrive, which makes it difficult to shift the computational complexity to off-line processing. Every second spent on checking queries for inferences contributes to the delay in answering the queries.

In the previous chapter, we have studied cardinality-based inference control method. However, two limitations of the proposed method motivate us to investigate other alternatives. First, the method can only deal with skeleton queries, which correspond to complete rows or columns in a cuboid. The method is not applicable to non-skeleton queries that aggregate partial rows or columns. Second, the cardinality-based conditions are sufficient but not necessary, which mean that we cannot tell whether a data cube can be compromised by inferences once the number of its empty cells is greater than the upper bound. These cause the proposed methods to have only limited power in controlling inferences.

We have discussed two different methods for controlling inferences in data cubes. Many lessons can be learned from these results as well as from the previous research on inference control in statistical databases. Most restrictionbased methods adopt a approach. That is, the queries are checked for inferences and only those that do not cause inferences are answered. However, the detection of inferences usually demands on-line (that is, after queries are posed) computations or the bookkeeping of all answered queries. This fact leads to the high on-line performance overhead and storage requirements exhibited by many existing methods.

Chapter 7 describes a novel way of controlling inferences in data cubes. That is, we prevent, instead of detecting, complex inferences through restrictions on queries, and then we remove the remaining simpler inferences. This approach reduces the on-line complexity of inference control to a practical level. It also eliminates the needs for impractical assumptions by supporting a customizable criteria of sensitive information. However, the method is , in the sense that the restrictions on queries are computed once and for all. Such a static approach may lead to unnecessary denials of queries and hence reduce the usefulness of an OLAP system, because optimal restrictions usually depend on actual incoming queries and the queries a user will eventually ask cannot always be predicted.

This book has addressed the following issue: