uh, is this sarcasm?
A bloom filter is the most appropriate data structure for this use-case. How is it overkill when it uses less space and is faster to query?
A bloom filter is the most appropriate data structure for this use-case. How is it overkill when it uses less space and is faster to query?
1: https://en.wikipedia.org/wiki/HyperLogLog 2: https://en.wikipedia.org/wiki/Count-distinct_problem
To find the fraction of queries each day which are new, you would want to add a second field to your aggregation (or just change the count), the first date the query was seen. After you get the first date each query was seen, sum up the total number of queries first seen on each date, compare it to the traffic for each date.
You could still hand the problem to a new hire (with the appropriate logs access), expect them to code up the MapReduce before lunch (or after if they need to read all the documentation), farm out the job to a few thousand workers, and expect to have the answer when you come back from lunch.