Density biased sampling with locality sensitive hashing for outlier detection

Xuyun Zhang*, Mahsa Salehi, Christopher Leckie, Yun Luo, Qiang He, Rui Zhou, Rao Kotagiri

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

5 Citations (Scopus)


Outlier or anomaly detection is one of the major challenges in big data analytics since unusual but insightful patterns are often hidden in massive data sets such as sensing data and social networks. Sampling techniques have been a focus for outlier detection to address scalability on big data. The recent study has shown uniform random sampling with ensemble can boost outlier detection performance. However, uniform sampling assumes that all points are of equal importance, which usually fails to hold for outlier detection because some points are more sensitive to sampling than others. Thus, it is necessary and promising to utilise the density information of points to reflect their importance for sampling based detection. In this paper, we formally investigate density biased sampling for outlier detection, and propose a novel density biased sampling approach. To attain scalable density estimation, we use Locality Sensitive Hashing (LSH) for counting the nearest neighbours of a point. Extensive experiments on both synthetic and real-world data sets show that our approach significantly outperforms existing outlier detection methods based on uniform sampling.

Original languageEnglish
Title of host publicationWeb Information Systems Engineering
Subtitle of host publicationWISE 2018 - 19th International Conference, 2018, Proceedings
EditorsHakim Hacid, Wojciech Cellary, Hua Wang, Hye-Young Paik, Rui Zhou
Place of PublicationSwitzreland
PublisherSpringer-VDI-Verlag GmbH & Co. KG
Number of pages16
ISBN (Electronic)9783030029258
ISBN (Print)9783030029241
Publication statusPublished - 1 Jan 2018
Externally publishedYes
Event19th International Conference on Web Information Systems Engineering, WISE 2018 - Dubai, United Arab Emirates
Duration: 12 Nov 201815 Nov 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11234 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th International Conference on Web Information Systems Engineering, WISE 2018
Country/TerritoryUnited Arab Emirates


  • Big data
  • Density biased sampling
  • Locality-Sensitive Hashing
  • Outlier/anomaly detection
  • Unsupervised learning


Dive into the research topics of 'Density biased sampling with locality sensitive hashing for outlier detection'. Together they form a unique fingerprint.

Cite this