Given a large cloud of multi-dimensional points, and an off-the-shelf outlier detection method, why does it take a week to finish? After careful analysis, we discovered that duplicate points create subtle issues, that the literature has ignored: if d_max is the multiplicity of the most overplotted point, typical algorithms are quadratic on d_max. For graph-related outlier detection, all the satellites of a 'star' node will have identical features, and thus create over-plotting with d_max being the highest degree; due to power law degree distributions, this may be huge, for real graph data. We propose several ways to eliminate the problem; we report wall-clock times and our time savings; and we show that our methods give either exact results, or highly accurate approximate ones.

16 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]