Compute several histograms with multiple filter conditions

Question

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 :

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.

Answer 1

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.