Storage Management for Evolving Databases

The problem of maintaining data that arrives continuously over time is increasingly prevalent in databases and digital libraries. Building on a model for sliding window indices developed by N. Shivakumar and H. Garcia-Molina (1997), we devise efficient algorithms for some of the central problems that arise. We also show connections between the problems in this model and some fundamental problems in optimization and graph theory.

Authors

• Jon M. Kleinberg
• Rajeev Motwani 0001
• Prabhakar Raghavan
• Suresh Venkatasubramanian

Keywords

• Databases
• Costs
• Computer science
• Software libraries
• Computer network management
• Graph theory
• Polynomials
• Computer networks
• Hardware
• Disk drives
• Storage Management
• Digital Library
• Maximum Size
• Directed Graph
• Pathfinding
• Algorithm For Problem
• Polynomial-time Algorithm
• Lexicographic
• Linear Graph
• Unit Interval
• Binary Search
• Online Algorithm
• Total Problems
• Weight Assignment
• Optimal Assignment
• Size Of Items
• Planar Graphs
• Interesting Open Question
• Active Compartments
• Loading Problem