Whiteboard: Somebody_s outline	last revised by 127.0.0.1 on Aug 17, 2005 3:44 am

 -Intro
    -progressive complexification, starting with simple trees
    -overview
        1:  simple balanced trees
        2:  add ability to edit contents: store relative offsets
        3:  re-use relative coordinates: retain edit history
        4:  doubly-linked trees: allow navigation to the roots
        5:  connect internal nodes to navigation info ("canopy"
        6:  another canopy for persistent detectors
        7:  2 things put off handling non-text, and balancing trees
        8:  coordinate spaces
        9:  performance claims
 -Quick access to lots of data
   -use trees
   -nodes split descendants into groups
        & describe coordinates of each branch
   -with balanced trees depth grows as log of number of leaves
        caveat: not addressing balancing now.
        note: splay trees with amortized cost
   -logs grow slowly
   -caveat: linear text for now.  Everything generalizes to
        multi-dimensional multi-media
   -access to text is O(log(n)
   -We explain as if text is characters at leaves.  It's really runs,
        (expanding loafs) which we break up as necessary.  ExpandingLoafs
        also enable infinite spaces 
 -Quick modifications
   -use relative coordinates, re-use parts of the tree
   -DspLoafs
        explain navigation, modification with DspLoafs
   -give examples
     -insert
         add a Dsp near the root, you can create a gap that stays big
         enough as you insert lots of text without having to touch all
         the characters in the document.  Emacs shuffles characters
         every time you insert at a new location.  They leave a large
         gap so they can do a lot of insertion before shuffling again.
     -delete
         add the Dsp, point at a sub-tree and you're done.
     -rearrange
         cut up the sub-trees, insert Dsps.
   -introduce the detailed and aggregate icons
   -editing is O(insert * log(insert) + log(delete) + log(rearrange)).
   -this structure produces the individual red trees in the abstract Ent
         map 
   -When retrieving docs, you follow the red tree leafward, accumulating
        the Dsps on each piece so you can assemble pieces correctly
 -Retain history, allow arbitrary sharing
    -rather than throwing away old state as we make changes, we make a
        new tree that shares the substructure.  show how the relative
        coordinates make this work.
    -use red/orange trees that share to show maintaining previous version
    -reproduce earlier examples, but maintain old structure
    -a root of an OTree represents an edition of a document
 -add upward pointers, find context of content, find sharers of data
    -give mental model of interpenetrating trees 
    -new terminology: north, south, rootward, leafward
    -south pointers are red, north pointers are blue
    -point to roots of OTrees as leafs of HTree
    -root of an HTree is a datum
    -This step introduces the inverted blue triangles in the Ent map
      -"stack" of such trees that share produces the tetrahedral map
    -describe the aggregate view showing trees (as triangles)
        peeling away from one another
    -point out that the sharing is convoluted, and the aggregate view
        works because, as it implies, there is consistently more sharing
        towards the bottom
    -describe detailed picture with inverted chevrons
        separate up-pointing part, down-pointing part 
 -add Canopies, allow navigation in H, do version compare 
    -looking at a reference or quote, want to find original context
    -want to navigate northward to a particular O-Root (known document),
        accumulating Dsps to find location in original of shared data.
    -Describe [abstractly!] how we use the canopies.  Leave why for later
      -explain the trip we want to make in the detailed diagram, then
           point out that there might be many sharers of the data, and we
           can't tell which route northward to take.
      -We could mark a particular OTree in the ent but that's expensive!
      -instead we want to project the tree sideways and only mark its
           shadow.  The shadow is log, while the tree is exponential
      -The hard part is admittedly finding a projection that works

      -canopies are drawn in green, pointers to canopy are brown
      -navigate south according to data coordinates.  No corresponding
           nav info going north.     [could we introduce it?*] 
        -doing it the same way would require storing an enumeration of
             all the docs that contain each datum at the south pole.
             Instead we project the volume of the ent onto the canopies.
             The effect is to store info about equivalence classes.  If
             the equivalence classes are properly designed, it's cheaper
             to navigate the canopy.
    -the sensor canopy finds out "what are all the editions that will
         ever* contain this data?" (and pass some filter)
      -the query is stored persistently so we can get future answers, too
      -recorder hoisting
    -constructing the canopy  [leave this for later, when we have a stable design.]

NOT IN THE CURRENT DOC:
    Balancing   
        splay trees for amortized balancing properties
        As trees get splayed, old pointers into the structure are
            maintained.
        As the volume is splayed, pointers to the canopy continue to
            function.
        Splay maintains balance if the splits are distinctions that make
            half-spaces.  (???)
            Splay trees can get arbitrarily unbalanced, but
            the most used stuff is closest to the root.
            trees re-balance if accesses are more uniform
        multi-dimensional spaces act sort of like K-d trees, except
            there's no imposed order on the axes.  If all your recent
            accesses have been acording to a particular axis, then all
            the relevant info for that axis is near the root.