IPR2015-00341, IPR20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`2.
`
`The Board properly rej ected Petit.ioner' s assertion that a
`" non-exhaustive sea rch " should be construed as " a S('a rch
`that locates a match without conducting a brute fo rce
`comparison of all possible ma tches, and all data within a ll
`possible matches."
`
`83_
`
`The "all data" clause (that I underlined above) in Petitioner's
`
`proposed construction (Pet. (' 237) at 5; Decision (,237) at 5-7) would improperly
`
`include as a "non-exhaustive" search any search that did not compare "all data" in
`
`each record, even if the search were a brute force comparison of each record in the
`
`database. As an illustrative example, assume the work to be identified "ABC" is
`
`compared wirh all records in a libmry, inC luding record " DEF." When comparing
`
`"ABC" with " DEF," the algorithm detennines that there is no match between
`
`"ABC" and " DEF' after just comparing the first letter of the work "A" with the
`
`first letter of the record " D." I f the algorithm does not unnecessarily compare the
`
`second and third letters, then according to Petitioner, the search is not "exhaustive"
`
`even though evel)' record is compared.
`
`84_
`
`Petitioner' s Declarant states that a non-exhaustive search is any search
`
`that is not a brute force search, and a "'brute force' search, in tum, is a search
`
`wherein a quel)' is compared to evel)' single portion of every single item in a
`
`database." Moulin Decl. (,237) 43. Petitioner's Declarant, however, I)rovides no
`
`NETWORK- I EXH IBIT 2005
`Googlc Inc. v. Network- I Technologics, lnc.
`[PR20 15· 00345
`
`56
`
`Page 60 of 292
`
`
`Declaration of George Karypis
`
`2.
`
`The Board properly rej ected Petit.ioner' s assertion that a
`" non-exhaustive sea rch " should be construed as " a S('a rch
`that locates a match without conducting a brute fo rce
`comparison of all possible ma tches, and all data within a ll
`possible matches."
`
`83_
`
`The "all data" clause (that I underlined above) in Petitioner's
`
`proposed construction (Pet. (' 237) at 5; Decision (,237) at 5-7) would improperly
`
`include as a "non-exhaustive" search any search that did not compare "all data" in
`
`each record, even if the search were a brute force comparison of each record in the
`
`database. As an illustrative example, assume the work to be identified "ABC" is
`
`compared wirh all records in a libmry, inC luding record " DEF." When comparing
`
`"ABC" with " DEF," the algorithm detennines that there is no match between
`
`"ABC" and " DEF' after just comparing the first letter of the work "A" with the
`
`first letter of the record " D." I f the algorithm does not unnecessarily compare the
`
`second and third letters, then according to Petitioner, the search is not "exhaustive"
`
`even though evel)' record is compared.
`
`84_
`
`Petitioner' s Declarant states that a non-exhaustive search is any search
`
`that is not a brute force search, and a "'brute force' search, in tum, is a search
`
`wherein a quel)' is compared to evel)' single portion of every single item in a
`
`database." Moulin Decl. (,237) 43. Petitioner's Declarant, however, I)rovides no
`
`NETWORK- I EXH IBIT 2005
`Googlc Inc. v. Network- I Technologics, lnc.
`[PR20 15· 00345
`
`56
`
`Page 60 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`analysis or support for this conclusory assertion which. I understand, is insufficient
`
`to satisfy Petitioner's burden in these IPR proceedings.
`
`85. One skilled in the art would understand that the "all data" clause is
`
`improper because it is:
`
`•
`
`inconsistent with how the non-exhaustive search concept is used in the IPR
`
`Patents which describes a linear exhaustive search as one where the search
`
`compares the work to all "N entries:' not all data within all " N entries" (see
`
`e.g, ' 179, 21: 10·42; 8:59.9:54); and
`
`• not part of the ordinary meaning of "non-exhaustive search" (.n'e Ex. 200 I).
`
`86. Moreover. objective sources confiml my understanding that an
`
`"exhaustive" or "brute-force" search systematically compares the work with each
`
`record in a database, not all data within each record, for example:
`
`" In computer science, brute-force search or exhaustive search, also
`
`known as generate and test, is II very general problenHolving
`
`technique that consists of systematically enumenlting all possible
`
`candidates for the solution and check ing whether each candidate
`
`salisfies the problem 's statement."
`
`Ex. 2001----each "candidate-- is checked. nOI "all data" within each candidate.
`
`57
`Page 61 of 292
`
`
`
`IPR2015-00341, IPR20 15-00145, IPR20 15-0014 7, fln(l IPR20 15-0014R
`Declaration of George Karypis
`
`87.
`
`Petitioner's own Declarant twice COnfimled my understand ing-
`
`that a
`
`"non-exhaustive" search searches a subset of "potential matches," not a subset of
`
`"all data within all potential matches" :
`
`( I ) " Because neighbor searching is computationally intensive, content
`
`recognition schemes typically employed search algorithms that increased
`
`efficiency by intelligently searching only a subset of potential matches (i.e. ,
`
`' non-exhaustive' algorithms)." Moulin Decl. (,237) 112;
`
`(2) "to maximize search efficiency, persons skilled in the an routinely employed
`
`more efficient searches that did not conduct a comparison of every single
`
`item in a database, somelimes referred to as non-exhaustive searches."
`
`Mouli n Dec!. ('237)
`
`3.
`
`88.
`
`For the reasons that I presented above, one skilled in the an would
`
`understand that the Board properly rejected Petitioner's "all data" clause.
`
`Decision ('237) at6.
`
`C.
`
`neighbor search I identifying a neighbor I neighbor I near
`neighbor ('237, ' 988, '1 79, a nd '441 patents).
`
`89. One ski lled in the an would understand that the Board properly
`
`construed a "neighbor search" and " identifYing a neighbor" as "identifying a close,
`
`but not necessarily exact or closest, match" and "neighbor" and "near neighbor" as
`
`58
`
`Page 62 of 292
`
`
`
`IPR2015-00341, IPR20 15-00145, IPR20 15-0014 7, 3n(l IPR20 15-0014R
`Declaration of George Karypis
`
`"a close, but not necessarily exact or closest, match." Decision (' 237) at 8:
`
`Decision ('988) at 7-8; Decision (' 179) at 8; Decision ('44 1) a1 7.
`
`90.
`
`Petitioner and its Declarant agree with the Board 's eonstmction of
`
`" neighbor search." See e.g. , Petition (' 179) at 6 ("The teml 'neighbor search'
`
`should be construed 10 mean ' identifying a close, but not necessarily exact,
`
`match ... ·); Moulin Decl. ('179) 45 C"neighbor search' means ' identifying a close.
`
`but not necessarily exact, match.'''); Moulin Dcpo. 250:2-5.
`
`91. One skilled in the an would understand that there are two relevant
`
`features of a neighbor search under this construction:
`
`92.
`
`Feature I: If a search necessarily identifies an exact or the closest
`
`match (I.e., the search is designed to guarantee that an exact or the closest march is
`
`identified each time the search is perfonned), it is not a neighbor or near neighbor
`
`search because it is not a search that "identiqies] a close, but not necessarily exact
`
`orclosesl, match." Rather, such a search necessarily identifi es an exact or Ihe
`
`closest match.
`
`93.
`
`Feature 2: If a search that necessarily identifies an exact or the closest
`
`match (e.g., Match I) but also identifies other matches that, by definition, are nOi
`
`the closest match (Match 2, Match 3, Match 4), the search still necessarily
`
`identifies an exact or the closest match (Match I) and therefore cannot be the
`
`claimed neighbor or near neighbor search.
`
`59
`Page 63 of 292
`
`
`
`IPR2015-00341, IPR20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`D.
`
`appro~ imat e nearest neighbor search ('237 [latent).
`
`94. As 1 noted above, the Petitioner did not identify a construction of
`
`"approximate nearest neighbor search."
`
`95. The Board preliminary determined thaI an "approximate nearest
`
`neighbor search" is a search "identifying a close match that is not necessarily the
`
`closest malch." Decision ('237) a19. One skilled in the an would understand that
`
`this construction is correct, but incomplete, as demonstrated by the '237
`
`speci fi cation. The '23 7 specification states that the claimed "approximate nearest
`
`neighbor search" is [ I) a sub-linear neighbor search that [21 does not always find
`
`the closest point to the query-
`
`i. c., does not always find the closest match:
`
`"[II One example ofa sub-linear time search is an approximate nearest
`neighbor search. [2J A nearest neighbor search always finds the closest
`
`point to the query. An approx imate nearest neighbor search does not always
`
`find the closest point to the query. For example, it might do so with some
`
`probability, or il might provide any point within some small distance of the
`
`closest point."
`
`' 237,9:12- 19.
`
`96. The first fea ture-that a "approximate nearest neighbor search" is a
`
`sub-linear time search-
`
`is not reflected in the Board 's preliminary construction
`
`and, as demonstrated below, shou ld be included in the construction. The second
`
`60
`Page 64 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`feature of the claimed "approximate nearest neighbor search" is renectcd in the
`
`Board's preliminary construction- " idenlifying a close match Ihal is not
`
`necessarily the closestlllatch." I address these two features in reversed order.
`
`I.
`
`'"'identirying a close match th at is not necessarily the closest
`match"
`
`97. This reature or "approximate nearest neighbor search" was properly
`
`adopted by the Board. A search that is guaranteed 10 return the actual closet match
`
`is not an "approximate nearest neighbor search." The ' 237 specification states that
`
`an "approx imate nearest neighbor search does not always find the closest point to
`
`the query." '23 7, 9: 15-1 6. Accordingly, a search that "always finds" (i. c. , is
`
`guaranteed to find) the closest match is not an "approx imate neareslneighbor
`
`search" while a search that is nOI guaranteed to find Ihe closest match can be an
`
`"approximate nearest neighbor search" if il identifies a close match. Sec Pel.
`
`('237) at 19 (stating that a rererence discloses an "approximate nearest neighbor
`
`search" because the search " identifies a neighbor, but not necessarily the nearest
`
`ncighbor." ).
`
`98. This understanding of "approximate nearest neighbor search" is
`
`consistent with the ordinary meaning of the phrase
`
`"Apnroximate nearest neighbor In some applications it may be
`acceptable to retrieve a 'good guess' of the nearest neighbor. In those
`
`6 1
`
`Page 65 of 292
`
`
`
`IPR2015-00341, IPR20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`cases. we can use an algorithm which doesn't guarantee to return the
`
`actual nearest neighbor in every case, in return for improved speed or
`
`memory savings."
`
`Ex. 2008
`
`(hup:llen.wikiredia.org/wikifNeares t neighbor searchNApproximate nearest neig
`
`hbor.) at 5.
`
`99.
`
`Similar to the neighbor and near neighbor searches addressed above,
`
`one skilled in the arl would understand that a search that necessarily identifies
`
`both: (I) an exact match or the closest match, and, in addition, (2) "a close match
`
`that is notnccessarily the closest match" is not an "approximate nearest neighbor
`
`search" because it is always guaranteed to identify the closest match.
`
`2.
`
`"s ubi in 1'8 rn
`
`100.
`
`It is my understanding that an inventor may act as his or her own
`
`lexicographer in defining tenns used in a patent's claims. One ski lled in the al1
`
`would understand Ihal the '237 patent defines "approximate neareSI neighbor
`
`search" as a type of sub-linear search.
`
`101 . Title: In the title of the '237 patent, the patentee identified an
`
`"approximate nearest neighbor search" as a type of sub-linear search: " Idemify ing
`
`works. using a sub-l inear time search, such as an approximate nearest neighbor
`
`~earch> for iniTialing a work-based aCTion, !luch as an action on the inlernet"
`
`'237,
`
`Title.
`
`62
`Page 66 of 292
`
`
`
`IPR 2015-00341, IPR20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`102. Abstract : It is my understanding that the abstract of a patent may be
`
`used to determine the scope of the invention. In its Abstract, the '23 7 patent also
`
`describes an "approximate nearest neighbor search" as a "sub-lincar timc search":
`
`"determining an identification of the media work ... using a sub-linear time
`
`search, such as an approximate nearest neighbor search for example." '237,
`
`Abstract.
`
`103. Specificalion: In describing methods for carrying ouI a sub-linear
`
`search of the reference data set, the '237 specification also describes an
`
`"approximate nearest neighbor search" as a type of sub-lincar search: "Qne
`
`example of a sub-l inear time search is an approximate nearest neighbor search."
`
`'237, 9:12- 14.
`
`104.
`
`In its preliminary construction, the Board did not include the sublinear
`
`feature of the claimed "approximate nearest neighbor search" based on what
`
`appears to be fau lty logic. The Board preliminarily found:
`
`63
`Page 67 of 292
`
`
`
`IPR 2015-00343, IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`We largely :tgree "ith Paten! Owner's conSll\lction, bUI note Ih:uthe
`Specific~lion refers to "(olne e~ample ofa sub-linear time search is an
`approximate nearest neighbor search" (Ex, 1001,9: I 2- 14), such thai we are
`not persuaded thai an ":1ppro~im:1tc nC:1rcSI neighbor search," mUSI be:1 sub(cid:173)
`linear search, as thptlenn has been construed above. As such, we arc
`persu~dcd that the proper construction of":1pproximatc nearcst neighbor
`search" is "idcntifying a close match that is not necess:trily thc elosest
`
`m~lch :'
`
`Decision ('237) at 9. The logic underlying the Board's reasoning appears to be as
`
`foll ows: If A is "one e~ amp l e " of B, A is not always B. In my opinion , this logic
`
`is fault y.
`
`105.
`
`If A is "one example" ofB, A is always B even though there may be
`
`examples other lhan A thai fal l within the scope ofB. If A is "one example" ofB,
`
`the scope ofB is not limited to just A (i.c., the scope of B can include C, D, and E)
`
`but A is always B. For example, a poodle is "one example" of a dog: a poodle is
`
`always a dog (thcre is no scenario whcre II poodle is not a dog) but there are other
`
`examples that fall within the scope of dog beyond poodles, i.e., terriers,
`
`Dalmatians, ete. Jusl like a '"poodle" being "one example" ofa dog must be a dog
`
`(e.g., a dog bred wilh a curly coat that is usually clipped ... ) an "approx imate
`
`nearest neighbor search" being "one example" of a "sublinear search that ..... "
`
`64
`
`Page 68 of 292
`
`
`
`IPR2015-00341, IPR20 15-00145, IPR20 15-0014 7, !In(l IPR20 15-0014R
`Declaration of George Karypis
`
`must be a sublinear search (i.e .. a "sublinear search identifying a close match that
`
`is not necessarily the closest match.")
`
`VI.
`
`' 237 patent.
`
`106.
`
`I understand that the Board instituted the ' 237 1PR based on three
`
`Grounds:
`
`• GrQlmd I : Claims I , 3- 5, 7- 9, 11 - 13, 15, 16, 21 - 25, 29, 30, 33, 37, and 38
`
`as unpatemable under 35 U.s.c. § 102(e) as amicipated by Iwamura;
`
`• Ground 2: Claims 1- 3, 5- 7, 9- 11, 13- 15, and 21 - 24 as unpatentable under
`
`35 U.s.C. § I 02(b) as anticipated by Ghias; and
`
`• Ground 3: Claims 26, 27, 34, and 35 as unpatentable under 35 U.s.c. § 103
`
`as obvious over lwamura and Chen.
`
`Decision ('237) at 21-22. I address each Ground in tum.
`
`A.
`
`' 237 G round 1: The instituted claims of the ' 237 paten I are nol
`an lici rlatcd by Iwa mura.
`
`107. The Board instituted Ground I based on the following: Claims 1, 3-~,
`
`7- 2. I I- .!J., 15. 16, 21 - fi, 29, 30, 33 , 37, and 38 as unpatentable under 35 U.S.c.
`
`§ 102(e) as anticipated by lwamura. Decision (,237) at 21 {I underlined the
`
`65
`
`Page 69 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`independent claims). Ground I fails because Iwamura does not disclose the
`
`following key elements from each instituted independent claim:
`
`• sub-linear lime search (claims 1, 5);
`
`• <lpproximllle ne(lreSI neighbor (cI<lims 9 (111(1 11);
`
`• nonexhaustive search ... to identify a ncar neighbor (claim 25); and
`
`• subl inear approximate nearest neighbor search (claim 33).
`
`[ address each in tum.
`
`I.
`
`su b-linear time search (claims elements I (b) and 5(b.2».
`
`I 08. Claims elements I (b) and 5(b.2) require a "sub-linear time search."
`
`109. As I explained above, a "sub-linear time search" is "a search whose
`
`execution lime scales with a less than linear relationship 10 Ihe size of the dala sel
`
`to be searched." Decision (,237) at7.
`
`110. One skilled in the art would understand Ihal Iwamura does not
`
`disclose a "sub-linear time search." Iwamura discloses a searching algorithm that
`
`is designed 10 be more efficient than al ternatives by comparing peak notes from the
`
`work 10 be identified with Ihe peak notes in the dalabase. Iwamurn, 6:59-60: 12:1-
`
`2. While the individual comparisons ofa work to a record in the library can be
`
`more efficient using this peak nole approach, Iwamura does nOI teach an algorithm
`
`thaI "scales with a less than lincar relationship to thc size of the dala sellO be
`
`searched" where the data set is either (a) the number of records in the database, or
`
`66
`Page 70 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`(b) even the length of an individual record. Instead, each melody in the melody
`
`database is processed as pan of the disclosed comparison and "[tJhe reference
`
`melody that gives the least difference is returned as a search result." lwamura,
`
`7:53-55.
`
`Ill. Specifically, [wamura confinns Ihat the referenced Boyer-Moore
`
`algorithm (the basis for alleged disclosure of a sub-linear search in the Petition,
`
`Declaration, and Decision) searches all items in the database and even searches
`
`"word by word from the beginning of the database to the end" and therefore cannot
`
`scale with a less than linear relationship to the size of the data set being search-
`
`i.e., it is not sublinear:
`
`" Boyer Moore (discussed below) or other string-matching algorithms
`
`do not have this kind of flexibilit y. They only search word by word
`
`from the beginning of the database to the end."
`
`Iwamura, 9:52-55.15
`
`112. The search algorithms disclosed in Iwamura do not reduce the number
`
`of records to be searched during a search (or even the data to be searched within a
`
`record) as the dataset increases. Rather, the disclosed algorithms speed up the
`
`comparison of the work to each record by matching peaks. Iwamura, 9:9-11 .
`
`Accordingly, the disclosed algorithms in I warnura search all records in the library,
`"
`
`The word-by-word comparison is valid for the worst case.
`
`67
`
`Page 71 of292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, lln(l IPR20 15-0014R
`Declaration of George Karypis
`
`and the computational time that the disclosed search takes to make such
`
`comparisons grows linearly with the number of re<:ords in the database (the
`
`relevant anal ysis) and even linearly with the data in each record. Iwarnura
`
`therefore teaches a linear search rather than the claimed "sublinear" search as the
`
`term is used in the IPR Patents, because the computational time that il takes to
`
`perfoml a search grows linearly as new data is added to the database.
`
`113. The Petition fails to satisfy its burden ofdemonstraling that Iwamura
`
`teaches a "sub-linear time search." As support fo r the "sub-linear" elements,
`
`Petitioner (and corresponding Declaration) exclusively relics on the Boyer-Moore
`
`algorithm referenced in hvamura:
`
`114. Petition: The text of the Petition does not address the sub-Imear
`
`elements or state that hvamura discloses a "sub-linear time search." Pet. (,237) at
`
`7- 10. Neither the word sublinear nor the concept appears in the text of the Petition.
`
`115. Petition Chart: In its chart, Petitioner exclusively relies on the
`
`referenced Boyer-Moore algorithm as support for the sub-li near search elements
`
`(highlighted in yellow in the passages below):
`
`Claim I(b):
`
`68
`Page 72 of 292
`
`
`
`IPR 2015-00341, IPR20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`b)d~ng. byll.e CO"llIllCf
`.ysl<"ln "" dcnlifOC:3lKIn or..,
`mOOl3 I>.lIfIr; using the ~t!I-ro
`fOal""'5 <::<uxlcd from !I.e m:d;'
`work 10 perfoml a sub.1iIror mu.:(cid:173)
`~e=hof ntrxlcd frol~ of
`idC'llufl<."d mOOl.1 wOIks 10 dcnufy 3
`neighbor: :mil
`
`'''11I\'"WlI cklmnircs an idtnlifoc:aliofl of..,
`mOOQ M.rk us-ng!l.e t:<UX led f'::I1U11:S by
`"fnll i>J;1 the c 1os.cs1 melody from the
`d:ll.1b.>Se."" hoc:h IS :I neighbor. 9;.!s..JlI.
`12:1_2. r"3nlur:t dll<:lM~S=hini usq:
`the "So).".·Moo", aIgorahm" (9:6J-6.I.
`IO:I-J).. "flich to; subme:.r (El. IOl7 :. 1).
`Ex. IQO.I al 'J n.
`
`Pet. (' 237) at 10-11.
`
`Claim 5(b.2) (Petitioner references Claim I):
`
`Petitioner IK:OrPOr.IICS the abo'-e
`dtScUssKmoflw;u" .. " rcgardi-lg eb..-. lb.
`
`2) dClCnn.,ng. by the COmplllcr
`syslan. an .:h:rnifOC:31J:>n of the
`mod .. work using the f.::t1UftS
`c_.UXled fmm the mcdl.1 ... 0 11: 10
`perfonna sub·me"," 1m., ",,"'hof
`•. «r.tCted frollJl"tS ofdcntif>ed
`medl.l " -000 to identify II neighbor.
`
`""
`
`Pet . (,237) at 12.
`
`116. Declaration: The Dcrlaration also exclusively rclies on the Boyer-
`
`Moore algorithm as suppan for the subJinear search elements:
`
`n . 11'$ my opllUon trun Iwamum funher I( OCIIts ho" Ihl$:>c3fCh can be
`
`,;ublinnr. For ~x:"npk. tw:unum disclose:'> !hat di ff<n:rn """,reh algomhms may
`
`be appli..! 10 perfonn lII~lody ",,:u<hes. "(id. al 10:2·.1). weh as Ihe "IIo)-",.), t oor~
`
`algoruhm." (N! at 9:63). "On Ilk: a' =I!<" lho. [l3o)"",·)'loo.-.:J algoriThm has II
`
`,;uhlm.:"r bdIa, lOur." E.,. 10 t7 al I.
`
`Moulin Decl. ('237) 72.
`
`117. Declaration Chan: The chan in the Declaration also exclusively relies
`
`on the Boyer. Moore algorithm:
`
`69
`Page 73 of 292
`
`
`
`IPR 2015-00343, IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`Claim reb):
`
`b) de'.munm\!. by ,I>< romrmc:T
`.~.,,''''n. :on HS.""(I<:" uon of Ib"
`",,,d,,, work u>l11~ lh< """''''al
`fcam,,,,, <xlnIC!<d from II>< ,,""' ..
`"OJk '0 r",Coml " ... t..hll<:Jr lun.
`",.",11 of Ulno,.,.j fo",,,,,,, of
`,d<lIl1iial mal", ,, 00:< 10 Identi fy "
`'\'"'Shbor: "nd
`
`1"-""",,,, d .. cI~ ,Il<....., of3 . .... "'''
`"'2'11<· '0 de,mnlll<:on ,dclltlfic311Of1 of
`II>< 0"""3 " -ork IIS'''I ,I>< "~lr.><l.d (""'Uf<S
`by "find(IIl!lIIh< c~ IIlCkxly from lb.
`~: "h",h ,) " "",ghbo)( 11.25038.
`12: 1·2 IW3nlU'" ili,d<><c, ,,,,,,,,h,,,! ",mJ;
`lhe ·&)""·~Ioorc 3I,.,."hm" t96~.
`10, 1·3). " hioh i. ",bI",.3r (b
`tol7 31 1)_
`
`Moulin Dec!. ('237) 75.
`
`Claim S(b.l) <the Declarant references Claim I l :
`
`I incorporJle my abo,"e discussioll of
`IW;J.m urJ regarding Claim lb.
`
`2) detcnnini ng. by the computer
`system. :m idellli fi ca,ion o f ,he
`media ",ork using the reaturc-s
`e.xlracled from the medIa work to
`perfonn a sub-linear ll~ scJ reh of
`eX lracted fea tures of idemi ficd
`media works to idcmify a neighbor.
`~ nd
`
`Moulin Dec!. C237) 75.
`
`118. Neither the Petition nor Declaration identifies any basis for assening
`
`that Iwamura discloses the sub-linear search clements other than the referenced
`
`Boyer-Moore algorithm. Pet. (' 237) at 10-12: Moulin Decl. (, 237) 72. My
`
`understanding is confinned by Petitioner's Declarant:
`
`o
`
`The only thi~9 you ide~tify in your
`
`24 Declaration about Iwamura that could disclose a
`
`25
`
`sublinear ti.e sea r ch is t he eoyer-Koore a190rlth=,
`
`correct?
`
`1
`
`,
`
`3
`
`Dec l a u tioll at thlt ti.,."
`
`:r·es .
`
`7.
`Page 74 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, an(l IPR20 15-0014R
`Declaration of George Karypis
`
`Moulin Depo. 82:23-83:3.
`
`119. One skilled in the an would understand that the referenced Boyer-
`
`Moore algorithm, however, docs not disclose or even address a subli near search-
`
`that is " a search whose execution time scales with a less than linear relationship to
`
`the size of the data set to be searched." Decision C237) at 7. Because lwamura
`
`itself docs 1101 state that Boyer-Moore algorithm is sublinear, the entire basis in the
`
`Petition and corresponding Declaration for the claimed sublinear clements is the
`
`single statement in the Petitioner's Declaration:
`
`"On the average the [Boyer-Moore) algorithm has a sub-liner behavior."
`
`Moulin Dec!. (,237) 72 (quoting Ex. 1017 at I). One skilled in the art would
`
`understand that this statement is not accurate with respect to the relevant sub-l inear
`
`behavior, i.e. , with respect 10 the size of the database. My understanding was
`
`con finned by Petirioner's Declarant who testified that:
`
`(I) he understood that "sub-linear" in the context of the '237 patent is
`
`based on the size of the data set searched, not the size of the query or
`
`pallenl to be matched (from the work to be identified);
`
`(2)
`
`the Boyer-Moore algorithm docs not disclose a search that is sublinear
`
`with respect to the dataset or database or even the length of a record to
`
`be search (it does not even address a database or dataset); and
`
`71
`
`Page 75 of 292
`
`
`
`IPR2015-00341, IPR 20 15-00145, IPR20 15-0014 7, !In(l IPR20 15-0014R
`Declaration of George Karypis
`
`(3)
`
`that when he wrote "which is sublinear" in his Declaration. he did not
`
`intend the Board 10 interpret "sublinear" in the context of the '237
`
`patent but instead in a different context unrelated to '137 patent.
`
`120.
`
`( I) As I noted above, Petitioner's Declaralll understood that
`
`"sublinear" in the context of the '237 patent is based on the size of the searched
`
`dataset, not the size of the query or pattern of the work to be matched (which is the
`
`correct understanding):
`
`53.
`
`r undeTSland and agree Wllh l'eI;lionITS pos;~ion ~ha( (he (enn
`
`"SlIblincar search" meanS "a :;careh whose ... :,",cution time has a subh...,ar
`
`rebtionstllp to datnb""" ,,~~ . " For instance. a lincar search of a 200-it~-m databasc
`
`would take twice as ton!! as a linenr st.-arch of 3 1000item databa:;c. By conlrJS1. a
`
`SlJbtinear sea",h of a 200-item database woul d ta ke !<:ss than twice as long as a
`
`subti near lienrch of a 1000item database. perhaps. for illslance. 1.5 timcs as long.
`
`Moulin Oed. (,237) 53.
`
`72
`Page 76 of 292
`
`
`
`IPR2015-00343 , IPR 20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`,
`
`,
`
`J
`
`you applied the definition that a .ublinear search
`
`S
`
`time has a sublin .. ar rela t ionship to t he database
`
`,
`•
`
`g
`
`I e
`
`"
`
`12
`
`Tha t
`
`i s cor r eet, yea .
`
`,
`
`be app l ied , o r are you applyinq the vronq
`
`definition?
`
`In my opinion , this 1. t he correct
`
`de fi n i t i on to be u.ed .
`
`Moulin Depo. 24:1-12.
`
`Is it the case that f or a search to be
`
`sublinear as it ' s used in the ' 2J7 patent , it ' s no t
`
`enouqh t or ! t to ha"" .. " .. cut l on tl.,.. t hat i s
`
`s .. bUn e n
`
`1n relationahip to the ai : .. of th ..
`
`pat t ern , it muat a l .o be aublinear in rela t ionship
`
`t o
`
`t he size o f
`
`t he da t Alnse?
`
`, When I read ~ subli near ~ in , say, Clai .. ~
`
`o f th .. p a t .. nt , aa \O/e
`:luat d i d ,
`I und .. ratand
`sublin .. ar to ""'an 1n relatton with the si:e ot th ..
`
`da t abase ,
`
`I t does not .ay any t hinq about 1n
`
`reiat l0n wi t h the size o t
`
`t he que r y .
`
`12
`
`13
`
`14
`
`IS
`
`16
`
`"
`
`18
`
`1 '1
`
`20
`
`~i
`
`Moulin Depo. 26: \\-21 .
`
`73
`
`Page 77 of 292
`
`
`
`IPR2015-00343 , IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`•
`
`, Would it be .. ronq ,
`
`then, to asse ..... heth"r
`
`5
`
`a .earch i • • ~blinear by app l yinq a de f ini ti on t hat
`
`6
`
`1
`
`,
`
`.ald, "I t ' s .~blinear if t his execution tl_ has a
`
`.ubline.r rel.tion.hip to the .ize of the query or
`
`, It would not be very relevant, Again,
`
`10
`
`.... th"lUtlc.lly, It c.n be don" .
`
`F:.verythinq c.n be
`
`11
`
`12
`
`done. But it "ould not be r"levant, from an
`
`"nllineerinll vie"Poin t, f or an .pplicat ion 11ke this.
`
`Moulin Oepo. 25:4-12.
`
`"
`
`~
`
`J
`
`,
`
`8
`
`..
`
`IAt '. aUlime that the Pat.nt Trial al'ld
`Appul Board .... pr.nnt...:l with prior art that
`
`pre •• nt.d a .earch t h.t .... line.r wnh nspect to
`
`tne .1:e of the dAubAn. but it .... . ubhn .... r w:.th
`
`, P.ople say it'. a l1n.ar ••• rch, all51n,
`
`becau •• it'. in r.lation 'With the .1:e ot the
`
`d.ot.t>a... . And as you lUSt .aid, that cotepl .. ><1ty 15
`
`10 nUl lin •• r: .0 ","opl. would .. y it h
`
`• lln •• r
`
`,
`
`" 14
`
`or t~,~ 'I.~C<~ •
`
`."hid, h \I~"eally n"t the
`
`15
`
`par....,t.t of -- the rel.· ... nt pu .... t.r.
`
`Moulin Oepo. 26:25-27: 15.
`
`74
`Page 78 of 292
`
`
`
`IPR2015-00343 , IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`, Is i ~ ~he cilse ~ ha t it we had a pie~ of
`
`"
`
`17
`
`prlo~ art thaI: was linea~ wIth ,,,spect ~o ~h" sl:e
`
`IS
`
`of th" d..t.tilbase bu~ sublinea, wi~h '''.p"ct to ~he
`
`1~
`
`si:e ot th .. qu .. ry Or ~h .. pattern. thilt that prior
`
`20
`
`~l
`
`"
`
`~3
`
`2~
`
`ar~ would nO ~ ~ .. ach a sUblin .. ar ."arch as i~ · . us .. d
`
`1n Claim ~5?
`
`,
`
`1n term. in r"la~lon ~o ~he size of ~he da~abas".
`
`thAt would b.. A -- A linear seArch.
`
`Moul in Depo. 27;16-24.
`
`~
`
`Let's ilSSume w,,'ve qot A pi.c. o f prior
`
`S art that scales at a sub linear r .. lationship with th ..
`
`6
`
`7
`
`8
`
`':I
`
`s1.e o f ~ he pattern Or query but it scales a t a
`
`11nea, ,,,lationship with the size of th" database
`
`~hat ' l t...in9 search"d .
`
`lIould that prior art de"",nsrrat .. or
`
`10
`
`disclose a lublin"ar sea r ch as i~'s used in th"
`
`,
`
`1~
`
`L5
`
`~ntion of ~ subll~ .. ar ," it m .. ans 1n terms o f ~he
`
`d..t.tAbase s1:e .
`
`It do". not lay it explicitly: it 's
`
`16 my inference based on my knowl"dge ilnd my e"pertise .
`
`Moulin Depo. 28:4-16.
`
`75
`Page 79 of 292
`
`
`
`IPR 2015-00343, IPR20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`17
`
`comp.1Ired to tl:e size of the dataset bein<;l searcl:ed :
`
`yes .
`
`o
`
`20
`
`"
`
`A. .. d then ,'ou wrote this clai .. chart In
`
`23
`
`part of the claim: rl<;lht?
`
`"
`Moulin Depo, 77:14-14.
`
`A
`
`Tha~'. correct, yes .
`
`121,
`
`(2) Petitioner' s Declarant confimled my understanding-
`
`that the
`
`Boyer-Moore algorithm referenced in Iwamura does not disclose a search that is
`
`subl inear with respect to the database size (i.e. , the size of the data set to be
`
`scarched)-it does not even address a database (Moulin Depo, 53: 19-22 ("There's
`
`no database in Boyer-M oore.")}-but instead has a relationship to the size of the
`
`qucry pattern from the work to be identificd:
`
`lQ
`
`BoY"r- H<>ore a19<,rlthlo wit h r .. ~~ct to the size o f
`
`20
`
`"
`
`22
`
`'lJ
`
`24
`
`the dataset beln<;l searched?
`
`, It ' s described here . So , a<;lain , thIs I ,
`
`if you look at th .. worst case , I Is N minus patlen,
`
`th<?n yo," (>btaln It _ A .. 1 ~,,1<1 , It "Ill t"!' a l1n"' .. r
`
`telatlvnshlp .
`
`7.
`Page 80 of 292
`
`
`
`IPR2015-00343 , IPR 20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`Moulin Depo. 61 : 18-24; 44:20-46:6: 59:6-9: 61 :25-62:9: 68 :25-69:4.
`
`122.
`
`(3) Petitioner's Declarant confirmed my understanding-
`
`that the
`
`statement in his Declaration-Petitioner's only suppon for the sub-linear
`
`clements-was wrong. He testified that when he wrote:
`
`·On th~ 3\era.g~ tht [Boyer-Moore] algomhm has a
`
`Sl,lblin~arbeha\IOl,lr. · Ex. tOl 7 at I.
`
`(Moulin Decl . ('237) 72) and wrotejusl a few pages earlier:
`
`53.
`
`I understand and ag .... e with P ..... ition ...... s position matlhc I~nn
`
`· sublinear search" means "3 search whose execution time h3s 3 ~ubhnear
`
`rclahO.bll1p to oolaha,c ~,u. · For in<lane~., linear SC":Irch of a 200-ilCm wtabase
`
`(Moulin Decl. ('237) 53), he was not trying to convey that the Boyer-Moore
`
`algorithm was sublinear or " has a sublinear behavior" in the context of the '23 7
`
`patent - i.e., "has a sublinear relationship to the database size":
`
`120
`
`121
`
`22
`
`23
`
`Q When you wrote this , were you tryinq to
`
`convey that searching using the Boyer-Moore
`
`algorithm would be .ub~inear with respect to t he
`
`size of the dataset being searched?
`
`A
`
`~Io .
`
`I did not -- no.
`
`Moulin Depo. 74:20-24; 74:8-12 .
`
`77
`Page 81 of 292
`
`
`
`IPR2015-00343 , IPR 20 15-00345, IPR20 15-0034 7, an(l IPR20 15-0034R
`Declaration of George Karypis
`
`,
`
`Q
`
`1(1
`
`11
`
`1~
`
`"
`
`14
`
`IS
`
`16
`
`convey1n':! t.o t.he reader t.hat. t. he Boyer-Moore
`
`Ill90rithm is sllbltnellr w!th leS~ct to the d:e of
`
`t.he dataset be1n,:! sellrched?
`
`A
`
`No. All I do is quote a part of a paper
`
`th"t ~hOW3 why thot "190r1thm 13 much f"3ter th,,~
`
`brute force. That's all I ' m doin9' You ' re
`
`inferrinq thin'ls I ' m not SIlyinq or writinq .
`
`Moulin Oepo. 69:9-16.
`
`9
`
`10
`
`11
`
`"
`
`14
`
`15
`
`16
`
`17
`
`18
`
`In p .. raqraph 72. are you representin<,i to
`
`the Board th.t it ' s your underst.ndinq th.t the
`
`Boyer-Moore .l':!orithal has a sublinear bel ... vier with
`
`A
`
`110. This is jua. a quote ef another paper
`
`discussin':! Boyer-Moore . This Boyer-Moore alqorithm
`
`haa been uaed in a variety of centexts. includinq .
`
`of course. content rec09nition.
`
`I'm 51r.-.ply quotinq
`
`fr_ another pa~r here .
`
`I ' m not presentin"
`
`anything about what you aaked .
`
`Moulin Ocpo. 66:9-18.
`
`2)
`
`When yeu wrete this .enUnc. here on
`
`~5
`
`lookinq at this mlqht think tha. you mean. that a
`
`1
`
`2
`
`(t.e Boye~-!ioore alqorit~_,. was subl:.,..ea" as used In
`
`the patent claim?
`
`I dld.~' t t hink of it tblt .... y. no .
`
`Moulin Oepo. 75:23-76:3.
`
`78
`
`Page 82 of 292
`
`
`
`IPR2015-00343 , IPR 20 15-00345, IPR20 15-0034 7, !In(l IPR20 15-0034R
`Declaration of George Karypis
`
`0
`
`And wh .. n ,00 wrOt .. thia, w .. re ,00 tryinq
`
`"
`"
`<0 convey <0 "" Board that the Boyer -Hoo re
`alqorithm " 0"" that , H you uu, ". it ' s s",hHnen
`"
`" with r,upeCt to the .i:e of the d.ot.tal:>ll.se7
`, '0.
`"
`
`Moulin Depo. 67:17-21.
`
`'0.
`
`123. Consistent with my understanding, Petitioner' s Declarant clari
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
