Blocking for external graph searching |
| |
Authors: | M H Nodine M T Goodrich J S Vitter |
| |
Affiliation: | (1) Motorola Inc., 5918 W. Courtyard Dr., Suite 200, 78746 Austin, TX, USA;(2) Department of Computer Science, The Johns Hopkins University, 21218 Baltimore, MD, USA;(3) Department of Computer Science, Duke University, 27708-0129 Durham, NC, USA |
| |
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.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. |
| |
Keywords: | External searching Isothetic hypercubes Blocking Input/output complexity Redundancy |
本文献已被 SpringerLink 等数据库收录! |
|