Investigating privacy-aware distributed query evaluation

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.