Differentially Private Data Publishing and Analysis: A Survey <s> Stream Data Publishing <s> Collectors of confidential data, such as governmental agencies, hospitals, or search engine providers, can be pressured to permit data to be used for purposes other than that for which they were collected. To support the data curators, we initiate a study of pan-private algorithms; roughly speaking, these algorithms retain their privacy properties even if their internal state becomes visible to an adversary. Our principal focus is on streaming algorithms, where each datum may be discarded immediately after processing. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Stream Data Publishing <s> We ask the question - how can websites and data aggregators continually release updated statistics, and meanwhile preserve each individual user's privacy? Given a stream of 0's and 1's, we propose a differentially private continual counter that outputs at every time step the approximate number of 1's seen thus far. Our counter construction has error that is only poly-log in the number of time steps. We can extend the basic counter construction to allow websites to continually give top-k and hot items suggestions while preserving users' privacy. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Stream Data Publishing <s> Differential privacy is a recent notion of privacy tailored to privacy-preserving data analysis [11]. Up to this point, research on differentially private data analysis has focused on the setting of a trusted curator holding a large, static, data set; thus every computation is a "one-shot" object: there is no point in computing something twice, since the result will be unchanged, up to any randomness introduced for privacy. However, many applications of data analysis involve repeated computations, either because the entire goal is one of monitoring, e.g., of traffic conditions, search trends, or incidence of influenza, or because the goal is some kind of adaptive optimization, e.g., placement of data to minimize access costs. In these cases, the algorithm must permit continual observation of the system's state. We therefore initiate a study of differential privacy under continual observation. We identify the problem of maintaining a counter in a privacy preserving manner and show its wide applicability to many different problems. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Stream Data Publishing <s> Numerous applications require continuous publication of statistics or monitoring purposes, such as real-time traffic analysis, timely disease outbreak discovery, and social trends observation. These statistics may be derived from sensitive user data and, hence, necessitate privacy preservation. A notable paradigm for offering strong privacy guarantees in statistics publishing is e-differential privacy. However, there is limited literature that adapts this concept to settings where the statistics are computed over an infinite stream of "events" (i.e., data items generated by the users), and published periodically. These works aim at hiding a single event over the entire stream. We argue that, in most practical scenarios, sensitive information is revealed from multiple events occurring at contiguous time instances. Towards this end, we put forth the novel notion of w-event privacy over infinite streams, which protects any event sequence occurring in w successive time instants. We first formulate our privacy concept, motivate its importance, and introduce a methodology for achieving it. We next design two instantiations, whose utility is independent of the stream length. Finally, we confirm the practicality of our solutions experimenting with real data. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Stream Data Publishing <s> Given a set D of tuples defined on a domain Omega, we study differentially private algorithms for constructing a histogram over Omega to approximate the tuple distribution in D. Existing solutions for the problem mostly adopt a hierarchical decomposition approach, which recursively splits Omega into sub-domains and computes a noisy tuple count for each sub-domain, until all noisy counts are below a certain threshold. This approach, however, requires that we (i) impose a limit h on the recursion depth in the splitting of Omega and (ii) set the noise in each count to be proportional to h. The choice of h is a serious dilemma: a small h makes the resulting histogram too coarse-grained, while a large h leads to excessive noise in the tuple counts used in deciding whether sub-domains should be split. Furthermore, h cannot be directly tuned based on D; otherwise, the choice of h itself reveals private information and violates differential privacy. To remedy the deficiency of existing solutions, we present PrivTree, a histogram construction algorithm that adopts hierarchical decomposition but completely eliminates the dependency on a pre-defined h. The core of PrivTree is a novel mechanism that (i) exploits a new analysis on the Laplace distribution and (ii) enables us to use only a constant amount of noise in deciding whether a sub-domain should be split, without worrying about the recursion depth of splitting. We demonstrate the application of PrivTree in modelling spatial data, and show that it can be extended to handle sequence data (where the decision in sub-domain splitting is not based on tuple counts but a more sophisticated measure). Our experiments on a variety of real datasets show that PrivTree considerably outperforms the states of the art in terms of data utility. <s> BIB005
In real world scenarios, it is more practical to publish continuously updated data. This type of data can be simplified as a bit string f0; 1g n and each 1 in the stream represents the occurrence of an event BIB001 . A differentially private mechanism releases one bit at every time step. T , where T represents a time sequence T ¼ ft k : k ¼ 0; . . .g. The bit sðt k Þ 2 f0; 1g denotes whether an event has occurred at time t k . At each time step t k , the count of 1s is denoted as fðt k Þ and the noisy output of the mechanism is b fðt k Þ. Dataset partitioning. Partitioning the dataset in stream data aims to recursively split the stream into sub-domains and evaluate a noisy count for each sub-domain. The problem lies in defining the sub-domain and how many times the stream can be divided. Chan et al. BIB002 presented a p-sums mechanism which computes the partial sum of consecutive bits in a stream. Each sub-domain is defined by p-sum, which is an intermediate result estimating the count at each time interval. Laplace noise is added to a p-sum result rather than an individual count answer. This guarantees an error bound of Oð log 3=2 jT j Þ, which decreases the linear complexity of noise to log complexity. Zhang et at. BIB005 created a quadtree for spatial datasets. They defined a threshold to determine the minimum of a sub-domain and another threshold to limit the height of a quadtree. Using these two thresholds, the amount of noise added to the quadtree can be limited to a constant. Iteration. Dwork et al. BIB003 proposed a continual output transformation algorithm and developed an iteration release mechanism to output the continual count at each time step. The error is decreased to Oð log 3=2 jT j Þ. Georgios et al. BIB004 proposed the notion of w-event privacy to achieve a balanced privacy target. They formulated the iteration mechanism using a sliding window methodology. This w-event privacy aims to mask any event sequence within w time steps, which is suitable for infinite stream releases. Discussion. Even though continual publishing is a popular topic in the data mining community, there are still many unsolved problems in the privacy preserving area. For example, releasing a multi-dimensional dataset periodically, and dealing with other statistical queries needs further exploration.