即使該過程檢查巨大數(shù)據(jù)集中的每個數(shù)據(jù)點,因為它每次只處理數(shù)據(jù)點的小集合,它仍然保持了很高的計算效率。在他們的論文中,研究人員證明,對于涉及一系列通用縮減工具的應(yīng)用,他們提供的縮減方法提供了對完整數(shù)據(jù)集非常好的近似結(jié)果。
該方法取決于數(shù)據(jù)的幾何解釋,涉及稱為超球面的概念,它是圓的多維模擬。任何一個多變量數(shù)據(jù)可以看做是多維空間中的一個點。以同樣的方式,數(shù)字對(1,1)定義二維空間中的點:在X軸上的點和Y軸上的點——就是維基百科表中的一行,其440萬個數(shù)字,定義了一個440萬個圓的空間上每一個點。
研究人員的縮減算法從找到數(shù)據(jù)點子集的平均值開始——比如說20個,那就要進行縮減。這也定義了高維空間中的點,稱之為初始點。然后將20個數(shù)據(jù)點中的每一個“投影”到以初始點為中心的超球面上。也就是說,算法在數(shù)據(jù)點方向上找到超球面上的唯一點。
該算法選擇超球面上的20個數(shù)據(jù)投影之一。然后選擇最遠離第一個的超球面上的投影。它找到兩者之間的中點,然后選擇距離中點最遠的數(shù)據(jù)投影;然后它再找到這兩點之間的中點,并選擇距離它最遠的數(shù)據(jù)投影;如此循環(huán)。
研究人員能夠證明通過這種方法選擇的中點將非??斓厥諗吭诔蛎娴闹行摹T摲椒▽⒖焖龠x擇其平均值接近20個初始點的點的子集。這使得它們特別合適核心集中的候選者。