Online Pricing and Trading of Private Data in Correlated Queries

With the commoditization of private data, data trading in consideration of user privacy protection has become a fascinating research topic. The trading for private web browsing histories brings huge economic value to data consumers when leveraged by targeted advertising. And the online pricing of these private data further helps achieve more realistic data trading. In this paper, we study the trading and pricing of multiple correlated queries on private web browsing history data at the same time. We propose CTRADE, which is a novel online data CommodiTization fRamework for trAding multiple correlateD queriEs over private data. CTRADE first devises a modified matrix mechanism to perturb query answers. It especially quantifies privacy loss under the relaxation of classical differential privacy and a newly devised mechanism with relaxed matrix sensitivity, and further compensates data owners for their diverse privacy losses in a satisfying manner. CTRADE then proposes an ellipsoid-based query pricing mechanism according to a given linear market value model, which exploits the features of the ellipsoid to explore and exploit the close-optimal dynamic price at each round. In particular, the proposed mechanism produces a low cumulative regret, which is quadratic in the dimension of the feature vector and logarithmic in the number of total rounds. Through real-data based experiments, our analysis and evaluation results demonstrate that CTRADE balances total error and privacy preferences well within acceptable running time, indeed produces a convergent cumulative regret with more rounds, and also achieves all desired economic properties of budget balance, individual rationality, and truthfulness.