{'fraction_non_alphanumeric': 0.018664047151277015, 'fraction_numerical': 0.0, 'mean_word_length': 4.629834254143646, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Extracting sparse data via histogram queries

We investigate the problem of extracting a sparse data set via histogram queries. A data set is a collection of items, and each item carries a piece of data. A data set is called sparse if there are only a small number of items carrying data of interest. We show that the fundamental limit on the query complexity is equation, n being the size of the data set and k < n being the sparsity level. A counting argument is used to establish the converse part, that is, the lower bound on query complexity. For the achievability part, we analyze a randomized querying method, where in each query, the items to be included in the queried subset are uniformly randomly selected. It is shown that with high probability, the randomly constructed querying method exactly recovers the desired data. Furthermore, we propose an adaptive deterministic algorithm to extract the sparse data set with query complexity equation, achieving the fundamental limit to within a log log k factor.