BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-96-36
       ENTRY:: June 13, 1996
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Efficient Snapshot Differential Algorithms for Data
               Warehousing
        TYPE:: Technical Note
      AUTHOR:: Garcia-Molina, Hector
      AUTHOR:: Labio, Wilburt Juan
        DATE:: June 1996
       PAGES:: 25
    ABSTRACT:: Detecting and extracting modifications from information
               sources is an integral part of data warehousing. For
               unsophisticated sources, in practice it is often necessary to
               infer modifications by periodically comparing snapshots of
               data from the source. Although this em snapshot differential
               problem is closely related to traditional joins and
               outerjoins, there are significant differences, which lead to
               simple new algorithms. In particular, we present algorithms
               that perform (possibly lossy) compression of records. We also
               present a {\em window} algorithm that works very well if the
               snapshots are not ``very different.'' The algorithms are
               studied via analysis and an implementation of two of them;
               the results illustrate the potential gains achievable with
               the new algorithms.
       NOTES:: [Adminitrivia V1/Prg/19960613]
         END:: STAN//CS-TN-96-36