IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`2. 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.”
`
`
`83. The “all data” clause (that I underlined above) in Petitioner’s
`
`proposed construction (Pet. (‘237) at 5; Decision (‘237) at 5-7) would improperly
`
`include as a “non-exhaustive” search any search that did not compare “all data” in
`
`each record, even if the search were a brute force comparison of each record in the
`
`database. As an illustrative example, assume the work to be identified “ABC” is
`
`compared with all records in a library, including record “DEF.” When comparing
`
`“ABC” with “DEF,” the algorithm determines that there is no match between
`
`“ABC” and “DEF” after just comparing the first letter of the work “A” with the
`
`first letter of the record “D.” If the algorithm does not unnecessarily compare the
`
`second and third letters, then according to Petitioner, the search is not “exhaustive”
`
`even though every record is compared.
`
`84. Petitioner’s Declarant states that a non-exhaustive search is any search
`
`that is not a brute force search, and a “‘brute force’ search, in turn, is a search
`
`wherein a query is compared to every single portion of every single item in a
`
`database.” Moulin Decl. (‘237) ¶43. Petitioner’s Declarant, however, provides no
`
` NETWORK-1 EXHIBIT A2005
` Google Inc. v. Network-1 Technologies, Inc.
`56
` IPR2015-00345
`Page 60 of 292
`
`
`Declaration of George Karypis
`
`2. 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.”
`
`
`83. The “all data” clause (that I underlined above) in Petitioner’s
`
`proposed construction (Pet. (‘237) at 5; Decision (‘237) at 5-7) would improperly
`
`include as a “non-exhaustive” search any search that did not compare “all data” in
`
`each record, even if the search were a brute force comparison of each record in the
`
`database. As an illustrative example, assume the work to be identified “ABC” is
`
`compared with all records in a library, including record “DEF.” When comparing
`
`“ABC” with “DEF,” the algorithm determines that there is no match between
`
`“ABC” and “DEF” after just comparing the first letter of the work “A” with the
`
`first letter of the record “D.” If the algorithm does not unnecessarily compare the
`
`second and third letters, then according to Petitioner, the search is not “exhaustive”
`
`even though every record is compared.
`
`84. Petitioner’s Declarant states that a non-exhaustive search is any search
`
`that is not a brute force search, and a “‘brute force’ search, in turn, is a search
`
`wherein a query is compared to every single portion of every single item in a
`
`database.” Moulin Decl. (‘237) ¶43. Petitioner’s Declarant, however, provides no
`
` NETWORK-1 EXHIBIT A2005
` Google Inc. v. Network-1 Technologies, Inc.
`56
` IPR2015-00345
`Page 60 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`analysis or support for this conclusory assertion which, I understand, is insufficient
`
`to satisfy Petitioner’s burden in these IPR proceedings.
`
`85. One skilled in the art would understand that the “all data” clause is
`
`improper because it is:
`
`(cid:120) inconsistent with how the non-exhaustive search concept is used in the IPR
`
`Patents which describes a linear exhaustive search as one where the search
`
`compares the work to all “N entries,” not all data within all “N entries” (see
`
`e.g., ‘179, 21:10-42; 8:59-9:54); and
`
`(cid:120) not part of the ordinary meaning of “non-exhaustive search” (see Ex. 2001).
`
`86. Moreover, objective sources confirm my understanding that an
`
`“exhaustive” or “brute-force” search systematically compares the work with each
`
`record in a database, not all data within each record, for example:
`
`“In computer science, brute-force search or exhaustive search, also
`known as generate and test, is a very general problem-solving
`technique that consists of systematically enumerating all possible
`candidates for the solution and checking whether each candidate
`satisfies the problem’s statement.”
`
`Ex. 2001—each “candidate” is checked, not “all data” within each candidate.
`
`57
`Page 61 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`87. Petitioner’s own Declarant twice confirmed my understanding—that a
`
`“non-exhaustive” search searches a subset of “potential matches,” not a subset of
`
`“all data within all potential matches”:
`
`(1)“Because neighbor searching is computationally intensive, content
`
`recognition schemes typically employed search algorithms that increased
`
`efficiency by intelligently searching only a subset of potential matches (i.e.,
`
`‘non-exhaustive’ algorithms).” Moulin Decl. (‘237) ¶12;
`
`(2)“to maximize search efficiency, persons skilled in the art routinely employed
`
`more efficient searches that did not conduct a comparison of every single
`
`item in a database, sometimes referred to as non-exhaustive searches.”
`
`Moulin Decl. (‘237) ¶43.
`
`88.
`
` For the reasons that I presented above, one skilled in the art would
`
`understand that the Board properly rejected Petitioner’s “all data” clause.
`
`Decision (‘237) at 6.
`
`C. neighbor search / identifying a neighbor / neighbor / near
`neighbor (‘237, ‘988, ‘179, and ‘441 patents).
`
`89. One skilled in the art would understand that the Board properly
`
`construed a “neighbor search” and “identifying a neighbor” as “identifying a close,
`
`but not necessarily exact or closest, match” and “neighbor” and “near neighbor” as
`
`58
`Page 62 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`“a close, but not necessarily exact or closest, match.” Decision (‘237) at 8;
`
`Decision (‘988) at 7-8; Decision (‘179) at 8; Decision (‘441) at 7.
`
`90. Petitioner and its Declarant agree with the Board’s construction of
`
`“neighbor search.” See e.g., Petition (‘179) at 6 (“The term ‘neighbor search’ …
`
`should be construed to mean ‘identifying a close, but not necessarily exact,
`
`match.’”); Moulin Decl. (‘179) ¶45 (“‘neighbor search’ means ‘identifying a close,
`
`but not necessarily exact, match.’”); Moulin Depo. 250:2-5.
`
`91. One skilled in the art would understand that there are two relevant
`
`features of a neighbor search under this construction:
`
`92. 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
`
`or closest, match.” Rather, such a search necessarily identifies an exact or the
`
`closest match.
`
`93. 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.
`
`59
`Page 63 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`D.
`
`approximate nearest neighbor search (‘237 patent).
`
`94. As I noted above, the Petitioner did not identify a construction of
`
`“approximate nearest neighbor search.”
`
`95.
`
`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 (‘237) at 9. One skilled in the art would understand that
`
`this construction is correct, but incomplete, as demonstrated by the ‘237
`
`specification. The ‘237 specification states that the claimed “approximate nearest
`
`neighbor search” is [1] a sub-linear neighbor search that [2] does not always find
`
`the closest point to the query—i.e., 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.”
`
`‘237, 9:12-19.
`
`96.
`
`The first feature—that a “approximate nearest neighbor search” is a
`
`sub-linear time search—is not reflected in the Board’s preliminary construction
`
`and, as demonstrated below, should be included in the construction. The second
`
`60
`Page 64 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`feature of the claimed “approximate nearest neighbor search” is reflected in the
`
`Board’s preliminary construction—“identifying a close match that is not
`
`necessarily the closest match.” I address these two features in reversed order.
`
`1.
`
`“identifying a close match that is not necessarily the closest
`match”
`
`97.
`
`This feature of “approximate nearest neighbor search” was properly
`
`adopted by the Board. A search that is guaranteed to return the actual closet match
`
`is not an “approximate nearest neighbor search.” 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. See Pet.
`
`(‘237) at 19 (stating that a reference discloses an “approximate nearest neighbor
`
`search” because the search “identifies a neighbor, but not necessarily the nearest
`
`neighbor.”).
`
`98.
`
`This understanding of “approximate nearest neighbor search” is
`
`consistent with the ordinary meaning of the phrase
`
`“Approximate nearest neighbor In some applications it may be
`acceptable to retrieve a ‘good guess’ of the nearest neighbor. In those
`
`61
`Page 65 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`cases, we can use an algorithm which doesn’t guarantee to return the
`actual nearest neighbor in every case, in return for improved speed or
`memory savings.”
`
`Ex. 2008
`(http://en.wikipedia.org/wiki/Nearest neighbor search#Approximate nearest neig
`hbor.) at 5.
`99.
`
`Similar to the neighbor and near neighbor searches addressed above,
`
`one skilled in the art would understand that a search that necessarily identifies
`
`both: (1) an exact match or the closest match, and, in addition, (2) “a close match
`
`that is not necessarily the closest match” is not an “approximate nearest neighbor
`
`search” because it is always guaranteed to identify the closest match.
`
`2.
`
`“sublinear”
`
`100. It is my understanding that an inventor may act as his or her own
`
`lexicographer in defining terms used in a patent’s claims. One skilled in the art
`
`would understand that the ‘237 patent defines “approximate nearest neighbor
`
`search” as a type of sub-linear search.
`
`101. Title: In the title of the ‘237 patent, the patentee identified an
`
`“approximate nearest neighbor search” as a type of sub-linear search: “Identifying
`
`works, using a sub-linear time search, such as an approximate nearest neighbor
`
`search, for initiating a work-based action, such as an action on the internet.” ‘237,
`
`Title.
`
`62
`Page 66 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`102. Abstract: It is my understanding that the abstract of a patent may be
`
`used to determine the scope of the invention. In its Abstract, the ‘237 patent also
`
`describes an “approximate nearest neighbor search” as a “sub-linear time search”:
`
`“determining an identification of the media work . . . using a sub-linear time
`
`search, such as an approximate nearest neighbor search for example.” ‘237,
`
`Abstract.
`
`103. Specification: In describing methods for carrying out a sub-linear
`
`search of the reference data set, the ‘237 specification also describes an
`
`“approximate nearest neighbor search” as a type of sub-linear search: “One
`
`example of a sub-linear time search is an approximate nearest neighbor search.”
`
`‘237, 9:12–14.
`
`104. In its preliminary construction, the Board did not include the sublinear
`
`feature of the claimed “approximate nearest neighbor search” based on what
`
`appears to be faulty logic. The Board preliminarily found:
`
`63
`Page 67 of 292
`
`
`
`IPR2015-00343, IPR20 15-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`We largely agree with Patent Owner's construction, but note that the
`
`Specification refers to "[o ]ne example of a sub-linear time search is an
`
`approximate nearest neighbor search" (Ex. 1001, 9: 12- 14 ), such that we are
`
`not persuaded that an "approximate nearest neighbor search," must be a sub(cid:173)
`
`linear search, as that term has been construed above. As such, we are
`
`persuaded that the proper construction of "approxi1nate nearest neighbor
`
`search" is "identifying a close match that is not necessarily the closest
`
`match."
`
`Decision ('237) 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. In my opinion, this logic
`
`is faulty.
`
`105. If A is "one example" ofB, A is always Beven though there may be
`
`examples other than A that fall within the scope of B. If A is "one example" of B,
`
`the scope ofB is not limited to just A (i.e., the scope ofB can include C, D, and E)
`
`but A is always B. For example, a poodle is "one example" of a dog; a poodle is
`
`always a dog (there is no scenario where a poodle is not a dog) but there are other
`
`examples that fall within the scope of dog beyond poodles, i.e., terriers,
`
`Dalmatians, etc. Just like a "poodle" being "one example" of a dog must be a dog
`
`(e.g., a dog bred with a curly coat that is usually clipped ... ) an "approximate
`
`nearest neighbor search" being "one example" of a "sub linear search that ..... "
`
`64
`
`Page 68 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`must be a sublinear search (i.e., a “sublinear search identifying a close match that
`
`is not necessarily the closest match.”)
`
`VI. ‘237 patent.
`
`106. I understand that the Board instituted the ‘237 IPR based on three
`
`Grounds:
`
`(cid:120) Ground 1: Claims 1, 3–5, 7–9, 11–13, 15, 16, 21–25, 29, 30, 33, 37, and 38
`
`as unpatentable under 35 U.S.C. § 102(e) as anticipated by Iwamura;
`
`(cid:120) Ground 2: Claims 1–3, 5–7, 9–11, 13–15, and 21–24 as unpatentable under
`
`35 U.S.C. § 102(b) as anticipated by Ghias; and
`
`(cid:120) Ground 3: Claims 26, 27, 34, and 35 as unpatentable under 35 U.S.C. § 103
`
`as obvious over Iwamura and Chen.
`
`Decision (‘237) at 21-22. I address each Ground in turn.
`
`A. ‘237 Ground 1: The instituted claims of the ‘237 patent are not
`anticipated by Iwamura.
`
`107. The Board instituted Ground 1 based on the following: Claims 1, 3–5,
`
`7–9, 11–13, 15, 16, 21–25, 29, 30, 33, 37, and 38 as unpatentable under 35 U.S.C.
`
`§ 102(e) as anticipated by Iwamura. Decision (‘237) at 21 (I underlined the
`
`65
`Page 69 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`independent claims). Ground 1 fails because Iwamura does not disclose the
`
`following key elements from each instituted independent claim:
`
`(cid:120) sub-linear time search (claims 1, 5);
`
`(cid:120) approximate nearest neighbor (claims 9 and 13);
`
`(cid:120) nonexhaustive search … to identify a near neighbor (claim 25); and
`
`(cid:120) sublinear approximate nearest neighbor search (claim 33).
`
`I address each in turn.
`
`1.
`
`sub-linear time search (claims elements 1(b) and 5(b.2)).
`
`108. Claims elements 1(b) and 5(b.2) require a “sub-linear time search.”
`
`
`
`109. As I explained above, a “sub-linear time search” is “a search whose
`
`execution time scales with a less than linear relationship to the size of the data set
`
`to be searched.” Decision (‘237) at 7.
`
`
`
`110. One skilled in the art would understand that Iwamura does not
`
`disclose a “sub-linear time search.” Iwamura discloses a searching algorithm that
`
`is designed to be more efficient than alternatives by comparing peak notes from the
`
`work to be identified with the peak notes in the database. Iwamura, 6:59-60; 12:1-
`
`2. While the individual comparisons of a work to a record in the library can be
`
`more efficient using this peak note approach, 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, or
`
`66
`Page 70 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`(b) even the length of an individual record. Instead, each melody in the melody
`
`database is processed as part of the disclosed comparison and “[t]he reference
`
`melody that gives the least difference is returned as a search result.” Iwamura,
`
`7:53-55.
`
`111. Specifically, Iwamura confirms that the referenced Boyer-Moore
`
`algorithm (the basis for alleged disclosure of a sub-linear search in the Petition,
`
`Declaration, and Decision) searches all items in the database and even searches
`
`“word by word from the beginning of the database to the end” and therefore cannot
`
`scale with a less than linear relationship to the size of the data set being search—
`
`i.e., it is not sublinear:
`
`“Boyer Moore (discussed below) or other string-matching algorithms
`do not have this kind of flexibility. They only search word by word
`from the beginning of the database to the end.”
`
`Iwamura, 9:52-55.15
`
`112. The search algorithms disclosed in Iwamura do not reduce the number
`
`of records to be searched during a search (or even the data to be searched within a
`
`record) as the dataset increases. Rather, the disclosed algorithms speed up the
`
`comparison of the work to each record by matching peaks. Iwamura, 9:9-11.
`
`Accordingly, the disclosed algorithms in Iwamura search all records in the library,
`
`15
`
`The word-by-word comparison is valid for the worst case.
`
`67
`Page 71 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`and the computational time that the disclosed search takes to make such
`
`comparisons grows linearly with the number of records in the database (the
`
`relevant analysis) and even linearly with the data in each record. Iwamura
`
`therefore teaches a linear search rather than the claimed “sublinear” search as the
`
`term is used in the IPR Patents, because the computational time that it takes to
`
`perform a search grows linearly as new data is added to the database.
`
`
`
`113. The Petition fails to satisfy its burden of demonstrating that Iwamura
`
`teaches a “sub-linear time search.” As support for the “sub-linear” elements,
`
`Petitioner (and corresponding Declaration) exclusively relies on the Boyer-Moore
`
`algorithm referenced in Iwamura:
`
`114. Petition: The text of the Petition does not address the sub-linear
`
`elements or state that Iwamura discloses a “sub-linear time search.” Pet. (‘237) at
`
`7-10. Neither the word sublinear nor the concept appears in the text of the Petition.
`
`115. Petition Chart: In its chart, Petitioner exclusively relies on the
`
`referenced Boyer-Moore algorithm as support for the sub-linear search elements
`
`(highlighted in yellow in the passages below):
`
`Claim 1(b):
`
`68
`Page 72 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Pet. (‘237) at 10-11.
`
`Claim 5(b.2) (Petitioner references Claim 1):
`
`Pet. (‘237) at 12.
`
`116. Declaration: The Declaration also exclusively relies on the Boyer-
`
`Moore algorithm as support for the sublinear search elements:
`
`Moulin Decl. (‘237) ¶72.
`
`117. Declaration Chart: The chart in the Declaration also exclusively relies
`
`on the Boyer-Moore algorithm:
`
`69
`Page 73 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Claim 1(b):
`
`Moulin Decl. (‘237) ¶75.
`
`Claim 5(b.2) (the Declarant references Claim 1):
`
`Moulin Decl. (‘237) ¶75.
`
`118. Neither the Petition nor Declaration identifies any basis for asserting
`
`that Iwamura discloses the sub-linear search elements other than the referenced
`
`Boyer-Moore algorithm. Pet. (‘237) at 10-12; Moulin Decl. (‘237) ¶72. My
`
`understanding is confirmed by Petitioner’s Declarant:
`
`70
`Page 74 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 82:23-83:3.
`
`119.
`
` One skilled in the art would understand that the referenced Boyer-
`
`Moore algorithm, however, does not disclose or even address a sublinear search—
`
`that is “a search whose execution time scales with a less than linear relationship to
`
`the size of the data set to be searched.” Decision (‘237) at 7. Because Iwamura
`
`itself does not state that Boyer-Moore algorithm is sublinear, the entire basis in the
`
`Petition and corresponding Declaration for the claimed sublinear elements is the
`
`single statement in the Petitioner’s Declaration:
`
`“On the average the [Boyer-Moore] algorithm has a sub-liner behavior.”
`
`Moulin Decl. (‘237) ¶72 (quoting Ex. 1017 at 1). One skilled in the art would
`
`understand that this statement is not accurate with respect to the relevant sub-linear
`
`behavior, i.e., with respect to the size of the database. My understanding was
`
`confirmed by Petitioner’s Declarant who testified that:
`
` (1) he understood that “sub-linear” in the context of the ‘237 patent is
`
`based on the size of the data set searched, not the size of the query or
`
`pattern to be matched (from the work to be identified);
`
`(2)
`
`the Boyer-Moore algorithm does not disclose a search that is sublinear
`
`with respect to the dataset or database or even the length of a record to
`
`be search (it does not even address a database or dataset); and
`
`71
`Page 75 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`(3)
`
`that when he wrote “which is sublinear” in his Declaration, he did not
`
`intend the Board to interpret “sublinear” in the context of the ‘237
`
`patent but instead in a different context unrelated to ‘237 patent.
`
`120. (1) As I noted above, 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 or pattern of the work to be matched (which is the
`
`correct understanding):
`
`Moulin Decl. (‘237) ¶53.
`
`72
`Page 76 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 24:1-12.
`
`Moulin Depo. 26:11-21.
`
`73
`Page 77 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 25:4-12.
`
`Moulin Depo. 26:25-27:15.
`
`74
`Page 78 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 27:16-24.
`
`Moulin Depo. 28:4-16.
`
`75
`Page 79 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 77:14-24.
`
`121.
`
`(2) Petitioner’s Declarant confirmed my understanding—that the
`
`Boyer-Moore algorithm referenced in Iwamura 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 (“There’s
`
`no database in Boyer-Moore.”))—but instead has a relationship to the size of the
`
`query pattern from the work to be identified:
`
`76
`Page 80 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 61:18-24; 44:20-46:6; 59:6-9; 61:25-62:9; 68:25-69:4.
`
`122.
`
`(3) Petitioner’s Declarant confirmed my understanding—that the
`
`statement in his Declaration—Petitioner’s only support for the sub-linear
`
`elements—was wrong. He testified that when he wrote:
`
`(Moulin Decl. (‘237) ¶72) and wrote just a few pages earlier:
`
`(Moulin Decl. (‘237) ¶53), he was not trying to convey that the Boyer-Moore
`
`algorithm was sublinear or “has a sublinear behavior” in the context of the ‘237
`
`patent –i.e., “has a sublinear relationship to the database size”:
`
`Moulin Depo. 74:20-24; 74:8-12.
`
`77
`Page 81 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 69:9-16.
`
`Moulin Depo. 66:9-18.
`
`Moulin Depo. 75:23-76:3.
`
`78
`Page 82 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 67:17-21.
`
`123. Consistent with my understanding, Petitioner’s Declarant clarified that
`
`he was not claiming that the Boyer-Moore algorithm referenced in Iwamura
`
`discloses a sub-linear search in the context of the ‘237 patent, i.e., with respect to
`
`the size of the dataset:
`
`Moulin Depo. 77:25-78:15.
`
`79
`Page 83 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 78:16-79:6.
`
`Moulin Depo. 79:9-18
`
`80
`Page 84 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Moulin Depo. 79:19-80:12; 80:15-83:3.
`
`124. Accordingly, one skilled in the art would understand that the support
`
`in the Petition and Declaration for the sublinear search elements fails to disclose
`
`the sublinear search elements.
`
`125. Board’s concerns: I now address the Board’s specific concerns
`
`(identified in its Decision) with respect to whether Iwamura discloses the claimed
`
`“sub-linear time search.” In instituting Ground 1, I note that the Board preliminary
`
`found that Iwamura disclosed the “sub-linear time search because (a) a sub-linear
`
`81
`Page 85 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`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 Boyer-Moore searches
`
`all items in the database therefore does not demonstrate that the Boyer-Moore
`
`algorithm is not sub-linear:
`
`Decision (‘237) at 11.
`
`Decision (‘237) at 12. It is my opinion that the Board’s preliminary analysis is
`
`flawed on multiple levels for the reasons I explain below.
`
`126. First, the Board’s preliminary analysis is based on an incorrect
`
`interpretation of the construction of sub-linear as it would be understood by one
`
`skilled in the relevant art at the time of the inventions. The Board construed a
`
`82
`Page 86 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`“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. As I explained above in detail above and reflected in in the
`
`Board’s analysis of the construction of sub-linear, the data set is the number of
`
`records in the database to be searched—“the size of the data set (“N”).” Decision
`
`(‘237) at 7.
`
`127. In addition, as I explained above in detail, those skilled in the art
`
`understand that the size of the data set in the context of the ‘237 patent refers to the
`
`number of records in the database to be searched (N) and not the length of any
`
`particular record in the database. This understanding is consistent with Dr.
`
`Moulin’s explanation in his Declaration. See Moulin Decl. (‘237) ¶53.
`
`Accordingly, the Board’s preliminary analysis is based on an improper
`
`interpretation of the construction of “sublinear.”
`
`128. Second, it is my understanding that the Board’s preliminary analysis
`
`has the relevant burden backwards—it is not the Patent Owner’s burden to
`
`demonstrate that the referenced Boyer-Moore algorithm does not disclose a
`
`sublinear search. Rather it is my understanding that it was the Petitioner’s burden
`
`to demonstrate that referenced Boyer-Moore algorithm discloses a sublinear
`
`search. As I showed above, Petitioner failed to satisfy this burden. As I explained
`
`83
`Page 87 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`above, in my opinion, one of ordinary skill in the art would understand that Boyer-
`
`Moore algorithm is not a sublinear search in the context of the ‘237 patent.
`
`129. Third, one skilled in the art would understand that 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 (‘237) at 7); or (b) the length of an
`
`individual record being searched. In my opinion, one of ordinary skill in the art
`
`would understand that it is not.
`
`130. The two references to the Boyer-Moore algorithm in Iwamura are:
`
`Iwamura, 9:52-55.
`
`Iwamura, 9:61-64. While the Boyer-Moore algorithm is described as being
`
`“efficient,” one skilled in the art would understand that neither passage states that
`
`the algorithm is sublinear with respect to either the number of references in the
`
`database or the length of an individual record to be searched.
`
`84
`Page 88 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`131. Fourth, as I explained above, Petitioner’s Declarant confirmed my
`
`understanding—that the referenced Boyer-Moore algorithm does not disclose a
`
`search that is sublinear in the context of the ‘237 patent.
`
`2.
`
`approximate nearest neighbor search (claim elements 9(b)
`and 13(b.2)).
`
`132. As I presented above, one of ordinary skill in the art would understand
`
`that, in the context of the ‘237 patent, an “approximate nearest neighbor search” is
`
`a sub-linear search identifying a close match that is not necessarily the closest
`
`match. Also, as I 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.
`
`133. One skilled in the art would understand that Iwamura does not
`
`disclose the claimed “approximate nearest neighbor search” for two independent
`
`reasons.
`
`
`
`134. Reason 1: One skilled in the art would understand that 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.”
`
`Iwamura discloses a search that always identifies an exact or the closest match.
`
`Consistent with my understanding, Petitioner’s Declarant likewise confirmed that
`
`85
`Page 89 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`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.
`
`135. The system in Iwamura will always find the closest match, even if
`
`unimportant peaks are skipped or repeated patterns are avoided. My understanding
`
`is consistent with the understanding of Petitioner’s Declarant:
`
`(cid:120) “[W]’re still going to be identifying the closest match” even when “the
`
`unimportant peaks are skipped…. Dropping an unimportant part is not going
`
`to affect the ability to find the best match.” Moulin Depo. 317:14-23.
`
`(cid:120) “If we implement that feature of Iwamura… skipping a repeated pattern….
`
`It will not affect the ability to find the best match.” Moulin Depo. 318:11-
`
`18.
`
`136. Petitioner asserts that Iwamura identifies a neighbor because: “the
`
`‘search engine will find the closest melody from the database.” Pet. (‘237) at 8
`
`(quoting Iwamura, 9:24-25)); Moulin Decl. (‘237) ¶69. A person of ordinary skill
`
`in the art would understand that these statements do not disclose an “approximate
`
`nearest neighbor search” which is a search identifying a close match that is not
`
`necessarily the closest match. Instead, these statements confirm that Iwamura
`
`always identifies the closest match—necessarily the closest match—rather than a
`
`match that is not necessarily the closest match as required by the claimed
`
`86
`Page 90 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`“appropriate nearest neighbor search.” See ‘237, 9:15–16 (an “approximate
`
`nearest neighbor search does not always find the closest point to the query.”).
`
`137. Because the searches disclosed in Iwamura necessarily return the
`
`closest match, they are not search algorithms that identify a match that is not
`
`necessarily the closest match, as the properly construed claim element requires.
`
`Accordingly, in my opinion, Iwamura neither expressly nor inherently
`
`(necessarily) discloses an “approximate nearest neighbor search”—a search that
`
`does not necessarily find the closest match.
`
`138. Reason 2: One skilled in the art would understand that Iwamura does
`
`not disclose an “approximate nearest neighbor search” because Iwamura does not
`
`disclose a sublinear search. As I demonstrated above, an “approximate nearest
`
`neighbor search” is “one example” of a sublinear search. Also, as I demonstrated
`
`above, Iwamura does not disclose a sublinear search. Accordingly, Iwamura does
`
`not disclose the claimed “approximate nearest n
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
