Filed on Behalf of NETWORK-1 TECHNOLOGIES, INC.
`
`By: Charles R. Macedo (Reg. No. 32,781)
`Brian A. Comack (Reg. No. 45,343)
`Amster, Rothstein & Ebenstein LLP
`90 Park Avenue
`New York, NY 10016
`Telephone: (212) 336–8074
`Facsimile: (212) 336–8001
`cmacedo@arelaw.com
`N1-Google-IPR@arelaw.com
`
`Gregory Dovel (admitted pro hac vice)
`Dovel & Luner, LLP
`201 Santa Monica Blvd., Suite 600
`Santa Monica, CA 90401
`Telephone: (310) 656-7066
`greg@dovellaw.com
`
`
`
`
`
`
`
`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
`Patent 8,205,237
`_________________
`
`PATENT OWNER’S RESPONSE PURSUANT TO 37 C.F.R. § 42.120
`
`
`613390.1
`
`

`
`D.
`
`Table of Contents
`Claim Constructions. ....................................................................................... 2
`A.
`sub-linear. .............................................................................................. 2
`B.
`non-exhaustive search. .......................................................................... 6
`C.
`neighbor search / identifying a neighbor / neighbor / near
`neighbor. ................................................................................................ 7
` approximate nearest neighbor search. .................................................. 8
`1.
`“identifying a close match that is not necessarily the closest
`match” ......................................................................................... 9
`“sublinear” .................................................................................. 9
`2.
`‘237 Ground 1: The instituted claims of the ‘237 patent are not anticipated
`by Iwamura. ................................................................................................... 11
`A.
`sub-linear time search (claims elements 1(b) and 5(b.2)). .................. 11
`B.
`approximate nearest neighbor search (claim elements 9(b) and
`13(b.2)). ............................................................................................... 19
`nonexhaustive search (claim 25). ........................................................ 25
`C.
`sublinear approximate nearest neighbor search (claim 33). ................ 40
`E.
`‘237 Ground 2: The instituted claims of the ‘237 patent are not anticipated
`by Ghias. ........................................................................................................ 41
`A.
`sublinear time search (claim elements 1(b) and 5(b.2)). ..................... 42
`B.
`approximate nearest neighbor search (claim elements 9(b) and
`13(b.2)). ............................................................................................... 51
`‘237 Ground 3: The instituted claims of the ‘237 patent are not obvious over
`Iwamura and Chen. ........................................................................................ 56
`
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`
`
`I.
`
`II.
`
`IV.
`
`V.
`
`
`
`613390.1
`
`i
`
`

`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`TABLE OF AUTHORITIES
`
`
`CASES
`CallCopy, Inc. v. Verint Americas, Inc.,
`IPR2013-00492, Paper 14 (PTAB Feb. 5, 2014) ................................................ 56
`
`Page(s)
`
`Retractable Techs. v. Becton, Dickinson & Co.,
`659 F.3d 1369 (Fed. Cir. 2011) ............................................................................ 9
`
`TRW Automotive v. Magna Electronics,
`IPR2014-00262, Paper 37 (PTAB June 25, 2015) ....................................... 17, 49
`
`OTHER AUTHORITIES
`
`37 C.F.R. § 42.104(b)(3) ............................................................................................ 8
`
`Office Patent Trial Practice Guide,
`77 Fed. Reg. 48,756 (Aug. 14, 2012) ........................................................... 17, 49
`
`
`
`
`
`613390.1
`
`ii
`
`

`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`Exhibit List
`
`Description
`
`Exhibit
`Number
`2001
`
`“Brute-force search”—http://en.wikipedia.org/wiki/Bruteforce_
`search (3/19/2015)
`2002 U.S. Patent 8,447,762 (Brendel)
`2003 U.S. Patent 7,167,984 (Graveman)
`2004 Declaration of Greg Dovel in Support for Pro Hac Vice Admission
`2005 Declaration of Dr. George Karypis
`2006 Deposition of Dr. Pierre Moulin, dated August 19-20, 2015
`2007 Modern Dictionary of Electronics 425-426 (1999).
`2008
`http://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_ne
`arest_neighbor
`http://en.wikipedia.org/wiki/Big_O_notation
`P. N. Yianilos, “Locally lifting the curse of Dimensionality for nearest
`Neighbor Search” SODA 2000: 361-370
`
`2009
`2010
`
`613390.1
`
`iii
`
`

