En flaskhals för att upptäcka avstånd och densitet baserade avvikelser är att en närmaste granne sökning krävs för var och en av datapunkterna, vilket resulterar i ett kvadratiskt antal parvisa avstånd utvärderingar. I detta dokument föreslår vi en ny metod som använder den relativa densiteten med avseende på en fast uppsättning referenspunkter för att uppskatta graden av densitet som definieras i termer av närmaste grannar till en datapunkt. Körtiden för vår algoritm baserad på denna approximation är O(Rn log n) där n är storleken på datasetet och R är antalet referenspunkter. Kandidaternas avvikande värden är rangordnade på grundval av den poäng som tilldelas varje datapunkt. Teoretisk analys och empiriska studier visar att vår metod är effektiv, effektiv och mycket skalbar till mycket stora dataset.
En annan tillnärmning som grundar sig på referenspunkter föreslås i Ref.
An Efficient Reference-Based Approach to Outlier Detection in Large Datasets
{'venue': "Sixth International Conference on Data Mining (ICDM'06)", 'journal': "Sixth International Conference on Data Mining (ICDM'06)", 'mag_field_of_study': ['Computer Science']}