# Lens depth function and k-relative neighborhood graph: versatile tools for ordinal data analysis

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2016.

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

- [Statistical Depth Meets Machine Learning: Kernel Mean Embeddings and Depth in Functional Data Analysis](https://mlsanity.com/paper/2105.12778/) (2021)
- [Anomaly detection using data depth: multivariate case](https://mlsanity.com/paper/2210.02851/) (2022)
- [Generalized partitioned local depth](https://mlsanity.com/paper/2303.10167/) (2023)
- [Data Depth and Core-based Trend Detection on Blockchain Transaction Networks](https://mlsanity.com/paper/2303.14241/) (2023)
- [LORE: Jointly Learning the Intrinsic Dimensionality and Relative Similarity Structure From Ordinal Data](https://mlsanity.com/paper/2602.04192/) (2026)

## Abstract (arXiv)

In recent years it has become popular to study machine learning problems in a setting of ordinal distance information rather than numerical distance measurements. By ordinal distance information we refer to binary answers to distance comparisons such as d(A,B)<d(C,D). For many problems in machine learning and statistics it is unclear how to solve them in such a scenario. Up to now, the main approach is to explicitly construct an ordinal embedding of the data points in the Euclidean space, an approach that has a number of drawbacks. In this paper, we propose algorithms for the problems of medoid estimation, outlier identification, classification, and clustering when given only ordinal data. They are based on estimating the lens depth function and the k-relative neighborhood graph on a data set. Our algorithms are simple, are much faster than an ordinal embedding approach and avoid some of its drawbacks, and can easily be parallelized.