File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611973402.39
- Scopus: eid_2-s2.0-84902078319
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Exploiting metric structure for efficient private query release
Title | Exploiting metric structure for efficient private query release |
---|---|
Authors | |
Issue Date | 2014 |
Publisher | Society 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? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/201110 |
ISBN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | en_US |
dc.contributor.author | Roth, A | en_US |
dc.date.accessioned | 2014-08-21T07:13:35Z | - |
dc.date.available | 2014-08-21T07:13:35Z | - |
dc.date.issued | 2014 | en_US |
dc.identifier.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 | en_US |
dc.identifier.isbn | 978-1-611973-38-9 | - |
dc.identifier.uri | http://hdl.handle.net/10722/201110 | - |
dc.description.abstract | We 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.language | eng | en_US |
dc.publisher | Society for Industrial and Applied Mathematics (SIAM). | - |
dc.relation.ispartof | Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | en_US |
dc.rights | © 2014 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms in 2014, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.title | Exploiting metric structure for efficient private query release | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Huang, Z: hzhiyi@hku.hk | en_US |
dc.identifier.authority | Huang, Z=rp01804 | en_US |
dc.description.nature | postprint | - |
dc.identifier.doi | 10.1137/1.9781611973402.39 | - |
dc.identifier.scopus | eid_2-s2.0-84902078319 | - |
dc.identifier.hkuros | 234386 | en_US |
dc.identifier.spage | 523 | - |
dc.identifier.epage | 534 | - |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 141016 | - |