@inproceedings{dwork2005sub-linear,
author = {Dwork, Cynthia},
title = {Sub-linear Queries Statistical Databases: Privacy with Power},
series = {Lecture Notes in Computer Science},
booktitle = {Cryptographers' Track, RSA Conference (CT-RSA '05)},
year = {2005},
month = {February},
abstract = {We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a database, a query consists of a pair (S, f) where S is a set of rows in the database and f is a function mapping database rows to [0, 1]. The true response is 
r∈S f(DBr), a noisy version of which is released. Results in [3, 4] show that a strong form of privacy can be maintained using a surprisingly small amount of noise, provided the total number of queries is sublinear in the number n of database rows. We call this a sub-linear queries (SuLQ) database. The assumption of sublinearity becomes reasonable as databases grow increasingly large.

The SuLQ primitive – query and noisy reply – gives rise to a calculus of noisy computation. After reviewing some results of [4] on multi-attribute SuLQ, we illustrate the power of the SuLQ primitive with three examples [2]: principal component analysis, k means clustering, and learning in the statistical queries learning model.},
publisher = {Springer},
url = {http://approjects.co.za/?big=en-us/research/publication/sub-linear-queries-statistical-databases-privacy-with-power/},
pages = {1-6},
volume = {3376},
edition = {Cryptographers' Track, RSA Conference (CT-RSA '05)},
}