{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:01:51Z","timestamp":1765544511659,"version":"3.41.0"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T00:00:00Z","timestamp":1435622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF-61402182"},{"name":"SERC 102-158-0074 from Singapore's A&ast;STAR"},{"name":"SUG Grant M58020016 from Nanyang Technological University"},{"name":"NSF (61100148, 61202269, 61472089)"},{"name":"AcRF Tier 2 grant ARC19\/14 from Ministry of Education, Singapore"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2015,6,30]]},"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 Li et al. [2010], has suggested that, with an appropriate strategy, processing a batch of correlated queries as a whole achieves considerably higher accuracy than answering them individually. However, to our knowledge there is currently no practical solution to find such a strategy for an arbitrary query batch; existing methods either return strategies of poor quality (often worse than naive methods) or require prohibitively expensive computations for even moderately large domains. Motivated by this, we propose a\n            <jats:italic>low-rank mechanism<\/jats:italic>\n            (LRM), the first practical differentially private technique for answering batch linear queries with high accuracy. LRM works for both exact (i.e., \u03f5-) and approximate (i.e., (\u03f5, \u03b4)-) differential privacy definitions. We derive the utility guarantees of LRM and provide guidance on how to set the privacy parameters, given the user's utility expectation. Extensive experiments using real data demonstrate that our proposed method consistently outperforms state-of-the-art query processing solutions under differential privacy, by large margins.\n          <\/jats:p>","DOI":"10.1145\/2699501","type":"journal-article","created":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T15:45:37Z","timestamp":1435679137000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Optimizing Batch Linear Queries under Exact and Approximate Differential Privacy"],"prefix":"10.1145","volume":"40","author":[{"given":"Ganzhao","family":"Yuan","sequence":"first","affiliation":[{"name":"South China University of Technology, Guangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"Advanced Digital Sciences Center, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marianne","family":"Winslett","sequence":"additional","affiliation":[{"name":"Advanced Digital Sciences Center and University of Illinois at Urbana-Champaign, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"Hamad Bin Khalifa University, Qatar"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhifeng","family":"Hao","sequence":"additional","affiliation":[{"name":"South China University of Technology and Guangdong University of Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,30]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"An elementary introduction to modern convex geometry","volume":"31","author":"Ball K.","year":"1997","unstructured":"K. Ball . 1997 . An elementary introduction to modern convex geometry . Flavors Geom. 31 , 1 -- 58 . K. Ball. 1997. An elementary introduction to modern convex geometry. Flavors Geom. 31, 1--58.","journal-title":"Flavors Geom."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drp035"},{"volume-title":"Nonlinear Programming","author":"Bertsekas D. P.","key":"e_1_2_1_4_1","unstructured":"D. P. Bertsekas . 1999. Nonlinear Programming . Athena Scientific . D. P. Bertsekas. 1999. Nonlinear Programming. Athena Scientific."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835869"},{"volume-title":"Probability and Measure","author":"Billingsley P.","key":"e_1_2_1_6_1","unstructured":"P. Billingsley . 2012. Probability and Measure , vol. 939 . John Wiley and Sons , New York . P. Billingsley. 2012. Probability and Measure, vol. 939. John Wiley and Sons, New York."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497330963"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374464"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021036"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/040616413"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-97-00777-1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645506"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_18"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989347"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390191"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"e_1_2_1_24_1","volume-title":"Nonlinear Programming: Sequential Unconstrained Minimization Techniques","author":"Fiacco A. V.","year":"1968","unstructured":"A. V. Fiacco and G. P. Mccormick . 1968 . Nonlinear Programming: Sequential Unconstrained Minimization Techniques . John Wiley and Sons , New York . A. V. Fiacco and G. P. Mccormick. 1968. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley and Sons, New York."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835868"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076828X"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(99)00074-7"},{"volume-title":"Proceedings of the Conference on Neural Information Processing Systems (NIPS'12)","author":"Hardt M.","key":"e_1_2_1_28_1","unstructured":"M. Hardt , K. Ligett , and F. Mcsherry . 2012. A simple and practical algorithm for differentially private data release . In Proceedings of the Conference on Neural Information Processing Systems (NIPS'12) . 2348--2356. M. Hardt, K. Ligett, and F. Mcsherry. 2012. A simple and practical algorithm for differentially private data release. In Proceedings of the Conference on Neural Information Processing Systems (NIPS'12). 2348--2356."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214088"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807104"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168653"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448529"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350251"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2046556.2046581"},{"key":"e_1_2_1_39_1","unstructured":"Z. Lin M. Chen L. Wu and Y. Ma. 2010. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. http:\/\/yima.csl.illinois.edu\/psfile\/Lin09-MP.pdf.  Z. Lin M. Chen L. Wu and Y. Ma. 2010. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. http:\/\/yima.csl.illinois.edu\/psfile\/Lin09-MP.pdf."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851182.1851199"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557090"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020487"},{"key":"e_1_2_1_44_1","series-title":"Applied Optimization Series","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Nesterov Y. E.","unstructured":"Y. E. Nesterov . 2003. Introductory Lectures on Convex Optimization: A Basic Course . Applied Optimization Series , vol. 87 . Kluwer Academic Publishers . Y. E. Nesterov. 2003. Introductory Lectures on Convex Optimization: A Basic Course. Applied Optimization Series, vol. 87. Kluwer Academic Publishers."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488652"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213972"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544900"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559812"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807247"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806794"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.v4i1.612"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068816.2068825"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the Conference on Advances Neural Information Processing Systems (NIPS'04)","volume":"17","author":"Srebro N.","unstructured":"N. Srebro , J. D. Rennie , and T. Jaakkola . 2004. Maximum-margin matrix factorization . In Proceedings of the Conference on Advances Neural Information Processing Systems (NIPS'04) . Vol. 17 . 1329--1336. N. Srebro, J. D. Rennie, and T. Jaakkola. 2004. Maximum-margin matrix factorization. In Proceedings of the Conference on Advances Neural Information Processing Systems (NIPS'04). Vol. 17. 1329--1336."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.02.013"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/28\/11\/115010"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-012-0044-1"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989348"},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE'10)","author":"Xiao X.","key":"e_1_2_1_58_1","unstructured":"X. Xiao , G. Wang , and J. Gehrke . 2010. Differential privacy via wavelet transforms . In Proceedings of the IEEE International Conference on Data Engineering (ICDE'10) . 225--236. X. Xiao, G. Wang, and J. Gehrke. 2010. Differential privacy via wavelet transforms. In Proceedings of the IEEE International Conference on Data Engineering (ICDE'10). 225--236."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.48"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0309-y"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213910"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350252"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465330"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350253"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699501","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699501","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:59Z","timestamp":1750227419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699501"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,30]]},"references-count":64,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6,30]]}},"alternative-id":["10.1145\/2699501"],"URL":"https:\/\/doi.org\/10.1145\/2699501","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2015,6,30]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}