# Nearest-Neighbour-Induced Isolation Similarity and its Impact on Density-Based Clustering

arXiv: https://arxiv.org/abs/1907.00378 · HTML: https://mlsanity.com/paper/1907.00378/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2019.

## Built on by (most cited first, 11 of 11)

- [Anomaly Detection Based on Isolation Mechanisms: A Survey](https://mlsanity.com/paper/2403.10802/) (2024)
- [Text Anomaly Detection with Simplified Isolation Kernel](https://mlsanity.com/paper/2510.13197/) (2025)
- [Detecting Change Intervals with Isolation Distributional Kernel](https://mlsanity.com/paper/2212.14630/) (2022)
- [Breaking the curse of dimensionality with Isolation Kernel](https://mlsanity.com/paper/2109.14198/) (2021)
- [SDC-HSDD-NDSA: Structure Detecting Cluster by Hierarchical Secondary Directed Differential with Normalized Density and Self-Adaption](https://mlsanity.com/paper/2307.00677/) (2023)
- [IDK-S: Incremental Distributional Kernel for Streaming Anomaly Detection](https://mlsanity.com/paper/2512.05531/) (2025)
- [A principled distributional approach to trajectory similarity measurement](https://mlsanity.com/paper/2301.00393/) (2023)
- [A New Framework for Explainable Rare Cell Identification in Single-Cell Transcriptomics Data](https://mlsanity.com/paper/2601.01358/) (2026)
- [Interpretable Graph-Level Anomaly Detection via Contrast with Normal Prototypes](https://mlsanity.com/paper/2602.10708/) (2026)
- [Optimization-Free Graph Embedding via Distributional Kernel for Community Detection](https://mlsanity.com/paper/2602.13634/) (2026)
- [Learning to Unlearn: Machine Unlearning via Learning the Unlearning Behaviors](https://mlsanity.com/paper/2608.16700/) (2026)

## Abstract (arXiv)

A recent proposal of data dependent similarity called Isolation Kernel/Similarity has enabled SVM to produce better classification accuracy. We identify shortcomings of using a tree method to implement Isolation Similarity; and propose a nearest neighbour method instead. We formally prove the characteristic of Isolation Similarity with the use of the proposed method. The impact of Isolation Similarity on density-based clustering is studied here. We show for the first time that the clustering performance of the classic density-based clustering algorithm DBSCAN can be significantly uplifted to surpass that of the recent density-peak clustering algorithm DP. This is achieved by simply replacing the distance measure with the proposed nearest-neighbour-induced Isolation Similarity in DBSCAN, leaving the rest of the procedure unchanged. A new type of clusters called mass-connected clusters is formally defined. We show that DBSCAN, which detects density-connected clusters, becomes one which detects mass-connected clusters, when the distance measure is replaced with the proposed similarity. We also provide the condition under which mass-connected clusters can be detected, while density-connected clusters cannot.