throbber
Filed on behalf of: Google Inc.
`
`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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

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.

throbber

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.

Become a Member

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

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket