Automatically assigned DDC number:

Manually assigned DDC number: 00574

Number of references: 0

Title: Storage Management for Evolving Databases

Author:

Author:

Author:

Author:

Subject: J. Kleinberg,R. Motwani,P. Raghavan,S. Venkatasubramanian Storage Management for Evolving Databases

Description: 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 in [24], 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. 1 Introduction Large volumes of data arriving continuously over time add new complexity to problems of storage management in databases and digital libraries. Recent work in these communities has resulted in a framework for studying these issues (see e.g. [24] and the references therein). Among other results, we show here that one of the central problems within this model has a non-trivial polynomial-time solution, and we establish connections between some of these problems and a novel generalization of graph coloring that appears to be of interest in its own right. We begin by highlighting three...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-08-20

Pubyear: unknown

Format: ps

Identifier: http://citeseer.ist.psu.edu/140719.html

Source: http://theory.stanford.edu/~rajeev/postscripts/archives.ps.gz

Language: en

Rights: unrestricted