Efficient Deterministic Quantitative Group Testing for Precise Information Retrieval
share
The Quantitative Group Testing (QGT) is about learning a (hidden) subset K of some large domain N using the shortest-possible sequence of queries, where a result of a query provides some information about the size of the intersection of the query with the unknown subset K. Due to very large size of N the length of the sequence of queries proportional to |N| is not acceptable. Thus, the goal of QGT is to extract the knowledge about K using the number of queries that only logarithmically depends on |N| and polynomially on |K|. The QGT framework has already proven its applicability to extracting knowledge from large streams of data, such as finding hot elements or histograms, and to identifying infected records using a small number of tests. We also show other applications to extracting elements from long data streams, maintaining dynamically changing graphs and hypergraphs and private parallel Information Retrieval. Almost all previous work focused on randomized algorithms, which in case of large datasets or streams may have a significant deviation from the expected precision. To mitigate this effect and, instead, to seek a solution for any dataset/stream, in this work we propose an efficient non-adaptive deterministic QGT algorithms for constructing queries and deconstructing hidden set K from the results of the queries. The efficiency is three-fold. First, in terms of almost-optimal number of queries and memory to produce them. Second, all algorithms work in polynomial time. Third, they work for any hidden set K, as well as multi-sets, and even if the results of the queries are capped at √(|K|).
READ FULL TEXT