Låt R vara en uppsättning objekt. Ett objekt o R är en utlier, om det finns mindre än k objekt i R vars avstånd till o är som mest r. Värdena för k, r, och avståndet metrisk tillhandahålls av en användare vid körtiden. Målet är att återbörda alla outliers med den minsta I/O-kostnaden. I detta dokument behandlas en generisk version av problemet, där det inte finns någon information tillgänglig för beräkning av outlier, med undantag för objektens ömsesidiga avstånd. Vi visar en övre gräns för minnesförbrukningen som gör det möjligt att upptäcka alla avvikelser genom att skanna datasetet 3 gånger. Den övre gränsen visar sig vara extremt låg i praktiken, t.ex. mindre än 1% av R. Eftersom den faktiska minneskapaciteten hos en realistisk DBMS är vanligtvis större, utvecklar vi en ny algoritm som integrerar våra teoretiska resultat med noggrant utformade heuristiker som utnyttjar det extra minnet för att förbättra I/O-effektiviteten. Vår teknik rapporterar alla outliers genom att skanna datauppsättningen högst två gånger (i vissa fall, även en gång), och avsevärt överträffar de befintliga lösningarna med en faktor upp till en storleksordning.
Tao och Al. REF visar en övre gräns för minnesförbrukningen, vilket gör det möjligt att upptäcka alla avvikelser genom att skanna datasetet tre gånger, men det är inte tillämpligt på strömmar där tillgängliga data hela tiden förändras.
Mining distance-based outliers from large databases in any metric space
{'venue': "KDD '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}