Lehr- und Forschungseinheit für Datenbanksysteme

Breadcrumb Navigation


Accepted paper at EDBT 2021

KISS - A fast kNN-based Importance Score for Subspaces



Anna Beer, Ekaterina Allerborn, Valentin Hartmann, Thomas Seidl


The 24th International Conference on Extending Database Technology (EDBT 2021),
23–26 March 2021
, Nicosia, Cyprus



In high-dimensional datasets some dimensions or attributes can be more important than others. Whereas most algorithms neglect one or more dimensions for all points of a dataset or at least for all points of a certain cluster together, our method KISS (kNN-based Importance Score of Subspaces) detects the most important dimensions for each point individually. It is fully unsupervised and does not depend on distorted multidimensional distance measures. Instead, the kNN in one-dimensional projections of the data points are used to calculate the score for every dimension’s importance. Experiments across a variety of settings show that those scores reflect well the structure of the data. KISS can be used for subspace clustering. What sets it apart from other methods for this task is its runtime, which is linear in the number of dimensions and O(n log(n)) in the number of points, as opposed to quadratic or even exponential runtimes for previous algorithms.