Att definiera outliers genom sitt avstånd till angränsande exempel är ett populärt sätt att hitta ovanliga exempel i en datauppsättning. Nyligen har mycket arbete utförts med målet att hitta snabba algoritmer för denna uppgift. Vi visar att en enkel loopalgoritm som i värsta fall är kvadratisk kan ge nästan linjär tidsprestanda när datan är i slumpmässig ordning och en enkel beskärningsregel används. Vi testar vår algoritm på verkliga högdimensionella datauppsättningar med miljontals exempel och visar att den nära linjära skalningen håller över flera storleksordningar. Vår genomsnittliga fallanalys tyder på att en stor del av effektiviteten beror på att tiden för att bearbeta icke-outliers, som är de flesta exempel, inte beror på storleken på datamängden.
Bay och Schwabacher REF tillhandahåller detaljerad analys för denna typ av algoritm, och upptäcker att i genomsnitt tid komplexitet blir linjär med datamängd storlek.
Mining distance-based outliers in near linear time with randomization and a simple pruning rule
{'venue': "KDD '03", 'journal': None, 'mag_field_of_study': ['Computer Science']}