Data Deduplication For Redundant Graph Structures Files
summary
Investigates deduplication vs retrieval fragmentation by modeling files as self-avoiding walks on a graph and measuring worst-case chunk-read expansion. Proves the placement problem is NP‑hard (reduces to graph bandwidth), derives simple bounds (cycle bandwidth = 2) and gives a folding/zigzag algorithm for sparse Hamiltonian‑path graphs with an upper bound of about 9k/5 (~1.8) on expansion. Introduces recursive redundancy constructions inspired by Coffey–Klimesh that provably achieve bandwidth reduction (e.g., one extra copy linearizes a cycle), and reports these constructions as effective on the proposed graph models.
AI-written summary · about
chapters (9)
- 0:00Introduction and context
- 1:18Data deduplication basics
- 2:22The fragmentation problem
- 6:07Retrieval and storage trade-offs
- 14:41Modeling files with graphs
- 19:14Mathematical analysis of layout
- 36:17Role of redundancy
- 45:43Conclusion and future research
- 48:10Q&A and closing remarks
related talks
12mThe Dilemma between Deduplication and Locality: Can Both be Achieved?
24mEfficient Algorithms for Dynamic Bidirected Dyck-Reachability
31mIndexing the Extended Dyck-CFL Reachability for Context-Sensitive Program Analysis
13mThe what, The from, and The to: The Migration Games in Deduplicated Systems
05mExploring Data Deduplication in LSM Tree-based Key-Value Stores (Work-in-Progress Report)
20mGraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System...
16mControlling Memory Footprint of Stateful Streaming Graph Processing
09mEfficient Large Graph Processing with Chunk-Based Graph Representation Model