sponsored byIEEEACMThe International Conference for High Performance 
Computing, Networking, Storage and Analysis
FacebookTwitterGoogle PlusLinkedInYouTubeFlickr

SCHEDULE: NOV 16-21, 2014

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

Pardicle: Parallel Approximate Density-Based Clustering

SESSION: Graph Algorithms


TIME: 2:00PM - 2:30PM


AUTHOR(S):Md. Mostofa Ali Patwary, Nadathur Satish, Narayanan Sundaram, Fredrik Manne, Salman Habib, Pradeep Dubey



DBSCAN is a widely used isodensity-based clustering algorithm for particle-data well-known for its ability to isolate arbitrarily-shaped clusters and to filter noise-data. The algorithm is super-linear (O(nlogn)) and computationally expensive for large-datasets. Given the need for speed, we propose an approximate DBSCAN algorithm using density-based-sampling, which performs equally well in quality compared to exact algorithms, but is more than an order-of-magnitude faster. Our experiments on astrophysics and synthetic massive-datasets (8.5B numbers) shows that our approximate algorithm is upto 56x faster than exact algorithms with almost identical quality (Omega-Index>=0.99). We develop a new parallel DBSCAN algorithm, which uses dynamic-partitioning to improve load-balancing and locality. We demonstrate near-linear speedup on shared memory (15x on 16-core Intel® Xeon® E5-2680 systems and 59x on Intel® Xeon Phi™ with 2x performance improvement over Xeon) and distributed memory (3917x using 4096 Xeon cores) computers. Additionally, existing exact algorithms can achieve upto 3.4 times speedup using dynamic-partitioning.

Chair/Author Details:

Felix Wolf (Chair) - German Research School for Simulation Sciences

Md. Mostofa Ali Patwary - Intel Corporation

Nadathur Satish - Intel Corporation

Narayanan Sundaram - Intel Corporation

Fredrik Manne - University of Bergen, Norway

Salman Habib - Argonne National Laboratory

Pradeep Dubey - Intel Corporation

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar

Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society