Given $n$ items with $k$ properties, construct a query that contains between $\frac {n} 3$ to $\frac {2n} 3$ items

Question

I have $n$ items that have a total of $k$ properties. Each item can have any number of properties, from $1$ to $k$. There is no upper limit to k (the lower limit is $\lceil log(n) \rceil$). The items are distinct, so they have different properties.

The query must only contain AND logical operators. For example, a query can be property A and NOT property B and property C.

Obviously, I must construct a query that has an intersection of properties such that the search space is reduced by $1/3$. Is there a faster way of doing this than simply doing a $O(2^k)$ brute force algorithm?

Answer 1

You are missing a condition – no two elements have exactly the same set of properties. Consider for example the extreme case in which no item has any properties – any query will get either all elements or none of them. We can also assume that $n>1$.

A simple iterative procedure constructs such a query. Let the properties be $P_1,\ldots,P_k$.

• Let $x_1$ be the setting of $P_1$ which maximizes the number of elements satisfying $P_1=x_1$.
• Let $x_2$ be the setting of $P_2$ which maximizes the number of elements satisfying $P_1=x_1$ and $P_2=x_2$.
• And so on.

Denote by $N_i$ the number of elements satisfying $P_1=x_1,\ldots,P_i=x_i$. Thus $N_0 = n$ and $N_k = 1$ (by the missing condition). Let $i>0$ bet the minimal index such that $N_i < 2n/3$ (such an index exists since $N_k=1 < 2n/3$). Thus $N_{i-1} \geq 2n/3$. By construction, $N_i \geq N_{i-1}/2 \geq n/3$. It follows that $n/3 \leq N_i < 2n/3$.