`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`Patent Owner Network-1 respectfully submits this response to the Petition as
`
`
`
`instituted by the decision to institute an Inter Partes Review of Patent No.
`
`8,205,237 (the “‘237 patent”). IPR2015-00345, paper 6 (“Decision”).
`
`
`
`Network-1 appreciates the guidance and concerns that the Board provided
`
`and raised in the Decision. In this Response, Network-1 addresses the Board’s
`
`specific concerns. In doing so, Network-1 provides an extensive and detailed
`
`technical analysis in the accompanying Declaration of expert Dr. George Karypis
`
`(ex. 2005, “Karypis Decl.”) that it was not permitted to submit along with its prior
`
`filings.1
`
`
`
`In addition, Nework-1 quotes dozens of admissions from the deposition of
`
`Petitioner’s own Declarant, Dr. Pierre Moulin (ex. 2006), to corroborate most of
`
`the arguments made in this Response.
`
`
`
`First, the Response addresses the claim constructions relevant to this IPR.
`
`
`1
`To avoid duplication, to make the proceeding more efficient, and to avoid
`
`confusion (by citing multiple versions of Karypis Declarations), Patent Owner
`
`provides a single Karypis Declaration (ex. 2005) for the four related IPRs
`
`(IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348). As a
`
`result, certain paragraphs of the Declaration (e.g., ¶¶19-27, 38-44) are not directly
`
`relevant to this IPR.
`
`613390.1
`
`1
`
`

