Blocking for external graph searching

ABSTRACT

In this paper, we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for complete d-ary trees and d-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted.

REFERENCES

• AgP: Alok Aggarwal and James Park, "Notes on Searching in Multidimensional Monotone Arrays," Proceedings of 29#h Annual IEEE Symposium on Foundations of Computer Science (October 1988), 497-512.
• AlR: Romas Aleliunas and Arnold L. Rosenberg, "On Embedding Rectangular Grids in Square Grids," IEEE Transactzons on Computers C- 31 (1982), 907-913.
• Ber: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• BIR: Allan Borodin , Prabhakar Raghavan , Sandy Irani , Baruch Schieber, Competitive paging with locality of reference, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.249-259, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103422]
• CRS: F.R.K. Chung, A. L. Rosenberg, and Lawrence Snyder, "Perfect Storage Representations for Families of Data Structures," SIAM J. Algorithms and Discrete Methods 4(1983), 548- 565.
• DEL: Richard A. DeMillo , Stanley C. Eisenstat , Richard J. Lipton, Preserving average proximity in arrays, Communications of the ACM, v.21 n.3, p.228-231, March 1978 [doi>10.1145/359361.359447]
• GaJ: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Ihl: Edmund Ihler, Bounds on the quality of approximate solutions to the group Steiner problem, Proceedings of the 16th international workshop on Graph-theoretic concepts in computer science, p.109-118, May 1991, Berlin, Germany
• Knu: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• LED: R. J. Lipton , S. C. Eisenstat , R. A. DeMillo, Space and Time Hierarchies for Classes of Control Structures and Data Structures, Journal of the ACM (JACM), v.23 n.4, p.720-732, Oct. 1976 [doi>10.1145/321978.321990]
• ReW: G. Reich , P. Widmayer, Beyond Steiner's problem: a VLSI oriented generalization, Proceedings of the fifteenth international workshop on Graph-theoretic concepts in computer science, p.196-210, March 1990, Castle Rolduc, The Netherlands
• Rosa: Arnold L. Rosenberg, "Preserving Proximity in Arrays," SIAM J. Comput. 4 (1975), 443-460.
• Rosb: Arnold L. Rosenberg, "Data Encodings and Their Costs," Acta Informatica 9(1978), 273- 292.
• Rosc: Arnold L. Rosenberg, Encoding Data Structures in Trees, Journal of the ACM (JACM), v.26 n.4, p.668-689, Oct. 1979 [doi>10.1145/322154.322160]
• RoS: Arnold L. Rosenberg and Lawrence Snyder, "Bounds on the Costs of Data Encodings," Math. Systems Theory 12 (1978), 9-39.
• Ull: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• UlY: Jeffrey D. Ullman and Mihalis Yannakakis, "The Input/Output Complexity of Transitive Closure," Annals of Mathematics and Artificial Intelligence (1991), 331-360.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Verification