It is true that there needs to be a way to store the aggregate queries "per user". In the current approach of collection this place happens to be on Server, but aggregation per user can easily be done on client-side by leveraging Browser storage.
Approaches like k-anonymity or L-diversity are good but they tackle the problem from a different perspective - making sensitive data available for querying without revealing actual content. The approach suggested in this article talks about methodology which removes the need to collect such data in the first place.
You can also check our paper: https://www.0x65.dev/pages/dissemination-cliqz.html#GreenAna...
We will talk in detail about this methodology- Human Web and how we use to collect data for our search, without compromising users privacy and based on client-side aggregation.
Disclaimer: I work with Cliqz.