algorithm - 真正大数据的不相交集

Question

对于真正的大数据(例如超过 2^32 个元素和超过 2^32 个对并集)是否有任何增强的不相交集算法？

显然最大的问题是我不能做这么大的数组，所以我想知道是否有更好的算法或更好的数据结构来完成我的任务？

Answer 1

处理真正大数据的一种方法是在外部存储器中运行数据。 http://terrain.cs.duke.edu/pubs/union-find.pdf (I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis) 包含一个理论算法，包括对其他批处理算法的相当复杂的调用序列，以及(第 3 节)一个独立的递归算法，它不是渐近有效，但看起来可能很实用。