Density biased sampling with locality sensitive hashing for outlier detection

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

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

1 Citation (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 – WISE 2018
Subtitle of host publication19th International Conference, Dubai, United Arab Emirates, November 12–15, 2018 Proceedings, Part II
EditorsHakim Hacid, Wojciech Cellary, Hua Wang, Hye-Young Paik, Rui Zhou
Place of PublicationCham Switzerland
Number of pages16
ISBN (Electronic)9783030029258
ISBN (Print)9783030029241
Publication statusPublished - 2018
EventInternational Conference on Web Information Systems Engineering 2018 - Dubai, United Arab Emirates
Duration: 12 Nov 201815 Nov 2018
Conference number: 19th

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Web Information Systems Engineering 2018
Abbreviated titleWISE 2018
CountryUnited Arab Emirates
Internet address


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

Cite this