File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Exploiting metric structure for efficient private query release

TitleExploiting metric structure for efficient private query release
Authors
Issue Date2014
PublisherSociety for Industrial and Applied Mathematics (SIAM).
Citation
The 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR., 5-7 January 2014. In Conference Proceedings, 2014, p. 523-534 How to Cite?
AbstractWe consider the problem of privately answering queries defined on databases which are collections of points belonging to some metric space. We give simple, computationally efficient algorithms for answering distance queries defined over an arbitrary metric. Distance queries are specified by points in the metric space, and ask for the average distance from the query point to the points contained in the database, according to the specified metric. Our algorithms run efficiently in the database size and the dimension of the space, and operate in both the online query release setting, and the offline setting in which they must in polynomial time generate a fixed data structure which can answer all queries of interest. This represents one of the first subclasses of linear queries for which efficient algorithms are known for the private query release problem, circumventing known hardness results for generic linear queries. Copyright © 2014 by the Society for Industrial and Applied Mathematics.
Persistent Identifierhttp://hdl.handle.net/10722/201110
ISBN

 

DC FieldValueLanguage
dc.contributor.authorHuang, Zen_US
dc.contributor.authorRoth, Aen_US
dc.date.accessioned2014-08-21T07:13:35Z-
dc.date.available2014-08-21T07:13:35Z-
dc.date.issued2014en_US
dc.identifier.citationThe 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR., 5-7 January 2014. In Conference Proceedings, 2014, p. 523-534en_US
dc.identifier.isbn978-1-611973-38-9-
dc.identifier.urihttp://hdl.handle.net/10722/201110-
dc.description.abstractWe consider the problem of privately answering queries defined on databases which are collections of points belonging to some metric space. We give simple, computationally efficient algorithms for answering distance queries defined over an arbitrary metric. Distance queries are specified by points in the metric space, and ask for the average distance from the query point to the points contained in the database, according to the specified metric. Our algorithms run efficiently in the database size and the dimension of the space, and operate in both the online query release setting, and the offline setting in which they must in polynomial time generate a fixed data structure which can answer all queries of interest. This represents one of the first subclasses of linear queries for which efficient algorithms are known for the private query release problem, circumventing known hardness results for generic linear queries. Copyright © 2014 by the Society for Industrial and Applied Mathematics.en_US
dc.languageengen_US
dc.publisherSociety for Industrial and Applied Mathematics (SIAM).-
dc.relation.ispartofProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithmsen_US
dc.rightsProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Copyright © Association for Computing Machinery.-
dc.rights©ACM, 2014. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleExploiting metric structure for efficient private query releaseen_US
dc.typeConference_Paperen_US
dc.identifier.emailHuang, Z: hzhiyi@hku.hken_US
dc.identifier.authorityHuang, Z=rp01804en_US
dc.description.naturepostprint-
dc.identifier.doi10.1137/1.9781611973402.39-
dc.identifier.scopuseid_2-s2.0-84902078319-
dc.identifier.hkuros234386en_US
dc.identifier.spage523-
dc.identifier.epage534-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 141016-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats