This disclosure relates to using probabilistic data structures to enable systems to detect fraud while preserving user privacy. In one aspect, a method includes obtaining a set of frequency filters. Each frequency filter defines a maximum event count for a specified event type over a specified time duration and corresponds to a respective content provider. A subset of the frequency filters are identified as triggered frequency filters for which an actual event count for the specified event type corresponding to the frequency filter exceeds the maximum event count defined by the frequency filter during a time period corresponding to a specified time duration for the frequency filter. A probabilistic data structure that represents at least a portion of the frequency filters in the subset of frequency filters is generated. A request for content is sent to multiple content providers. The request for content includes the probabilistic data structure.