ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Blocking for External Graph Searching.

Mark H. Nodine, Michael T. Goodrich, Jeffrey Scott Vitter: Blocking for External Graph Searching. PODS 1993: 222-232
@inproceedings{DBLP:conf/pods/NodineGV93,
  author    = {Mark H. Nodine and
               Michael T. Goodrich and
               Jeffrey Scott Vitter},
  title     = {Blocking for External Graph Searching},
  booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 25-28, 1993, Washington,
               DC},
  publisher = {ACM Press},
  year      = {1993},
  isbn      = {0-89791-593-3},
  pages     = {222-232},
  ee        = {http://doi.acm.org/10.1145/153850.153880, db/conf/pods/NodineGV93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC. ACM Press 1993, ISBN 0-89791-593-3
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 932 KB]

Journal Edition

Mark H. Nodine, Michael T. Goodrich, Jeffrey Scott Vitter: Blocking for External Graph Searching. Algorithmica 16(2): 181-214(1996) BibTeX

References

[AgP]
Alok Aggarwal, James K. Park: Notes on Searching in Multidimensional Monotone Arrays (Preliminary Version). FOCS 1988: 497-512 BibTeX
[AlR]
...
[Ber]
...
[BIR]
Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber: Competitive Paging with Locality of Reference (Preliminary Version). STOC 1991: 249-259 BibTeX
[CRS]
...
[DEL]
Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton: Preserving Average Proximity in Arrays. Commun. ACM 21(3): 218-231(1978) BibTeX
[GaJ]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[Ihl]
...
[Knu]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[LED]
Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo: Space and Time Hierarchies for Classes of Control Structures and Data Structures. J. ACM 23(4): 720-732(1976) BibTeX
[ReW]
...
[Rosa]
Arnold L. Rosenberg: Preserving Proximity in Arrays. SIAM J. Comput. 4(4): 443-460(1975) BibTeX
[Rosb]
Arnold L. Rosenberg: Data Encodings and Their Costs. Acta Inf. 9: 273-292(1978) BibTeX
[Rosc]
Arnold L. Rosenberg: Encoding Data Structures in Trees. J. ACM 26(4): 668-689(1979) BibTeX
[RoS]
Arnold L. Rosenberg, Lawrence Snyder: Bounds on the Costs of Data Encodings. Mathematical Systems Theory 12: 9-39(1978) BibTeX
[Ull]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[UlY]
...

Referenced by

  1. Vasilis Samoladas, Daniel P. Miranker: A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries. PODS 1998: 44-51
  2. Ajit A. Diwan, Sanjeeva Rane, S. Seshadri, S. Sudarshan: Clustering Techniques for Minimizing External Path Length. VLDB 1996: 342-353
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:08 2009