Sublinear algorithms for outlier detection and generalized closeness testing
Sublinear algorithms for outlier detection and generalized closeness testing
复制标题
用于异常值检测和广义接近度测试的次线性算法
DOI：
10.1109/isit.2014.6875425
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Suresh
中科院分区：
文献类型：
--
作者：
Jayadev Acharya;Ashkan Jafarpour;A. Orlitsky;A. Suresh
异常检测是在一组相同的分布中找到一些不同分布的问题。紧密测试是确定两个分布是相同还是不同的问题。我们关联了这两个问题，为不等的样本长度构建了亚线性的广义亲密测试，并使用此结果来得出亚线性普遍离群探测器。我们还降低了两个问题的样本复杂性。
Outlier detection is the problem of finding a few different distributions in a set of mostly identical ones. Closeness testing is the problem of deciding whether two distributions are identical or different. We relate the two problems, construct a sub-linear generalized closeness test for unequal sample lengths, and use this result to derive a sub-linear universal outlier detector. We also lower bound the sample complexity of both problems.