Skip to main content
SpringerLink
Log in

Blocking for external graph searching

  • Published:
Algorithmica Aims and scope Submit manuscript

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 completed-ary trees andd-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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D. E. Knuth,The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.

    Google Scholar 

  2. A. Aggarawal and J. Park, Notes on Searching in Multidimensional Monotone Arrays,Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, White Plains, NY, October 1988, pp. 497–512.

  3. J. D. Ullman,Principles of Database and Knowledge-Base Systems, Computer Science Press, Rockville, MD, 1988.

    Google Scholar 

  4. A. Borodin, S. Irani, P. Raghavan, and B. Schieber, Competitive Paging with Locality of Reference,Proceedings of the 23rd ACM Symposium on Theory of Computing, New Orleans, LA, May 1991, pp. 249–259.

  5. J. D. Ullman and M. Yannakakis, The Input/Output Complexity of Transitive Closure,Ann. Math. Artificial Intel. 3 (1991), 331–360.

    Article  Google Scholar 

  6. A. L. Rosenberg, Preserving Proximity in Arrays,SIAM J. Comput. 4 (1975), 443–460.

    Article  Google Scholar 

  7. R. A. DeMillo, S. C. Eisenstat, and R. J. Lipton, Preserving Average Proximity in Arrays,Comm. ACM 21 (1978), 228–231.

    Article  Google Scholar 

  8. A. L. Rosenberg, Encoding Data Structures in Trees,J. Assoc. Comput. Mach. 26 (1979), 668–689.

    Google Scholar 

  9. A. L. Rosenberg, Data Encodings and Their Costs,Acta Inform. 9 (1978), 273–292.

    Article  Google Scholar 

  10. A. L. Rosenberg and L. Snyder, Bounds on the Costs of Data Encodings,Math. Systems Theory 12 (1978), 9–39.

    Article  Google Scholar 

  11. F. R. K. Chung, A. L. Rosenberg, and L. Snyder, Perfect Storage Representations for Families of Data Structures,SIAM J. Algebraic Discrete Methods 4 (1983), 548–565.

    Google Scholar 

  12. R. Aleliunas and A. L. Rosenberg, On Embedding Rectangular Grids in Square Grids,IEEE Trans. Comput. 31 (1982), 907–913.

    Google Scholar 

  13. R. J. Lipton, S. C. Eisenstat, and R. A. DeMillo, Space and Time Hierarchies for Classes of Control Structures and Data Structures,J. Assoc. Comput. Mach. 23 (1976), 720–732.

    Google Scholar 

  14. C. Berge,Graphs and Hypergraphs, 2nd edn., North-Holland, Amsterdam, 1976.

    Google Scholar 

  15. G. Reich and P. Widmayer, Beyond Steiner's Problem: A VSLI Oriented Generalization, inGraph-Theoretic Concepts in Computer Science: Proceedings of the 15th International Workshop WG '89 (G. Goos and J. Hartmanis, eds.), Lecture Notes in Computer Science, Vol. 411, Springer-Verlag, Berlin, 1990, pp. 196–210.

    Google Scholar 

  16. E. Ihler, Bounds on the Quality of Approximate Solutions to the Group Steiner Problem, inGraph-Theoretic Concepts in Computer Science, Proceedings of the 16th International Workshop WG '90 (G. Goos and J. Hartmanis, eds.), Lecture Notes in Computer Science, Vol. 484, Springer-Verlag, Berlin, 1991, pp. 109–118.

    Google Scholar 

  17. M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Motorola Inc., 5918 W. Courtyard Dr., Suite 200, 78746, Austin, TX, USA

    M. H. Nodine

  2. Department of Computer Science, The Johns Hopkins University, 21218, Baltimore, MD, USA

    M. T. Goodrich

  3. Department of Computer Science, Duke University, 27708-0129, Durham, NC, USA

    J. S. Vitter

Authors
  1. M. H. Nodine
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. T. Goodrich
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. S. Vitter
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by D. P. Dobkin.

Support was provided in part by an IBM Graduate Fellowship, by NSF Research Grants CCR-9007851 and IRI-9116451, and by Army Research Office Grant DAAL03-91-G-0035.

Support was provided in part by NSF Grants CCR-9003299, CCR-9300079, and IRI-9116843, and by NSF/DARPA Grant CCR-8908092.

Support was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, and by Army Research Office Grant DAAL03-91-G-0035.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Nodine, M.H., Goodrich, M.T. & Vitter, J.S. Blocking for external graph searching. Algorithmica 16, 181–214 (1996). https://doi.org/10.1007/BF01940646

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01940646

Key words

Search

Navigation