Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 1 of 13
`
`UNITED STATES DISTRICT COURT
`SOUTHERN DISTRICT OF NEW YORK
`
`
`
`
`NETWORK-1 TECHNOLOGIES, INC.,
`
`
`
`
`
`Plaintiff,
`
`
`
`v.
`
`
`
`
`
`14 Civ. 2396 (PGG)
`
`14 Civ. 9558 (PGG)
`
`
`
`
`
`
`GOOGLE LLC and YOUTUBE, LLC,
`
`
`
`
`
`
`
`
`Defendants.
`
`
`
`
`
`
`DECLARATION OF PROFESSOR MICHAEL D. MITZENMACHER IN SUPPORT OF
`PLAINTIFF NETWORK-1 TECHNOLOGIES, INC.’S
`REPLY CLAIM CONSTRUCTION BRIEF
`
`
`
`
`
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 2 of 13
`
`I.
`
`INTRODUCTION
`
`1.
`
`I provide this declaration in support of Plaintiff Network-1 Technologies, Inc.’s
`
`Reply Claim Construction Brief. My qualifications are detailed in the declaration I submitted in
`
`this case in support of Network-1’s Opening Claim Construction Brief, and in the curriculum
`
`vitae attached to that declaration.
`
`2.
`
`I provide this declaration in response to several points concerning “non-
`
`exhaustive search” raised by Defendants in their Response Claim Construction Brief, and by Dr.
`
`Storer in his declaration in support of that brief.
`
`II. MATERIALS CONSIDERED
`
`3.
`
`In forming my opinions set forth in this declaration, in addition to the materials I
`
`reviewed in preparing my first declaration, I have also reviewed Defendants’ Responsive Claim
`
`Construction Brief, Dr. Storer and Samuel Davidoff’s declarations in support of that brief and the
`
`exhibits thereto, the transcript of my June 24, 2019 deposition, and the transcript of the July 10,
`
`2019 deposition of Dr. Storer.
`
`4.
`
`As with my first declaration, I have also considered the parties’ respective
`
`proposed claim constructions. In addition, I have relied upon my professional and academic
`
`experience, as well as a number of references identified in the body of this declaration and the
`
`prior submissions. I reserve the right to consider additional materials or information as I become
`
`aware of them and to revise my opinions accordingly in light of such additional information.
`
`III.
`
`“NON-EXHAUSTIVE [. . .] SEARCH”
`
`5.
`
`In my opinion, the term “non-exhaustive search” is a term that is well understood
`
`by skilled artisans in the field of the patents, was well understood at the time of the invention, is
`
`not indefinite, and under the claim construction standard I understand to apply here, should be
`
`
`
`1
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 3 of 13
`
`construed as “a search designed to locate a [near] neighbor without comparing to all possible
`
`matches (i.e., all records in the reference data set), even if the search does not locate a [near]
`
`neighbor.”
`
`6.
`
`The Federal Circuit’s opinion discussed by Dr. Storer does not compel any
`
`different conclusions. I understand that the Federal Circuit applied a claim construction standard
`
`called the broadest reasonable interpretation (“BRI”), which is different from the Phillips
`
`ordinary and customary meaning standard that I understand applies here. The only difference
`
`between the Federal Circuit’s construction and Network-1’s proposed construction is whether
`
`searches that compare against all records, but not necessarily all data within all records, are
`
`exhaustive or non-exhaustive. A comparison of the Federal Circuit’s and Network-1’s
`
`formulation of “exhaustive” is instructive:
`
`
`
`Comparison of all possible
`matches using sufficient data
`to determine whether a given
`record is a match;
`AND any additional data in a
`record, even though not
`necessary to determine if a
`record is a match.
`
`Federal Circuit’s
`BRI Construction
`ü
`
`Network-1’s
`Proposed Construction
`ü
`
`ü
`
`NO
`
`
`Both the Federal Circuit’s BRI construction and Network-1’s proposed construction define an
`
`exhaustive search as one that is designed to compare to all records. Under both, any search that
`
`does not compare to all records is “non-exhaustive.” The only instance in which a search would
`
`be non-exhaustive under the Federal Circuit’s construction but exhaustive under Network-1’s
`
`proposed construction is when the search compares the query to all of the records in the data set,
`
`but does not compare that query to all of the data in each record. This would only arise where
`
`comparison of the query to a particular record could determine that the record either does or does
`
`
`
`2
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 4 of 13
`
`not match the query without comparing to all of the data in that record. If there is no extraneous
`
`data in the records used in a search, the definitions merge and there is no difference between the
`
`Federal Circuit’s BRI construction and Network-1’s construction.
`
`7.
`
`As an oversimplified example, if the reference set has a record for each of 100
`
`pieces of music and includes 10 characteristics about each piece, but a query is seeking to
`
`determine only which records match a specific five of those characteristics, that search would
`
`only need to compare the query to the relevant five characteristics, and not to the other five,
`
`irrelevant (to this search) characteristics. This search would be exhaustive under Network-1’s
`
`proposed definition because it would compare the query to all of the records, but would not
`
`compare the query to the extraneous and unnecessary data in the records that was not needed to
`
`determine if a record was or was not a match to the query. If there is no extraneous data in the
`
`records, then the Federal Circuit’s definition of “exhaustive” merges with Network-1’s
`
`definition. The only type of search that would be “exhaustive” under the narrower understanding
`
`of that term applied by the Federal Circuit, but not under Network-1’s definition is one that is
`
`forced to compare against extraneous data in one or more records (i.e., data that is not needed to
`
`determine or is irrelevant in determining whether or not a record is a match). The use of a
`
`definition that would define non-exhaustive searches based on whether or not they perform
`
`comparisons to unnecessary and extraneous portions of the data in a record is not consistent with
`
`the understanding that a person skilled in the art would have based on the usage in the art, and
`
`based on the intrinsic record of the patents, including the references that are incorporated by
`
`reference in the patents, as discussed further below and in my prior declaration. As a general
`
`matter, I do not agree that there are multiple, equally possible definitions of “non-exhaustive . . .
`
`search” to persons skilled in the art understanding that term in light of the intrinsic evidence of
`
`
`
`3
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 5 of 13
`
`the Network-1 patents and their file histories, nor do I agree that the term is unclear or somehow
`
`renders the claims of the patens-in-suit uncertain. Put simply, a skilled artisan would not design
`
`a search that unnecessarily compares against extraneous or irrelevant data, as it would be a
`
`wasteful use of computing resources, nor would such a skilled artisan use the term “exhaustive
`
`search” only to refer to such searches that may perform unnecessary work.
`
`8.
`
`In particular, the patent specification indicates the term “non-exhaustive search”
`
`does not render the claims indefinite, and supports Network-1’s construction. As explained in
`
`detail in my first declaration, a skilled artisan would have understood with reasonable certainty
`
`what searches were within the scope of the claims based on the specification’s focus on efficient
`
`searching as well as the exemplary searches it provides—all of which are algorithms that
`
`examine a data set by comparing a query to less than all of the records in the data set.
`
`9.
`
`The specification does not explicitly address how much data within each record
`
`must be compared to a query in any of the searches it describes. However, as I explain above in
`
`the context of evaluating the Federal Circuit’s construction, a person of skill in the art would
`
`have recognized there is no reason the specification should do so—he or she would have known
`
`it may not be necessary to examine all data in a given record to determine whether or not that
`
`record is a match. In particular, a skilled artisan would have known to design a search, including
`
`those that compare all records to a query, so that the search compares against only sufficient data
`
`in the record to the query to determine whether or not a given record is a match. To avoid
`
`examining unnecessary data and using more computer resources than necessary, the skilled
`
`artisan would have known to not compare against extraneous, irrelevant, or any data beyond
`
`what is sufficient to reach a conclusion about the record—such searches are simply not
`
`conducted and therefore are of course not described in the literature. A person of skill in the art
`
`
`
`4
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 6 of 13
`
`would have therefore known that the specification was drawing a distinction between searches
`
`that compare against all records (exhaustive) to those that do not (non-exhaustive). For example,
`
`the specification of the ’988 patent refers to the difference between a binary search (non-
`
`exhaustive under both Network-1’s definition and the BRI definition used by the Federal Circuit)
`
`and a “linear search of all N entries.” ’988 patent at 9:19-28. A skilled artisan would understand
`
`that this distinction is about whether two kinds of different searches, those designed to compare a
`
`query to all of the records in the database (exhaustive) and those designed to compare the query
`
`to fewer than all of the records in the database (non-exhaustive). These two kinds of searches are
`
`not distinguished by whether or not they compare the query to all of the data in each record
`
`because even the linear search described in the patent might not need to compare the query to all
`
`of the data in each record. This understanding of a skilled artisan is confirmed by the explicit
`
`language in the specification that distinguishes the searches by the number of comparisons
`
`performed (not the amount of data in each record compared). The specification contrasts the
`
`binary search requiring “at most log(N) comparisons” to the “linear search of all N entries,”
`
`indicating that “[o]n average, this will require N/2 comparisons.” Id. N in both of these refers to
`
`the number of entries (records) in the database, as explicitly stated in the patent specification.
`
`The amount of data in each record compared to the query is not the relevant distinction; the
`
`relevant distinction is the number of records compared.
`
`10.
`
`This distinction (based on the number of comparisons) is also true of the other
`
`types of searches discussed in the patent specification. kd-trees, vantage point trees, and
`
`excluded middle vantage point forests are specifically referenced in the specification. See id. at
`
`9:29-38, 22:1-37. These types of search techniques are also discussed in various references
`
`discussed in my prior declaration, which are incorporated by reference into the patent
`
`
`
`5
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 7 of 13
`
`specification. Those references and these search techniques are all distinguished from
`
`exhaustive searching by the fact that they are designed to compare the query to fewer than all of
`
`the references in the database. The specification notes that not all such searches would
`
`necessarily be sublinear, but notes that the “excluded middle vantage point forest . . . guarantees
`
`sub-linear worst-case search times.” Id. at 22:10-15. The key distinction between such an
`
`excluded middle vantage point forest search and a linear search is that the excluded middle
`
`vantage point forest search is designed not to compare the query to all of the references in the
`
`data set, not whether or not the searches compare the query to all data in records in the reference
`
`set. For example, using the same criteria, both a linear search and an excluded middle vantage
`
`point search of the same data set might only require comparing the query to something less than
`
`all of the data in at least some of the records in the data set, but one would compare the query to
`
`all records, and the other would not. This again shows the patent specification clearly pointing a
`
`skilled artisan toward the well-understood distinction in the art between exhaustive and non-
`
`exhaustive searches—whether or not the search is designed to compare the query to all records in
`
`the data set.
`
`11.
`
`In addition, I have reviewed the various “extrinsic” references the parties
`
`submitted. None of the extrinsic references (books, articles, and patents) indicate or imply that
`
`exhaustive search requires comparison to both all records and all data in each of those records.
`
`Similarly, none of these references describe a non-exhaustive search that compares to every
`
`record in the data set. In addition, Dr. Storer also provided no testimony in his declaration or at
`
`his deposition that the Federal Circuit’s construction is the correct construction under the Phillips
`
`standard I understand applies here, or that it is the ordinary and customary meaning of this term
`
`
`
`6
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 8 of 13
`
`to a person of skill in the art. In particular, Dr. Storer was unable to directly answer the
`
`questions on these points from Network-1’s counsel:
`
`Q. Can you identify any references in the literature that say that in order to
`be exhaustive one has to not only consider all possible records, but has to
`consider all data in the record, including data that is not necessary or
`relevant to determine whether the entry is a match?
`A. I seem to recall a number of references that were ambiguous on that point.
`They didn’t address it one way or the other, so you don’t know; again, another
`evidence that there is no agreed-upon definition.
`And I don’t know -- I can’t remember -- I go over -- I give a number of examples
`in my declaration as to whether one of them included that. I’d have to look
`through the declaration. So I don’t remember specifically, sitting here without
`reviewing those examples, whether one of them explicitly said that. I do recall a
`number of them saying, the effect I don’t want to do the exhaustive thing. I do
`want to do whatever it is the paper’s about.
`And when they said they didn’t want to do it, it was unclear in some cases exactly
`what that meant. Did it mean examining all the data in every match? Examining
`it even if -- of course, even if depended on the literature. Sometimes there was no
`alternative. Even the court mentions that. Sometimes you sort of had to look at
`everything. You know, the way -- the way the application was there really wasn’t
`-- it wouldn’t even fit into your question.
`So I don’t remember specifically sitting here. I could look at some of the
`examples in the report.
`Q. As you sit here, can you identify any reference in the literature that says
`unambiguously that in order to be exhaustive, one has to consider not only
`all possible records, but has to consider all data in the record, including data
`that is not necessary or relevant to determine whether the entry is a match?
`A. Actually, so that’s -- that’s a good question. Many or most of the references
`don’t really give an explicit -- they’re often very ambiguous about exhaustive.
`Because what they’re doing is trying to advocate some approximation or fast
`thing, and they just don’t want to do anything that would be considered
`exhaustive under any number of definitions.
`So I do not recall, without looking at my report at this moment, a specific formal
`definition of that nature. In fact, very -- it was very hard to find any reference that
`actually tried to define exhaustive. It usually was we just don’t want to be
`exhaustive and we want to do something else, which was the point of the
`reference, as typical.
`There was one I identified -- in fact, let me go there. But I don’t think that
`particular one is exact -- is exactly what you’re asking. Let me see if I can find
`that, and I will double check that one anyway.
`
`
`
`7
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 9 of 13
`
`Well, I can’t find it right now. I do recall pointing out one reference that actually
`attempted to define exhaustive, but I don’t think it defined it in the way you’re
`proposing, so I don’t think it would be an example to your question in my best --
`and that’s my best memory. And so my best memory is that at least within this
`declaration, I don’t cite a reference and I don’t recall a reference that explicitly
`gave that definition.
`In fact, I recall it being very difficult to find any references that gave any explicit
`definition, and that was one of the problems that I point out, that different
`references seemed to use it in a different way, rarely would give a formal
`definition, et cetera.
`Q. So as you sit here, you’re not able to identify and can’t identify anything
`in your declaration, any reference, that unambiguously defines exhaustive
`such that in order to be exhaustive one has to consider not only all possible
`records, but would have to consider all data in the record, including data
`that is not necessary or relevant to determine whether that entry is a match,
`correct?
`A. So just to be clear, I saw quite a few references that might, in fact, include that.
`They were just ambiguous about that. They didn’t address that point one way or
`the other. They simply said they don’t want to do this, and so that -- but in terms
`of unambiguous -- and that’s your question, formal definition, almost -- it was
`very difficult to find any reference that had a formal definition that was specific.
`Some of them clearly steered you to different understandings, but many of them,
`even if the understanding was different than another one, may not have addressed
`that point one way or the other.
`
`Transcript of Deposition of James A. Storer, dated July 10, 2019 (attached to concurrently filed
`
`declaration of Amy E. Hayden as Exhibit 1) at 89:16-93:14. By contrast, I am able to answer
`
`counsel’s question definitively—none of the references cited by Network-1, Defendants, Dr.
`
`Storer, or myself state that “in order to be exhaustive one has to not only consider all possible
`
`records, but has to consider all data in the record, including data that is not necessary or relevant
`
`to determine whether the entry is a match,” and I am not otherwise aware of any such references.
`
`Moreover, a person of skill in the art would understand that the distinction between the
`
`exhaustive and non-exhaustive searches in these references is the number of records the searches
`
`compare against, not the amount of data in each record that is compared.
`
`12.
`
`I understand that Defendants criticize the Orwant reference I cited in my first
`
`
`
`8
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 10 of 13
`
`declaration because it states that the “the definition of exhaustive search is vague.” See Dkt. No.
`
`148-20 (Orwant) at 183. In my opinion, a person of skill in the art would understand the
`
`“vagueness” Orwant refers to is that there are different ways to perform exhaustive searches, i.e.,
`
`there are numerous exhaustive search algorithms. As Orwant explains, “[t]he exact meaning of
`
`‘try everything’ depends upon the particular problem.” Id. For some problems, you might have
`
`to compare against all of the data in one or more records; for other problems, you might not. But
`
`a person of skill in the art would understand that both of these searches would be exhaustive.
`
`13.
`
`The non-technical example Orwant provides would also be informative to the
`
`skilled artisan. In this example, finding the most interesting item in a large museum (the British
`
`Museum), one would not need to examine all “data” in each item to determine if it is interesting
`
`or not. See id. at 180. There would be no reason to examine every brushstroke of a painting if
`
`one were not interested in paintings as a whole. Similarly, a skilled artisan would not design an
`
`exhaustive search algorithm to do the unnecessary work of continuing to examine data in a given
`
`record if it already determined the record was not a match.
`
`14.
`
`Dr. Storer also opines that a person of skill in the art would not know what to
`
`make of Denny’s reference to “pruning” and “backtracking.” See, e.g., Dkt. No. 152 (Storer
`
`Decl.) ¶¶ 57, 66-68, 73. But as Denny explains, “the use of intelligent pruning techniques, such
`
`as rejecting partial feasible solutions which either cannot extend to valid solutions or are
`
`equivalent in some way to feasible solutions already considered, can significantly reduce the
`
`required execution time of such an [exhaustive] algorithm.” Dkt. No. 148-19 (Denny) at 48. I
`
`also addressed this issue at my deposition. See Dkt. No. 153-12 (Mitzenmacher Depo.) at
`
`171:11-172:16, 174:3-176:8, 186:3-12 (explaining how Denny’s backtracking algorithm is
`
`designed to compare to every record in the data set in the “worst case” scenario).
`
`
`
`9
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 11 of 13
`
`15.
`
`Dr. Storer also points to the Nievergelt reference as inconsistent with Network-1’s
`
`proposed construction. See Storer Decl. ¶ 71. But Nievergelt explains that “[i]n a worst case
`
`configuration, however, exhaustive search is forced to visit all states of S.” Dkt. No. 153-18
`
`(Nievergelt) at 25. Like Denny, Nievergelt also provides “backtrack” as an example of a
`
`common exhaustive search algorithm. Id. Nievergelt contrasts such exhaustive searching with
`
`one of the examples of non-exhaustive search in the patent specification: “By constant, binary
`
`search is not exhaustive; when the table contains 3 or more keys, binary search will never probe
`
`all of them.” Id. Thus, like the patent specification, Nievergelt is distinguishing between
`
`exhaustive and non-exhaustive searches based on whether they are designed to compare the
`
`query to all of the records in the dataset. References to “worst case” in these kinds of references
`
`are helpful because this clarifies that there might be a non-worst case where, for example, a
`
`solution (match) is found before completing the comparison to every record in the dataset. The
`
`patent specification points to the same feature of linear search, noting that, on average, a linear
`
`search will require “N/2 comparisons.” ’988 patent at 21:23-39. This refers to the idea that you
`
`could stop when you found the result (match) to the query, so over a number of times running a
`
`search, the probability is that on average, you will have performed a comparison to half of the
`
`records in the database before finding a match. In a “worst case” however, the match is not
`
`found until a comparison to the very last record in the database, in which case the query would
`
`be compared to every record in the database.
`
`16.
`
`As with the specification, a skilled artisan would have understood why these
`
`“extrinsic” references do not explicitly state how much data within each record is considered in
`
`an exhaustive search—a skilled artisan would not design a search algorithm to examine more
`
`
`
`10
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 12 of 13
`
`data than necessary and thus use more computer resources than needed to determine whether any
`
`individual record matched or did not match the query parameters.
`
`17.
`
`Dr. Storer further opines that a defining characteristic of a non-exhaustive search
`
`is that is does not guarantee finding a match if one exists in the data set. See Storer Decl. ¶¶ 76-
`
`78, 82. However, this is the wrong focus. As I explained in my first declaration and at my
`
`deposition, some non-exhaustive searches, such as the binary search and vantage point trees
`
`examples referenced in the patent specification, can guarantee finding a match if one exists in the
`
`data set. See Mitzenmacher Depo. at 202:1-9.
`
`18.
`
`Finally, from my review of Defendants’ responsive brief, Dr. Storer’s declaration,
`
`and his deposition testimony, it is clear that Defendants did not specifically address whether
`
`claim 17 of the ’988 patent is indefinite. I understand that claim 17 “depends” from claim 15,
`
`meaning that claim 17 contains all the claim elements of claim 15 as well as the claim limitation
`
`that it adds: “wherein the non-exhaustive search is sublinear.” ’988 patent at claim 17.
`
`19.
`
`I further understand that the parties have agreed that a “sublinear” search is “a
`
`search whose execution time scales with a less than linear relationship to the size of the data set
`
`to be searched, assuming computer power is held constant.” By contrast, a linear search is a
`
`search whose execution time scales proportionately with the size of the data set to be searched.
`
`A search that compares to all records scales linearly: as the number of records, N, doubles, so
`
`will the time to compare to all N records. There are examples of searches that compare to less
`
`than all records in a data set that scale linearly, such as those that compare to the same
`
`percentage of a random selection of records in the data set regardless of data set size (a search
`
`that compares to a random half of the records does not compare against all records, but the time
`
`required for such a search scales linearly with the size of the data set, since it always compares
`
`
`
`11
`
`
`
`

`

`Case 1:14-cv-02396-PGG-MHD Document 158-7 Filed 07/19/19 Page 13 of 13
`
`against half of the records). But any search that compares to all records is a linear search, as it
`
`will necessarily scale proportionately with the size of the data set. Sublinear searches thus
`
`necessarily compare to less than all records in the data set. Even if Dr. Storer were correct that
`
`the possible definitions of “non-exhaustive” search that he puts forward created some ambiguity
`
`about whether a particular search was “non-exhaustive” (he is not), the “sublinear” limitation of
`
`claim 17 resolves any such purported ambiguity. Thus, even if “non-exhaustive” search were
`
`indefinite standing alone (and again, it is not), claim 17 of the ’988 patent would not be
`
`indefinite because the additional, narrowing clarification of “sublinear” to that term removes any
`
`such ambiguity. Dr. Storer suggests that some searches might compare a query to every record
`
`in a database, but not to all of the data in every record, and that, in his view, such a search could
`
`fairly be described as non-exhaustive. While I disagree that such a search could be called non-
`
`exhaustive, Dr. Storer does not suggest that any search that fit that description could also be
`
`sublinear. Indeed, a search that was designed to compare a query to all records in a database
`
`would not be sublinear. In my view, claim 17 of the ’988 patent is not indefinite for this
`
`additional reason.
`
`
`
`I declare under penalty of perjury that the forgoing is true and correct. Executed this 19th day of
`
`July 2019 at Lexington, Massachusetts.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Prof. Michael D. Mitzenmacher
`
`
`
`
`
`12
`
`
`
`