Högdimensionella problem som uppstår från robotrörelseplanering, biologi, datautvinning och geografiska informationssystem kräver ofta beräkning av k närmaste granne (kn) grafer. Knn- grafen för en datamängd erhålls genom att ansluta varje punkt till dess k närmaste punkter. Eftersom forskningen inom ovannämnda områden successivt tar itu med problem av aldrig tidigare skådad komplexitet, ökar efterfrågan på datorgrafik baserat på godtyckliga avståndsmått och stora högdimensionella datamängder, utöver de resurser som finns tillgängliga för en enda maskin. I detta arbete distribuerar vi effektivt beräkningen av knn grafer för kluster av processorer med meddelande passerar. Extensions till vårt distribuerade ramverk inkluderar beräkning av grafer baserat på andra närhets frågor, såsom ungefärlig knn eller intervall frågor. Våra experiment visar nästan linjär speedup med över hundra processorer och indikerar att liknande speedup kan erhållas med flera hundra processorer.
En distribuerad decentraliserad algoritm för k-Nearest Neighbor (kNN) graf REF föreslogs för att distribuera beräkningen av kNN graf med ultra stora datauppsättningar genom att använda den sekventiella strukturen av kNN data.
Distributed Computation of the knn Graph for Large High-Dimensional Point Sets Abstract
{'venue': 'Journal of parallel and distributed computing', 'journal': 'Journal of parallel and distributed computing', 'mag_field_of_study': ['Medicine', 'Computer Science']}