2
$\begingroup$

I have a numerical dataset of $N$ columns ($\approx 150$) and $K$ rows ($\approx 60000$).

On a user interface, you can apply a filter to one or more columns. We can call the number of filters = $Z$ (with $Z \le N$). Those filters are double sliders allowing to get a min/max for the column. For each filter, I would like to compute the histogram by applying all filters except this one.

The simplest method would be for each filter, to apply all other filters in the complete dataset and compute the histogram of this remaining column. That leads to a $O(Z^2)$ filtering on the dataset and poor performance with an important number of $Z$ and also $K$.

Is there a smarter way ? I have a "feeling" there is probably a way in $O(Z)$ but I am not able yet to clear it in my mind to write it :). It looks quite similar to the problem of the product of an array except self in term of thinking.

Maybe a more concrete example may help

On a e-commerce, you are selling RAMs and you have a filter by:

  • price
  • number of modules
  • frequency
  • memory size

If you filter the price between 100€-200€ and a frequency above 3000Mhz, you will mainly have a memory size of 16Gb. The benefit of the histogram is to see on the "price" slider, in which direction you may have more result with the smallest change. For example going below 100€ will not provide a lot more result as there is nearly no ram below 90€. However, if you increase to 250€ you may have a lot more choice for this range of frequency. Similarly, if you reduce the frequency, you will end up with more choice (lower frequency is cheaper so maybe 32gb will be available at 200€.

To see that:

  • you need to compute the distribution of the price after applying the filter on frequency only
  • then compute the distribution of the frequency after applying the filter on price to have the number of product available below 3000Mhz.

The objective is to be able to render something like :

Double slider with histogram

The histogram is available on the complete range of even if there is a filter on this given range (blue section). This is quite simple if there is only 1 filter as you compute only once the histogram but on my case, depending on other filters, this histogram varies.

I hope this example makes it clear.

$\endgroup$
3
  • $\begingroup$ I don't understand what a filter does. I'm having a hard time understanding "double sliders allowing to get a min/max for the column". Can you help me understand any better? $\endgroup$
    – D.W.
    Jan 4 at 21:38
  • $\begingroup$ Do filters have any properties? Are they commutative? Does the order in which you apply the filters affect the result? Does each filter have an inverse (i.e., a reverse operation that allows to undo the effect of the filter)? Does a filter just select a subset of rows? Anything else like that? $\endgroup$
    – D.W.
    Jan 4 at 21:39
  • $\begingroup$ I have added an image to show what I call "1 filter". As it is simply defining a min-max range for each values, it is commutative. As you mentioned, it is indeed just selecting a subset of rows. $\endgroup$
    – Nicolas M.
    Jan 5 at 6:30
2
$\begingroup$

I'm going to assume that each filter is a predicate on rows that identifies whether that row should be kept or discarded. If so, then yes, this can be solved with many fewer than $O(Z^2)$ applications of the filters. I'll describe two algorithms with different tradeoffs between time vs space: the first applies $O(Z)$ filters but uses $O(ZK)$ memory; the second applies $O(Z \lg Z)$ filters and uses just $O(K \lg Z)$ memory. In both, let $F_1,\dots,F_Z$ denote the filters.

Algorithm 1: minimizing computation time

Here is an algorithm that applies $O(Z)$ applications filters and uses $O(ZK)$ memory. (This corresponds to something like $O(ZK)$ time and $O(ZK)$ memory.) Roughly speaking the algorithm computes a "prefix sum" and a "suffix sum", using two linear scans. In more detail:

  1. For each $i$, compute the subset $S_i$ of rows that are retained if you apply filters $F_1,\dots,F_i$.

  2. For each $j$, compute the subset $S'_j$ of rows that are retained if you apply filters $F_j,\dots,F_Z$.

  3. For each $i$, compute the intersection $S_{i-1} \cap S'_{i+1}$; this is the set of rows that are retained if you apply all the filters except for $F_i$.

Note that step 1 can be done in a linear scan using a total of $Z$ applications of filters, as you can obtain $S_{i+1}$ from $S_i$ using a single application of $F_{i+1}$. Similarly step 2 can be done using $Z$ applications of filters, for a total of $2Z=O(Z)$ applications of filters. Unfortunately you have to store all of $S_1,\dots,S_Z,S'_1,\dots,S'_Z$, which takes $O(ZK)$ memory.

Algorithm 2: minimizing memory usage

A divide-and-conquer algorithm can solve the problem with $O(Z \lg Z)$ applications of filters and $O(K \lg Z)$ memory. (This corresponds to approximately $O(ZK \lg Z)$ time and $O(K \lg Z)$ memory.) The algorithm works like this:

  1. If $Z=1$ or $Z=2$, the problem is trivial; this is the base case. Otherwise:

  2. Compute the subset of rows that are retained if you apply filters $F_1,\dots,F_{Z/2}$. Then, recursively apply the algorithm to this reduced set of rows and to the filters $F_{Z/2+1},\dots,F_Z$.

  3. Compute the subset of rows that are retained if you apply filters $F_{Z/2+1},\dots,F_Z$. Then, recursively apply the algorithm to this reduced set of rows and to the filters $F_1,\dots,F_{Z/2}$.

Notice that you can compute the subsets of rows in steps 2,3 with $O(Z)$ applications of filters. So, if we let $T(Z)$ denote the number of filter applications used by this algorithm when running on $Z$ filters, we have the recurrence relation

$$T(Z) = 2 T(Z/2) + O(Z),$$

which has the solution $T(Z) = O(Z \lg Z)$. The claimed running time follows; and it's not too hard to see that the amount of memory used is as claimed, too (as there are $O(\lg Z)$ levels to the recursion tree, and you store $O(K)$ records per level of the recursion tree at a time).

Can we do better?

A natural question is to ask whether it is possible to find an algorithm that is optimal in both time and memory usage: e.g., $O(Z)$ applications of filters and $O(ZK)$ memory. I don't know whether that is possible or not.

$\endgroup$
3
  • $\begingroup$ Thanks a lot for this detailed answer :O. The solution 1 seems more appropriate (there is no real concern about memory (at least for the amount of data we have now). I'll try to implement it today and accept it just after. In the implementation, I think it will be $O(NKZ)$ as we will store a boolean for each row as result of the filter but no worries, it is linked to the implementation itself $\endgroup$
    – Nicolas M.
    Jan 5 at 6:45
  • $\begingroup$ @NicolasM., Doh! I got $N$ and $K$ confused. Everywhere I wrote $N$ should have been $K$. I just fixed that. Hopefully it's better now? $\endgroup$
    – D.W.
    Jan 5 at 7:28
  • $\begingroup$ Solution 1 works perfectly ;). I have generated a fake dataset of 150000x150 and apply randomly 20 filters. The naive approach tooks 0.893s to return all histograms. The approach 1 tooks 0.623s (30% faster). However, the number of filter ($Z$) being a "a lot" smaller than the number of columns ($K$), I slightly modified it to compute only $F_i$ for selected filter ($Z$ times instead of $K$) and apply the intersection of all $F_i$). This leads to a 0.467s (48% faster). All benchmark done on the same dataset/filters. Many thanks for your time and sharing all this knowledge :) $\endgroup$
    – Nicolas M.
    Jan 5 at 11:12

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.