Interactive Exploration of Subspace Clusters on Multicore Processors

TY - CHAP

T1 - Interactive Exploration of Subspace Clusters on Multicore Processors

AU - Pham, The Hai

AU - Kristensen, Jesper

AU - Mai, Son T.

AU - Assent, Ira

AU - Jacobsen, Jon

AU - Vo, Bay

AU - Le, Anh

PY - 2018

Y1 - 2018

N2 - The PreDeCon clustering algorithm finds arbitrarily shaped clusters in high-dimensional feature spaces, which remains an active research topic with many potential applications. However, it suffers from poor runtime performance, as well as a lack of user interaction. Our new method AnyPDC introduces a novel approach to cope with these problems by casting PreDeCon into an anytime algorithm. In this anytime scheme, it quickly produces an approximate result and iteratively refines it toward the result of PreDeCon at the end. AnyPDC not only significantly speeds up PreDeCon clustering but also allows users to interact with the algorithm during its execution. Moreover, by maintaining an underlying cluster structure consisting of so-called primitive clusters and by block processing of neighborhood queries, AnyPDC can be efficiently executed in parallel on shared memory architectures such as multi-core processors. Experiments on large real world datasets show that AnyPDC achieves high quality approximate results early on, leading to orders of magnitude speedup compared to PreDeCon. Moreover, while anytime techniques are usually slower than batch ones, the algorithmic solution in AnyPDC is actually faster than PreDeCon even if run to the end. AnyPDC also scales well with the number of threads on multi-cores CPUs.

AB - The PreDeCon clustering algorithm finds arbitrarily shaped clusters in high-dimensional feature spaces, which remains an active research topic with many potential applications. However, it suffers from poor runtime performance, as well as a lack of user interaction. Our new method AnyPDC introduces a novel approach to cope with these problems by casting PreDeCon into an anytime algorithm. In this anytime scheme, it quickly produces an approximate result and iteratively refines it toward the result of PreDeCon at the end. AnyPDC not only significantly speeds up PreDeCon clustering but also allows users to interact with the algorithm during its execution. Moreover, by maintaining an underlying cluster structure consisting of so-called primitive clusters and by block processing of neighborhood queries, AnyPDC can be efficiently executed in parallel on shared memory architectures such as multi-core processors. Experiments on large real world datasets show that AnyPDC achieves high quality approximate results early on, leading to orders of magnitude speedup compared to PreDeCon. Moreover, while anytime techniques are usually slower than batch ones, the algorithmic solution in AnyPDC is actually faster than PreDeCon even if run to the end. AnyPDC also scales well with the number of threads on multi-cores CPUs.

KW - Active clustering

KW - Anytime clustering

KW - Interactive algorithm

KW - Subspace clustering

UR - http://www.scopus.com/inward/record.url?scp=85069186338&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-58415-6_6

DO - 10.1007/978-3-662-58415-6_6

M3 - Book chapter

SN - 978-3-662-58415-6

VL - 11310

T3 - Lecture Notes in Computer Science (LNCS)

SP - 169

EP - 199

BT - Transactions on Large-Scale Data- and Knowledge-Centered Systems XXXIX - Special Issue on Database- and Expert-Systems Applications

A2 - Hameurlain, Abdelkader

A2 - Wagner, Roland

A2 - Benslimane, Djamal

A2 - Damiani, Ernesto

A2 - Grosky, William I.

PB - Springer VS

CY - Berlin, Heidelberg

ER -