Med de enorma mängder data som finns tillgängliga idag, är det vanligt att lagra och bearbeta data med hjälp av flera maskiner. Parallella programmeringsplattformar som MapReduce och dess varianter är populära ramar för hantering av så stora data. Vi presenterar de första bevisligen effektiva algoritmer att beräkna, lagra och fråga datastrukturer för räckvidd frågor och ungefärliga närmaste granne frågor i en populär parallell dator abstraktion som fångar de framträdande funktionerna i MapReduce och andra massivt parallella kommunikation (MPC) modeller. I synnerhet beskriver vi algoritmer för kd-träd, rangträd och BBD-träd som endast kräver O(1)-kommunikationsrundor för både förbearbetning och förfrågan samtidigt som de förblir konkurrenskraftiga i fråga om körtid och arbetsbelastning till sina klassiska motsvarigheter. Våra algoritmer är randomiserade, men de kan göras deterministiska med en viss ökning av sin körtid och arbetsbelastning samtidigt som antalet kommunikationsrundor hålls konstant.
Agarwal m.fl. REF beskriver algoritmer för att konstruera distribuerade varianter av klassiska geometriska datastrukturer i MPC-modellen.
Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures
{'venue': "PODS '16", 'journal': None, 'mag_field_of_study': ['Computer Science']}