I/O-efficient batched union-find and its applications to terrain analysis
I/O-efficient batched union-find and its applications to terrain analysis
复制标题
I/O高效的批量联合查找及其在地形分析中的应用
DOI：
10.1145/1137856.1137884
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
K. Yi
中科院分区：
文献类型：
--
作者：
P. Agarwal;L. Arge;K. Yi
尽管在过去的四十年中进行了广泛的研究和大量的应用程序，但没有已知的I/ o高效算法用于联合查找问题。在本文中，我们提出了一个I/ o高效的算法，用于批量（离线）版本的联合查找问题。给定任意N个并集和查找操作序列，其中每个并集操作连接两个不同的集合，我们的算法使用O(sort(N)) = O(N/BlogM/BN/B) I/O，其中M是内存大小，B是磁盘块大小。在最坏情况下，这个界是渐近最优的。如果存在将集合与自身连接起来的联合操作，我们的算法使用O(sort(N) + mst(N)) I/O，其中mst(N)是计算具有N条边的图的最小生成树所需的I/O数。我们还描述了一个简单实用的O(sort(N)log(N/M))-I/O算法，我们已经实现了这个算法。我们对联合发现问题很感兴趣，因为它在地形分析中的应用。地形可以抽象为定义在R2上的高度函数，处理此类函数的许多问题需要联合查找数据结构。随着现代测绘技术的出现，产生了大量的高程数据，这些数据太大而无法装入内存，因此需要高效的I/ o算法来有效地处理这些数据。在本文中，我们研究了两个受益于联合发现数据结构的地形分析问题：(i)计算拓扑持久性和（ii）构造等高线树。这些结构在地形建模、流动分析、拓扑特征提取等方面有着重要的应用。对于这两个问题，我们给出了第一个O(sort(N))-I/O算法，假设输入地形被表示为具有N个顶点的三角形网格。最后，我们报告了一些初步的实验结果，表明我们的算法在不适合内存的大型数据集上比以前的方法有了数量级的改进。
Despite extensive study over the last four decades and numerous applications, no I/O-efficient algorithm is known for the union-find problem. In this paper we present an I/O-efficient algorithm for the batched (off-line) version of the union-find problem. Given any sequence of N union and find operations, where each union operation joins two distinct sets, our algorithm uses O(sort(N)) = O(N/BlogM/BN/B) I/Os, where M is the memory size and B is the disk block size. This bound is asymptotically optimal in the worst case. If there are union operations that join a set with itself, our algorithm uses O(sort(N) + mst(N)) I/Os, where mst(N) is the number of I/Os needed to compute the minimum spanning tree of a graph with N edges. We also describe a simple and practical O(sort(N)log(N/M))-I/O algorithm for this problem, which we have implemented.We are interested in the union-find problem because of its applications in terrain analysis. A terrain can be abstracted as a height function defined over R2, and many problems that deal with such functions require a union-find data structure. With the emergence of modern mapping technologies, huge amount of elevation data is being generated that is too large to fit in memory, thus I/O-efficient algorithms are needed to process this data efficiently. In this paper, we study two terrain analysis problems that benefit from a union-find data structure: (i) computing topological persistence and (ii) constructing the contour tree. These structures have important applications such as terrain modeling, flow analysis, topological feature extraction, etc. We give the first O(sort(N))-I/O algorithms for these two problems, assuming that the input terrain is represented as a triangular mesh with N vertices.Finally, we report some preliminary experimental results, showing that our algorithms give order-of-magnitude improvement over previous methods on large data sets that do not fit in memory.