On-Device Algorithms for Public-Private Data with Absolute Privacy Skip to main content Explore our many areas of focus Explore all research areas Applied AI & sciences Earth AI Health AI Science AI Sustainability & crisis resilience Foundational ML & algorithms Algorithms & theory Information retrieval Machine intelligence Machine perception Natural language processing People, systems & quantum AI Human-computer interaction and visualization Networking Quantum AI Responsible AI Anti abuse Software engineering Software systems Learn More Publications Projects Building a collaborative ecosystem Datasets Access high-quality datasets to accelerate your research. Tools & services Explore our latest AI models and products. Open source Discover open-source code and collaborate with the community. Shaping the future together See all programs Faculty programs Participating in the academic research community through meaningful engagement with university faculty. Student programs Supporting the next generation of researchers through a wide range of programming. Locations Find your place in our global offices and research labs. Translating discovery into real-world impact People Our researchers drive advancements in computer science through both fundamental and applied research. Teams Collaborative groups tackling the world's most challenging AI problems. Research Explore our many areas of focus Explore all research areas Applied AI & sciences Earth AI Health AI Science AI Sustainability & crisis resilience Foundational ML & algorithms Algorithms & theory Information retrieval Machine intelligence Machine perception Natural language processing People, systems & quantum AI Human-computer interaction and visualization Networking Quantum AI Responsible AI Anti abuse Software engineering Software systems Learn More Publications Projects Resources Building a collaborative ecosystem Datasets Access high-quality datasets to accelerate your research. Tools & services Explore our latest AI models and products. Open source Discover open-source code and collaborate with the community. Conferences & events Careers Shaping the future together See all programs Faculty programs Participating in the academic research community through meaningful engagement with university faculty. Student programs Supporting the next generation of researchers through a wide range of programming. Locations Find your place in our global offices and research labs. Blog About Translating discovery into real-world impact People Our researchers drive advancements in computer science through both fundamental and applied research. Teams Collaborative groups tackling the world's most challenging AI problems. Google Research Google AI Learn about all our AI Google DeepMind Explore the frontier of AI Google Labs Try our AI experiments Research Resources Conferences & events Careers Blog About Search Home Publications On-Device Algorithms for Public-Private Data with Absolute Privacy Alessandro Epasto Hossein Esfandiari Vahab Mirrokni Proceedings of The Web Conference 2019 (WWW'19) (to appear) Download Google Scholar Copy Bibtex Abstract Motivated by the increasing need to preserve privacy in digital devices, we introduce the on-device public-private model of computation. Our motivation comes from social-network based recommender systems in which the users want to receive recommendations based on the information available on their devices, as well as the suggestions of their social contacts, without sharing such information or contacts with the central recommendation system. Our model allows us to solve many algorithmic problems while providing absolute (deterministic) guarantees of the privacy of on-device data and the user's contacts. In fact, we ensure that the private data and private contacts are never revealed to the central system. Our restrictive model of computation presents several interesting algorithmic challenges because any computation based on private information and contacts must be performed on local devices of limited capabilities. Despite these challenges, under realistic assumptions of inter-device communication, we show several efficient algorithms for fundamental data mining and machine learning problems, ranging from k-means clustering to heavy hitters. We complement this analysis with strong impossibility results for efficient private algorithms without allowing inter-device communication. In our experimental evaluation, we show that our private algorithms provide results almost as accurate as those of the non-private ones while speeding up the on-device computations by orders of magnitude. Research Areas Algorithms and theory Meet the teams driving innovation Our teams advance the state of the art through research, systems engineering, and collaboration across Google. See our teams Follow us Explore our other initiatives Google AI Discover how Google AI is committed to enriching knowledge and solving complex challenges Products Build Research Responsibility Societal Impact About Google Cloud High-performance infrastructure for cloud computing, data analytics & machine learning Overview Solutions Products Pricing Resources Google DeepMind Our mission is to build AI responsibly to benefit humanity Models Research Science About Google Labs Explore the future of AI responsibly with Google Labs About Experiments Stay connected About Google Google Products Privacy Terms Cookies management controls ×