{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:48:39Z","timestamp":1763466519301},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            Differential privacy is a promising privacy-preserving paradigm for statistical query processing over sensitive data. It works by injecting random noise into each query result, such that it is provably hard for the adversary to infer the presence or absence of any individual record from the published noisy results. The main objective in differentially private query processing is to maximize the accuracy of the query results, while satisfying the privacy guarantees. Previous work, notably the matrix mechanism [16], has suggested that processing a batch of correlated queries as a whole can potentially achieve considerable accuracy gains, compared to answering them individually. However, as we point out in this paper, the matrix mechanism is mainly of theoretical interest; in particular, several inherent problems in its design limit its accuracy in practice, which almost never exceeds that of na\u00efve methods. In fact, we are not aware of any existing solution that can effectively optimize a query batch under differential privacy. Motivated by this, we propose the\n            <jats:italic>Low-Rank Mechanism<\/jats:italic>\n            (LRM), the first practical differentially private technique for answering batch queries with high accuracy, based on a\n            <jats:italic>low rank approximation<\/jats:italic>\n            of the workload matrix. We prove that the accuracy provided by LRM is close to the theoretical lower bound for any mechanism to answer a batch of queries under differential privacy. Extensive experiments using real data demonstrate that LRM consistently outperforms state-of-the-art query processing solutions under differential privacy, by large margins.\n          <\/jats:p>","DOI":"10.14778\/2350229.2350252","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1352-1363","source":"Crossref","is-referenced-by-count":54,"title":["Low-rank mechanism"],"prefix":"10.14778","volume":"5","author":[{"given":"Ganzhao","family":"Yuan","sequence":"first","affiliation":[{"name":"South China University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"Advanced Digital Sciences Center, Illinois at Singapore Pte. Ltd."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marianne","family":"Winslett","sequence":"additional","affiliation":[{"name":"Advanced Digital Sciences Center, Illinois at Singapore Pte. Ltd. and University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"Advanced Digital Sciences Center, Illinois at Singapore Pte. Ltd."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhifeng","family":"Hao","sequence":"additional","affiliation":[{"name":"South China University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835869"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497330963"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374464"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021036"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-97-00777-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645506"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989347"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390191"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835868"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807104"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2046556.2046581"},{"key":"e_1_2_1_18_1","volume-title":"The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices. Arxiv preprint arXiv:1009.5055","author":"Lin Z.","year":"2010","unstructured":"Z. Lin , M. Chen , L. Wu , and Y. Ma . The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices. Arxiv preprint arXiv:1009.5055 , 2010 . Z. Lin, M. Chen, L. Wu, and Y. Ma. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices. Arxiv preprint arXiv:1009.5055, 2010."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851199"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557090"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020487"},{"key":"e_1_2_1_23_1","series-title":"Applied Optimization","volume-title":"Introductory lectures on convex optimization: a basic course","author":"Nesterov Y.","year":"2003","unstructured":"Y. Nesterov . Introductory lectures on convex optimization: a basic course , volume 87 of Applied Optimization . Kluwer Academic Publishers , 2003 . Y. Nesterov. Introductory lectures on convex optimization: a basic course, volume 87 of Applied Optimization. Kluwer Academic Publishers, 2003."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807247"},{"key":"e_1_2_1_25_1","volume-title":"Learning in a large function space: Privacy-preserving mechanisms for SVM learning. To appear in Journal of Privacy and Confidentiality","author":"Rubinstein B. I. P.","year":"2012","unstructured":"B. I. P. Rubinstein , P. L. Bartlett , L. Huang , and N. Taft . Learning in a large function space: Privacy-preserving mechanisms for SVM learning. To appear in Journal of Privacy and Confidentiality , 2012 . B. I. P. Rubinstein, P. L. Bartlett, L. Huang, and N. Taft. Learning in a large function space: Privacy-preserving mechanisms for SVM learning. To appear in Journal of Privacy and Confidentiality, 2012."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2307\/30044198"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989348"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447831"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.48"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:28:12Z","timestamp":1672226892000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350252"}},"subtitle":["optimizing batch queries under differential privacy"],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":29,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350252"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350252","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}