\documentclass[11pt]{article}

\newcommand{\bptree}{B\textsuperscript{+}-tree}
\newcommand{\bptrees}{B\textsuperscript{+}-trees}
\newcommand{\PersiFS}{PersiFS}
\newcommand{\PersiFSone}{\PersiFS$_1$}
\newcommand{\PersiFStwo}{\PersiFS$_2$}

\begin{document}

\title{Structures for Efficient File~System-Scale Partial~Persistence}
\author{Dan R. K. Ports and Austin
  T. Clements\\\texttt{\{drkp,amdragon\}@mit.edu}}
\date{May 12, 2005}
\maketitle

A \emph{persistent file system} stores every previous state of each
file, allowing convenient access to the full state of the file system
as it appeared at any point in the past. Achieving this convenient
feature presents a challenging data structural problem because the
amount of data involved is so large: it must use as little space as
possible, and provide efficient operations for modifying the current
state and accessing both current and past states. We formalize
persistent file systems as a problem in data structures, and analyze
it in the context of the external memory model. We begin by
considering the design of our initial solution to this problem from
the \PersiFSone\ file system, which is based on a log of metadata
changes and an indirection layer for storing file data. These
``systems'' data structures support the desired operations, but are
not asymptotically efficient. Applying more advanced data structures,
we refine the design into the next version, \PersiFStwo. We use
\bptrees\ for file content indexing in order to improve the space
efficiency of the system, and we present a novel partially-persistent
\bptree\ design, which can be used to track changes to files with
logarithmic modification and query cost. \PersiFStwo\ has been
implemented as a working file system with these data structures, and
our measurements indicate that the new file system data structure
provides dramatically improved access time for previous revisions with
a small increase in cost for modifications.

\end{document}