`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`Second, the Response addresses each of the two grounds at issue in this IPR.
`
`Claim Constructions.
`
`The Board identified certain claim constructions in its Decision:
`
`
`
`I.
`
`
`
`sub-linear
`
`“a search whose execution time scales with a less than
`linear relationship to the size of the data set to be
`searched” Decision at 7.
`“a search that locates a match without a comparison of
`all possible matches” Decision at 7.
`“identifying a close, but not necessarily exact or
`closest, match” Decision at 8
`
`“identifying a close match that is not necessarily the
`closest match” Decision at 9.
`
`non-exhaustive search /
`non-exhaustive…search
`neighbor search /
`identifying a neighbor /
`near neighbor
`approximate nearest
`neighbor search
`
`Each construction is addressed in turn.
`
`A.
`
`sub-linear.
`
`
`
`There are two possible interpretations of the Board’s construction of
`
`sublinear—“size of the data set” in the Board’s construction refers to (1) the
`
`records in the data set being searched; or (2) the length of an individual record in
`
`the database.2 The phrase “size of the dataset,” ‘237 specification, and Petitioner’s
`
`
`2
`As demonstrated below, the asserted art does not disclose a sub-linear search
`
`under either interpretation.
`
`613390.1
`
`2
`
`

`
`Declarant confirm that first interpretation is correct. Karypis Decl. ¶¶61-78.
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`
`
`“size of the dataset” A “data set,” in the context of the ‘237 patent, is a
`
`database (i.e., set of records), not an individual record in a database. Karypis Decl.
`
`¶¶63-65. The Board incorporated the phrase “size of the dataset” in its preliminary
`
`construction based on the fact that “database” and “dataset” are “largely
`
`consistent.” Decision at 7. “Dataset” and “database” are in fact the same in this
`
`context. Moulin Depo. 22:14-16; 110:11-15. A database comprises all records in
`
`the database; a single record is not a database. Karypis Decl. ¶64; Moulin Depo.
`
`89:4-13. Moreover, the phrase “data set” came from Patent Owner’s Preliminary
`
`Response in which Patent Owner clarified that the “‘size of the data set’ is the
`
`number of potential matches in the data set (i.e., the ‘number of entries in the
`
`search database.’” Pre. Resp. at 9-10 (quoting Moulin Decl. ¶54). Neither the
`
`Patent Owner nor the Petitioner suggested that sublinear should be based on the
`
`length of an individual query in the dataset.
`
`
`
`‘237 specification: The specification describes “linear” with respect to
`
`“N”—the number of records in the database being searched—not with respect to
`
`the length of an individual record in the database:
`
`If binary search was possible, then a database containing N vectors
`would require at most log(N) comparisons. …. it was not uncommon
`to perform a linear search of all N entries, perhaps halting the search
`when the first match is found. On average, this will require N/2
`
`613390.1
`
`3
`
`

`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`comparisons. If N is large, this search can be computationally very
`expensive.
`‘237, 8:54–63; 21:14–23. Karypis Decl. ¶69. The specification also identifies
`
`search techniques that are sub-linear with respect to the number of records in the
`
`database being searched (N), not with respect to the length of an individual record
`
`being searched: “A number of possible data structures are applicable including kd-
`
`trees and vantage point trees. These data structures and associated search
`
`algorithms organize a N-point dataset (N=90,000,000 in out previous example) so
`
`that sub-linear time searches can be performed on average.” ‘237, 21:56–60; 8:64–
`
`9:7. The ‘237 specification describes linear with respect to “N”—the number of
`
`records in the database being searched—not with respect to the length of an
`
`individual record. Karypis Decl. ¶¶69; 71.
`
`
`
`Petitioner’s Declarant: According to Petitioner, a sublinear search is “a
`
`search whose execution time has a sublinear relationship to database size”—where
`
`the database size is the number of records in the database, not the length of an
`
`individual record in the database.
`
`
`Moulin Decl. ¶53; Moulin Depo. 13:24-14:4; 103:16-22; 16:4-12; 24:1-12. The
`
`Petition and Declaration interpret “database size” as the number of records in the
`
`613390.1
`
`4
`
`

`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`database: “For instance, a linear search of a 200-item database would take twice as
`
`long as a linear search of a 100-item database. By contrast, a sublinear search of a
`
`200-item database would take less than twice as long as a sublinear search of a
`
`100-item database, perhaps, for instance, 1.5 times as long.” Pet. at 6; Moulin
`
`Decl. ¶53.
`
`
`
`Moulin Decl. ¶54 (depicting sub-linear and linear with respect to the “number of
`
`entries in the search database”). “[I]t is my opinion that a search whose execution
`
`time is proportional to the logarithm of the size of the data set (e.g., a search with
`
`execution time proportional to A log (BN), where A and B are constants, and N is
`
`the number of entries in the database) is sublinear.” Moulin Decl. ¶56. Nowhere
`
`does Petitioner or the Declarant suggest that a relevant sublinear search is with
`
`respect to the length of an individual record to be searched. Karypis Decl. ¶75.
`
`
`
`Importantly, under any possible interpretation of sublinear in the context of
`
`the ‘237 patent, a search algorithm is sublinear is only with respect to the size of
`
`613390.1
`
`5
`
`

`
`the dataset, not the size of the query (pattern) of the work to be identified. Karypis
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`Decl. ¶76. As Petitioner’s expert confirmed, whether a prior art search “scales
`
`based upon the size of the query or pattern” would not “be accurately assessing the
`
`‘237 patent claims.” Moulin Depo. 25:22-26:8; 26:11-21; 25:4-12; 26:25-27:15;
`
`27:16-24; 28:4-16.
`
`non-exhaustive search.
`
`B.
`The Board’s preliminary construction—“a search that locates a match
`
`
`
`without a comparison of all possible matches” is correct. Moulin Decl. ¶12; ‘237,
`
`8:64-67; 8:59-61; Karypis Decl. ¶¶79-88; ex. 2001.
`
`
`
`The Board properly rejected Petitioner’s assertion that a non-exhaustive
`
`search should be construed as “a search that locates a match without conducting a
`
`brute force comparison of all possible matches, and all data within all possible
`
`matches.” The “all data” clause 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. Karypis Decl. ¶¶83-
`
`88. The “all data” clause is:
`
` inconsistent with how the non-exhaustive search concept is used in the ‘237
`
`Patent 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., ‘237, 8:54-63); and
`
`613390.1
`
`6
`
`

`
` not part of the ordinary meaning of non-exhaustive search (Karypis Decl.
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`¶85; ex. 2001 (each “candidate” is checked, not “all data” within each
`
`candidate)).
`
`Petitioner’s Declarant confirmed that a non-exhaustive search searches a subset of
`
`potential matches, not a subset of “all data within all potential matches”:
`
`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. ¶¶12, 43.
`
`C. neighbor search / identifying a neighbor / neighbor / near
`neighbor.
`
`
`
`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 “a close, but not necessarily exact or closest, match.”
`
`Decision at 8; Karypis Decl. ¶¶89-93. Petitioner and its Declarant agree with the
`
`Board’s construction. Petition at 6; Moulin Decl. ¶48; Moulin Depo. 250:2-5.
`
`There are two relevant features of a neighbor search under this construction:
`
`
`
`Feature 1: 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 performed), it is not a neighbor or near neighbor
`
`search because it is not a search that “identif[ies] a close, but not necessarily exact
`
`613390.1
`
`7
`
`

