Preserving privacy for on-line analytical processing

Preserving Privacy for On-Line Analytical Processing addresses the privacy issue of On-Line Analytic Processing (OLAP) systems. OLAP systems usually need to meet two conflicting goals. First, the sensitive data stored in underlying data warehouses must be kept secret. Second, analytical queries about the data must be allowed for decision support purposes. The main challenge is that sensitive data can be inferred from answers to seemingly innocent aggregations of the data. This volume reviews a series of methods that can precisely answer data cube-style OLAP, regarding sensitive data while provably preventing adversaries from inferring data.

Preserving Privacy for On-Line Analytical Processing is appropriate for practitioners in industry as well as graduate-level students in computer science and engineering.

1 Introduction	p. 1
1.1 Background	p. 1
1.2 Problem Statement	p. 4
1.3 Overview	p. 6
1.3.1 Overview of Basic Concepts	p. 7
1.3.2 Adapting Previous Approaches to Data Cubes	p. 8
1.3.3 A Lattice-based Solution	p. 10
2 OLAP and Data Cubes	p. 13
2.1 OLAP	p. 13
2.2 Data Cube	p. 15
3 Inference Control in Statistical Databases	p. 21
3.1 Query Set Size Control and Trackers	p. 23
3.2 The Star Query Model	p. 25
3.3 Key-Specified Queries	p. 26
3.4 Linear System Attack and Audit Expert	p. 28
3.5 Intractbility of Inference Control	p. 32
4 Inferences in Data Cubes	p. 37
4.1 Introduction	p. 37
4.2 Preliminaries	p. 38
4.3 Arbitrary Range Queries	p. 41
4.4 Restricted Range Queries	p. 45
4.4.1 Even Range Query Attack	p. 45
4.4.2 Indirect Even Range Query Attack	p. 48
4.4.3 Skeleton Query Attack	p. 49
4.5 Conclusion	p. 51
5 Cardinality-based Inference Control	p. 53
5.1 Introduction	p. 53
5.2 Preliminaries	p. 57
5.2.1 Data Cube	p. 57
5.2.2 Compromisability	p. 60
5.2.3 Formalization Rationale	p. 63
5.3 Cardinality-based Sufficient Conditions	p. 66
5.3.1 Trivial Compromisability	p. 66
5.3.2 Non-trivial Compromisability	p. 68
5.4 A Three-Tier Inference Control Model	p. 76
5.5 Cardinality-based Inference Control for Data Cubes	p. 80
5.5.1 Inference Control Algorithm	p. 80
5.5.2 Correctness and Time Complexity	p. 81
5.5.3 Implementation Issues	p. 83
5.5.3.1 Integrating Inference Control into OLAP	p. 83
5.5.3.2 Re-ordering Tuples in Unordered Dimensions	p. 84
5.5.3.3 Update Operations	p. 85
5.5.3.4 Aggregation Operators Other Than Sum	p. 86
5.6 Conclusions	p. 86
6 Parity-based Inference Control for Range Queries	p. 91
6.1 Introduction	p. 91
6.2 Preliminaries	p. 93
6.2.1 Motivating Examples	p. 93
6.2.2 Definitions	p. 94
6.3 Applying Existing Methods to MDR Queries	p. 97
6.3.1 Query Set Size Control, Overlap Size Control and Audit Expert	p. 97
6.3.2 Finding Maximal Safe Subsets of Unsafe MDR Queries	p. 99
6.4 Parity-Based Inference Control	p. 102
6.4.1 Even MDR Queries	p. 103
6.4.2 Characterizing the QDT Graph	p. 107
6.4.3 Beyond Even MDR Queries	p. 110
6.4.4 Unsafe Even MDR Queries	p. 112
6.5 Discussion	p. 114
6.6 Conclusion	p. 116
7 Lattice-based Inference Control in Data Cubes	p. 119
7.1 Introduction	p. 119
7.2 The Basic Model	p. 120
7.3 Specifying Authorization Objects in Data Cubes	p. 123
7.4 Controlling Inferences in Data Cubes	p. 126
7.4.1 Inferences in Data Cubes	p. 127
7.4.2 Preventing Multi-Dimensional Inferences	p. 130
7.4.2.1 Assumptions	p. 130
7.4.2.2 A Special Case	p. 131
7.4.2.3 The General Case	p. 136
7.4.3 Eliminating One-Dimensional Inferences	p. 140
7.5 Implementation Options and Complexity	p. 143
7.6 Summary	p. 145
8 Query-driven Inference Control in Data Cubes	p. 147
8.1 Introduction	p. 147
8.2 Authorization Objects and Queries in Data Cubes	p. 148
8.3 The Static Approach and Its Impact on Availability	p. 149
8.4 Query-Driven Prevention of Multi-Dimensional Inferences	p. 151
8.4.1 A Special Case	p. 152
8.4.2 The General Case	p. 156
8.4.3 Authorizing Queries	p. 160
8.4.4 Complexity Analysis	p. 165
8.5 Summary	p. 167
9 Conclusion and Future Direction	p. 169
References	p. 173
Index	p. 179

Available:*

On Order

Summary

Summary

Table of Contents