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
[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
- Vasilis Samoladas, Daniel P. Miranker:
A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries.
PODS 1998: 44-51
- 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