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:
- number of modules
- 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.