Cause I'm a Genial Imprecise Point: Outlier Detection for Uncertain Data

Abstrakt

In this paper, we introduce the outlier detection problem in a set of uncertain points. We study two variants of the problems based upon the definition of the outlier. For a given positive integer k(<n) and a set R of n regions as the imprecise points, the first type of the outlier detection problem that we study is to locate n−k points on distinct regions, such that the size of the smallest axis-aligned bounding box (AABB), the diameter or the smallest enclosing circle (SEC) of the resulting points gets minimized. The uncertainty regions we study are squares or disks, and the excluded k regions are considered as outliers. We also study the covering versions in which the objectives of the SEC and the AABB problems are to find the smallest circle or axis-aligned bounding box, respectively, that covers the area of at least n−k regions. In the second-type of outliers, the outliers are those k regions that mostly reduce the uncertainty-induced gap between the lower bound and the upper bound on the size of the output. We give polynomial time algorithms for several variants of the mentioned problems, ranging in running time from O(nlogn) to O(n5.5logn) .