I/O-efficient batched union-find and its applications to terrain analysis
Abstract
In this article 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 / B log M/B N / 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 01, 2010
- Source ID
- 10.1145/1868237.1868249
Entities
People
- Ke Yi
- Lars Arge
- Pankaj Agarwal
Organizations
- Aarhus University
- Army Research Office
- Division of Environmental Biology
- Duke University
- Hong Kong University of Science and Technology
- National Science Foundation
- Research Grants Council, University Grants Committee