--------------------------------------------------------------------------


		     B O S T O N   U N I V E R S I T Y

			Computer Science Department

			    C O L L O Q U I U M


	   The BT-forest: a Branched and Temporal Access Method


			      Betty Salzberg
			  Northeastern University


		      Wednesday, December 9 at 3:00pm
			 (Coffee served at 2:45pm)

			  Seminar Room / MCS 135


As a design  evolves over  time, new  versions  of the design are  created.
They may share components or only parts of components with earlier versions
or with versions which had branched from a common ancestor.  We combine the
ideas of time-varying data  and branching versions  to produce a new access
method, the BT-Forest.    Following standard notation   from the algorithms
community, we say it  is FULLY PERSISTENT in that  it captures all the past
states of a data structure such  as a B+tree,  and allows any past state to
be updated, creating a new branch.  (A  PARTIALLY PERSISTENT data structure
only  allows updates to the most  recent state.)  Only the fully persistent
B+-tree in the 1991 SIGMOD paper  of Lanka and Mays  and another of our own
methods,  the BT-Tree, also  provide  full persistence  in an access method
supporting data space subsetting (such as  key range searches).  Sharing of
components from different branches can also be easily supported.

The  BT-forest  has  a   simpler  search   algorithm and  better  isolation
properties   than  the  Lanka-Mays tree or    the  BT-Tree.  Its disk space
requirements are  about  the same.   The   BT-forest uses a  new  partially
persistent B-tree, the LV-tree (Linear Version Tree),  as a building block.
In this talk we describe the LV-tree and the BT-Forest.

This  is joint  work with  David  Lomet, Manuel  Barrena,   Linan Jiang and
Richard Rasala.

Host: Prof. Azer Bestavros (best@cs.bu.edu)

---------------------------------------------------------------------------
For colloquium info and directions, see http://www.cs.bu.edu/colloquium
---------------------------------------------------------------------------