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?