Finding frequent items using a small amount of memory, while preserving privacy

What is it about?

Suppose we get a long sequence of items – this can be anything from web page requests or sensor readings, to log entries of some software. One of the most common questions in this situation is “Which items are the most frequent”. But what if the sequence is so long that we do not want to store all of it, but we can only access the items one by one? Ways of answering this question were known, but they could potentially violate the users’ privacy. There also existed privacy-preserving ways to do this, but they required storing the whole sequence. In this paper, we provide an algorithm that uses a small amount of space, while also protecting users’ privacy (in the sense of differential privacy).

Featured Image

Photo by Campaign Creators on Unsplash

Photo by Campaign Creators on Unsplash

Why is it important?

Our algorithm can efficiently answer one of the most common questions people have about data streams while preserving users’ privacy.

Perspectives