Predicting the right number of TVs (Device Reach) in real-time based on a user-specified targeting attributes is imperative for running multi-million dollar ADs business. The traditional approach of SQL queries to join billions of records across multiple targeting dimensions is extremely slow. As a workaround, many applications will have an offline process to crunch these numbers and present the results after many hours. In our case, the solution was an offline process taking 24 hours to onboard a customer resulting in a potential loss of business. To solve this problem, we have built a new real-time prediction system using MinHash and HyperLogLog (HLL) data sketches to compute the device reach at runtime when a user makes a request. However, existing MinHash implementations do not solve the complex problem of multilevel aggregation and intersection. This work will show how we have solved this problem, in addition, we have improved MinHash algorithm to run 4 times faster using Single Instruction Multiple Data (SIMD) vectorized operations for high speed and accuracy with constant space to process billions of records. Finally, by experiments, we prove that the results are as accurate as traditional offline prediction system with an acceptable error rate of 5%.

本研究解决了基于用户指定目标属性进行实时设备覆盖预测的慢速传统SQL查询带来的问题，导致客户入驻时间长达24小时，对业务造成潜在损失。通过使用MinHash和HyperLogLog（HLL）数据草图构建的新实时预测系统，不仅提高了预测速度，且保证了准确性，使结果与传统离线预测系统相当，误差率可接受为5%。

实时设备覆盖预测利用HLL和MinHash数据草图