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

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00534694" target="_blank" >RIV/67985807:_____/21:00534694 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-030-67899-9_13" target="_blank" >http://dx.doi.org/10.1007/978-3-030-67899-9_13</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-67899-9_13" target="_blank" >10.1007/978-3-030-67899-9_13</a>

Result language
angličtina
Original language name
Cause I'm a Genial Imprecise Point: Outlier Detection for Uncertain Data
Original language description
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) .
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Structural properties of visibility in terrains and farthest color Voronoi diagrams</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)