`
`or closest, match.” Rather, such a search necessarily identifies an exact or the
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`closest match. Karypis Decl. ¶92.
`
`
`
`Feature 2: If a search that necessarily identifies an exact or the closest
`
`match (e.g., Match 1) but also identifies other matches that, by definition, are not
`
`the closest match (Match 2, Match 3, Match 4), the search still necessarily
`
`identifies an exact or the closest match (Match 1) and therefore cannot be the
`
`claimed neighbor or near neighbor search. Karypis Decl. ¶93.
`
` D.
`
` approximate nearest neighbor search.
`
`
`
`Petitioner failed to identify a construction of approximate nearest neighbor
`
`search. See 37 C.F.R. § 42.104(b)(3). The Board preliminary determined that an
`
`approximate nearest neighbor search is a search “identifying a close match that is
`
`not necessarily the closest match.” Decision at 9. This construction is correct, but
`
`incomplete (Karypis Decl. ¶¶94-105), as demonstrated by the ‘237 specification
`
`which confirms that an approximate nearest neighbor search” is [1] a sub-linear
`
`neighbor search that [2] does not always find the closest match:
`
`[1] One example of a sub-linear time search is an approximate nearest
`neighbor search. [2] A nearest neighbor search always finds the
`closest point to the query. An approximate nearest neighbor search
`does not always find the closest point to the query. For example, it
`might do so with some probability, or it might provide any point
`within some small distance of the closest point.
`
`613390.1
`
`8
`
`

`
`‘237, 9:12-19 (enumeration added). These two features are addressed in
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`reversed order.
`
`1.
`
`“identifying a close match that is not necessarily the closest
`match”
`
`
`
`This feature of approximate nearest neighbor search was properly adopted
`
`by the Board. Karypis Decl. ¶¶94-96. The ‘237 specification states that an
`
`“approximate nearest neighbor search does not always find the closest point to the
`
`query.” ‘237, 9:15–16. Accordingly, a search that “always finds” (i.e., is
`
`guaranteed to find) the closest match is not an approximate nearest neighbor search
`
`while a search that is not guaranteed to find the closest match can be an
`
`approximate nearest neighbor search if it identifies a close match. This
`
`understanding of approximate nearest neighbor search is consistent with the
`
`ordinary meaning of the phrase. Karypis Decl. ¶¶97-98.
`
`Approximate nearest neighbor In some applications it may be
`acceptable to retrieve a ‘good guess’ of the nearest neighbor. In
`those 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 (nearest neighbor search, Wikipedia) at 5.
`
`2.
`
`“sublinear”
`
`
`
`An inventor may act as his or her own lexicographer in defining terms used
`
`in a patent’s claims. Retractable Techs. v. Becton, Dickinson & Co., 659 F.3d
`
`613390.1
`
`9
`
`

