I/O-efficient batched union-find and its applications to terrain analysis

ABSTRACT

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/Blog_M/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 R², 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.

REFERENCES

• 1: P. K. Agarwal, L. Arge, and K. Yi. I/O-efficient construction of constrained Delaunay triangulations. In Proc. 13rd European Sympos. Algorithms, pages 355--366, 2005.
• 2: Pankaj K. Agarwal , Herbert Edelsbrunner , John Harer , Yusu Wang, Extreme elevation on a 2-manifold, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997871]
• 3: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 4: Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 5: Lars Arge , Gerth Stølting Brodal , Laura Toma, On external-memory MST, SSSP and multi-way planar graph separation, Journal of Algorithms, v.53 n.2, p.186-206, November 2004 [doi>10.1016/j.jalgor.2004.04.001]
• 6: Lars Arge , Jeffrey S. Chase , Patrick Halpin , Laura Toma , Jeffrey S. Vitter , Dean Urban , Rajiv Wickremesinghe, Efficient Flow Computation on Massive Grid Terrain Datasets, Geoinformatica, v.7 n.4, p.283-313, December 2003 [doi>10.1023/A:1025526421410]
• 7: Lars Arge , Octavian Procopiuc , Jeffrey Scott Vitter, Implementing I/O-efficient Data Structures Using TPIE, Proceedings of the 10th Annual European Symposium on Algorithms, p.88-100, September 17-21, 2002
• 8: Lars Arge , Darren Erik Vengroff , Jeffrey Scott Vitter, External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (Extended Abstract), Proceedings of the Third Annual European Symposium on Algorithms, p.295-310, September 25-27, 1995
• 9: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 10: P. T. Bremer, V. Pascucci, H. Edelsbrunner, and B. Hamann. A topological hierarchy for functions on triangulated surfaces. IEEE Trans. Vis. Comput. Graphics, 10:385--396, 2004.
• 11: Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Computational Geometry: Theory and Applications, v.24 n.2, p.75-94, February 2003 [doi>10.1016/S0925-7721(02)00093-7]
• 12: Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
• 13: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 14: R. Dementiev, P. Sanders, D. Schultes, and J. Sibeyn. Engineering an external memory minimum spanning tree algorithm. In Proc. 3rd IFIP Intl. Conf. on Theoretical Computer Science, pages 195--208, 2004.
• 15: Herbert Edelsbrunner , John Harer , Afra Zomorodian, Hierarchical morse complexes for piecewise linear 2-manifolds, Proceedings of the seventeenth annual symposium on Computational geometry, p.70-79, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378626]
• 16: H. Edelsbrunner , D. Letscher , A. Zomorodian, Topological persistence and simplification, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.454, November 12-14, 2000
• 17: Environmental Systems Research Inc. ARC/INFO Professional GIS, 1997. Version 7.1.2.
• 18: F. W. Fredman and D. E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In Proc. 31st IEEE Sympos. Found. Comput. Sci. pages 718--725, 1990.
• 19: M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
• 20: H. Gabow and R. Tarjan. A linear time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci., 30:209--221, 1985.
• 21: Benrard A. Galler , Michael J. Fisher, An improved equivalence algorithm, Communications of the ACM, v.7 n.5, p.301-303, May 1964 [doi>10.1145/364099.364331]
• 22: M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In Proc. 34th IEEE Sympos. Found. Comput. Sci., pages 714--723, 1993.
• 23: GRASS Development Team. GRASS GIS homepage. http://www.baylor.edu/grass/.
• 24: S. Jenson and J. Domingue. Extracting topographic structure from digital elevation data for geographic information system analysis. Photogrammetric Engineering and Remote Sensing, 54(11):1593--1600, 1988.
• 25: B. M. E. Moret and H. D. Shapiro. An empirical analysis of algorithms for constructing a minimum spanning tree. In Proc. Workshop Algorithms Data Struct., pages 400--411, 1991.
• 26: North Carolina Flood Mapping Program. http://www.ncfloodmaps.com.
• 27: J. F. O'Callaghan and D. M. Mark. The extraction of drainage networks from digital elevation data. Computer Vision, Graphics and Image Processing, 28, 1984.
• 28: Raimund Seidel , Micha Sharir, Top-Down Analysis of Path Compression, SIAM Journal on Computing, v.34 n.3, p.515-525, 2005 [doi>10.1137/S0097539703439088]
• 29: Sergey P. Tarasov , Michael N. Vyalyi, Construction of contour trees in 3D in O(n log n) steps, Proceedings of the fourteenth annual symposium on Computational geometry, p.68-75, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276892]
• 30: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 31: R. E. Tarjan. A class of algorithms that require nonlinear time to maintain disjoint sets. J. Comput. and Sys. Sci., 18:110--127, 1979.
• 32: Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]
• 33: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 34: Marc van Kreveld , René van Oostrum , Chandrajit Bajaj , Valerio Pascucci , Dan Schikore, Contour trees and small seed sets for isosurface traversal, Proceedings of the thirteenth annual symposium on Computational geometry, p.212-220, June 04-06, 1997, Nice, France [doi>10.1145/262839.269238]
• 35: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 36: Afra J. Zomorodian , M. J. Ablowitz , S. H. Davis , E. J. Hinch , A. Iserles , J. Ockendon , P. J. Olver, Topology for Computing (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2005

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Experimentation

Keywords:
I/O-efficient, algorithms, contour trees, terrain analysis, union-find