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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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) .

Název v anglickém jazyce

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

Popis výsledku anglicky

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) .

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Strukturální vlastnosti viditelnosti terénů a Voroného diagramů nejvzdálenější barvy</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

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

Název statě ve sborníku

Algorithms and Discrete Applied Mathematics

ISBN

978-3-030-67898-2

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

14

Strana od-do

165-178

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Rupnagar

Datum konání akce

11. 2. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—