`
`1369, 1371 (Fed. Cir. 2011). The ‘237 patent defines approximate nearest
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`neighbor search as a type of sub-linear search.
`
` “a sub-linear time search, such as an approximate nearest neighbor search”
`
`‘237, Title; ‘237 Abstract (same);
`
` “One example of a sub-linear time search is an approximate nearest neighbor
`
`search.” ‘237, 9:12–14.
`
`The Board did not include the sublinear aspect of an approximate nearest neighbor
`
`search in its preliminary construction based on what appears to be faulty logic:
`
`
`
`Decision at 9. The logic underlying the Board’s reasoning appears to be as
`
`follows: If A is “one example” of B, A is not always B. This logic is faulty. If A
`
`is “one example” of B, A is always B even though there may be examples other
`
`than A that fall within the scope of B. If A is “one example” of B, the scope of B
`
`is not limited to just A (i.e., the scope of B can include C, D, and E) but A is
`
`613390.1
`
`10
`
`

`
`always B. Karypis Decl. ¶¶104-105.
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`II.
`
`‘237 Ground 1: The instituted claims of the ‘237 patent are not
`anticipated by Iwamura.
`
`
`
`Ground 1 fails because Iwamura does not disclose the following elements
`
`from each instituted independent claim:
`
` sub-linear time search (claims elements 1(b) and 5(b.2)).
`
`A.
`Claims elements 1(b) and 5(b.2) require a sub-linear time search. As
`
`
`
`explained above (Section I(A)), a sub-linear time search is “a search whose
`
`execution time scales with a less than linear relationship to the size of the data set
`
`to be searched.” Decision at 7; Karypis Decl. ¶¶108-109; 61-78.
`
`
`
`Iwamura does not teach an algorithm that “scales with a less than linear
`
`relationship to the size of the data set to be searched” where the data set is either
`
`(a) the number of records in the database (the proper interpretation), or (b) even the
`
`length of an individual record. Karypis Decl. ¶¶110-131. Instead, each melody in
`
`the database is compared and “[t]he reference melody that gives the least
`
`difference is returned as a search result.” Iwamura, 7:53-55; Karypis Decl. ¶110.
`
`
`
`Specifically, Iwamura confirms that the referenced Boyer-Moore algorithm
`
`(the basis for the sub-linear search in the Petition 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
`
`613390.1
`
`11
`
`

`
`(discussed below) or other string-matching algorithms do not have this kind of
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`flexibility. They only search word by word from the beginning of the database to
`
`the end.” Iwamura, 9:52-55; Karypis Decl. ¶111.
`
`
`
`The Petition fails to satisfy its burden of demonstrating that Iwamura teaches
`
`a sub-linear search. As support for the sub-linear elements, Petitioner exclusively
`
`relies on the referenced Boyer-Moore algorithm:
`
`Pet. at 7-12; Moulin Decl. ¶¶72, 75; Moulin Depo. 82:23-83:3. The referenced
`
`Boyer-Moore algorithm, however, does not disclose a sublinear search. Karypis
`
`Decl. ¶¶113-118. On cross examination, Petitioner’s Declarant conceded the
`
`
`
`following:
`
`
`
`(1) Petitioner’s Declarant 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 of
`
`the work to be matched:
`
`613390.1
`
`12
`
`

`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`
`Moulin Decl. ¶53; Moulin Depo. 24:1-12. Sublinear is not “in relation with the
`
`size of the query.” Moulin Depo. 26:11-21; 25:4-12 (sublinear in relation to the
`
`query or pattern “would not be relevant”). Petitioner’s Declarant admitted that if a
`
`reference discloses a search that is sublinear with respect to the length of the query
`
`but linear with respect to the size of the database, it is not sublinear in the context
`
`of the ‘237 patent. Moulin Depo. 26:25-27:15; 27:16-24.
`
`613390.1
`
`13
`
`
`
`

`
`Moulin Depo. 28:4-16; 77:14-24.
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`
`
`(2) During cross examination, Petitioner’s Declarant admitted that the
`
`Boyer-Moore algorithm does not disclose a search that is sublinear with respect to
`
`the database size (i.e., the size of the data set to be searched)—it does not even
`
`address a database (Moulin Depo. 53:19-22)—but instead has a relationship to the
`
`size of the query pattern from the work to be identified: 3
`
`
`
`Moulin Depo. 61:18-24; 44:20-46:6; 59:6-9; 61:25-62:9; 68:25-69:4.
`
`
`
`(3) After being confronted with the fact that the Boyer-Moore algorithm
`
`referenced in Iwamura does not even address a dataset, much less disclose “a
`
`search whose execution time scales with a less than linear relationship to the size
`
`of the data set to be searched,” Petitioner’s Declarant confirmed that the
`
`representation in his Declaration—Petitioner’s only support for the sub-linear
`
`elements—was wrong. He testified that when he wrote:
`
`
`3
`The size of the query pattern in would be, for example, the number of notes
`
`hummed by the user.
`
`613390.1
`
`14
`
`

`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`
`(Moulin Decl. ¶72) and wrote just a few pages earlier:
`
`
`
`
`
`(Moulin Decl. ¶53), he was not trying to convey that Boyer-Moore was sublinear
`
`in the context of the ‘237 patent –i.e., “sublinear relationship to the database size”:
`
`Moulin Depo. 74:20-24; 74:8-12; 69:9-16; 66:9-18; 75:23-76:3.
`
`
`
`
`
`Moulin Depo. 67:17-21. Petitioner’s Declarant wanted to make it very clear that
`
`he was not claiming that the Boyer-Moore algorithm referenced in Iwamura—
`
`Petitioner’s only support for the sub-linear elements—discloses a sub-linear search
`
`in the context of the ‘237 patent, i.e., with respect to the size of the dataset:
`
`613390.1
`
`15
`
`

`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`
`
`Moulin Depo. 79:9-18; 79:19-80:12; 80:15-83:3; 77:25-78:15; 78:16-79:6.
`
`
`
`Realizing that (a) Petitioner exclusively relied on the referenced Boyer-
`
`Moore algorithm for the claimed sublinear elements, and (b) Boyer-Moore does
`
`not disclose a sublinear search, Petitioner’s Declarant, Dr. Moulin, suggested in his
`
`deposition that there may be additional undisclosed reasons why Iwamura
`
`discloses the claimed sublinear search elements (Moulin Depo. 83:4-12; 70:24-
`
`71:8) and that he may try to “supplement” his opinions. Moulin Depo. 66:24-67:7;
`
`376:11-21; 103:23-104:12 (“I would like to supplement my – my opinion”); 84:22-
`
`85:17 (“I can supplement them”); 71:1-13 (“I supplemented my views now”);
`
`293:3-10 (“I want to supplement my opinion”). Any attempt by Petitioner or its
`
`Declarant to rely on some disclosure in Iwamura for the claimed sub-linear search
`
`elements beyond the referenced Boyer-Moore algorithm—either in the Reply,
`
`Reply Declaration, or at oral argument—should be rejected as violating the
`
`613390.1
`
`16
`
`

`
`controlling rules and prejudicing Patent Holder. TRW Automotive v. Magna
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`Electronics, IPR2014-00262, Paper 37 at 12-13 (June 25, 2015) (citing Office
`
`Patent Trial Practice Guide, 77 Fed. Reg. 48,756, 48,767 (Aug. 14, 2012)).
`
`
`
`Board’s concerns: The following addresses the Board’s specific concerns
`
`(identified in its Decision) with respect to whether Iwamura discloses a sub-linear
`
`search. In instituting Ground 1, the Board preliminary found that Iwamura
`
`disclosed the sub-linear search because (a) a sub-linear search of the data within
`
`the records can be sublinear even if every record in the database is searched, and
`
`(b) Patent Owner’s argument that the Boyer-Moore algorithm searches all items in
`
`the database therefore does not demonstrate that Boyer-Moore is not sub-linear:
`
`
`
`Decision at 11-12. The Board’s preliminary analysis is flawed on multiple levels.
`
`
`
`First, the Board’s preliminary analysis is based on an incorrect interpretation
`
`of sub-linear. The Board construed a 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,” not the length of any specific record in the database. See Section
`
`I(A); Karypis Decl. ¶126.
`
`613390.1
`
`17
`
`

`
`Second, the Board’s preliminary analysis has the relevant burden
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`
`
`backwards—it is not Patent Owner’s burden to demonstrate that the referenced
`
`Boyer-Moore algorithm does not disclose a sublinear search. Rather it was
`
`Petitioner’s burden to demonstrate that Boyer-Moore discloses a sublinear search.
`
`As demonstrated above, Petitioner failed to satisfy this burden.
`
`
`
`Third, there is no evidence under any interpretation of sublinear in the
`
`context of the ‘237 patent that the referenced Boyer-Moore algorithm discloses a
`
`search that is sublinear with respect to either (a) the “size of the dataset” (Decision
`
`at 7); or (b) the even length of an individual record being searched. The two
`
`references to the Boyer-Moore algorithm in Iwamura are:
`
`Iwamura, 9:52-55.
`
`
`
`
`
`Iwamura, 9:61-64. Neither passage states that the algorithm is sublinear—with
`
`respect to either the number of references in the database (N) or the length of an
`
`individual record to be search. Karypis Decl. ¶130.
`
`
`
`Fourth, as demonstrated above, Petitioner’s Declarant confirmed that the
`
`referenced Boyer-Moore algorithm does not disclose a search that is sublinear in
`613390.1
`18
`
`

`
`the context of the ‘237 patent. See Section II(A); Karypis Decl. ¶131; Moulin
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`Depo. 79:9-18; 79:19-80:12; 80:15-83:3; 77:25-78:15; 78:16-79:6.
`
`B.
`
`approximate nearest neighbor search (claim elements 9(b) and
`13(b.2)).
`
`
`
`As set forth above (Section I(D)), an approximate nearest neighbor search is
`
`a sub-linear search identifying a close match that is not necessarily the closest
`
`match. Karypis Decl. ¶¶132; 94-105. Also, as explained above, a search that
`
`necessarily identifies the closest match is not an approximate nearest neighbor
`
`search even if it also identifies other near matches. Karypis Decl. ¶132. Iwamura
`
`does not disclose the claimed approximate nearest neighbor search for two
`
`independent reasons. Karypis Decl. ¶¶133-157.
`
`
`
`Reason 1: Iwamura does not disclose an approximate nearest neighbor
`
`search because Iwamura does not disclose “identifying a close match that is not
`
`necessarily the closest match.” Karypis Decl. ¶134. Iwamura discloses a search
`
`that always identifies an exact or the closest match. Petitioner’s Declarant
`
`confirmed that Iwamura will either produce an exact match if it finds one, or the
`
`“best match it finds using that approximate criterion.” Moulin Depo. 271:22-
`
`272:12; Karypis Decl. ¶134. The system in Iwamura will always find the closest
`
`match, even if unimportant peaks are skipped or repeated patterns are avoided.
`
`Moulin Depo. 317:14-23; 318:11-18. Accordingly, Iwamura neither expressly nor
`
`inherently discloses an “approximate nearest neighbor search”—a search that does
`613390.1
`19
`
`

