CORE-SG: Efficient Computation of Multiple MSTs for Density-Based Methods

Antonio Cavalcante Araujo Neto, Murilo Coelho Naldi, Ricardo J.G.B. Campello, Jorg Sander

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review


Several popular density-based methods for unsuper-vised and semi-supervised learning tasks, including clustering and classification, can be formulated as instances of a framework that is based on the processing of a minimum spanning tree of the data, where the edge weights correspond to a form of (unnormalized) density estimate w.r.t. a smoothing parameter mpts. While density-based methods are considered to be robust w.r.t. mpts in the sense that small changes in its value usually lead to slight or no changes in the resulting structure, wider ranges of mpts values may lead to different results that a user would like to analyze before choosing the most suitable value for a given data set or application. However, to explore multiple results for a range of mpts values, until recently, one had to re-run the density-based method for each value in the range independently, which is computationally inefficient. This paper proposes a new computationally efficient approach to compute multiple density-based minimum spanning trees w.r.t. a set of mpts values by leveraging a graph obtained from a single run of the density-based algorithm, without the need for re-runs of the original algorithm. We present theoretical and experimental results that show that our approach overcomes the drawbacks of the previous state-of-the-art, and it is considerably superior in runtime and graph size while being easier to implement. Our experimental evaluation using synthetic and real data shows that our strategy can lead to speed-up factors of hundreds to thousands of times on the computation of density-based minimum spanning trees.

TitelProceedings - 2022 IEEE 38th International Conference on Data Engineering, ICDE 2022
ISBN (Elektronisk)9781665408837
StatusUdgivet - 2022
Udgivet eksterntJa
Begivenhed38th IEEE International Conference on Data Engineering, ICDE 2022 - Virtual, Online, Malaysia
Varighed: 9. maj 202212. maj 2022


Konference38th IEEE International Conference on Data Engineering, ICDE 2022
ByVirtual, Online
NavnProceedings of the International Conference on Data Engineering

Bibliografisk note

Funding Information:
This study was partially funded by NSERC, FAPESP - Grant 2019/09817-6, and Serasa Experian.

Publisher Copyright:
© 2022 IEEE.


Dyk ned i forskningsemnerne om 'CORE-SG: Efficient Computation of Multiple MSTs for Density-Based Methods'. Sammen danner de et unikt fingeraftryk.