`
`By:
`James J. Elacqua
`james.elacqua@skadden.com
`(650) 470-4510
`
`Paper No. 20
`Date Filed: December 14, 2015
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`________________
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`________________
`
`Google Inc.
`Petitioner,
`v.
`Network-1 Technologies, Inc.
`Patent Owner.
`________________
`
`Case IPR2015-00345
`U.S. Patent 8,205,237
`________________
`
`
`
`PETITIONER'S REPLY TO
`PATENT OWNER'S RESPONSE TO PETITION
`
`
`
`
`
`
`
`
`
`TABLE OF CONTENTS
`
`IPR2015-00345
`Patent No. 8,205,237
`
`Page
`
`Table of Authorities ................................................................................................. iii
`
`Exhibit List ................................................................................................................ iv
`
`I.
`
`Introduction ...................................................................................................... 1
`
`II.
`
`Claim Interpretation ......................................................................................... 2
`
`A.
`
`Patent Owner Misinterprets the Board's Construction of
`"Sublinear Search" ................................................................................ 2
`
`B. An "Approximate Nearest Neighbor Search" Need Not Be
`"Sublinear" ............................................................................................ 4
`
`1.
`
`2.
`
`The Specification Does Not Demand Sublinearity ..................... 4
`
`The Claims Confirm that Sublinearity Is Not Required ............. 5
`
`III. Ground A: Iwamura Anticipates Claims 1, 3–5, 7–9, 11–13, 15, 16,
`21–25, 29, 30, 33, 37, and 38 .......................................................................... 6
`
`A.
`
`Iwamura Discloses "Non-Exhaustive Search" ...................................... 7
`
`1.
`
`Iwamura Explicitly Identifies Its Search as Non-
`Exhaustive ................................................................................... 7
`
`2.
`
`Iwamura Does Not Consider All "Possible Matches" ................ 8
`
`(a) The "Possible Matches" in Iwamura Are Melody
`Segments, Not Full Songs ................................................ 9
`
`(b)
`
`Iwamura Does Not Consider All Melody
`Segments, and Therefore Discloses Non-
`Exhaustive Search ........................................................... 12
`
`Iwamura Discloses "Approximate Nearest Neighbor Search" ........... 13
`
`Iwamura Discloses "Sublinear Search" ............................................... 15
`
`-i-
`
`B.
`
`C.
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`
`1.
`
`2.
`
`Contrary to the Arguments Raised in Network-1's
`Response, Iwamura Discloses "Sublinear Search" ................... 16
`
`Petitioner's Arguments Regarding "Sublinear Search"
`Are Both Timely and Responsive ............................................. 18
`
`IV. Ground B: Ghias Anticipates Claims 9–11, 13–15, and 23–24 .................... 20
`
`A. Ghias Discloses "Approximate Nearest Neighbor Search" ................ 20
`
`1.
`
`2.
`
`Ghias's Subsequent Searches Do Not Always Consider
`the Closest Match ...................................................................... 21
`
`Ghias Cannot Always Identify the Closest Match in a
`Group of Close Matches ........................................................... 22
`
`V. Ground C: Iwamura and Chen Render Obvious Claims 26, 27, 34, and
`35 ................................................................................................................... 24
`
`A. Dr. Karypis's Testimony Includes Attorney Argument Which
`Should Be Given Little Weight ........................................................... 24
`
`VI. Conclusion ..................................................................................................... 25
`
`
`
`
`-ii-
`
`
`
`TABLE OF AUTHORITIES
`
`CASES
`
`IPR2015-00345
`Patent No. 8,205,237
`
`Page
`
`Belden Inc. v. Berk-Tek LLC,
`610 Fed. Appx. 997 (Fed. Cir. 2015) ............................................................ 19
`
`Digital-Vending Services International., LLC v. University of Phoenix, Inc.,
`672 F.3d 1270 (Fed. Cir. 2012) ....................................................................... 6
`
`Facebook, Inc. v. Pragmatus AV, LLC,
`582 F. App'x 864 (Fed. Cir. 2014) ................................................................... 5
`
`Gateway Equipment Corp. v. United States,
`247 F. Supp. 2d 299 (W.D.N.Y. 2003) .......................................................... 25
`
`Phillips v. AWH Corp.,
`415 F.3d 1303 (Fed. Cir. 2005) ....................................................................... 5
`
`Ramirez v. Salvation Army, No. C06-0631,
`2008 WL 670153 (N.D. Cal. Mar. 6, 2008) .................................................. 25
`
`Renishaw PLC v. Marposs Societa' per Azioni,
`158 F.3d 1243 (Fed. Cir. 1998) ....................................................................... 5
`
`INTER PARTES REVIEWS
`
`Canon Inc. v. Intellectual Ventures II LLC,
`IPR2014-00631, Paper 50 (August 19, 2015) ............................................... 19
`
`Nintendo of America Inc. v. Motion Games, LLC,
`IPR2014-00164, Paper 51 (May 15, 2015) ................................................... 19
`
`
`
`
`
`-iii-
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`
`EXHIBIT LIST
`
`U.S. Patent No. 8,205,237 to Cox
`
`Prosecution History of U.S. Patent No. 8,205,237
`
`Visual Summary of Petition Grounds
`
`December 3, 2014 Declaration of Dr. Pierre Moulin
`
`Curriculum Vitae of Dr. Pierre Moulin
`
`Sunil Arya, et al., "An Optimal Algorithm for Approximate Nearest
`Neighbor Searching in Fixed Dimensions" ("Arya")
`
`Christian Böhm, et al., "Efficient Similarity Search in Digital
`Libraries" ("Böhm")
`
`U.S. Patent No. 7,444,353 ("Chen")
`
`U.S. Patent No. 6,970,886 ("Conwell")
`
`U.S. Patent No. 5,874,686 ("Ghias")
`
`U.S. Patent No. 6,597,405 ("Iggulden")
`
`U.S. Patent No. 6,188,010 ("Iwamura")
`
`U.S. Patent No. 6,505,160 ("Levy")
`
`U.S. Patent No. 6,098,106 ("Philyaw")
`
`U.S. Patent No. 7,743,092 ("Wood")
`
`Prosecution History of U.S. Patent App. No. 09/438,469
`
`Timo Raita, "Tuning the Boyer–Moore–Horspool String Searching
`Algorithm"
`
`Aristides Gionis, et al., "Similarity Search in High Dimensions via
`Hashing"
`
`Plaintiff Network-1 Technologies, Inc.'s Responses to Defendants
`Google, Inc. and YouTube, LLC's First Set of Interrogatories (Nos.
`
`-iv-
`
`1001
`
`1002
`
`1003
`
`1004
`
`1005
`
`1006
`
`1007
`
`1008
`
`1009
`
`1010
`
`1011
`
`1012
`
`1013
`
`1014
`
`1015
`
`1016
`
`1017
`
`1018
`
`1019
`
`
`
`
`
`1–4) in Network-1 Technologies, Inc. v. Google, Inc., et al.
`(S.D.N.Y. Case No. 14-cv-2396-PGG)
`
`1020
`
`Transcript of the November 12, 2015 Deposition of Dr. George
`Karypis
`
`IPR2015-00345
`Patent No. 8,205,237
`
`-v-
`
`
`
`
`
`
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`
`I.
`
`INTRODUCTION
`
`The Board has instituted Inter Partes Review of U.S. Patent No. 8,205,237
`
`("the '237 patent") (Ex. 1001) on the grounds that claims 1–4, 5–8, 9–12, 13–16,
`
`21–24, 25–27, 29, 30, 33–35, 37, and 38 (independent claims bolded) are
`
`anticipated and/or obvious in view of U.S. Patent Nos. 6,188,010 ("Iwamura"),
`
`5,874,686 ("Ghias"), and 7,444,353 ("Chen"), as summarized in the following
`
`table:
`
`Ground
`
`A
`
`B
`
`C
`
`'237 Patent Claims
`1, 3–5, 7–9, 11–13, 15, 16, 21–25, 29, 30,
`
`33, 37, and 38
`1–3, 5–7, 9–11, 13–15, and 21–24
`26, 27, 34, and 35
`
`Grounds for Trial
`Anticipated by Iwamura
`
`Anticipated by Ghias
`Obvious over Iwamura
`
`and Chen
`
`
`The parties dispute whether Iwamura and Ghias disclose one element—(1)
`
`"approximate nearest neighbor search"—and whether Iwamura discloses two
`
`additional limitations—(2) "non-exhaustive search"; and (3) "sublinear search."
`
`Patent Owner's expert witness concedes that at least the first two limitations were
`
`well known in the prior art. Ex. 1020, 25:22–26:8 (agreeing that "non-exhaustive
`
`searching was a concept known in the art"); see Ex. 1020, 78:24–79:6 (agreeing
`
`that "Dr. Cox doesn't purport to have invented neighbor searching"). Indeed, Ghias
`
`and Iwamura disclose all three limitations, and therefore anticipate and/or render
`
`obvious independent claims 1, 5, 9, 13, 25, and 33. Additionally, because Patent
`
`
`
`1
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`Owner does not dispute any further limitations of the instituted dependent claims,
`
`Ghias and Iwamura anticipate and/or render obvious the instituted dependent
`
`claims for the reasons discussed in the Petition and recognized by the Board in its
`
`Institution Decision.
`
`II. CLAIM INTERPRETATION
`
`A.
`
`Patent Owner Misinterprets the Board's Construction of
`"Sublinear Search"
`
`In its Institution Decision, the Board construed "sublinear search" as "a
`
`search whose execution time scales with a less than linear relationship to the size of
`
`the data set to be searched." Paper No. 6 at 7 (emphasis added). To escape the
`
`prior art, Patent Owner argues that "the size of the data set" must refer to "the
`
`[number of] records in the data set being searched." Paper No. 17 at 2–7. To reach
`
`this conclusion, Patent Owner asserts that the term can only refer to either (1) "the
`
`[number of] records in the data set being searched; or (2) the length of an individual
`
`record in the database." Paper No. 17 at 2; Ex. 2005, ¶ 61. This is a false choice.
`
`Instead, "size" should simply be afforded its plain meaning: the amount of disk
`
`space a data set occupies. Indeed, when questioned, Patent Owner's expert, Dr.
`
`Karypis, conceded that disk space "can also be an appropriate interpretation" of the
`
`size of the data set. See Ex. 1020, 105:13–106:6.
`
`Patent Owner also misrepresents the only intrinsic support for its argument.
`
`2
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`Patent Owner and Dr. Karypis contend that sublinearity must be evaluated on the
`
`basis of the number of records in a data set because the specification discloses "a
`
`linear search of all N entries" in a "database containing N vectors." Paper No. 17 at
`
`3–4 (emphasis modified); Ex. 2005, ¶ 69 (quoting Ex. 1001, 8:54–63, 21:14–23).
`
`However, Dr. Karypis admitted that, as used in the specification, "linear search" is
`
`simply a synonym for a "sequential search" of all records, not—as pertains to the
`
`claim language at issue—a reference to whether or not a work has sublinear time
`
`complexity. Ex. 1020, 69:22–70:20, 66:6–12. Thus, the intrinsic evidence Patent
`
`Owner cites does not even relate to sublinearity, let alone explain how to evaluate
`
`it.
`
`Contrary to Patent Owner's position, the specification explains that "size"
`
`refers to the amount of disk space a data set occupies. The specification describes a
`
`database containing 100,000 commercials with 900 frames each, one in ten of
`
`which are stored in the database, for a total of 9,000,000 frames. Ex. 1001, 21:14–
`
`23. The specification explains that the "size" of the database is not the number of
`
`records (100,000 commercials), but the total number of frames within all the
`
`commercials (9,000,000 frames). See Ex. 1001, 21:14–23 ("[I]ts size is . . . nine
`
`million."). The specification further measures this "size" in terms of disk space.
`
`Ex. 1001, 21:24–26 (for a database of 9,000,000 frames, "if each vector is 1 Kbyte,
`
`then the storage requirement is 9 Gigabytes," i.e., 9,000,000 * 1 Kbyte) (emphasis
`3
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`added); Ex. 1020, 104:13–105:8. When asked to interpret this evidence, Dr.
`
`Karypis conceded that the amount of disk space a data set occupies is the
`
`appropriate representation of data set size. Ex. 1020, 105:6–12. Thus, Dr. Karypis
`
`acknowledges and the specification confirms that the "size" of a data set for
`
`purposes of evaluating sublinearity is the amount of disk space it occupies.
`
`B. An "Approximate Nearest Neighbor Search" Need Not Be
`"Sublinear"
`
`1.
`
`The Specification Does Not Demand Sublinearity
`
`The parties agree that, in general, an "approximate nearest neighbor
`
`search . . . doesn't have to be [sublinear]." Ex. 1020, 94:22–95:6 (emphasis added).
`
`Patent Owner argues, however, that two isolated statements in the specification
`
`redefine the term in the context of this patent:
`
`(1) "a sub-linear time search, such as an approximate nearest neighbor
`
`search" Ex. 1001, Abstract (emphasis added); Ex. 1001, Title.
`
`(2) "One example of a sub-linear time search is an approximate
`
`nearest neighbor search." Ex. 1001, 9:12–14 (emphasis added).
`
`Because "a poodle is always a dog . . . but there are other examples that fall within
`
`the scope of dog beyond poodles, i.e., terriers," Patent Owner interprets the above
`
`statements to require that all "approximate nearest neighbor searches" are
`
`"sublinear." Ex. 2005, ¶ 105.
`
`As the Board has recognized, Paper No. 6 at 9, the above statements do not
`
`4
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`"rise[] to the 'exacting' level of lexicography or disavowal" required to redefine an
`
`"approximate nearest neighbor search" as necessarily "sublinear." Facebook, Inc.
`
`v. Pragmatus AV, LLC, 582 F. App'x 864, 868 (Fed. Cir. 2014) (only "clear and
`
`unmistakable statements" constitute lexicography); see also Renishaw PLC v.
`
`Marposs Societa' per Azioni, 158 F.3d 1243, 1249 (Fed. Cir. 1998). They express
`
`only that an "approximate nearest neighbor search" could be configured to operate
`
`in a "sublinear" manner, not that it must be. Patent Owner's own analogy illustrates
`
`this: a dog may be called an example of a pet (because a dog can be a pet), but not
`
`all dogs are pets (because wild dogs are not pets). Similarly, an "approximate
`
`nearest neighbor search" may be called an example of a "sublinear" search (because
`
`it can operate in a "sublinear" manner), but not all "approximate nearest neighbor
`
`searches" are "sublinear" (because they can also operate in a linear manner).
`
`2.
`
`The Claims Confirm that Sublinearity Is Not Required
`
`Patent Owner's proposed construction violates the doctrine of claim
`
`differentiation. Claim 33 recites "a sublinear approximate nearest neighbor
`
`search," but Claims 9 and 12 recite the same language without the "sublinear"
`
`limitation. Ex. 1001, Cl. 9, 12, 33. Interpreting all "approximate nearest neighbor
`
`searches" to be "sublinear" would thus improperly (1) render the "sublinear"
`
`limitation in Claim 33 superfluous; and (2) equate the terms "sublinear approximate
`
`nearest neighbor search" and "approximate nearest neighbor search." See Phillips
`
`5
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`v. AWH Corp., 415 F.3d 1303, 1314 (Fed. Cir. 2005) ("[T]he claim in this case
`
`refers to 'steel baffles,' which strongly implies that the term 'baffles' does not
`
`inherently mean objects made of steel."); Digital-Vending Servs. Int'l., LLC v.
`
`Univ. of Phoenix, Inc., 672 F.3d 1270, 1274–75 (Fed. Cir. 2012) (declining to
`
`construe "registration server" as "free of content" to avoid vitiating language in
`
`another claim reciting a "'registration server being further characterized in that it is
`
`free of content'" because "'claims are interpreted with an eye toward giving effect to
`
`all terms in the claim'" (emphasis modified) (citations omitted)).
`
`III. GROUND A: IWAMURA ANTICIPATES CLAIMS 1, 3–5, 7–9, 11–13,
`15, 16, 21–25, 29, 30, 33, 37, AND 38
`
`The Board instituted review on the ground that Iwamura anticipates claims 1,
`
`3–5, 7–9, 11–13, 15, 16, 21–25, 29, 30, 33, 37, and 38 (independent claims bolded).
`
`Patent Owner contends only that Iwamura does not disclose only (1) the "non-
`
`exhaustive search" element of independent claim 25; (2) the "approximate nearest
`
`neighbor search" element of independent claims 9, 13, and 33; and (3) the
`
`"sublinear search" element of independent claims 1, 5, and 33. Paper No. 17 at 11,
`
`19, 25, 40. In fact, Iwamura discloses these elements and anticipates independent
`
`claims 1, 5, 9, 13, 25, and 33. Patent Owner does not dispute that Iwamura
`
`discloses all additional limitations of the instituted claims that depend from
`
`independent claims 1 (claims 3, 21–22), 5 (claims 7–8), 9 (claims 11–12, 23–24),
`
`6
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`13 (claims 15–16), 25 (claims 29–30), and 33 (claims 37–38). Thus, Iwamura
`
`additionally anticipates these dependent claims.
`
`For the Board's convenience, the following table summarizes the claim
`
`limitations at issue in this ground:
`
`Claim Element
`"non-exhaustive search"
`
`Recited In Claims
`25, 29–30
`
`"approximate nearest neighbor search"
`
`9, 11–12, 13, 15–16, 23–24, 33, 37–38
`
`"sublinear search"
`
`1, 3, 5, 7–8, 21–22, 33, 37–38
`
`A.
`
`Iwamura Discloses "Non-Exhaustive Search"
`
`Claims 25 and 29–30 recite a "non-exhaustive search." Iwamura discloses
`
`this limitation.
`
`1.
`
`Iwamura Explicitly Identifies Its Search as Non-Exhaustive
`
`At a minimum, Iwamura discloses "non-exhaustive search" because it
`
`specifically identifies its "peak notes" search as such:
`
`Peak notes are approximately 20% of the total number of notes in a
`
`typical melody. That means search speed using peak notes is 20% of
`
`a brute force search . . . .
`
`Ex. 1012, 9:7–11 (emphasis added). The terms "brute force search" and
`
`"exhaustive search" are synonymous. Ex. 2005, ¶ 82 ("an 'exhaustive search' . . . is
`
`also referred to as using 'brute force'" (emphasis added)); Ex. 2001, 1 ("brute force
`
`7
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`search or exhaustive search . . . is a very general problem solving technique"
`
`(emphasis modified)); Paper No. 6 at 7 ("an example . . . shows the ordinary
`
`meaning of 'exhaustive search' or 'brute force search.'" (emphasis added)). Any
`
`search other than a "brute force search" (i.e., an "exhaustive search") is a "non-
`
`exhaustive search." E.g., Paper No. 6 at 7 ("To the extent that Dr. Moulin testifies
`
`that a non-exhaustive search 'encompassed anything other than a brute force
`
`search,' . . . we agree." (emphasis added)); Ex. 1004, ¶ 43. Thus, because
`
`Iwamura's "peak search" is not a "brute force search" (i.e., an "exhaustive search"),
`
`it is "non-exhaustive."
`
`2.
`
`Iwamura Does Not Consider All "Possible Matches"
`
`In Iwamura, each melody is represented by a string of numbers
`
`corresponding to "relative pitch data" within the work (e.g., a sequence of five
`
`notes, 54321). To identify a query melody, Iwamura calculates the absolute
`
`difference between the relative pitch data of the query and the relative pitch data of
`
`melody segments within reference songs (e.g., comparing a five note query to
`
`multiple five note sequences within a reference song). Ex. 1012, 7:22–48. Rather
`
`than compare a query to every melody segment in a reference, however, Iwamura
`
`only compares segments where the peaks (i.e., "note[s] that [are] higher than . . .
`
`8
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`each of the adjacent notes") align.1 Ex. 1012, 6:60–64, 7:52–54. For instance, if
`
`Iwamura were to search for the query, 54321, in the reference 622221654321, it
`
`would only compare 54321 to 62222 and 65432 (bold numbers indicate peak
`
`notes). Ex. 1020, 130:24–133:1, 133:23–134:4, 135:11–14.
`
`(a) The "Possible Matches" in Iwamura Are Melody
`Segments, Not Full Songs
`
`Patent Owner's argument that Iwamura considers all "possible matches"—
`
`and therefore does not disclose a "non-exhaustive search"—hinges on the false
`
`premise that the "possible matches" in Iwamura are full songs. Paper No. 17 at 25–
`
`26 (citing Ex. 2005, ¶ 163). In fact, Iwamura matches short query melodies to short
`
`melody segments within longer reference songs. See, e.g., Ex. 1012, 3:32–34 &
`
`Fig. 4; Ex. 2006, 377:20–379:13. Indeed, as Dr. Karypis' diagrams demonstrate,
`
`Ex. 2005, ¶¶ 160–62, (shown below with purple annotations) Iwamura computes
`
`the "total absolute difference" between a query melody segment and individual
`
`reference melody segments, Ex. 1012, 7:21–50.
`
`
`1 A peak note need not be the highest note in a reference, just one that is higher
`
`than its adjacent notes. Ex. 1012, 6:60–64. For instance, in the reference
`
`0123234565, both 3 and 6 are peak notes, because they are higher than the
`
`adjacent notes. See Ex. 1012, 6:60–64.
`
`9
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`
`
`Ex. 2005, ¶¶ 160–62. Iwamura never evaluates which song provides the best
`
`
`
`overall match by, for instance, summing or averaging these absolute differences
`
`over the length of a song. Ex. 1012, 7:22–50. Rather, it simply "return[s] the score
`
`of the best match, [i.e.,] the best scoring subsegment or the [lowest] scoring
`
`subsegment." Ex. 1020, 113:11–114:5 (emphasis added). Therefore, the "possible
`
`matches" of Iwamura are the melody segments, not the songs themselves.
`
`Dr. Karypis' testimony regarding the below diagram, depicting query
`
`"54321" and reference "005432100543210054321005432100," confirms this.
`
`
`
`Ex. 1020, 146:7–147:23 & Exh. 9. Dr. Karypis explained that each instance of the
`
`"54321" melody segment within the reference song was a "match." Ex. 1020, 147:
`
`2–17. In total, Dr. Karypis counted "four portions that match" "within the
`
`reference [song]." Ex. 1020, 147:18–23 (emphasis added).
`
`Moreover, the rationale underlying Patent Owner's assertion that songs are
`
`"possible matches"—the fact that Iwamura displays the title of the song containing
`
`10
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`an identified match, see Paper No. 17 at 25–26—is improper because it causes the
`
`exhaustivity of a search to depend on what action a system takes after performing
`
`the search. According to Patent Owner, if a content identification system is
`
`configured to display a song title to the user, then songs are "possible matches."
`
`Following Patent Owner's logic, if the same system were configured to display the
`
`identity of a melody segment, melody segments would be "possible matches." If
`
`that system considers all songs but not all melody segments, the first of these
`
`configurations would be exhaustive, while the second would be non-exhaustive.
`
`Thus, the same search algorithm could be considered "exhaustive" or "non-
`
`exhaustive" depending on how its results are reported. Such a capricious definition
`
`cannot be a sound construction.
`
`Further, in view of the Board's construction of "non-exhaustive search,"
`
`defining songs as "possible matches" would conflict with Iwamura's self-
`
`identification as "non-exhaustive." See Ex. 1012, 9:7–11 ("search speed using peak
`
`notes is 20% of a brute force search"); Ex. 2005, ¶ 82; Ex. 2001, 1; Paper No. 6 at
`
`6–7. Iwamura considers all reference songs. Paper No. 17 at 25–26; Ex. 2005,
`
`¶ 313. If songs were "possible matches," Iwamura would therefore consider all
`
`"possible matches." Thus, Iwamura would be a self-described non-exhaustive
`
`search that nevertheless considers all possible matches. This contradiction cannot
`
`stand, and therefore melody segments are "possible matches."
`11
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`(b) Iwamura Does Not Consider All Melody Segments, and
`Therefore Discloses Non-Exhaustive Search
`
`Because Iwamura does not consider all melody segments, it discloses "non-
`
`exhaustive" search. Iwamura's "peak search" increases search speed by comparing
`
`a query only to reference melody segments where peaks align. For instance, as
`
`depicted below, the reference 622221654321 contains 16 melody segments that are
`
`"possible matches" for the query 54321. However, Iwamura's "peak notes" search
`
`would only compare the query to the two melody segments with aligning peak
`
`notes: "comparison number 5, and . . . comparison number 11," highlighted below.
`
`Ex. 1020, 131:7–12, 132:16–133:1; see also Ex. 1020, 123:7–125:24.
`
`
`
`Reference
`
`Aligning
`Peak Notes
`
`12
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`Ex. 1020, Exh. 9 (annotations added). Moreover, Iwamura skips not only lower
`
`quality matches (with a greater absolute difference); but also higher quality
`
`matches (with a lower absolute difference) such as Comparison Nos. 3–4, 13, and
`
`16; and even the highest quality match, Comparison No. 12. Ex. 1020, 132:16–
`
`133:1, 134:5–135:10. Thus, as Dr. Karypis acknowledges, Iwamura "skip[s] . . .
`
`comparisons," Ex. 2005, ¶ 162, and "reduc[es] the number of comparisons made
`
`between the work and a specific record," Ex. 2005, ¶ 159, and is therefore non-
`
`exhaustive.
`
`Iwamura additionally discloses several embodiments that further reduce the
`
`number of melody segments considered. For instance, Iwamura discloses that
`
`"unimportant portions" and "repeated pattern[s]" of a reference "can be omitted"
`
`from the search. Ex. 1012, 9:36–51 & Fig. 14. These embodiments further
`
`confirm that Iwamura discloses a "non-exhaustive search."
`
`B.
`
`Iwamura Discloses "Approximate Nearest Neighbor Search"
`
`Claims 9, 11–12, 13, 15–16, 23–24, 33, 37–38 recite an "approximate nearest
`
`neighbor search." Iwamura discloses this limitation.
`
`As explained in detail above (p. 4–5), the Board's construction of
`
`"approximate nearest neighbor" search does not require a sublinear search; it
`
`requires at most that the search does not always identify the closest match.
`
`Consistent with this construction, Iwamura's "peak notes" search does not
`
`13
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`necessarily even consider the closest match, let alone identify it. Rather, this search
`
`only compares a query to reference melody segments where the peaks align. Ex.
`
`1012, 7:52–54; Paper No. 17 at 29–30; Ex. 2005, ¶¶ 162–63. If the closest
`
`matching melody segment does not occur at a peak alignment, Iwamura will neither
`
`consider nor locate it. See Ex. 1020 at 128:13–135:14, Exh. 9.
`
`For instance, in the diagram depicted above (p. 12), which reflects the 16
`
`possible comparisons of the query 54321 to the reference 622221654321 (bold
`
`numbers indicate peak notes), a lower "total absolute difference" indicates a closer
`
`match. Ex. 1012, 7:38–39. Comparison No. 12, which has a "total absolute
`
`difference" of zero, is the closest match. Ex. 1020, 134:5–17; see also Ex. 1020,
`
`151:20–152:5. But Iwamura will never perform Comparison No. 12, because it
`
`does not occur at a peak alignment. Ex. 1020, 134:5–135:10 & Exh. 9. Rather,
`
`Iwamura will perform only Comparison Nos. 5 and 11, which are inferior not only
`
`to Comparison No. 12, but also to Comparison Nos. 3–4, 13, and 16, all of which
`
`have lower "total absolute differences." Id. Therefore, Iwamura will not always
`
`locate the closest matching melody segment, and discloses an "approximate nearest
`
`neighbor search."
`
`Iwamura further discloses an "approximate nearest neighbor search" because
`
`it contemplates skipping "unimportant portions" of a reference. Ex. 1012, 9:44–52.
`
`Because a "user"—rather than any quantitative or objective criteria—determines
`14
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`which portions to designate "unimportant," the closest matching melody may fall
`
`within a skipped section. Ex. 1020, 135:15–137:3; see Ex. 1012, 9:44–52.
`
`These results hold true even if songs—rather than segments—are "possible
`
`matches," as Patent Owner contends. Because Iwamura does not necessarily locate
`
`the closest matching segment, it does not always identify the song containing the
`
`closest segment. In the above example, Iwamura would perform only Comparison
`
`Nos. 5 and 11, both of which have a "total absolute difference" of 5. If it also
`
`considered a second reference, 005432200, it would make a single comparison of
`
`54321 to 54322, and compute a "total absolute difference" of 1. Because 1 is lower
`
`than 5, Iwamura would incorrectly identify the second reference as the song
`
`containing the closest matching segment, when in fact Comparison No. 12 in first
`
`reference has a "total absolute difference" of zero. Thus, even if songs are
`
`"possible matches," Iwamura does not always locate the closest match, and
`
`therefore discloses an "approximate nearest neighbor search."
`
`C.
`
`Iwamura Discloses "Sublinear Search"
`
`Claims 1, 3, 5, 7–8, 21–22, 33, and 37–38 recite a "sublinear search."
`
`Iwamura discloses this limitation.
`
`15
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`
`1.
`
`Contrary to the Arguments Raised in Network-1's
`Response, Iwamura Discloses "Sublinear Search"
`
`Network-1 broadly contends that "Iwamura does not teach an algorithm that
`
`'scales with a less than linear relationship to the size of the data set to be searched.'"
`
`Paper No. 17 at 11 (emphasis added). This is incorrect. "The size of the data set to
`
`be searched" refers to the amount of disk space a data set occupies. Because
`
`Iwamura's search speed scales at a less than linear relationship to disk space when
`
`higher resolution works are added to a reference database of lower resolution
`
`works, Iwamura discloses "sublinear search."
`
`Iwamura stores reference songs in two different file formats—low resolution
`
`MIDI, and high resolution waveform (".wav")—each requiring a different amount
`
`of disk space to represent the same music. MIDI files are "compressed" and
`
`contain "only . . . pitch and duration values," "[s]o [their] size is very compact."
`
`Ex. 1012 1:18–19, 3:57–60. "Each waveform file is several Kbytes" and, therefore,
`
`substantially "larger than a MIDI file."2 Ex. 1012 3:65–4:1.
`
`
`2 Iwamura's database may store either (1) music files (i.e., .wav and/or MIDI files)
`
`(e.g., Ex. 1012, 5:14–22 ("The melody data may be stored as a MIDI file. When
`
`searched, its melody is extracted from the MIDI file . . . ."); Ex. 1012, 12:9–10);
`
`or (2) both music files and corresponding strings of extracted notes, (e.g., Ex.
`
`16
`
`(cont'd)
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`Though MIDI and .wav files occupy different amounts of disk space, in
`
`Iwamura, they may be represented by the same number of notes. Specifically,
`
`Iwamura discloses an embodiment wherein "up to 64 notes are stored for a
`
`melody." Ex. 1012 5:29–30. Songs of standard length contain more than 64 notes,
`
`and are thus represented by the maximum 64 notes in Iwamura's database,
`
`regardless of file type. Because the "distance between the peak notes" in these files
`
`is "a function of the music," reference songs on average have the same number of
`
`peak notes, regardless of file type. Ex. 1020, 126:10–18; see also Ex. 1012 6:60–
`
`61. Thus, because Iwamura's "search time greatly depends on the number of . . .
`
`peaks," searches based on MIDI and .wav files take the same amount of time. Ex.
`
`1012 8:11–13.
`
`Due to the foregoing characteristics, Iwamura discloses a sublinear search
`
`when .wav files are added to a database of MIDI files.3 For instance, assume a
`
`________________________
`(cont'd from previous page)
`1012, Cl. 1–12, 21–33 (reciting both "stored [pitch] values" and "stored
`
`melodies")). In either case, database entries containing .wav files occupy more
`
`disk space than database entries containing MIDI files.
`
`3 The same logic applies when adding a .wav file to a database with .wav and MIDI
`
`files because the average song in the mixed database is smaller than a .wav file.
`
`17
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`database containing a single MIDI song of size S, which may be searched in time
`
`T. If a single .wav song is added to this database, the size will increase to more
`
`than 2S, because .wav files occupy more disk space than MIDI files. However,
`
`because both songs will be represented by the same number of peak notes, and
`
`Iwamura's search time depends on the number of peak notes, search time will only
`
`increase to 2T. Ex. 1012 8:11–13; see Ex. 1012 9:7–10. As depicted below, search
`
`speed increases disproportionately slowly relative to the increase in database size,
`
`and Iwamura discloses a "sublinear search."
`
`
`
`2.
`
`Petitioner's Arguments Regarding "Sublinear Search" Are
`Both Timely and Responsive
`
`Betraying its concern that Iwamura discloses "sublinear search," Patent
`
`Owner urges the Board to ignore the above argument. Petitioner argued in its
`
`Petition that Iwamura's use of the "Boyer-Moore algorithm" constituted disclosure
`
`of a "sublinear search." Paper No. 1 at 11–12, 16. Patent Owner argues now that
`
`18
`
`
`
`
`
`IPR2015-00345
`Patent No. 8,205,237
`"Boyer-Moore does not disclose a sublinear search," and claims that "[a]ny attempt
`
`by Petitioner . . . to rely on some disclosure in Iwamura for the claimed sub-linear
`
`search elements beyond the referenced Boyer-Mo