Arrays of (locality-sensitive) Count Estimators (ACE): Anomaly Detection on the Edge
Arrays of (locality-sensitive) Count Estimators (ACE): Anomaly Detection on the Edge
复制标题
DOI：
10.1145/3178876.3186056
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Chen Luo;Anshumali Shrivastava
中科院分区：
文献类型：
--
作者：
Chen Luo;Anshumali Shrivastava
异常检测是大规模数据处理应用程序中经常且重要的子例程之一，即使是一个良好的话题，现有的无人看待异常检测技术需要存储大量的数据，特别是对于具有超低记忆预算和有限的计算能力的小型移动设备。计数估计算法的算法比大多数最新的无监督异常检测算法的算法。可以利用任何现代处理器的3级缓存。该位置敏感的哈希（LSH）的采样视图与近邻居搜索的广泛流行的视图明显不同和有效。 -CUP99数据是最大的公共基准，完成了超过50万个带有地面真相异常标签的条目。
Anomaly detection is one of the frequent and important subroutines deployed in large-scale data processing applications. Even being a well-studied topic, existing techniques for unsupervised anomaly detection require storing significant amounts of data, which is prohibitive from memory, latency and privacy perspectives, especially for small mobile devices which has ultra-low memory budget and limited computational power. In this paper, we propose ACE (Arrays of (locality-sensitive) Count Estimators) algorithm that can be 60x faster than most state-of-the-art unsupervised anomaly detection algorithms. In addition, ACE has appealing privacy properties. Our experiments show that ACE algorithm has significantly smaller memory footprints (∠ 4MB in our experiments) which can exploit Level 3 cache of any modern processor. At the core of the ACE algorithm, there is a novel statistical estimator which is derived from the sampling view of Locality Sensitive Hashing (LSH). This view is significantly different and efficient than the widely popular view of LSH for near-neighbor search. We show the superiority of ACE algorithm over 11 popular baselines on 3 benchmark datasets, including the KDD-Cup99 data which is the largest available public benchmark comprising of more than half a million entries with ground truth anomaly labels.