Abstract-DBSCAN är en välkänd densitetsbaserad klusteralgoritm som kan upptäcka godtyckliga formade kluster och eliminera bullerdata. Men parallellisering av DBSCAN är utmanande eftersom den uppvisar en inneboende sekventiell dataåtkomstordning. Dessutom antar befintliga parallella genomföranden en master-slav-strategi som lätt kan orsaka en obalanserad arbetsbörda och därmed leda till låg parallelleffektivitet. Vi presenterar en ny parallell DBSCAN algoritm (PDSDBSCAN) med hjälp av graf algoritmiska begrepp. Mer specifikt använder vi den osammanhängande datastrukturen för att bryta åtkomstsekvensen för DBSCAN. Dessutom använder vi en trädbaserad nedifrån-och-upp-strategi för att bygga kluster. Detta ger en bättre balans i arbetsbördan. Vi implementerar algoritmen både för delat och distribuerat minne. Med hjälp av datauppsättningar som innehåller upp till flera hundra miljoner högdimensionella punkter, visar vi att PDSDBSCAN avsevärt överträffar master-slave-metoden och uppnår upphastigheter upp till 25.97 med 40 kärnor på delad minnesarkitektur, och upphastigheter upp till 5 765 med 8,192 kärnor på distribuerad minnesarkitektur.
PDSDBSCAN föreslås av Patwary et al. REF använder en fullt distribuerad parallellalgoritm som använder den osammansatta strukturen för att påskynda kommunikationsprocessen.
A new scalable parallel DBSCAN algorithm using the disjoint-set data structure
{'venue': "SC '12", 'journal': None, 'mag_field_of_study': ['Computer Science']}