用哈希技术实时预测广告投放设备覆盖量，快4倍且误差仅5%。
Real-Time Device Reach Forecasting Using HLL and MinHash Data Sketches
- 用MinHash和HLL sketch技术实现毫秒级设备覆盖量计算
- 在常数空间内处理十亿级数据，速度比传统方法快4倍
- 支持多层聚合与交集，适合实时广告系统快速决策
基于用户指定的定向属性实时预测电视设备覆盖量（Device Reach）对千万美元级广告业务至关重要。传统SQL方法需跨多个定向维度关联数十亿条记录，速度极慢；许多系统采用离线计算，耗时数小时，导致客户接入延迟24小时，可能造成商业损失。为此，我们构建了一个基于MinHash和超日志计数器（HLL）数据摘要的实时预测系统，在用户请求时动态计算设备覆盖量。现有MinHash实现无法有效处理多层聚合与交集问题，本文提出解决方案，并通过单指令多数据（SIMD）向量化操作将算法加速4倍，同时保持恒定空间复杂度，可高效处理十亿级记录。实验表明，结果与传统离线系统精度相当，误差率控制在5%以内。
原文摘要 · Abstract (English)
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%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。