`Case 5:18—cv-05198—BLF Document 14-2 Filed 10/04/18 Page 1 of 63
`
`EXHIBIT 2
`EXHIBIT 2
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 2 of 63
`
`ilililillllilil lllil lilillill lllll lllll lllll lllll llll lllll lll llll llll
`us00692844282
`1ro; Patcnt No.: US 6,928,442 82
`(+s) Date of Patent: Aug. 9,2005
`
`FOREIGN PAIENT DOCUMENTS
`
`EP
`
`0592045
`
`411994
`
`OTHER PUBLICATIONS
`
`Gwertzman, James, et al. "The Case for Geographical Push-
`Caching." Techlical Reporl I{U TR 34-94 (excerpt), Har-
`vard University, DAS, Cambridge, MA 02138, 1994,2 pgs.
`Grigni, Michelangelo, et a1. "Tight Bounds on Minimum
`Broadcasts Networks." SIAM Journal of Discrete Math-
`emalics, r'o1. 4, No. 2, May 1991, pp.207-222.
`Devine, Robert. "Design and Implementation of DDH: A
`Distributed Dynamic Hashing Algorithm." In Proceedings
`of 4th Inlemational Conference on Foundations of Data
`Organizations and Algorithms, 1993, pp. 101-114.
`Deering, Stephen, et al. "Mullicast Rouling in Datagram
`Internefworks and Extendecl LANs." ACM Transactions on
`Computcr Systems, vol. 8, No. 2,May 1990, pp. 85-110.
`
`(Continued)
`
`ABSTRACT
`
`Prinary Examiner-1tke S Wossum
`Assistant Examiner--Xhanh Pham
`(74) Anorney, Agert, or Ftnn--Javidson Berquist Jackson
`& Gowdey, l.l,P
`(s7)
`Data files are distributed across a plurality of computers. The
`computers may form a network such as a conlent delivery
`network (CDN) or a peer-to-peer network. The network may
`operate as a TCP/IP network such as the Internet. Data files
`may represent may rcpresenl digital messages, images,
`videos or audio signals. For content--{ala items or liles in
`the systcm-a namc is obtained (or dctcrmincd), wherc lhc
`name is basecl, at least in part, on a given funclion of the data
`in a data item or fi1e. The given function may be a message
`digest or hash function, and it may be MD4, MD5, and SHA.
`A cony of a requested fi1e is only provided to licensed (or
`authorized) parties. The system may check one or more
`computers for unauthorized or unlicensed contenl. Content
`is served based on a measure of availability of servers.
`
`56 Claims, 31 Drawing Sheets
`
`('z) United States Patent
`Farber et al.
`
`(s4) ENFORCEMENT AND POLICING OF
`I,ICENSED CONTENT USING
`CONTENT-BASED IDENTIFIERS
`(75) lnventors: David A. Farber, Ojai, (lA (US);
`Ronnld l). Lachman, Norlhbrook, IL
`(US)
`(73) Assignees: Kinetech, Inc., Northbrook, IL (US);
`Savviq Inc,,'lirwn & (buntry, Mo
`(US)
`( - ) Notice: Subject to any disclaimer, the term ofthis
`patent is extended or adiusted uncler 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 091987,723
`(22) Filed: Nov. 15' 2001
`(65)
`Prior Publicntion l)atrr
`IJS 200210052&34 Al May 2,2002
`
`Related U.S. ApPlication Data
`
`(63) Continuation of application No. 091283,160. filed on Apr. 1,
`1999, now Pat. No. 6.41.5.280, which is a division of
`application No. 08i960,079, filed on Oct. 24, 1991. now Pat'
`No. -s.qlS,Zql, which is a continuation of application No.
`Ct81425,160, filcd on Apr. 11. 1995, now abandoned.
`Int. Cl.7
`G06F 17130
`7 07 I lO; 7 07 I 3; 7 O7 I I0I;
`u.s. ct.
`7 07 l2o0; 7 09 203 ; 7 09 l2t9 ; 709 1229
`(58) Field of Search
`70713,6,9, rO,
`707 l lC1, 2OO: 709 t203. 2 19. 229
`
`(s1)
`(s2)
`
`(s6)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6/1972 Evangelisti
`7/1980 Mitchell
`9/1981 Cichelli
`3,/1983 Rivest
`9/1983 Rivest
`10/1983 Neches
`
`(Continued)
`
`A AA A
`
`3,668,647
`4,215,402
`4,290,705
`4,376,299
`4,405,829
`4.412,28s
`
`","I
`
`DAfA I|EM
`
`COMPUTE''D FUNCTION ON
`DAIA TTEM
`
`LENGTH MODULO 12 OF
`DATA IIEM
`
`It
`
`EXHIBIT 2 . 1
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 3 of 63
`
`us 6,928,442 B2
`Page 2
`
`Rabin, Michael. "Eticient Dispersal of Intbrmation tbr
`Sccurity, Load Balancing, and Fault Tolcrancc." Journal of
`the ACM, vol. 36, No. 2, Apr. 1989, pp. 335-348.
`Ravi, R., "Rapid Rumor Ramificalion: Approximating the
`Minimum Broadcasl -lime." In Proceedings ol the 35th
`IEEE Symposium on Foundalion of Computer Science, Nor'.
`1994, pp. 202-2t3.
`Schmidt, Jeanette, et al. "Chernoff-HoeftUing Bouncls for
`Applications with Limited Independence." In Proceedings
`of thc 4th ACS-SIAM Symposium on Discrctc Algorithms,
`1993, pp. 331-340.
`Tarjan, Robert Endre, el al. "Storing a Sparse Table."
`Communications of thc ACM, vol. 22, No. 11, Nov. 1979,
`pp.606-611.
`Wegman, Mark, et a'I. "New Hash Functions and'lheir Use
`in Authentication and Set Equality." Journal of Computer
`and System Sciences vol.22, Jun. 1.981, pp.265-279.
`Vitter, .leffrey Scotl, et al. "Optimal Preletching via l)ata
`Compression." In Proceedings of32nd IEEE Symposium on
`Foundations ofComputer Science, Nov. 1991, pp. 121-130.
`Fredman, Michael, et al. "Storing a Sparse 'lhble with 0(1)
`Worsl Case Access Time." Journal of the Association for
`Computing Machincry, vol. 31, No. 3, Ju1. 1984, pp.
`538-544.
`Yao, Andrew Chi-Chih. "Should Tablcs bc Sorted?" Journa1
`of the Association for Computing Machinery, vol. 28, No. 3,
`.Iul. 1981, pp. 61-5-628.
`Flo;,d, Sally, et al. "A reliable Multicast Framework for
`Light-Weighl Sessions and Application Level Framing." In
`Proceeding of ACM SIGCOMM '95,pp.342-356.
`Feeley, Michael, el a1. "lmplementing G1oba1 Memory Man-
`agement in a Workstalion (lluster." In Proceedings of thc
`15th ACM Symposium on Operating Systems Principles,
`1995, pp. 20I-212.
`Carter, J. Lawrence, et al. "Universal Classes of Hash
`Funclions." Journal of Computer and System Sciences, vo1.
`18, No. 2, Apr.1979,pp.143-1'54.
`Patent Abstracts of Japan, "Electronic Mail Multiplexing
`System and Communication Control Method in The Sys-
`tem." Jun. 30, 1993, JP 05162529.
`Kim et a1., "Experiences wilh Tripwire: Using Integrity
`Chcckcrs For Intrusion Dclection", COAST Labs. Dept. of
`Computer Sciences Purdue University, Feb. 22, 1995, pp.
`T_I2.
`Kim et a1., "Thc Design and Implcmcntation of Tripwire: A
`file System Integrity Checker", COAST Labs. Dept. of
`Computer Sciences Purdue University, Nov. 79, 1993, pp.
`1-21.
`Bert dem Boer et a1., Collisions for the compression function
`of MDr, pp.292-304.
`Sakti Pramanik et a1., Multi-Directory Hasing, 1993, Info.
`Sys., vol, 18, No. 1, pp.63-:74.
`Muriidhar Koushik, Dynamic I{ashing with Distributed
`Overflow Space: A File Organization with Good Insertion
`Performance, 1993, Info. Sys., vol. 18, No. 5, pp.299-377.
`Witold Litrvin et a1., LII'-Linear Ilashing for Disnibuted
`Files, HP Labs Tech. Report No. I{PL-93-21, Jun. 1993, pp.
`t-22.
`Yuliang Zheng et al,, HAVAL-A One-Way Hashing Algo-
`rithm with Variable lrngth of Oulput (Extended Abstract),
`pp. tt3-105.
`Chris Charnes and Josef Pieprzky, Linear Nonequivalence
`versus Nonlinearity, Pieprzky, pp. 156-164.
`EXHIBIT 2 - 2
`
`I]-S- PAIENT DOCUMENTS
`
`1-t/1983
`4/1984
`8/1.984
`12/'1984
`2/1986
`j1 1986
`21"1987
`6/1987
`9/1987
`211988
`9/1988
`121.989
`121 1989
`51990
`5,11990
`1t/1990
`61991.
`911991.
`91991.
`10,i 1sq1
`t2lr9q1
`'tll992
`'711992
`9 1992
`l/t993
`4L993
`5//199-3
`1/1994
`211994
`4/1994
`4/1994
`811994
`8/r994
`10/1994
`1/t995
`4/1995
`9/1995
`70/1995
`7/1996
`12/1996
`6/199'7
`6/ 1997
`7/1998
`9/1998
`9/ 1998
`11/1998
`5t1999
`t2/1999
`10/2000
`
`Sumnrer,.Ir.
`Fletcher
`Benhase
`Dixon
`Emry,.lr.
`Matick
`Meaden
`Gmner
`Rivest
`Kronstadt
`Zamora
`Holloway
`Barnes
`Holloway
`Clrurnr et al. ...,,,,........... 7(17/1
`Burke
`Cho
`Marca
`Dyson
`Colwcll
`Bendert
`Kobayashi
`Tirfing
`Pogue" .lr.
`Colwell
`Granrliclr et al. ..,........... 7O7/2
`Vollcrt
`Howell
`Nenes
`Raiani
`Hanrilton
`Pitkin et al. ..............,. 7L\91226
`Moore
`Megory-Cohen
`Cannon
`Konrad
`Nelson et aI. .............. 7O7l2O5
`Burnett
`Neimat et al. ................ 7O7 I 1O
`Burnett
`Stefik et al. .................. 705/54
`Ilamilton eI al. ........... 7A9l3O3
`Haber er. al. ................ 713/177
`Balick et al. ............... 7O9l2O2
`Ngnyen ......................... 707/1
`Herz et al. .................. 345/810
`Gudmundson et al.
`Burnett et al. ......... 3951200.49
`Jones et al. ................. 709/330
`
`70'7/2
`
`A
`
`A AAA AA AA AA A A A
`
`AA AAAAA A AA AA
`
`4.414.624
`4,441,155
`4,464,113
`4"490,"182
`4,57t,700
`4,57'7,293
`4,642,793
`4,675.81.0
`4,691.,299
`4,7L5,945
`4,773,039
`4,887,235
`4,888,681
`4,922,414
`4,922,417
`4,972.367
`5,OL5,421
`5.050,074
`5,050,21.2
`5,057,837
`5.077,654
`5,129,081
`5.129.082
`5"144,667
`5,r79,680
`5.202,982
`5.208,858
`s.276.90t
`5,28'7,499
`5,301,286
`5,301.-316
`5.341.,4'77
`5,343.527
`5.357.623
`5,384,565
`5.404,508
`5,452.447
`5.459.860
`5,542,O87
`5,581,7-58
`5,638,443
`5,640.564
`5,781,629
`5,802,29r
`5,a09,494
`5,835,087
`5,907,104
`6,006,0r8
`6,t34,603
`
`OTHER PUBLICATIONS
`
`Cormen, Thomas II., et al. Infioductiort toAlgori.thnts, The
`MIT Press, Cambridge, Massachusetts, 1994, pp. 219-243,
`99r-993.
`Naor, Moni, et al. "The Load, Capacitv and Availability of
`Quorum Systems." In Proceedings of the 35th IEEE Sym-
`posium on Foundations of Computer Science, Nov. 1994,
`pp.214-225.
`Nisan, Noam. "Pseudorandon Generalors for Space-
`Boundcd Computalion." In Proceedings of the 'lwenly-
`Second Annual ACM Symposium on Theory of Computing,
`May 1990, pp.204-212.
`PaLmer, Mark, et al. "Fido: A Cache that Learns to Fctch."
`In Proceedings of the 17th International Conference on Very
`Large Data Bases, Sep. 1991, pp. 255-264.
`Peleg, David, et al. "The Availability of Quorum S1'stems."
`Information and Computation 123, 1995, 270_223.
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 4 of 63
`
`us 6,928,442 B2
`Page 3
`
`Witold Lilwin et al., Linear Hashing lbr Distrilruted Files,
`ACM SIGMOD, May 1993, pp.327-336.
`Ming-Ling l-o et ai., On Oplimal Processor Allocation 1o
`Support Pipelined Hash Joins, ACM SIGMOD, pp. 69-:78,
`May 1993.
`'l'homas A. Berson, I)ifferential Oryptanalysis Mo<l 232 with
`Applications to MD5, pp. 69-€1.
`William Pcrrizo cl a1., Dislributcd Join Proccssing Pcrfor-
`mance Evaluation, TWenty-Seventh Hawaii International
`Conference on System Sciences, vol. II, pp. 236-244.
`Viiay Kumar, A Concurrency Control Mechanism Based on
`Extendible Hashing for Main Memory Database Systems,
`ACM, vol. 3, 1989, pp. 109-113.
`Birgit Pfitzman, Sorting Out Signature Scliemes, Nov. 1993,
`1" (lonf. Oomputer & (-bmm. Securily '93, p. 74-t15.
`Zhiyu Tian et a1., A New Hashing Function: Statistical
`Behaviour and Algorithm, pp. 3-13.
`G. L. Friedman, Digital Camera with Apparatu for Authen-
`tication of Images Produced from an Image File, NASA
`Case No. NPO-19108-1-CU, U.S. Appl. No. 08/159,980,
`flled Nov. 24,7993.
`H. Goodman, Ada, Object-Oriented Techniques, and Con-
`currency in Teaching Data Structures and File Managemenl
`Report Documentation p. AD-A27-5 385 - 9H4277.
`Advanccs in Cryptology-Eurocrypt'93, Workshop on the
`Theory and Applicalion of Cryptographic Techniques
`Lofthus, Norway, May 23J7,1993 Proceedings.
`Proceeclings of the 1993 ACM SIGMOD Internalional Con-
`ference on Managemenl of Data, vo1. 22, Issue 2, J:un. L993.
`
`Advances in Cryptology AUSCRYPT '92-Workshop on
`the Thcory and Applicalion of Cryptographic Tcchniqucs
`Gold Coast, Queensland, Australia, Dec. 13-16, 1992 Pro-
`ceedings.
`Peter Deutsch (pelerd@bunyip.com), "Re: MD5 and LiFNs
`(was: Misc Ctrmments)", www.acl.lanl.gov/URl/archive/
`uri-94q2.messages/0106.html, Apr. 26, 1"994.
`Alexander Dupuy (dupuy@smans.com), "RE: MD5 and
`LIFNs (was: M isc f--om ments)", www. acl. la n l. goviURl/ar-
`chiv e lur i-94q2.messages/01 13.html, Apr. 26, I99 4.
`Alexander Dupuy (dupuy@smarts.com), "MD5 and LIFNs
`(was: Misc Cornments)", u'ww.acl.lanl.goviURl/archive/
`rrri 94q2.messagesi008l.htm1, Apr. 17, 1994.
`Albert Langer (cmf851 @anu.oz.au), http:/groups.google-
`.com/groups?se1m=
`199 | Aug7 .225159.7 86%4tlnewshost.anu.eclu. au&oe=
`UTF-8&output=gp1ain, Aug. 7, 1991.
`Clifford Lynch (Ca1ur@uccmvsa.bitnet), "ietf url/uri over-
`view draft paper (long)", www.acl.lanl.gov/URl/archive/
`uri-93q1.messages/0O15.h1m1, Mar. 25, 1,993.
`K. Sollins and L. Masinter, "Funclional Requirements for
`Uniform Resource Names", wwrv.w3.org/Addressing/
`rt'c1737.txt, Dec. 1994, pp. 1-7.
`W3C:ID, HTTP: A protocol for networked information,
`"Basic HTTP as definecl in 1992", www.w3.org,{Protocols,/
`HTTP2.htm1, 1992.
`European Search Report issued Dec. 23,2004.
`+ citecl lry examiner
`
`EXHIBIT 2 - 3
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 5 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 1 of 31
`
`us 6,928,442 B2
`
`(o
`C'
`IF
`
`(\Io
`
`&oooluoouA
`
`tro
`ru(Jouo.
`
`Qa
`
`h
`
`olol
`-l
`
`EXHIBIT 2 - 4
`
`tro
`v,
`@luo
`oe.
`
`O.
`
`uo.
`
`hq
`IrIo
`,
`o.
`
`oE
`
`$lo
`
`No
`
`I I I
`
`uooU'ulood
`
`A.
`
`^o
`= a(9
`-LL
`
`ol()
`
`to
`
`HH
`
`I t I
`
`rto Huc>
`PH
`Q
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 6 of 63
`
`LJ,S. Patent
`
`Aug. 9,2005 Sheet 2 of 3l
`
`us 6,928,442 82
`
`-t
`
`I I I
`
`__J
`
`EXHIBIT 2 . 5
`
`$t
`
`Ed
`
`E3
`-Al
`
`$d
`
`+Cl
`r(l<faD
`
`Eo
`ll
`E
`
`Et
`
`o
`
`SH
`
`atNILrl-
`
`@l-Sir
`
`Ol
`9, q,
`
`(O r-
`(v)'r
`
`EU
`
`r---
`
`I
`
`No
`
`!l
`
`FF
`
`Hu
`FE
`
`@
`
`coo o-o
`
`-cl
`=(9
`tL
`
`ct)
`
`to(t,
`utood
`
`o.
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 7 of 63
`
`fJ.S. Patent
`
`Aug. 9,2005 sheet 3 of 31
`
`us 6,9280442 82
`
`Fz
`]U
`=(9
`ulo
`
`NNF
`
`l\{N
`
`F
`
`N$l
`F
`
`Fz
`UJE(9
`llla
`
`UI
`
`Fz
`Eo
`ul
`U'
`
`5lr
`
`t I I
`
`5I
`
`L
`
`tilJtl.
`
`oN
`
`oN
`
`oN
`
`F
`
`floF(,
`
`UJd
`o
`
`t a a
`
`toFolu
`
`g,
`o
`
`toFo
`tltd
`o
`
`c)
`
`FF
`
`CO
`
`FF
`
`GO
`
`zIo
`
`UJ&
`
`zo(t
`
`IJJtr
`
`FF
`
`F,F
`
`zg
`oultr
`
`zo
`6ul
`
`tr,
`
`t\
`=
`
`FF
`
`(o
`
`FF
`
`=u{H
`=arL>o
`
`C\J
`a(9
`tr
`
`EXHIBIT 2 - 6
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 8 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 4 of 31
`
`us 6,928,442 B2
`
`FIG.3
`ion ID
`Pathnane
`Drue
`
`access
`Last nodificatlon
`
`rile IP
`Tiue
`Tirne of
`Safe f
`LoCk f
`Size
`Obtner
`
`FIG.4
`llrue Name
`File ID
`
`Source IDs
`
`FLle ID
`
`ssors
`
`Use count
`Time of last access
`
`delete count
`
`lon
`
`Reqion ID
`file
`thna:ne
`status
`ssor s
`ication count
`
`l{irror
`I'tirror
`POI
`FIG.5
`
`t38-
`
`r40
`
`t4z
`
`EXHIBIT 2 - 7
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 9 of 63
`
`I-J.S. Patent
`
`Aug. 9,2005 Sheet 5 of 3L
`
`us 6,928,442 82
`
`or
`
`O
`
`@g
`
`(o
`$
`
`$<
`
`l'
`
`c,
`q,
`l0
`tr
`
`on
`
`.r{
`F{
`
`oe.
`
`U o t
`
`{
`El
`
`oF.
`
`tl
`
`o,t{
`
`H
`
`i$c
`
`o T
`
`]ooo +
`
`r
`
`k+
`
`Ja
`o
`l{
`
`oo
`
`{J
`dtrtt
`
`oFt
`
`lta
`0)ah
`H
`
`oF.
`
`dc
`+)
`
`dA
`
`aAd
`
`tJo
`
`oFF
`
`aH
`tl
`lo
`
`o0
`
`oool
`
`rA
`
`oc
`
`l.I
`
`C{
`
`oHr
`
`dn
`r{
`fit
`tr..1
`U,
`T{
`t{o
`
`ao
`
`{J
`ft
`
`oo ouh,oo
`
`rJ
`
`dr
`
`t
`.ac
`F{
`T{6
`
`dout
`
`rdoo
`
`t!
`J,
`br{
`ti
`o(,
`
`!aoo
`
`o B+
`
`J out
`
`{7oo
`
`6H ot,
`
`{aoI
`
`T
`
`O)
`(9
`It
`
`O(
`
`9
`tr
`
`t*-
`(9
`tr
`
`(o
`(9
`I.t-
`
`EXHIBIT 2 - 8
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 10 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 6 of 31
`
`us 6,928,442 82
`
`FlG. lO(o)
`
`t
`
`t
`
`EXHIBIT 2 . 9
`
`SIM
`DATA ITEM
`
`,
`
`I
`12
`COMPUTE MD FUNCTION ON
`DATA ITEM
`
`l
`
`tI I I I I II Il II IIII IItIII III
`
`I
`t
`I
`
`s214
`APPEND LENGTH MODULO 32 OF
`DATA ]TEM
`
`TRUE
`
`I
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 11 of 63
`
`LJ.S. Patent
`
`Aug. 9, 2005 Sheet 7 of 31
`
`us 6,928,442 82
`
`s216
`DATA ITEM
`SIMPLE?
`
`FtG. to(b)
`
`s220
`PARTMON DATA ITEM INTO
`SEGMENTS
`
`t
`
`s218
`I coupurgrRuE
`innr,,ff oF SIMPLE
`. DATA ITEM
`t
`
`ASSIMILATE EACH SEGMENT
`(GoMPUTING trs TRUE NAME)
`
`CREATE INDIRECT BLOCK OF
`SEGMENTTRUE NAMES
`
`ASSIMILATE INDIRECT BLOCK
`(GoMPUTING ITS TRUE NAME)
`
`REPLACE FINAL 32 BITS OF TRUE
`NAMEWITH LENGHT MOD 32 OF DATA
`ITEM
`
`EXHIBIT 2 - IO
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 12 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 8 of 31
`
`us 6,928,442 B2
`
`eI
`
`UJgtr
`sH
`oF
`
`ct)
`
`IU
`
`J
`
`lr
`ulF
`UJJ
`UIo
`
`EXHIBIT 2 - 11
`
`F-(o
`$J
`U)
`
`AEFruZJlutr
`
`H3
`
`(o
`Coc{q)
`
`AE u'
`,=3
`53eH
`985fr
`HHIE
`HhPh
`????
`
`3\.
`
`tFo
`lE
`
`6u
`
`ul lu
`==
`=g.43
`ut uIF=uJdtrlF
`
`(\l
`(rt
`GI
`U)
`
`ru 14
`
`=dzg{
`HE
`E2
`Ul t-
`Hfr
`
`-C
`
`,
`FtL
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 13 of 63
`
`IJ.S. Patent
`
`Aug. 9,2005 Sheet 9 of 31
`
`us 6,928,442 B2
`
`FlG. 12
`
`s238
`FILE
`LOCKED?
`
`yEs
`
`s240
`UPDATE
`DEPENDENCY
`LIST
`
`$END MESSAGE TO
`CACHE SERVER TO
`UPDATE CACHE
`
`COMPRESS
`(rF DESTRED)
`
`s246
`MIRROR
`(rF DESTRED)
`
`EXHIBIT 2.12
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 14 of 63
`
`[I.S. Patent
`
`Aug. 9,2005 Sheet 10 of 31
`
`us 6,928,442 82
`
`FlG. 13
`
`FAIL
`
`s250
`SEARCH FOR
`THE
`PATHI.IAME
`
`rcUND
`
`s252
`LDE INGLUDES
`E NAM
`
`s258
`ASSIMIIATE
`FILE ID
`
`s254
`
`LDE IDENNHES
`DIRECTORY?
`
`s256
`FREEZE
`DIRECTORY
`
`EXHIBIT 2.13
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 15 of 63
`
`LJ.S. Patent
`
`Aug. 9, 2005 Sheet 11 of 31
`
`us 6,928,442 B2
`
`FtG. t4
`
`YES
`
`s268
`DELETE
`TRUE FILE
`
`CONFIRM THAT
`TRUE NAME
`EXISTS LOCALLY
`
`s262
`SEARCH FOR
`PATHNAME IN
`LDE TABLE
`
`s264
`CONFIRM TI{AT
`DIRECTORY
`pilsTs
`
`s266
`
`NAMED FILE
`EXTSTS?
`
`NO
`
`CREATE
`ENTRY IN LDE
`A UPDATE
`
`EXHIBIT 2 - 14
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 16 of 63
`
`fJ.S. Patent
`
`Aug. 9,2005 Sheet 12 of 31
`
`us 6,928,442 B2
`
`(o 3CJl',
`
`5p.L2
`il rHE
`trluftt,
`
`lU r-'
`
`lrJ
`
`ffiH
`EtrHl!
`
`ul
`ruP
`EF3n@
`O lll
`o.0a
`
`-HEEfi
`
`J I
`
`L
`
`HH
`
`3Blu luzd
`
`U)
`ur
`
`zo
`
`FoIp
`
`$l
`$l
`U)
`
`o=
`
`f,2
`Hgtr
`
`ulJ
`TLoz
`
`IL
`
`I I(9
`tr
`
`EXHIBIT 2 .15
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 17 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 13 of 31
`
`us 60928,442 82
`
`^o\,
`(o
`(9
`-IL
`
`i i
`
`+l
`
`I
`
`tU
`a,
`
`=oa.(n
`lltq
`
`l-(/,ZFga
`d=
`
`CN
`ur
`
`aDF
`
`EfiJ<ootr
`
`dl
`
`=utr
`
`UJ
`Ut
`
`=oq.
`Ut
`tu
`a(
`
`l-5--otu
`5F
`
`EXHIBIT 2.16
`
`J I
`
`L
`
`otroa)
`oto
`
`ct,
`UJ(,
`
`o.982lt O
`58frC'HI
`tr
`0.
`
`ETsi
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 18 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 14 of 31
`
`us 6,928,442 B2
`
`utFFAut*f,z- o
`=*,?&,Ya
`uJl-61
`EF;
`ilf
`
`E o
`
`)
`^la
`
`)
`
`Ie
`
`P
`ur=p4
`6eo'r
`
`o
`
`o
`
`HEru
`
`O^t
`
`HEEfl,
`
`*gEgEE
`
`^-cl
`
`\/I a
`C9tr
`
`EXHIBIT 2 - 17
`
`(tzo
`
`Fzl
`
`-o
`IUo
`
`UI
`
`JtrF
`ILo
`tuod
`=oo
`
`Eo&
`IL
`u,&
`UJ]L
`ILo
`ul
`=z
`
`oo
`
`)
`(\Ta
`
`ot
`
`r
`ruOx8
`HH
`E,
`o.
`
`c,
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 19 of 63
`
`[I.S. Patent
`
`Aug. 9,2005 Sheet 15 of 31
`
`us 6,928,442 B2
`
`ulzo
`
`cl
`
`g,oul&Hg@o
`
`(J
`tuo
`
`an
`lu
`
`o=
`
`(\.
`
`eU
`
`J4lr
`
`EXHIBIT 2 .18
`
`out6o
`
`IIJ
`e,
`
`G =o(
`
`,
`
`@o
`
`)
`N
`
`NC
`
`o=
`
`Eo
`
`Lr-
`
`eu
`
`lJ
`ll.
`
`ou
`
`r
`
`!C
`o,
`$l
`Q
`
`U,
`tu
`
`Jt
`
`oz
`
`(\.
`ul
`
`Ez
`
`ul
`GF
`EoIL
`eu.Fz
`
`.^ovtL
`
`ac,
`tr
`
`C\lo)
`Ntt 5IL
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 20 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 16 of 31
`
`us 6,928,442 82
`
`^-cl
`\.,L
`(9
`tr
`
`u,lJ
`lr
`
`tu
`
`)^r =,6Eoili
`Hfig
`f;dst,
`
`luzoo
`
`eU
`
`J&oF.n
`
`U'oF-$ olu
`nHqQ6
`
`v,
`
`luq
`
`oEoe
`
`UJJutr
`Ee(Jh
`A\JY=
`- lllu
`
`C\lodt
`
`Fc
`=ul
`E3
`
`EXHIBIT 2 - 19
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 21 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 17 of 31
`
`us 6,928,442 82
`
`rul
`s Eg
`E Ed<J
`
`=lL
`
`cct
`
`(t)a
`
`UI
`
`!uJqil
`EEF
`
`lll
`oo
`
`Eolr
`JJIL
`
`eU
`
`6t
`(Yt(/)
`
`oI
`
`a(9
`lr-
`
`(\.
`IUJ
`IL
`
`UJ
`
`=ct-
`tl.o
`o.oo
`tu
`E
`
`o(
`
`r?o
`
`(o
`(Y)
`U'
`
`g,
`EIIL
`Fzul
`
`cl
`
`lu3eF
`(Dz
`F6
`=]U
`
`(\.
`
`IUJlr
`
`EH
`o 2a;
`il
`
`EE
`
`uJzoo
`
`EXHIBIT 2 .20
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 22 of 63
`
`I-J.S. Patent
`
`Aug. 9,2005 Sheet L8 of 31
`
`us 6,9280442 82
`
`Xr
`fiIHH
`*E
`
`39 u
`Uf EI ..? O)
`
`fiEHfi
`NA
`* ui=Vr
`9-r o
`(Jtr
`
`A-
`
`o\/q
`a(9il
`
`(o
`
`GI(v)o
`
`F4t3
`=o()
`
`]U
`U'
`,J
`
`(\
`iF
`il
`
`EXHIBIT 2 .2I
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 23 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 19 of 31
`
`us 6,928,442 82
`
`o
`
`*;a-
`
`:)
`
`!!o(
`
`$fr8(/) rrt uJ&Ell.cf
`
`ia
`
`Er
`
`HF:@<Plu<E,Ao
`
`uJ>s F5
`H= ?frE
`FHHfiE6 EB
`
`EXHIBIT 2 .22
`
`^o\/q
`a(9
`tr
`
`Y
`ER
`
`EilzE
`
`-lL
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 24 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 sheet 20 of 31
`
`us 6,928,442 B2
`
`oioE
`
`EEfrF
`
`o!eg<=
`EluoHO-
`
`^-cl
`\./e
`a(D
`tr
`
`ruEt-*<o€
`327,a
`=t,uoHg*E
`
`cl
`
`e.oFoulxoz
`
`UJ
`
`o
`
`El=+utFFHi5tEIJ
`
`aa
`
`FUJZN
`;ggg
`UIOF
`
`EXHIBIT 2 .23
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 25 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 21 of 3l
`
`us 6,928,442 82
`
`u
`
`co ops s5a fruL&
`
`6
`
`ulEo
`E
`
`-l
`EfiFE16tEfi
`oE-
`Ir- O
`
`ag
`&Fz
`
`lrJ
`
`UJEo
`=oz
`
`*
`
`llJ
`
`ro38g
`
`ruJ
`
`s EgEuil<dElL
`
`oN
`a(9
`tr
`
`jtu
`=E
`(r ll.<
`fr HF
`luJ <u, o-o
`
`9ruI=
`$ tfi
`Yd3]-J
`
`EXHIBIT 2 - 24
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 26 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 22 of 3l
`
`us 6,928,442 82
`
`WA]T FOR
`FREEZE LOCK
`TO TURN OFF
`
`s356
`FIND TFR
`ENTRY
`
`FlG.2l
`
`s358
`DECREMENT
`REFERENCE
`COUNT
`
`s360
`
`REFERENGE COUNT IS
`ZERO & NO DEPENDENT
`SYSTEMS IN TFR?
`
`YES
`
`s362
`DELETE
`TRUE FILE
`
`s364
`
`REMOVE FILE ID
`AND COMPRESSED
`FILE ID
`
`EXHIBIT 2 .25
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 27 of 63
`
`[I.S. Patent
`
`Aug. 9,2005 Sheet 23 of 3l
`
`us 6,928,442 82
`
`FlG.22
`
`s368
`
`ASSIMII.ATE
`
`NEWTRUE
`FILE
`
`s378
`MODIFY USE
`COUNT OF EACH
`GOMPONENT
`
`RECORD TRUE
`NAME IN AUDIT
`FILE
`
`s365
`GET
`OPERATION
`
`s366
`CREATE OR
`MODIFY?
`
`s376
`
`COPY OR DELETE
`COMPOUND?
`
`s379
`FOR EACH PARENT
`DIRECTORY OR FILE,
`UPDATE USE COUNT,
`LASTACCESS AND
`MODIFY TIMES
`
`EXHIBIT 2 - 26
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 28 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 24 of 3l
`
`us 6,928,442 82
`
`FIG,23
`
`s382
`l/ERIFY
`GROOMING
`LOCK OFF
`
`s384
`SET
`GROOMING
`LOCK
`
`s386
`SET GROOM
`COUNTS
`
`EXHIBIT 2 - 27
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 29 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 25 of 31
`
`us 6,928,442 82
`
`FlG.24
`
`FIND LDE
`RECORD
`
`s390
`FIND TFR
`RECORD
`
`s392
`INCREMENT
`GROOMING
`DELETE COUNT
`
`s394
`ADJUST FILE
`slzEs
`
`EXHIBIT 2 - 28
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 30 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 26 of 31
`
`us 6,928,442 82
`
`FlG. 25
`
`s396
`DELETE
`FILE
`
`s398
`UNLOCK
`GROOMING
`LOGK
`
`EXHIBIT 2 - 29
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 31 of 63
`
`IJ.S. Patent
`
`Aug. 9,2005 Sheet 27 of 31
`
`us 6,9280442 82
`
`(\
`gJ
`tr
`
`oa
`
`!D
`H
`
`EXHIBIT 2 - 30
`
`l.-
`
`Io
`to
`
`@
`
`o*a
`
`ts6=
`=lu
`HB
`o.
`
`--f
`
`Izq
`
`o u
`
`,
`tr,
`
`@.
`
`+
`a)
`
`ut
`
`n frF
`ED'o
`
`aiul :ztro
`
`xFs
`r
`
`Not
`
`U'
`
`$.ooluzt-
`s$
`o
`
`o
`(o
`$l
`a(9
`tr
`
`oo
`3
`
`@F
`cnxul
`BIJ
`IL
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 32 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 28 of 31
`
`us 6,928,442 82
`
`o
`
`,grEs
`
`/-\.o
`\r.,(o
`c\l
`(9
`tr
`
`FOa
`P f g
`d EH(J Li9-
`
`HHE
`
`UJJztr
`5Ee
`E3
`
`o3
`
`t,
`
`tuJ
`g1 lL
`@ F:Ce <o
`
`il Hkotroo
`
`EXHIBIT 2 - 3I
`
`llld
`ILNul62
`
`Eu
`
`J
`
`(\
`o
`5Htr?
`(,
`
`CD
`
`rl'6
`
`Trllth
`sd
`oo
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 33 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 29 of 3l
`
`us 6,928,442 82
`
`^e,vF
`
`CN
`(9
`u-
`
`H5
`c,=
`ieH
`EE,2
`fiur
`
`uZho
`E5
`trH
`
`s.
`
`d,oFo
`ulg
`o
`
`zt
`
`r-o4oz.
`lll o
`6dqfi
`frEJIL
`
`oc
`
`t
`&,o(J
`ul
`tr,
`tu
`3
`
`(a
`
`Nr+a
`
`qU
`
`H- g
`JFtLuE(Dlu
`
`=fr"xd
`HEEo
`
`EXHIBIT 2 .32
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 34 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 Sheet 30 of 31
`
`us 6,928,442 82
`
`i
`rBut
`UTtrd;t
`(Jo
`
`oFg
`>J
`d,E
`E=ulo
`6<
`
`^.cl
`rJ,
`ft''
`AI
`a(9
`tr
`
`oFztoo
`
`EXHIBIT 2.33
`
`ulo
`
`=lrlo:to
`
`uItr
`
`(o
`
`Nta
`
`EH
`od42ruJ
`t4f,Jtv
`ll.F
`
`UJ
`
`ruJ
`l-t!
`o
`I u'l ru
`^ E=r
`
`luzo
`
`gFzoul
`
`tl
`cn
`
`IulJ
`
`tr
`
`ool$
`
`U'
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 35 of 63
`
`LJ.S. Patent
`
`Aug. 9,2005 sheet 31 of 31
`
`us 6,928,442 82
`
`to
`aotcll
`U)
`
`(\.o
`ur
`
`cttrftroIL
`
`tu
`trl
`
`oF
`Fg,
`IrJ3g
`trJtr
`
`$HH
`ze
`
`(\.oz
`=oIL
`
`ctF
`
`$HH
`
`oz
`
`aut
`
`@N
`o(9
`tr
`
`lrj
`o-E
`$ ?t
`f, out
`v'oJ
`JEF
`
`5I
`
`Laulo
`=Jo
`
`o!f\t
`
`U)
`
`(\'o
`luJ
`
`TL
`
`U,H>z
`FO
`frfr"
`
`EXHIBIT 2 - 34
`
`oU
`
`J
`
`U'o
`UId
`o.
`=oo
`
`do
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 36 of 63
`
`us 6,928,442 B2
`
`I
`I,NFORCEMBNT AND POLICING OF
`LICENSBD CONTENT USING CONTBNT-
`BASED IDENTIFIERS
`
`This is a continuation of application Scr. No. 091283,160,
`filed Apr. I, 1999, nou'U.S. Pat. No. 6,415,280, which is a
`division of application Ser. No. 08/960,079, filed Oct. 24,
`1997, now U.S. Pat. No. 5,918,791liled Oc1. 24, 2001 which
`is a continuation of Ser. No. 081425,160, filed Apr. 11, 19S5,
`now abandoned.
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invenlion
`'lhis invention relates to data processing syslems and,
`more particularly, 1o data proccssing systcms whcrcin data
`items are identified by substantially unique identifiers which
`depend on a1i of the dala in lhe data items and only on the
`data in the data items.
`2. Background of the Invention
`Dala processing (DP) systems, compulers, networks of
`computers, or the 1ike, typically offer users and programs
`various ways to identity the clata in the systems.
`Users typically identify data in the data processing system
`by giving the data some form of name. For example, a
`typical operating system (OS) on a computer provides a lile
`system in which data items are named by alphanumeric
`identifiers. Programs typically identify data in the data
`processing systcm using a location or address. For cxamplc,
`a program may identiS, a record in a file or database by using
`a record number which serves to locate lhat record.
`In all but the most primitive operating systems, users and
`programs are able to creale and use collections of named
`data ilems, these colleclions themselves being named by
`identifiers. These named collections can then, themselves,
`tre made part of other named collections. For example, an
`OS may provicle mechanisms to group files (data items) into
`directories (colleclions). These directories can then, them-
`selves be made parl of other directories. A data item may
`thus be idcntificd rclativc to thesc ncstcd dircctorics using a
`sequence of names, or a so-called pathname, which defines
`a path through the directories to a particular data item (file
`or directory).
`As another example, a dalabase management system may
`group data records (data items) into tables and then group
`these tables into database files (collections). The complete
`addrcss of any data rccord can thcn bc specifled using the
`database flle name, the table name, and the record number of
`that clala record.
`Other examples of idenlifying data items include: identi-
`fying liles in a netrvork lile system, identilying objects in an
`objecl-oriented database, identifying images in an image
`databasc, and identifying articlcs in a text databasc.
`In general, thc terms "data" and "data ilcm" as uscd hcrein
`refer to sequences of bits. Thus a data item may be the
`contents of a flle, a portion of a file, a page in memory, an
`object in an object-orientecl program, a digital message, a
`digital scanned image, a part ol a video or audio signal, or
`any other entity which can be represented by a sequence of
`bits. The tcrm "data processing" hercin rcfers to thc pro-
`cessing of data items, and is somelimes dependent on the
`type of data item being processed. For example, a dala
`pncessor for a digital image may differ lrom a dala pro-
`cessor ibr an auclio signal.
`In all of the prior data processing syslems lhe names or
`identiliers provided to identifu data items (the data items
`
`15
`
`?0
`
`?s
`
`30
`
`3,5
`
`40
`
`4-5
`
`2
`being files, directories, records in the clatatrase, otrjects in
`object-oriented programming, locations in memory or on a
`physical device, or the like) are always defined relalive to a
`specific context. For instance, the fi1e identified by a par-
`s ticular file name can only be delermined wlien the directory
`containing the Iile (the context) is known. The lile iclenlifled
`by a pathname can be determined only when the lile system
`(context) is known. Simiiarl,v, thc addrcsscs in a proccss
`address space, the keys in a database tab1e, or domain names
`i0 on a globai compuler network such as the Internet are
`meaningful only because they are specilied relative to a
`conlext.
`In prior art syslems for identifying data items lhere is no
`direct relationship between the data names and the clata iten-r.
`The same clata name in two different contexts may refer to
`differenl data ilems. and two different data names in the
`samc contcxl may rcfcr lo thc samc dala ilcm.
`In addition, because there is no correlation between a dala
`name and the data it rel'ers to, there is no a priori way ttl
`conlirm that a given data ilem is in fact the one named lry a
`data namc. For instancc, in a DP systcm, if onc proccssor
`requests that another processor deliver a data item with a
`given data name, the requesting processor cannot, in
`general, verify that the dala delivered is lhe correct data
`(given only the name). Therefore it may require ftrrther
`processing, typically on the part of the requesler, lo verify
`that the data item it has obtained is, in fact, the item it
`requcstecl.
`A common operation in a I)P system is adding a new data
`item to the system. When a new data item is aclded to the
`system, a name can be assigned to it only by updating the
`context in which names are deflned. Thus such systems
`require a centralized mechanism for the management of
`names. Such a mechanism is required even in a multi-
`processing system rl'hen data items are created and identified
`at separale processors in distincl locations, and in s'hich
`there is no other need for communication when data items
`are added.
`In many data processing systems or environments, data
`items are transfered lrelween different localions in the
`system. These locations may be processors in the data
`processing system, storage devices, memory, or the like. For
`example, one processor may obtain a data item from another
`processor or from an external storage device, such as a
`floppy disk, and may incorporate that data item into its
`system (using the name provided u,ith thal data ilem).
`However, when a pr<rcessor (or some krcatitln) obtains a
`data ilem fiom another location in the DP system, il is
`possiblc that this obtaincd data item is already prcscnt in thc
`system (either at the location of the processor or at some
`olher location accessible by the processor) and therefore a
`duplicate of the data ilem is created. This situation is
`common in a nelq,ork data processing environmenl where
`propriclary soflu,arc products are installcd from floppy disks
`onto several processors sharing a common flie server. In
`these systems, it is often the case that the same product will
`be installed on several systems, so that several copies of
`each Iile will reside <in the common Ille server.
`ln some dala processing systems in which several pro-
`cessors are connected in a network, one system is designated
`as a cachc server to mainlain master copics of data items,
`and other systems are designated as cache clients to copy
`local copies of the master data items into a local cache on an
`as-needed basis. Before using a cached item, a cache client
`must either reload the cached item, be infbrmed of changes
`to the cached item, or confirm thal lhe master item corre-
`EXHIBIT 2 - 35
`
`50
`
`55
`
`60
`
`65
`
`
`
`Case 5:18-cv-05198-BLF Document 14-2 Filed 10/04/18 Page 37 of 63
`
`us 6,928,442 82
`
`3
`sponding to the cached item has not changed. In other rvords,
`a cache c1ienl must synchronize its dala items with those on
`the cache server. This synchronization may involve reload-
`ing clata items onto the cache client. The need to keep tlre
`cache synchronized or reload it adds significant overheacl to s
`existing caching mechanisms.
`In view of the above and other problems with prior art
`systcms, it is thcrcfore dcsirablc to havc a mcchanism which
`ailows each processor in a multiprocessor system to deter-
`mine a common and subslantialiy unique identifier for a data 10
`item, using onlv the clala in the data item and not relying on
`any sort of context.
`Il is further desirable to have a mechanism for reclucing
`multiple copies of data items in a dala processing system and
`to have a mechanism which enablei the iclentification of 15
`identical data items so as to reduce mulliple copies. It is
`further desirable to determine *.hether trvo instances of a
`data item are in fact the same data item, and lo perform
`various olher systems' lunctions and applications on dala
`ilems rvithout rellng on any conlext intbrmation o. p.op- 20
`crtics of thc data itcm.
`It is also desirable lo provide such a mechanism in such
`a way as 1o make it transparent to users oi the data
`processing system, and it is desirable that a single mecha- ^.
`nism bc used to addrcss cach of thc problcms dcscribcd
`above.
`
`SUMMARY OF TTIE INVT,NTION
`This invention provides, in a clata processing system, a
`method and apparatus for iclentifying a data item in tbe
`system, where the identity of the clata ilem depends on all of
`the data in the dala item and only on the data in the dala item.
`Thus the identity of a clata item is independent of its name,
`origin, location, addrcss, or othcr informalion not dcrivablc
`directly from the da1a, and depends only on the data itself.
`This invention further provides an apparalus and a method
`for determining whether a particular data item is present in
`the system or at a location in the system, by examining only
`the data identities ol a plurality of data items.
`Using the method or apparatus of the present invention,
`the efficiency and integrity of a data processing system can
`be improvcd. The prescnt invention improvcs thc design and
`operation of a data slorage system, fi1e system, relational
`database, object-oriented database, or the like lhal stores a
`plurality of data items, by making possible or improving the
`design and operation of at leasl some or all of the following
`features:
`the system stores at mosl one copy of any data item at a
`given iocation, evcn whcn multiple data namcs in the
`system refer to