`Declaration of George Karypis
`
`247. The Petition . Declaration. and corresponding charts fail to
`
`demonstrate that Ghias discloses the claimed "approximate nearest neighbor
`
`search." The Petition and corresponding declaration assert that Ghias discloses the
`
`"approximate nearest neighbor search" because it pnxluces:
`
`(I) "8 ranked list of approximately matching melodies" (labeled 0 ); or
`
`(2) "the single most approximate matching melody"(labeledO ):
`
`248. Petition :
`
`Cbms '}:md lJ of!he '237 p=nl further requ .... \luI 1Ix- $=h Ioc:l.le;m
`
`"approltm:IIC nearesl IlC1&flbor." Ex. 100 t :II Cbms 9. Il. Ohm dlSClDKs th.1I thl5
`
`s<::lrch Ioc:ucs a neighbor by dctemunq: ":I. ~ tisl ofapprOltmatcly Il'I;llchll1g
`9
`mebthcs. :IS 6.strnled al 26" or "!he Single moSI approltlTl3lt' Il'I;llcllllll melody."
`
`Ex. 1010 312;50-59.6:60-63: Ex. tOO4 31 ' t 24.
`
`Pet . (,237) at 42.
`
`249. Petition Charts:
`
`Clailll 9(b):
`
`b) deu:rn\lrlt1&. by lilt tOllllIllCf S)'SlCm.
`3Il dtnllfO::31lOn Oflho: medl3 "oJ1.: LIS,,\:
`lhc m:ciI'ed fcalurtS QIIX\Cd from tho:
`mOOl3 .. Oft 10 pcrfonn :III :lppro~m.u.:
`DC;LJ'tS[ qhbor ~hof o::<1roCted
`f(a.UfG of idtnlifocd med .. "oJ1.:s: and
`
`P~.ioncr ""orpomlcs lilt abo\'C
`dScLlSslOnofGhas ~rdq; Chan
`Lb. Th IS m:I)' Ix: an 3ppro.urolC
`neighbor st::ll'th \h:u gtnrnlCS "~
`ranked lis! orappro~m:Ilt1y 0
`m:IIchq; .... doda. as ilUstr;l.ro " 0
`26" o. "the s .. ~ !TIOsl:l.ppro_~imlC
`m,l1c hIljl m.'1od~·." 2:5(1.59. 6:(,O..(.}.
`
`Pet . (,237) a145.
`
`NETWORK-I EXHIBIT 2005
`Google Inc . v. Network-I Technologies, Inc.
`IPRlOI5-00345
`
`161
`
`Page 165 of 292
`
`
`
`IPR 2015-00341, IPR20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`Claim 13(b.2) (referencing claim elemellt9Cb»:
`
`~)_ u~Ilg __ "~p~ cO"",UlersyslC11l,
`an iderllifac3tion Orthe media won; using
`the rccw.~ fC:l1urcs C:Xtr:lClCd from lhe
`media work 10 pcrfom' "" ;tpproxinl;ll~
`llC~rcsl rIC'lgbbOf search of e,\lr.I(lcd
`rc~tufl'$ ofidcmif-.;-d mcd.i.1 ",un;s.;tnd
`
`Petilioncr IICOrpOr.I!C5 lhe OOo\'c
`discussionofGIms ",gardmg (bim
`9b.
`
`Pet . at 46.
`
`250. Declaration:
`
`12-&.
`
`II is my opinion lhal Ghi as further discto5C'5 the eleme1lts of claims <)
`
`neighbor," E:c. 1001 al (bilils 9. I~ . In particular. Ghias diSCk'o
`
`thal Ihe search
`
`localcs a near or ncarcst I1CI~bbof by octermmlllg ~a runJ.:cd IiSI or approxunmely
`o
`maltbing nlclodu:s. as IIlUSll1llcd al 26" or -Ihe smgle DIOSI apprOXlll1alC nla"hmg
`
`mclod)'." Ex. 1010 at 2:.50-j9. 6:60.63_
`
`Moulin Decl. ('237) 124.
`
`251 . Declaration Charts:
`
`Claim 9(b):
`
`b) detcmllmng. by the computer
`SY$lcm. ~n "kmificalion of 1/", ",edi:!
`,,-ork "';n~ I"" rcc~;'cd f.-alU ......
`eXlr3eled from Ihe medi:! work 10
`perform an appro_~illl.1tc OeaJ1.'SI
`IIdPlbor search of e~lrnClc-d fcmum
`of idcolific-d media w<llb; and
`
`lln<;OI'pOfJIC my ~bo,-c discussion of
`Ghias re~arding Claim lb. Ghias further
`disel0SC5 111:1111115 ITI.ly be an
`apprO_~'ITI.lIC n<;,@bborsea",hlh:u 0
`g~ICS "3 rnnt.c-d lill orappro~unalcly
`ITI.llching "'Clod,,,!. 3S ,lIustr:nc-d 31 26"
`Of "Ihe single most appro~inl.1lc 0
`nl3lchin~ melody.' 2:50-5<). 6:60-6J.
`
`Moul in Decl. ('237) 127.
`
`Cl!lim l3(b.]) referencing claim element 9<b» :
`
`162
`Page 166 of 29]
`
`
`
`IPR 2015-00343, IPR20 15-00345, IPR20 15-0034 7, un(l IPR20 15-0034R
`Declaration of George Karypis
`
`I incorporale m)' abo,c disclt55ion of
`Ghias regarding Claim 9b.
`
`2) dClcrmininll. b)' 111(: COl1lpUlCT
`s),5lcln, an idenlificalion orlhc media
`work usinlllbc rC\:c;"ed fealUres
`C.<lra"ed fromlhc mcd;" won. to
`perfon" an awro.~ illl~IC m:al'l:SI
`ncighbor ",3"h of cxuaCled fcalul'l:s
`of idenlified mcdia " 'orks. and
`
`Moulin Decl. (,23 7) 127.
`
`252. One skilled in the art would understand that neither of the cited
`
`passages discloses the claimed "approximate nearest neighbor search" because, as
`
`described above, both the ranked list and single most approximate matching
`
`melody always identify the closest match. 1 address each passage in tum:
`
`253, Passage I:
`
`The qlM:ry engine 24
`liureh<... ... Ih~ melody da lab:a...., 14 and OlIlpUW • Inked list of
`lpproximaldy mllching melodies, as illUSlnred II 26. A
`pn:J;elcclcd error lo1eraflCe may be app1i~d 10 lhe ,!;Careh. The
`qucry engine: 24 may of COlII"liO: ahcrnal i,-ely be programmed
`10 OUlpUI lhe sing\<: most approximale malching melody Of,
`if desired, 10 OU1PUI an cxaCl malching melody. Ilowe .. ~r, by
`searching for UI apprOXimale maldling melody, IS herein(cid:173)
`afler discussed. ''1riOllS forms of Inlicipalcd errors may be
`llten inlo account.
`
`Ghias, 2: 50-59. As noted in the Petition and Declaration, this passage states that
`
`the search "outputs a ranked list of approx imately matching melodies. as illustrated
`
`at 26" or "the single most approximate matching melody." As I explained above,
`
`neither approach discloses the claimed "approximate nearest neighbor search." An
`
`"approximate nearest neighbor search" must identify "a close, but not necessarily
`
`exact or closest, match" Section V(O); Decision (,237) at 8. Both outputs
`
`163
`
`Page 167 of 292
`
`
`
`IPR2015-00343 , IPR 20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`disclosed in this passage necessarily disclose an exact or the closest match and.
`
`therefore, are nOl an "approximate nearest neighbor search:'
`
`254. Passage 2:
`
`'1lIe ~"Ompuler 16 may desirably be pl"Oj;fJmmcd so Ihal.
`for a gi ven query. lhe dallbasc t..j rClums I lis! or songs
`... nkcd by how wdl lhey matched lhcqucry, IlOIjUSl one bcsI
`malch.
`~
`
`Ghias, 6:60-63. This passage also does not disclose a neighbor search. As I
`
`explained above, a "list of songs ran ked by how well they matched the query"
`
`necessarily identities an exact or the closest match, and specifically identi lies such
`
`a song as the top-ranked song.
`
`255. Moreover, under the proper construction of "approximate nearest
`
`neighbor search," the search must be a sub-linear search. ' 237, 9: 12-19 (an
`
`approximate nearest neighbor search is an " example of a sub-linear time search" );
`
`Section V(D). As demonstrated above, these passages disclose a linear (rather than
`
`sublinear) search.
`
`256.
`
`Ilol.lrd :~ cOJ/cerl/.~: I now address the Board's specific concerns
`
`(identified in its Decision) with respect to whethcr Ghias discloses the claimed
`
`"approximate nearest neighbor search." In instituting Ground 2 of the ' 23 7 I PR,
`
`the Board found that Ghias disclosed the "approximate nearest neighbor search"
`
`164
`
`Page 168 of 292
`
`
`
`IPR 2015-00343, IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`because the error-tolerance search disclosed in Ghias "allows the user to identify
`
`sets of songs that comain simi lar melodies:"
`
`Ghias provides Iha l ··[I]he number of malehes Ihal Ihe dalabase 14
`
`should relrie\'e depends upon Ihe error-lol<'rtlllc{' used during Ihe key(cid:173)
`
`search.'· and ··Ihe user can perfonn a Ilt'l,' qll/'I) ' 011 II rnlricft'd $t'arch Ii$!
`
`romi$fmg oJ $()lIg$ JIIM ,.. .. lrh'I't'(/. This a)lows Ihe user 10 identify selS of
`
`songs Ihal eomain similar mt'lodics:' Ex . 10 10. 6: 6~-65 . 7:5-8 (emphases
`
`added). Thus. Ghias makes clear Ihal Ihe scareh need nOI bt' exhauslive. as
`
`Palelll Owner has argued. and will ael 10 " idemify[]a closc. bUI nOI
`
`necessarily exacI or closest. llIatch." per our claim cOnstnlc\ion.
`
`Decision ( '237) at 18-19. The Board did not cxplain, however, how "Ghias makes
`
`clear" that the search in Gh ias will " identifyO a close, but not necessarily exact or
`
`closest, match" as required by an "approximate nearest neighbor search."
`
`257. The Board noted that using an "error-tolerance," the user can adjust
`
`the number of output matches ("The number of matches that the database 14
`
`should retrieve depends upon the error-tolerance used during the key search."
`
`Ghias, 6:63-65); and a new query can be perfonned on the restricted list ("If the
`
`list is 100 large, the user can perfoml a new query on a restricted search list
`
`consisting of songs just retrieved." Ghias, 7:5-8). But nothing in these passages or
`
`anywhere else in Ghias states or even suggests that the output of the initial list or
`
`the output of the restricted search will " identify a close, but Ilot Ilccessarily exact or
`
`closest, match." As 1 explained above, no such search is ex])ressed in Ghias or is
`
`165
`Page 169 of 292
`
`
`
`IPR2015-00341, IPR20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`inherent (i.e., necessarily present). Rather, the search will always (" necessarily" )
`
`identify an exact or closest match. Accordingly. Ghias does not disclose the
`
`claimed "approximate nearest neighbor search."JO
`
`C.
`
`'237 Ground 3: The instituted claims of Ihe '237 patent arE' nOi
`obl'ious over )wamura and C hen.
`
`258.
`
`It is my understanding that if a combination of two references fai ls to
`
`teach an important claimed element, it is not possible for that combination to
`
`render the claim obvious. That is, assuming one of ordinary skill would have
`
`thought 10 combine prior art references, those references would still be missing an
`
`important element and therefore. even with the combination, one of ordinary skill
`
`would sti ll nOI possess the invention.
`
`259. Any combination of lwamura with Chen would still be missing the
`
`same elements addressed above in Ground I.
`
`260. Ground 3 is directed to only dependent claims 26 and 27 which
`
`depend either directly or indirectly on independent claim 25: and claims 34 and 35
`
`which depend either directly or indirectly on independent claim 33. Pet . (,237) at
`
`An approximate nearest neighbor search could miss one or more of the
`
`closest matches in the retumed search results. The searches disclosed in Ghias
`
`never purport to miss one or more of the closest matches in the retumed results.
`
`I ••
`
`Page 170 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`53-56: Decision ('237) at 22. Ground 3 presents two alternative grounds-
`
`that the
`
`dependent claims "are obvious over hvamura alone, or aliemalively, over [wamura
`
`in view of Chen." Pel. ('237) at 53.
`
`261. As I demonstrated above, Iwamura does not disclose key elements
`
`from the independent claims upon which Ground 3 is based (claims 25 and 33)
`
`including:
`
`• "non-exhaustive search ... to identify a near neighbor" (claim 25(b.2); and
`
`• "approximate nearest neighbor search" (claim 33(b.2».
`
`I note that Petitioner does not rely on Chen for these elements. Pet. ('237) at 53-
`
`56: Moulin Dcpo. 371 :17·20 (addressing sublinear); Moulin Depo. 372:2-4
`
`(addressing non-exhaustive): Moulin Depo. 372:5-7 (addressing approximate
`
`nearest neighbor search).
`
`262. Moreover, I note that Petitioner does not assert that these missing
`
`elements are obvious in light of Iwamura but rather continues to assert that they are
`
`expressly disclosed in Iwamura. See e.g. , Pel. ('237) 54 ("For the reasons
`
`expressed in Ground I [anticipation based on Iwamura], Iwalllura discloses all
`
`elements of claims 25 and 33."). Accordingly, Ground 3 fa ils at least because the
`
`elements frO Ill the independent claims addressed above are missing frolll Iwamura
`
`and the Pctition docs not idcmify any basis for correcting these deficiencies based
`
`on either Iwamura or Chen.
`
`167
`
`Page 171 of292
`
`
`
`IPR 20 15-00341, IPR20 15-00145, IPR20 15-0014 7, an(l IPR 20 15-0014 R
`Declaration of George Karypis
`
`VII.
`
`' 988 patent.
`
`263. llie Board instituted the '988 1PR based on three Grounds:
`
`• Ground I : Claims 15- 17, 2 1- 23, 28, 31, and 51 under 35 U.s.c. § I 02(b) as
`
`anticipated by Ghias;
`
`• Ground 2: Claims 22, 24-26, and 52 under 35 U.s.c. § 103(a) as obvious
`
`over Ghias: and
`
`• Ground 3: Claims 15- 17, 2 1, 23, 27. 28, 31 - 33, 38, and 5 1 under 35 U.s.c.
`
`§ 102(1') as anticipated by IWilmurn.:
`
`Decision ('988) at 22. I note that the only inst ituted independent claim is claim 15.
`
`I address each Ground in tum.
`
`A.
`
`' 998 Grou nd I: The instituted claims ofthe ' 988 Patent are not
`anticipated by Ghias.
`
`264. The single independent claim of the '988 patent instituted for trial
`
`requires a " non-exhaust ive search identifying a neighbor." '988, claim 15. Ghias
`
`does not disclose ( I ) a non-exhaustive search, (2) a search ident ifying a neighbor,
`
`or (3) detcnn ining an action based on the identification. I address each deficiency
`
`in tum.
`
`168
`
`Page 172 of 292
`
`
`
`IPR2015-00343 , IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`I.
`
`non-ex hausth'e search (claim element IS(b».
`
`265. As I explained above in detail (Section V(B)), a "non-exhaustive
`
`search" is "a search thaI locales a match wilhout a comparison of all possible
`
`matches."
`
`266. One ski lled inlhe an would understand Ihal Ghias teaches an
`
`exhaustive search thaI compares the work to be identified (user input 23) with "all
`
`the songs" in the database-i.e., "all possible matches." One skilled in the an
`
`would understand that all "possible matches" in the system di sclosed in Ghias are
`
`all oflhe songs in Ihe database. My understanding is confinned by Petitioner's
`
`Declarant:
`
`Q
`
`I s it th" ("., .. , tildt th., ".,t ot .11
`
`possi bl e matches f or Ghias are the set of the
`
`llIusica l "orb 1n the daubase?
`
`A
`
`Yes .
`
`20
`
`21
`
`"
`
`Moul in Depo. 325: 19-22. Ghias discloses a search that compares the work to be
`
`identified ("user input") with all possible matches- "all the songs" in the database:
`
`In or<.ler 10 "" .. rdr I~C <.I .. abo"... """gs in lbe <.Iarab_
`1-4
`an: preproccss.:d 10 coover! rhe mclo<.ly infO a SlrClm of rhe
`pn:viou.~ty d~<41.LI.<oo:d U.lJ.S ch:arKlel'i. and rhe convened
`uS<". input (the b:y 23) is ~'OIIIpa",d wilh aU the songs.
`
`Ghias, 5:66-6:2. As Petitioner's Declarant acknowledged when addressing the
`
`paragraph from Ghias quoted above:
`
`169
`
`Page 173 of 292
`
`
`
`IPR2015-00343 , IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`o
`
`W~lL it. says . " In ord~ r t. o s ~ arch t.he
`
`dat.abaae.
`
`.onqs are preprocessed t.o COnVe rt. t. he
`
`"",lady int.o a stre"", of characters", riqht?
`
`A
`
`1I.1qht .
`
`compared with all the sonqs"; rlQht?
`
`:~
`
`:4
`,
`,
`,
`
`1
`
`Moulin Depo. 339:23:-340:5 .
`
`,
`
`,
`
`8
`
`,
`
`o Does Ghlas t.each dolnq a aeareh by
`performinq a c""'parlson with all the poulbla sonqs
`
`that. a r e possible matches in the database?
`
`Moulin Dcpo. 340:6-9.
`
`o But what you've identified in Ghias . in
`
`t.he records in the database , rl'1ht?
`
`o Would it ~ the case that the Ghlas sea r c h
`is '101n9 t o ~ perf orl!l1nq a co",psrison t o each o f
`
`the "",ledie. that are pes.lbie ~tche. in the
`
`database?
`
`A
`
`I t doe. a e""'Parison . yea . t o each o!
`
`6
`
`,
`•
`
`9
`
`10
`
`II
`
`IJ
`
`the", .
`
`Moulin Oepo. 323:4- 13.
`
`267. The user input (23) is not compared with some songs in the melody
`
`database (1 4); rather, it " is compared with all the songs." Ghias does not disclose a
`
`170
`Page 174 of 292
`
`
`
`IPR2015-00343 , IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`search algorithm that does not compare the query to every record in the reference
`
`data set. Petitioner's Declarant confirmed my understanding-
`
`that 'he search
`
`disclosed in Ghias compares the song to be identified with each record in the
`
`database and is therefore no, "llOn-exhaus,ive"-"a search that locates a match
`
`without a comparison of all possible matches" (Section V(B» ; Decision ('998) at
`
`7)
`
`4
`
`S
`
`E
`
`,
`
`S
`
`9
`
`10
`
`11
`
`12
`
`AS a seArch that does a :omparlson to each of the
`
`poasible mAtch.s in the d.tsbsse thst we ' re
`
`search i nq OVer.
`
`In that in.tan:e , if we hsve that
`
`de f inition, would you Aqr~ that GhiAS da.s perform
`
`sn exhaustive search?
`
`MR . £LACQUA: Obje:tlon .
`
`THE WITNESS : U"der your tlA"Ad detin!.tio",
`
`yes, it would.
`
`Moulin Depo. 327:3- 12.
`
`17 )
`
`Page 175 of 292
`
`
`
`IPR2015-00343 , IPR 20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`..
`
`11
`
`18
`
`19
`
`"
`"
`
`23
`
`2 4
`
`25
`
`1
`
`,
`,
`
`.:1< •• n"t p""!':' • • e<:oopoort""n v' e"eh ,'·f .he
`
`po",,,thl ......... '1 ... " 1n :>II,'
`.ec<,.<1 Udt.b.U ...
`lIbuld y"" a<H .....
`
`t hen .
`
`[!>.ot GhUs does n(,'
`
`MR. EUoCQU"' : Objec:t1""n .
`
`THE WITNESS :
`
`I w-, ,,1<1 hdve to th1n k -- to re.d
`
`tile patent .9aln It he c<:-nsldeu the poss 1b111ty ,·f
`
`n<:ot
`
`.. earc:hlnq the enti re d"t"h.ue . Cle",'l y , 1t ' "
`
`Int .. nd.-<I to ..... reh the .. ",Ir" ,1 .. u~ .
`
`BY 11R . DOVEL :
`
`...
`
`Y ... .
`
`Moulin Depo. 327:14-328:4_
`
`268. The Petition and corresponding Declaration fai l to demonstrate Ihat
`
`Ghias discloses a non-exhaustive search.
`
`269 . Petilion: As suppan for the claimed "non-exhaustive search," the
`
`Petition relies on the following assenions (and corresponding references to Ghias)
`
`labeled 0 and 0 :
`
`172
`Page 176 of 292
`
`
`
`IPR 2015-00343, IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`. ""cesS,,,, n<>1<.S "hieh :u b. "I'prox.n:>Iety m;"c~ .. . !he ",dody. - ). Ghgj;
`
`~flic.ml :.pprosm.l'<' P3ttcm m.lldung ~t.n- r:II~ 1h.1n an al@OfI:t.n IIIJI 0
`(l1Jr.1111«J 10 ~1C1J 3 111:11.::11. Jd 3. 6:7.11 . :\Ioreon:r. GIms 1<!3C"'-" IIDI -sC' <"1":18
`j\lgor1lulb IIJ, <' b.. ... ,. d~" .. bJll.'tI I!~n :I<IJI\..", [1M J probJ..'111· r"'gD'JC !rom "bn~~
`
`O(kn)orO(nbgtlU) •• -).1<1 (lI6:2.l •. l5.
`
`Pet . ('988) 9· 1 o.
`
`270. Petition Charts: The charts in the Petition rely on the same assertions
`
`and passages from Ghias: Petitioner's chan for claim 15, elemem (c 1 incorporates
`
`the chart for claim I , element (c]:
`
`P<1i.ioncr incorpora,.,,;!he ~,bo", dis<;uss ion
`o rGb"", n:garding (bun Ie.
`
`.... cmmms an
`) e "'tromca ,
`idcwif",:llion ofdIC el'ClroIli<:
`work based on .he CX1DC1...!
`f<"d'W"CS. ,,"""'i, 1he dcnlIf"'3.im
`is has...! on a non-exhaus.i",
`.~""b d<mlil'.... a neitUlbor.
`Pet. ('988) at 14. The chan for claim I, element r c], in tum, provides:
`
`173
`
`Page 177 of 292
`
`
`
`IPR 2015-00343, IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`fl rtttn q; III !he: ponot.lc Climl
`de-icc from the 01\1: O. mort
`5(1'\= on dtnl1fo;.n:m ofobt
`clotll(K1r "001: b:tSQd on 1M
`0J<IJX1Cd rC31lRS. """,", the
`jdmifJCOIion • bosed on ~ non(cid:173)
`c.Wus,,,,, sc:m:h d mol}-.cs •
`~.-
`
`Gl\QS Itt ..... ", :md OUIpUISM lhe co.....-.
`..-ho;h IS ~ pon:lble dim de> o;c (E:.. l~ at
`• 73).,olisl or cdmtif1l:;cUons orcioxtronlC
`..-orb. 2:..'O-S2. 6-(,().63. 7 .... S. ~:16-28.
`MI~ SUf;hcdnwf1l:lD,)1I$ :In' dO\e'f1flmOd
`by"san:tung 1~ meklod) d.~ 14-10
`Iocat 0 RUcchll'lll mdMI~ 2;50.'9. 6:ro.6J.
`7: .... 5. AbslQCI. 8:16-2!!, lS:6l-63 TIllS
`,=b 1lliJ)' empioy ~ 1IOIK.Wlln"f 0
`' ilPDrnuNlc p.u .......... hmJI.....,· or
`:InDIbor all/llI.tun 1l1:li opcr.uos ("'let lh:cn~ 0
`brulO fon:uc:ln:1L 6.:'_1 t. 6.23·35 Th ..
`1I(I~\f\'C m>n:h dmIfo:-s .~.
`lC" '. rritd 10;1 ohpproun:udy IRIIchllg
`mdMIits: 2~S9. 6JiO.6J
`
`Pet , (' 988) at 12.
`
`271. Declaration: Petitioner's Declarat ion relies on the same assertions
`
`and passages from Ghias:
`
`rclali'-f pilCh di fTeoc lK0:5 bcI..,ttn succcui"c noles of thc melody.-). Ghiu fun lcer
`
`discloses Iml Ihis search rna)' be nOI1-Clth.1u~li'·c. Spedfically. Ghias ICaches Ihac
`
`-il is considel'Cd desirable 10 use an efficiem approximale panem nlalching
`
`algorilhm- ralher Ihan an algorilluu Ihal 1$ guar:ulIecd 10 yield a m:uch. /d. 31 6:7-
`
`II, ,\tortO"cr. Ghias leaches Iml -Severnl Algorilhms m'-c bee n de"clopcd Ih~ 1
`
`:cddrcu 11hisl problem" r:mgiug from "brule force' 10 sub51:umall y faslcr
`
`algomhms. ld. al 2J-3S ("Sc"cral Algonlhms llJ\'e been developed Iml address Ihe
`
`problem or approxlmale scnng matchIng Running limcs Iea,'c rn llged from O(mn)
`
`ror 11K brule force ah.'Ofilhm to O(I.-n) orO(nlog(m)." here '0' means'oo lhc order
`
`of.' m is IItc number or pilch differenccs in Ihe que!)'. aoo n IS Ibc SIze or lhe SIring
`
`I
`(song): ).1 Id al 6:23-35. Bcrause lhest algorilhms nre raSler Ihan bnne forcc
`searches. lhe)' are nOI1~AA.luslh·e under J>c-liliOlItr'S (OPSmldion. ~
`
`Moulin Decl. ('988) 69-70.
`
`17'
`Page 178 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, !In(l IPR20 15-0014R
`Declaration of George Karypis
`
`272. Declaration Chan s: Finally. the chans in the Declaration also rely on
`
`the same assertions and passages from Ghias:
`
`c) fC<:Cl'ln! allhe portobl. chenl
`dc\',,,,, from ,he one or """'" """..-n
`on Idmur""IIOII of the: dec.,..,r .. "
`"od:; bas.cd On the exlr.><.cJ fC3!Un:-<.
`"here,O the: ,dmldinloon i, I>.>..-.i on
`• non«h:MI.h, c ",.",11 ILknlifp"ll a
`nCI!'hbIr.
`
`Glu ... d,,,,I/»C$ rcffI. ... n~ and lIWpUIun~
`aI lhe ~"mpul"', ..-11l~h ,~ a ponabk
`chen. de ... "c. 3 h., or,dmllfi~3'~ of
`.1o"\ronI< ..-od:; •. !; SO-~2. 6:60-63. 7;~.
`~. 8:26-28. 8:61-63 Gh .. ., funhcr
`tb",loscj 'hOI _b lLknufi(.uons;or;<
`""ennlll"" by "..,arch",!! the melody
`d'1131>.>", IJ ",o ~ . "u,dun!!
`I1KIody. l : SO-~9. 6:60-63. 7 :J-~.
`""I»mo<,. 8:16-28. 8..61-63 Gh,,,, fun .....
`do><:k»c> ,b'l Ibl> >Car.:h 1II:t} mlplOl B
`_~xhau,'''e ":reImlX!!lW' pan....,
`ma,,,blD~ oll'"mlun" or 'lIQlhn
`al,.,..O!lIm Iha. opcr.>l'" fa'I'" lha".
`bru'e f""'" ",,,,,,h 6 ~-11. 6~J-J~
`Gh .... funller dJ ",,,,,,,s ,n.1 thl> __
`""hau",," ,~h ......... 1I1i~ . Ir>~hhot
`"". de,enn1rurlJ! ' 3 rank"" h>1 of
`
`Moulin Decl. ('988) 75.
`
`273. These are the only passages from Ghias cited by the Petitioner and
`
`Declarant 10 support the sub-linear claim elements. Moulin Depo. J J 3: J 5-21 . The
`
`assertions relating to these passages fails to: (a) apply Petitioner's construction (or
`
`any other construction) of non-exhaustive to Ghias; or (b) explain how an
`
`"approximate string matching algorithm" is expressly or inherently a non-
`
`exhaustive search. One skilled in Ihe art would understand that neither the
`
`assertions nor the passages from Ghias disclose the claimed non-exhaustive search.
`
`I address each in tum.
`
`274. Passage 1:
`
`175
`
`Page 179 of 292
`
`
`
`IPR 2015-00343 , IPR20 15-00345, IP R20 15-0034 7 , an(l IPR20 15 -0034R
`Declaration of George Karypis
`
`I'Qr pcrfQnning thc key·~~rcb within thc d~lab;u;c 14, il
`is considered desirable 10 usc an cnicio:nl approximate
`allem match ing algorilhm. By -apl)ro ~ imalc- is mcanllh~1
`be algorithm should be ab~ 10 lake into 3oCC()Unl various
`forms of errors.
`
`Ghias, 6:7-11. First, this passage does nOI stale Ihallhe algorilhm is nOI
`
`guaranteed to yield a match (as interpreled by Pelilioner). Second, and more
`
`importantly, the described algorithm does not state (or even suggest) that all
`
`possible matches in the database are not searched. The passage does not state that
`
`all matches are not considered, or even that all data in all possible matches is not
`
`considered. My understanding is confinned by Petitioner's Declarant:
`
`You would aqree thot the term - approximat e
`
`_ t cbinq _lod:r·~ d".~n' t , x pr.uly .ay t bat ",,'~.
`
`901nq to be u.1nq a •• arcb approach where "e l.a~ .•
`
`"
`"
`"
`"
`"
`Moulin Depo. 347: 13-1 7.
`
`
`O~t ,11 -- .om. of t h e da t .
`I 'que ,
`
`A
`
`; ~1qht ?
`
`275. Passage 2:
`
`Several Algoritbms ha"c becn developed tbat addro:"" the
`problem of approximate striog matching. Running times
`have ranged from O(mn) for the brule force algorilh m 10
`O(kn) nr O(n1og(m). when: "0" means ··on lhe order of.- m
`is lhe number of pilCh diffeICIl<X$ in lhe query. and n is lhe
`si7.e of the string (oong). See Ricardo l)ae7;a·Yales and G. 11.
`Gannet ••. Fast SIring Malehing wilh Mism.IChcs.·· /"/o,,m,,'
`li(lll a"d CQmpuraliQII, t992. Apreftrrtd algorithm which is
`considered 10 offer beller pc:rformaocc in general For lhis
`purpose i_~ that o:k:scribed in Ricardo A. Bacsa·Yalcs and
`allis II. l'erichcrg. ··""st and I'nClical Approximalc SIring
`Malch ing. ··Combinmorill/ I'allern Mlllching, 17)ini AIIIU/"/
`SY"'PQSilO", ·· pages 185-192, 1992.
`
`17.
`Page 180 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`Ghias, 6:23-35. One skilled in the art would understand that the "approximate
`
`string matching" algorithms discussed in this passages involve matching a work
`
`with a record in the database, where the work to be identified includes an "error"
`
`so that "various fomlS of errors" would not prevent a proper match from being
`
`identified. The "approximate Siring malching" algorithm is applied when the work
`
`melody ·'is compared with all the songs" in the database and all of the data within
`
`each record. Ghias, 5:66-6:2; Moulin Depo. 347: 13-17. This passage discusses
`
`comparing the work with a single record in the database.
`
`276. Accordingly, Ghias does nol disclose a search that would even meet
`
`Petitioner' s improper construcrion of "non -exhaustive search," because Ghias does
`
`not search less than ··all possible matches" or even less than ··all data within all
`
`possible matches."
`
`277.
`
`I obsetved that Petitioner only ciled the two passages quoted above as
`
`support that Ghias discloses the claimed non-exhaustive search. Petitioner's expert
`
`con finned my obsetvation:
`
`177
`
`Page 181 of292
`
`
`
`IPR2015-00343 , IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`11
`
`18
`
`0
`
`Jus ~ new . whe~ yeu -- we hAd ycu ge
`
`threugh And examine eAch ef the portions o f Ghias
`
`li
`
`that you cite wi t h respect to the none xhaustive
`
`20
`
`21
`
`ZZ
`
`search; riqht1
`
`A
`
`0
`
`Yes.
`
`Khan you did that, did YO" ldantHy any
`
`25
`
`A
`
`I dld,, ' t identif y t hem , .. hich does no t
`
`_an t hey don' t exist . They miqht exis t .
`
`It they
`
`do e><ist, I d i d nOt <::i t e
`
`t he m.
`
`Moulin Depo. 332: 17-333:2. As I demonstrated above, these two passages fail to
`
`disclose the claimed non-exhaustive searc h. Accordingly, Petitioner failed to
`
`satisfy its burden of establishing that Ghias discloses the claimed non-exhaustive
`
`search.
`
`278. Moreover, Petitioner's expen confirmed that other passages from
`
`Ghias cited in his Declara tion~in an attempt to establish other claimed elements~
`
`also do not establish the claimed non-exhaustive search. Moulin Depo. 330: 19-
`
`33 1 :24; 239:22-25 (2:50-52 "does not teach excluding a portion of the database
`
`from our search'"); Moulin Depo. 330: 15-18 {2:50-52 ("Q. Does Ghias have any
`
`ponion in where it teaches affirmatively searching only part of the database. A.
`
`Not in that sentence, no."): Moulin Depo. 330: 1-14 (2:50-52 (the "natural
`
`inference" from the statement that the "query engine 24 searches the melody
`
`database 14" is that "it's going to search the entire database"); Moulin Depo.
`
`178
`
`Page 182 of 292
`
`
`
`IPR2015-00343 , IPR 20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`334:2-21 (Q. "[D]oes Ghias teach looking at only a portion of the database? ... A.
`
`It does not do that in this paragraph."); Moulin Depo. 337:7-338: 17.
`
`279.
`
`/Joan ! :,. CflIICerl/.\·: I now address the Board's specific concerns
`
`(identified in its Decision in the '988 IPR) with respect to whether Ghias discloses
`
`the claimed non-exhaustive search. I note that in instituting Ground 2, the Board
`
`did not rely on the arguments presented by Petitioner and its Declarant or the
`
`passages from Ghias quoted by Petitioner and its Declarant in an attempt to
`
`establish the claimed non-exhaustive search. Instead, the Board initially found that
`
`Ghias disclosed the "non-exhaustive" search because the search discloscd in Ghias
`
`could produce a list of matches based on an error-tolerance and the user can
`
`perfoml a "new query on a restricted search list eonsisling of songs just retrieved:"
`
`011 the presenl m:ord. we:lTe nol persuaded by Palelll Owner's
`argulllents. Ghias pro"ides lhat "J t Jhe uumber of matches lhal lhe
`d:uabase 1-1 should retriC"\.·e depends upon lhe .'rror-/Q/emllc,' used dunug
`the key-search:' E.x. IOto. 6:6J-65 (emphasis added). Ghias funher
`pfO\'ides that '"Ihe uscr can perfonn a I/t'I,' qllery UII II ""SlriCI,~1 Sl.'orc-h 1i~1
`('()"sis/i"g oj $O"gs jllSI f'('lnI'1wf. This allows Ihe user 10 identi fy selS of
`songs that comain similar melodies:' /d. at 7:5-8 (emphasis added), Thus,
`Ghias makes dear that the search need 1101 be exhaustivc. :..s Pment Owner
`
`argues. and will aCllo '"identi fyQ a close. bill not neccssari ly exacI or
`closes!. l1I31ch:' per aliT claim construction. Addilionally. gh'en the
`
`179
`
`Page 183 of 292
`
`
`
`IPR2015-00341, IPR20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`Decision ('988) at 12. There arc two reasons why the Board 's reliance on the
`
`"new query on a remicted search list" does not satisfy Petitioner's burden of
`
`demonstrat.ing thaI the instituted clams are unpatentable based on Ghias.
`
`280. First, had the concept ofa new second search based on the restricted
`
`list (and these passages from Ghias cited by the Board) disclosed the claimed "non-
`
`exhaustive search" (as I demonstrated below, they do not), it is my understanding
`
`Ihat it could be improper for Ihe Board to rely on Ihese passages in finding the
`
`challenged claims unpatentable because these passages were not identified by the
`
`Petitioner as support for the non-exhaustive search.
`
`281 .
`
`I note that Petitioner never asserted (in the Petition, charts, or
`
`Declaration) thai Ghias discloses a non-exhaustive search because the "user can
`
`pcrfonn a new query on a restricted search list consisting of songs." The Petition
`
`does not even mention the words or concepts emphasized by the Board in its
`
`Decision and that fonn the basis for the Board' s preliminary findin g that Ghias
`
`discloses a non-exhaustive search: "error-tolerance" and "restricted search list
`
`consisting of songs just receive." The only references to Ghias presemed by the
`
`Petitioner for the claimed non-exhaustive search are Ghias, 6:7· 11 and 6:23·35
`
`addressing approximate string matching, not perfomling a "new query on a
`
`restricted search list consisting of songs just retrieved" based on an error tolerance.
`
`Petitioner' s Declaram did not "cite anything in [his} Declaration that teaches, in
`
`180
`Page 184 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`Ghias, performing a search that rcturns a list o f ranked matching songs and then
`
`performing a second search on fhat list." Moulin Depo. 146:21-147:21.
`
`282.
`
`I note Ihal the Board, however, rel ied exclusively on two completely
`
`different passages from Ghias not cited by Petitioner--Ghias, 6:6]-65 and 7:5-8.
`
`Decision ('988) at 12. One skilled in the an would understand thai these passages
`
`address a different concept than the approximate pattern matching concept
`
`identified by Petitioner as support for the nonexhaustive search elemen!.
`
`283. Second, using a "new query" on Ihe " restricted search list consisting
`
`of songs just received" does not disclose the claimed "non-exhaustive search." A
`
`" non-exhaustive search" is "a search that locates a match without a comparison of
`
`all possible matches." See Section VeB),
`
`The restricted search can be viewed
`
`in one of two ways.)1 Under either view. Ghias does not disclose a non-exhaustive
`
`search. I address each view in tum.
`
`284.
`
`l;ir.~1 view: Under the first view, the search to identifY the record lhat
`
`matches the song being hummed is viewed as a single search with two stages.
`
`Under Ihis view, the second search on the "restricted list" is not an independent
`
`search-
`
`the two stages of the search are not independent. Rather, the search on the
`
`Ghias provides no dctails or infonJlation about the search on the restricted
`
`search list.
`
`181
`
`Page 185 of 292
`
`
`
`IPR2015-00343 , IPR 20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`" restricted list" is the second stage ofa t1,\'o-stage search. dependent on the first
`
`stage. See Moulin Depo. 336:9-15. The second search depends on rhe first to
`
`generate a candidate set. A single work, i.e., the song being hummed (not two or
`
`more works), is being identified in the two-stage search. The IWO stages refine Ihe
`
`idenrified marches: Ihe second slage does nOI identify any new matches.
`
`285. To constitute a "non-exhaustive search" under this view, Ihe Iwo-
`
`stage search process disclosed in Ghias would have 10 conduci the search without
`
`comparing the work 10 be identified with all possible mat