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$
1
  • $\begingroup$ This is impossible in general. Suppose that no item has any property. $\endgroup$ Mar 1, 2017 at 13:55

1 Answer 1

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$
2
  • $\begingroup$ It states a lower limit of log(n) $\endgroup$
    – paparazzo
    Mar 1, 2017 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$ Mar 1, 2017 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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