2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is impossible in general. Suppose that no item has any property. $\endgroup$ – Yuval Filmus Mar 1 '17 at 13:55
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ It states a lower limit of log(n) $\endgroup$ – paparazzo Mar 1 '17 at 17:18
  • 1
    $\begingroup$ If the items are distinct then $k \geq \lceil \log_2 n \rceil$. There is no need to state this, you can prove it. $\endgroup$ – Yuval Filmus Mar 1 '17 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.