3
$\begingroup$

Given a 2D lattice with coordinates $1 \leq x \leq c$ and $1 \leq y \leq d$, we define $f(x, y) = xy$.

We wish to find a boolean function $I(x,y)$ that determines in $O(1)$ time whether or not $(x,y)$ belongs to the set of points $S$ of size $k$ such that the sum $Z(S) = \sum_{(x,y) \in S} f(x,y)$ is smaller or equal to any other set of size $k$. One may use $O(c+d+k)$ time and space to construct $I$.

Is this possible? Is this a known problem (my search turned up nothing)? Can https://en.wikipedia.org/wiki/Divisor_summatory_function and its approximation help us?

Motivation: I work in NLP and am trying to find an optimal way of storing part of a word-word cooccurrence matrix in memory and part on disk. This matrix is very sparse. I'm making the simplifying assumption that the probability of two works co-occurring is proportional to their unigram frequencies. By ranking words in terms of frequency, we get the $c$ and $d$ terms. So the smaller the ranks $c$ and $d$, the more likely they are to co-occur, so this value should be stored in memory. Since there will be billions of lookups, $I$ needs to be fast.

Thanks!

$\endgroup$
  • $\begingroup$ Corrected bounds. Will add more details that motivate the question. Not a textbook. Something that came up in my research. Trying to find optimal caching strategy for an NLP problem. $\endgroup$ – Alexandre Dec 22 '16 at 4:35
  • $\begingroup$ Motivation added! $\endgroup$ – Alexandre Dec 23 '16 at 16:20
3
$\begingroup$

The set $S$ must have the following form: there must exist a threshold $t$ such that:

  • If $xy < t$, then $(x,y)$ is in $S$.
  • Some or all of the points $(x,y)$ with $xy=t$ are in $S$.
  • If $xy > t$, then $(x,y)$ is not in $S$.

Moreover, in the second bullet, it doesn't matter which points with $xy=t$ you put into $S$; all that matters is how many of them you put into $S$. Finally, notice that the locus of points $(x,y)$ such that $xy=t$ forms a hyperbola.

It follows that one way to parametrize the set is as

$$S = \{(x,y) : xy < t \text{ or } (xy=t \text{ and } x<u)\},$$

for some parameters $t,u$. It's clear that, given $t,u$, membership can tested in $O(1)$ time, i.e., your oracle will run in $O(1)$ time, as required.

So, we simply need to select suitable values of $t,u$ during the precomputation to construct $I$. How can we do that?

One easy way is to use binary search. Notice that it's easy to count the number of lattice points $(x,y)$ such that $xy < t$ in $O(c)$ time: just iterate over $x=1,2,\dots,c$ and count the number of values $y$ such that $xy < t$, i.e., such that $y < t/x$; there are $\lfloor (t-1)/x \rfloor$ of them, so we sum that over $x=1,2,\dots,c$. Now use binary search on $t$ until you find the largest $t$ such that the number of such points is at most $k$. This gives you the value of $t$. It also gives you the number of points $(x,y)$ such that $xy<t$; call that number $k_0$.

Once you know the value of $t$, the next step is to choose a suitable value for $u$. We'll need to choose $u$ so that there are exactly $k-k_0$ lattice points $(x,y)$ such that $xy=t$ and $x<u$. Finding $u$ can be done by iterating over $x=1,2,\dots,c$; for each $x$, check whether $y=t/x$ is an integer, keep track of how many lattice points you've found, and stop once you've found $k-k_0$ of them.

In the end, the precomputation requires something like $O(\min(c,d) \log k)$ time and the oracle can be computed in $O(1)$ time. The precomputation can probably be done even faster through implementation tricks and/or some number theory, but given your problem statement, I'm guessing this might already be good enough.

$\endgroup$
  • $\begingroup$ A lot to chew on here D.W. Give me a day or two to think it over. Looks good though. Thank you for your contribution. Had you seen something similar before? $\endgroup$ – Alexandre Dec 22 '16 at 20:47
  • $\begingroup$ I'm trying to understand how your algorithm's set $S$ of size $k$ necessarily has $Z(S) \leq Z(S')$ for any $S'$ of size $k$ that is not equal to $S$. Think you can sketch a proof? Perhaps by contradiction: Suppose there is an $S'$ such that $Z(S') < Z(S)$. Then $t'$ must less than $t$, which is impossible because... $\endgroup$ – Alexandre Dec 23 '16 at 16:32
  • $\begingroup$ @Alexandre, it's a very simple argument: if you have a bunch of numbers and want to form a set of size $k$ whose sum is minimal, you have to take the $k$ smallest numbers. In this case, each point $(x,y)$ corresponds to a number $xy$. Taking the $k$ smallest numbers corresponds to taking a set of points of the form given at the beginning of my answer. $\endgroup$ – D.W. Dec 23 '16 at 18:11
  • $\begingroup$ @Alexandre, alternative proof: Let $S$ be the set where $Z(S)$ is smallest. I claim $S$ has the desired form. Let $t = \max\{xy : (x,y) \in S\}$. If there was any lattice point $(x',y')$ with $x'y'<t$ that's not in $S$, you could swap it in (removing the lattice point $(x,y)$ with $xy=t$), obtaining a new set with a smaller value of $Z(\cdot)$ -- but that contradicts the assumed minimality of $S$, so that can't be possible. i.e., every lattice point $(x,y)$ with $xy<t$ is in $S$. And by defn of $t$, $S$ doesn't have any lattice point $(x,y)$ with $xy>t$. That completes the proof. $\endgroup$ – D.W. Dec 23 '16 at 18:14

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.