More Web Proxy on the site http://driver.im/

research-article

Investigating privacy-aware distributed query evaluation

Authors:

Nicholas L. Farnan,

Ting YuAuthors Info & Claims

WPES '10: Proceedings of the 9th annual ACM workshop on Privacy in the electronic society

Pages 43 - 52

https://doi.org/10.1145/1866919.1866926

Published: 04 October 2010 Publication History

Abstract

Historically, privacy and efficiency have largely been at odds with one another when querying remote data sources: traditional query optimization techniques provide efficient retrieval by exporting information about the intension of a query to data sources, while private information retrieval (PIR) schemes hide query intension at the cost of extreme computational or communication overheads. Given the increasing use of Internet-scale distributed databases, exploring the spectrum between these two extremes is worthwhile. In this paper, we explore the degree to which query intension is leaked to remote data sources when a variety of existing query processing and view materialization techniques are used. We show that these information flows can be quantified in a concrete manner, and investigate the notion of privacy-aware distributed query evaluation. We then propose two techniques to improve the balance between privacy and efficiency when processing distributed queries, and discuss a number of interesting directions for future work.

References

[1]

}}A. Beimel, Y. Ishai, and T. Malkin. Reducing the servers' computation in private information retrieval: Pir with preprocessing. J. Cryptol., 17(2):125--151, 2004.

Digital Library

[2]

}}P. A. Bernstein, F. Giunchiglia, A. Kementsietsidis, J. Mylopoulos, L. Serafini, and llya Zaihrayeu. Data management for peer-to-peer computing: A vision. pages 89--94, 2002.

[3]

}}M. Blaze, J. Feigenbaum, and J. Lacy. Decentralized trust management. In IEEE Symposium on Security and Privacy, pages 164--173, 1996.

Digital Library

[4]

}}Y.-C. Chang. Single database private information retrieval with logarithmic communication. In ACISP, pages 50--61, 2004.

[5]

}}B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval. J. ACM, 45(6):965--981, 1998.

Digital Library

[6]

}}V. Ciriani, S. D. C. di Vimercati, S. Foresti, S. Jajodia, S. Paraboschi, and P. Samarati. Keep a few: Outsourcing data while maintaining confidentiality. In ESORICS, pages 440--455, 2009.

Digital Library

[7]

}}J. Colquhoun and P. Watson. Evaluating a peer-to-peer database server based on bittorrent. In Proceedings of the 26th British National Conference on Databases: Dataspace: The Final Frontier, pages 171--179, Berlin, Heidelberg, 2009. Springer-Verlag.

Digital Library

[8]

}}C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265--284, 2006.

Digital Library

[9]

}}C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum. Differential privacy under continual observation. In STOC, pages 715--724, 2010.

Digital Library

[10]

}}M. J. Franklin, B. T. Jónsson, and D. Kossmann. Performance tradeoffs for client-server query processing. SIGMOD Rec., 25:149--160, June 1996.

Digital Library

[11]

}}Y. Gertner, S. Goldwasser, and T. Malkin. A random server model for private information retrieval or how to achieve information theoretic pir avoiding database replication. In RANDOM, pages 200--217, 1998.

Digital Library

[12]

}}D. Kossmann. The state of the art in distributed query processing. ACM Comput. Surv., 32(4):422--469, 2000.

Digital Library

[13]

}}E. Kushilevitz and R. Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. In FOCS, pages 364--373, 1997.

Digital Library

[14]

}}B. T. Loo, T. Condie, M. Garofalakis, D. E. Gay, J. M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. Declarative networking: language, execution and optimization. In SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pages 97--108, New York, NY, USA, 2006. ACM.

Digital Library

[15]

}}A. Machanavajjhala, D. Kifer, J. Gehrke, and M. Venkitasubramaniam. L-diversity: Privacy beyond k-anonymity. ACM Trans. Knowl. Discov. Data, 1(1):3, 2007.

Digital Library

[16]

}}V. Papadimos and D. Maier. Distributed queries without distributed state. In WebDB, pages 95--100, 2002.

[17]

}}V. Papadimos, D. Maier, and K. Tufte. Distributed query processing and catalogs for peer-to-peer systems. In CIDR, pages 5--8, 2003.

[18]

}}P. Samarati and S. D. C. di Vimercati. Data protection in outsourcing scenarios: issues and directions. In ASIACCS, pages 1--14, 2010.

Digital Library

[19]

}}R. Sion and B. Carbunar. On the practicality of private information retrieval. In NDSS, 2007.

