Blocking for External Graph Searching (Extended Abstract)
Summary: Disk-blocking model for external-memory graph search that permits vertex replication to exploit redundancy and optimize block-use. Matching upper/lower bounds for complete d-ary trees and d-dimensional grids and near-regular graphs; isothetic-hypercube blocking yields provable speed-up with small redundancy. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Mark H. Nodine (Motorola)
- 2. Michael T. Goodrich (Johns Hopkins University)
- 3. Jeffrey Scott Vitter (Duke University)
BibTeX Citation
@inproceedings{nodine_pods93,
address = {New York, NY, USA},
series = {{PODS} '93},
title = {{Blocking for External Graph Searching (Extended Abstract)}},
url = {https://dl.acm.org/doi/10.1145/153850.153880},
doi = {10.1145/153850.153880},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Nodine, Mark H. and Goodrich, Michael T. and Vitter, Jeffrey Scott},
year = {1993}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,730 | A Lower Bound Theorem for Indexing Schemes and its Application to Multidimensional Range Queries | 1998 | PODS | 6.5348792e-05 |
| 5,888 | Clustering Techniques for Minimizing External Path Length | 1996 | VLDB | 6.0498293e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,855 | The Input/Output Complexity Of Transitive Closure | 1990 | SIGMOD | 9.606146e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,119 | GConnect: A Connectivity Index for Massive Disk-Resident Graphs | 2009 | VLDB |
| 2 | 8,657 | An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs | 2025 | SIGMOD |
| 3 | 2,135 | Path Caching: A Technique for Optimal External Searching (Extended Abstract) | 1994 | PODS |
| 4 | 11,198 | Constant-time Connectivity Querying in Dynamic Graphs | 2024 | SIGMOD |
| 5 | 5,370 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD |
| 6 | 9,759 | Divide & Conquer: I/O Efficient Depth-First Search | 2015 | SIGMOD |
| 7 | 3,857 | Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach | 2012 | SIGMOD |
| 8 | 3,450 | Keyword Search on External Memory Data Graphs | 2008 | VLDB |
| 9 | 1,529 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS |
| 10 | 1,561 | Efficient Searching with Linear Constraints (Extended Abstract) | 1998 | PODS |