`
`not necessarily find the closest match. Karypis Decl. ¶137.
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`
`
`Reason 2: Iwamura does not disclose an approximate nearest neighbor
`
`search because Iwamura does not disclose a sublinear search. As demonstrated
`
`above, an approximate nearest neighbor search is “one example” of a sublinear
`
`search. Section I(D)(2). Also, as demonstrated above, Iwamura does not disclose
`
`a sublinear search. Section II(A). Accordingly, Iwamura does not disclose the
`
`claimed approximate nearest neighbor search.
`
`
`
`The Petition, Declaration, and corresponding charts fail to demonstrate that
`
`Iwamura discloses the claimed approximate nearest neighbor search. As support
`
`for the claimed approximate nearest neighbor search, the Petition relies on (1) the
`
`fault tolerance, and (2) skipped portions features described in Iwamura.
`
`
`
`Pet. at 12, 13; Moulin Decl. ¶75. These statements in the Petition (and
`
`Declaration) and corresponding passages from Iwamura fail to (a) provide a
`
`construction of approximate nearest neighbor search, (b) explain how Iwamura
`
`discloses the claimed approximate nearest neighbor search, (c) explain why the
`
`613390.1
`
`20
`
`

`
`fault tolerance capability and skipped portion are relevant to or disclose an
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`approximate nearest neighbor search, and (d) establish that Iwamura discloses an
`
`approximate nearest neighbor search. Karypis Decl. ¶¶139-144. The quoted
`
`passages do not disclose an approximate nearest neighbor search because the
`
`quoted passages do not disclose a search that (a) is not guaranteed to identify the
`
`closest match, and (b) is sublinear. See Section II(B); Karypis Decl. ¶145.
`
`
`
`First, the passage from element 1(b) cross-referenced in Petitioner’s chart
`
`does not disclose an approximate nearest neighbor search. Karypis Decl. ¶146. As
`
`explained above (Section II(B)), an approximate nearest neighbor search identifies
`
`a close match that is not necessarily the closest match. Decision at 9. The passage
`
`cited in the Petition confirms that the search disclosed in Iwamura finds “the
`
`closest melody from the database.” Pet. at 8 (quoting Iwamura, 9:24-35).
`
`
`
`Second, Petitioner’s references to searches that have (a) an input fault
`
`tolerance (Pet. at 12, quoting Iwamura, 10:17-18), or (b) skipped portions that
`
`should not be searched (Pet. at 12, quoting Iwamura, 12:6-7, 9:36-44, and 9:44-45)
`
`do not expressly or inherently disclose a search that (1) does not necessarily
`
`identify the closest match, and (2) is sublinear. Karypis Decl. ¶147. Neither
`
`enables a search to return a result other than the closest match. Karypis Decl.
`
`¶148.
`
`
`
`input fault tolerance: The input fault tolerance allows a user to identify the
`
`613390.1
`
`21
`
`

`
`closest match, even when the melody entered by a user has some errors. Iwamura,
`
`IPR2015-00345; Pat. No. 8,205,237
`Patent Owner’s Response
`
`
`9:33-39 (input fault tolerance enables “a correct search . . . notwithstanding
`
`inaccurate input from the user.”). Karypis Decl. ¶149. Using the fault tolerance
`
`feature, the peak note search first performs a search based