Our algorithm is about estimating the true statistic values from a data set. The data set is a table in relational database, we are going to estimate the statistic value for filtered records, like
SUM("Sales") WHERE city="New York". We do this because the table is too large to calculate the true answer.
We use relative error for accuracy measurement at first, but we soon noticed that for small values, the error usually exceeds 100% and raises the average error. For example, if the true answer is 3, and my algorithm gives 9, it is a 200% error and will result in a very high average error, even if the other queries are answered properly. So I'm wondering if using relative error is not proper here, because if my algorithm always estimate a very small value, there will be unlikely for my algorithm to give an average error over 100%. It is unfair if my algorithm overestimates the true value.
Please note that I'm not trying to develop an algorithm to do the estimation, but I'm finding a fair measurement to evaluate the accuracy for different estimation algorithms. For example, we can estimate the sum by 1) Sampling from the original data set and estimate the sum with CLT, or 2) Draw a histogram offline and give an approximate answer for specific queries online according to the histogram. My question here is that under the traditional definition of relative error, the algorithm that always give small values tend to benefit more, so I'm looking for another measurement which is fairer.
I use the following formula in the past, but I'm wondering if it has any theories behind it:
So is there any better measurement to measure the error for an estimation algorithm?