Blocking for external graph searching

DOI10.1007/BF01940646zbMath0851.68022OpenAlexW2085998092MaRDI QIDQ1920428

Mark H. Nodine, Jeffrey Scott Vitter, Michael T. Goodrich

Publication date: 12 August 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01940646

zbMATH Keywords

redundancyisothetic hypercubes

Mathematics Subject Classification ID

Searching and sorting (68P10) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep ⋮ Topology B-trees and their applications ⋮ Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep ⋮ An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications ⋮ Paging more than one page ⋮ Succinct and I/O efficient data structures for traversal in trees ⋮ Optimal cache-oblivious mesh layouts ⋮ I/O-efficient path traversal in succinct planar graphs ⋮ Data replication in static tree structures ⋮ An external memory data structure for shortest path queries ⋮ Worst-case optimal tree layout in external memory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data encodings and their costs
• The input/output complexity of transitive closure
• Competitive paging with locality of reference
• Perfect Storage Representations for Families of Data Structures
• Encoding Data Structures in Trees
• On Embedding Rectangular Grids in Square Grids
• Preserving Proximity in Arrays
• Space and Time Hierarchies for Classes of Control Structures and Data Structures
• Preserving average proximity in arrays
• Bounds on the costs of data encodings