[20]

}}L. Sweeney. k-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl.-Based Syst., 10(5):557--570, 2002.

Digital Library

Cited By

Chouldechova ARoth A(2020)A snapshot of the frontiers of fairness in machine learningCommunications of the ACM10.1145/337689863:5(82-89)Online publication date: 20-Apr-2020
https://dl.acm.org/doi/10.1145/3376898
Ion ABaudisch P(2019)Interactive metamaterialsInteractions10.1145/337449827:1(88-91)Online publication date: 26-Dec-2019
https://dl.acm.org/doi/10.1145/3374498
Tosch EBakshy EBerger EJensen DMoss J(2019)PlanAlyzer: assessing threats to the validity of online experimentsProceedings of the ACM on Programming Languages10.1145/33606083:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360608
Show More Cited By

Index Terms

Investigating privacy-aware distributed query evaluation

Recommendations

Combining Joint and Semi-Join Operations for Distributed Query Processing

The application of a combination of join and semi-join operations to minimize the amount of data transmission required for distributed query processing is discussed. Specifically, two important concepts that occur with the use of join operations as ...
Generating query plans for distributed query processing using genetic algorithm
ICICA'11: Proceedings of the Second international conference on Information Computing and Applications

Query Processing is a key determinant in the overall performance of distributed databases. It requires processing of data at their respective sites and transmission of the same between them. These together constitute a distributed query processing ...
Distributed Query Plan Generation using Cuckoo Search Algorithm

Query processing in distributed databases involves data transmission amongst sites capable of providing answers to a distributed query. For this, a distributed query processing strategy, which generates efficient query processing plans for a given ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WPES '10: Proceedings of the 9th annual ACM workshop on Privacy in the electronic society

October 2010

136 pages

ISBN:9781450300964

DOI:10.1145/1866919

General Chair:
Ehab Al-Shaer
University of North Carolina, Charlotte, USA
,
Program Chair:
Keith Frikken
Miami University, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 October 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS '10

Sponsor:

SIGSAC

CCS '10: 17th ACM Conference on Computer and Communications Security 2010

October 4, 2010

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 106 of 355 submissions, 30%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
193
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chouldechova ARoth A(2020)A snapshot of the frontiers of fairness in machine learningCommunications of the ACM10.1145/337689863:5(82-89)Online publication date: 20-Apr-2020
https://dl.acm.org/doi/10.1145/3376898
Ion ABaudisch P(2019)Interactive metamaterialsInteractions10.1145/337449827:1(88-91)Online publication date: 26-Dec-2019
https://dl.acm.org/doi/10.1145/3374498
Tosch EBakshy EBerger EJensen DMoss J(2019)PlanAlyzer: assessing threats to the validity of online experimentsProceedings of the ACM on Programming Languages10.1145/33606083:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360608
Bavishi RLemieux CFox RSen KStoica I(2019)AutoPandas: neural-backed generators for program synthesisProceedings of the ACM on Programming Languages10.1145/33605943:OOPSLA(1-27)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360594
Salvaneschi GKöhler MSokolowski DHaller PErdweg SMezini M(2019)Language-integrated privacy-aware distributed queriesProceedings of the ACM on Programming Languages10.1145/33605933:OOPSLA(1-30)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360593
Chatterjee KPavlogiannis AToman V(2019)Value-centric dynamic partial order reductionProceedings of the ACM on Programming Languages10.1145/33605503:OOPSLA(1-29)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1145/3360550
Gong YLi SWattanachote KLuo X(2019)Advanced Stereo Seam Carving by Considering Occlusions on Both SidesACM Transactions on Multimedia Computing, Communications, and Applications10.1145/332151315:3(1-21)Online publication date: 20-Aug-2019
https://dl.acm.org/doi/10.1145/3321513
Dimitrova EChrysanthis PLee AHung CPapadopoulos G(2019)Authorization-aware optimization for multi-provider queriesProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3299731(431-438)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3299731
Zhao MLiu PLobo J(2015)Towards Collaborative Query Planning in Multi-party Database NetworksData and Applications Security and Privacy XXIX10.1007/978-3-319-20810-7_2(19-34)Online publication date: 23-Jun-2015
https://doi.org/10.1007/978-3-319-20810-7_2
Ali MPichler RTruong HDustdar S(2012)Incorporating Data Concerns into Query Languages for Data ServicesEnterprise Information Systems10.1007/978-3-642-29958-2_9(132-145)Online publication date: 2012
https://doi.org/10.1007/978-3-642-29958-2_9
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents