What is the proper way to measure error for an estimation algorithm? 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:
$error=abs(x_{estimate}-x_{true})/{max(x_{estimate},x_{true})}$
So is there any better measurement to measure the error for an estimation algorithm? 
Thanks!
 A: There are a lot of measures for error of estimation and the one you provided is a valid one. But since you are working with the sum of random variables, I suggest using normal distribution (supported by the Central Limit Theorem) and instead of calculating once the sum of sales in New York, you’ll have to repeat that algorithm (at least 30 times) including randomness in your selection.
With your sample of 30 "sum of sales" you can use Normal Distribution and not only calculate the Mean Square Error as a good estimator of error, but also calculate probabilities.
Another good news is most of statistical inference is developed for variables with normal distribution.
A: I would suggest adding a "small" number to the denominator of your ratio.
$$error=\frac{|x_{estimate}-x_{true}|}{x_{true}+K}$$
You set $K$ equal to a "negligible" amount. For your example, setting $K=6$ would give an error of 66% instead of 200% for $K=0$.
The number to add will depend on your context and what kind of absolute errors are negligible
