UNITED STATES PATENT AND TRADEMARK OFFICE
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`GOOGLE,
`
`INC., and YOUTUBE, LLC,
`
`Petitioner,
`
`vs.
`
`NETWORK-l TECHNOLOGIES,
`
`INC.,
`
`Patent UWHEJT .
`
`Case No.
`
`IPR2D15—flU34?
`
`VIDEOTAPED DEPOSITION OF PIERRE MOULIN, PhD
`
`VOLUME I
`
`Santa Monica. California
`
`Wednesday, August 19. 2Ul5
`
`NETWORK—l EXHIBIT 2006
`
`Google Inc. 1!, Network-1 Technologies, Inc.
`IPR2{}lS-00345
`
`REPORTED BY: RICH ALOSSI, RPR, CORR, CSR NO. 13497
`
`Job No: SEEDS
`
`TSG Reporting H Worldwide - BT7—Tfl2~95Bfl
`Pagel uf3H4
`
`
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`GOOGLE,
`
`INC., and YOUTUBE, LLC,
`
`Petitioner,
`
`vs.
`
`NETWORK-l TECHNOLOGIES,
`
`INC.,
`
`Patent UWHEJT .
`
`Case No.
`
`IPR2D15—flU34?
`
`VIDEOTAPED DEPOSITION OF PIERRE MOULIN, PhD
`
`VOLUME I
`
`Santa Monica. California
`
`Wednesday, August 19. 2Ul5
`
`NETWORK—l EXHIBIT 2006
`
`Google Inc. 1!, Network-1 Technologies, Inc.
`IPR2{}lS-00345
`
`REPORTED BY: RICH ALOSSI, RPR, CORR, CSR NO. 13497
`
`Job No: SEEDS
`
`TSG Reporting H Worldwide - BT7—Tfl2~95Bfl
`Pagel uf3H4
`
`
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`GOOGLE,
`
`INC., and YOUTUEE, LLC,
`
`Petitioner,
`
`vs.
`
`NETWORK-l TECHNOLOGIES,
`
`INC.,
`
`Patent Owner .
`
`Case No.
`
`IPR2D15—flU3é?
`
`‘JIDEOTAPED DEPOSITION OF PIERRE MOULIN, PhD,
`
`VOLUME I,
`
`taken on behalf of the Patent Owner, at 2G1
`
`Santa Monica Boulevard, Sixth Floor, Santa Monica,
`
`California, on Wednesday, August 19, 21315,
`
`from 9:02 AM to
`
`5:39 PM, before RICH ALOSSI, RPR, CORR, CSR NO. 13497.
`
`'.i.".|l'1|‘
`
`TSG Reporting H Worldwide - 8T7—Tfl2-958d
`Page 2 of 384
`
`
`
`APPEARANCES:
`
`For the Plaintiff:
`
`SKADDEN ARPS SLATE MEAGHER & FLOM
`
`BY:
`
`JAMES ELACQUA, Attorney at Law
`IAN CHEN, Attorney at Law
`525 University Avenue
`Palo Alto, CA 94361
`
`For the Patent Owner Network-l Technologies:
`
`DDVEL & LUNER
`
`GREGORY DOUEL, Attorney at Law
`BY:
`2fll Santa Monica Boulevard
`
`Santa Monica, CA Qfldfll
`
`-and-
`
`RUSS AUGUST & KAEAT
`
`MARC FENSTER, Attorney at Law
`BY:
`12424 Wilshire Boulevard
`
`Los Angeles, CA 9flD25
`
`Also Present:
`
`SCOTT MOHAIR, Videographer
`RICH SONNENTAG, Litigation Counsel, Googie,
`MATTHAEUS WEINHARDT
`
`Inc.
`
`TSG Reporting H Worldwide - BT7—Tfl2-95Bfl
`Page 3 1;:-F384
`
`
`
`I30--JETILHI-l‘-5L.nJf\J}—‘
`
`WITNESS
`
`PIERRE MDULIN, PhD, VOLUME I
`
`BY MR. DGVEL
`
`MARKED
`
`E X H I E I T S
`
`Exhibit E—23T— Decision re Institution of Inter
`
`Partes Review
`
`Exhibit
`
`lUU1-23- United States Patent Number
`
`8,2U5,23? E2
`
`Exhibit
`
`lflfle-lT— Declaration of Dr. Pierre Noulin
`
`in Support of Petition for Inter
`Partes Review of US Patent
`
`Number 3,EdU,1T9
`
`Exhibit
`
`lUU4—23— Declaration of Dr. Pierre Moulin
`
`in Support of Petition for Inter
`Partee Review of Us Patent
`
`Number 8,2U5,23?
`
`Exhibit
`
`lUU4-98- Declaration of Dr. Pierre Noulin
`
`in Support of Petition for Inter
`Partes Review of US Patent
`
`Number 3,fllU,93B
`
`1UU9— United States Patent Number
`
`6,9?U,E86 El
`
`1UlU- United States Patent Number
`
`5,8?d,E36
`
`1012- United States Patent Number
`
`E,lE8,U1U Bl
`
`2DU5— Handwritten List of Formulae
`
`TSG Reporting H Worldwide - 8T?—TU2-958D
`Page 4 of 384
`
`
`
`"A Fast String
`Exhibit 2UflE— Article Titled,
`Searching Algorithm," October
`19??
`
`Exhibit 2UfiT— Iwamura Data Examples
`Spreadsheet
`
`TSG Reporting H Worldwide H 8T7~Tfl2~95Bfl
`Page 5 of 384
`
`
`
`SANTA MONICA, CALIFORNIA; WEDNESDAY, AUGUST 19, 2fl15
`
`9:02 AM - 5:39 PM
`
`THE VIDEDGRAPHER: Good morning. This is the
`
`start of Tape Number 1 of the videotaped deposition
`
`of Pierre Moulin in the matter of Google,
`
`Incorporated, and YouTube, LLC, versus Network—l
`
`Technologies,
`
`Incorporated. This oase is before the
`
`US Patent and Trademark Office, Patent Trial and
`
`Appeal Board. Case number is IPR2Ul5-flD34?.
`
`This deposition is being held at 291 Santa
`
`Monica Boulevard, on the sixth floor,
`
`in
`
`Santa Monica, California. Today's date is
`
`August l9th, 2915.
`
`The time is 9:03 AM.
`
`My name is Scott MoNair from TSG
`
`Reporting,
`
`Incorporated.
`
`I‘m the legal video
`
`specialist.
`
`The court reporter today is
`
`Rich Alossi, also in association with TSG Reporting.
`
`Will oounsel please identify yourselves
`
`for the record.
`
`MR. DGVEL: My name is Greg Dovel.
`
`I
`
`represent the patent owner, Network-1.
`
`MR. ELACQUA: My name is Jim Elaogua with
`
`Skadden Arps, here to represent Google and YouTube.
`
`MR. CHEN:
`
`Ian Chen with Skadden, also on
`
`TSG Reporting H Worldwide - ST?—Tfl2-9589
`Page 15 of 384
`
`
`
`behalf of Google and YouTube.
`
`MR. SONNENTAG: Rich Eonnentag.
`
`in-house
`
`oounsel at Google.
`
`MR. FENSTER: Mare Fenster with Russ. August
`
`&
`
`Rabat, representing the patent holder in the
`
`litigation.
`
`THE UIDEOGRAPHER:
`
`Thank you. Will
`
`the court
`
`reporter p1ease swear in the witness.
`
`THE REPORTER:
`
`Please raise your right hand.
`
`Do you solemnly state that the testimony
`
`you are about
`
`to give in the matter now pending
`
`shall be the truth,
`
`the whole truth and nothing but
`
`the truth?
`
`THE WITNESS:
`
`I do.
`
`THE REPORTER:
`
`Thank you.
`
`We're on the reoord.
`
`PIERRE MOULIN, PhD,
`
`having been first duly sworn by
`
`the court reporter, was examined
`
`and testified as follows:
`
`BY MR. DOUEL:
`
`EXAMINATION
`
`Q
`
`Your name is pronounced -- is it Moulin?
`
`TSG Reporting H Worldwide - ET?—TO2-BEBO
`Page "I of3H4
`
`
`
`Yes. Almost.
`
`Dr. Moulin?
`
`Yes.
`
`Q
`
`How, Dr. Moulin, you're familiar with the
`
`concept of whether or not an algorithm is suhlinear?
`
`A
`
`Yes.
`
`Q Were you familiar with that before you
`
`started work on this case?
`
`A
`
`Yes
`
`Q When is it during the course of one's
`
`education that one would learn about
`
`the concept of
`
`suhlinear?
`
`A
`
`The concept of sublinear arises in many
`
`contexts, not just databases.
`
`The first time
`
`someone would be exposed to that would be typically
`
`in a university course, depending on their field.
`
`Q
`
`when you say "university Qourse," what
`
`course would that be?
`
`ME. ELACQUA:
`
`It depends on the field.
`
`So it
`
`could be in computer science. Often that might be
`
`TSG Reporting - Worldwide - 3TT*'?fl2~E+5Eifl
`Pngcfloffifld
`
`
`
`introduced at the senior level, or if it's
`
`electrical engineering,
`
`that might also be
`
`introduced around the same time.
`
`Each program is a
`
`different curriculum.
`
`MR. DDVEL:
`
`I'm going to mark as Exhibit
`
`Number lDU4—23T the Declaration of Dr. Moulin from
`
`the case related to the '23? patent.
`
`{Exhibit 1DD4—23T was marked for
`
`identification by the court reporter and is
`
`attached hereto.}
`
`MR. DDVEL:
`
`I've placed that in front of the
`
`witness.
`
`BY MR. DOUEL:
`
`Q
`
`In your Declaration that I've placed in
`
`front of you, you provide a definition of the
`
`concept of sublinear execution time;
`
`is that
`
`correct?
`
`A Where?
`
`Q
`
`A
`
`Q
`
`Pages 19 to 20 of your Declaration.
`
`That is correct, yes.
`
`How, on page 2D you've got a diagram that
`
`illustrates the concept of what is a sublinear
`
`search and what is a linear search; correct?
`
`A
`
`Q
`
`It illustrates it, yes.
`
`Is it the case that if we have a linear
`
`TSG Reporting H Worldwide - 8T?—TD2-958D
`Page 9 of 384
`
`
`
`search,
`
`that it will have a constant slope as you've
`
`depicted in your diagram there?
`
`A
`
`"Constant slope" in terms of ——
`
`in terms
`
`of the number of entries in the search database, you
`
`mean?
`
`Is that what you mean?
`
`Q
`
`A
`
`Q
`
`Yes. Yes.
`
`In this example, yes.
`
`Is it the case that as sublinear is used
`
`in the patent, it's going to result in a scaling of
`
`the search time compared to the size of the database
`
`such that it will have a constant slope?
`
`A
`
`Q
`
`A
`
`Q
`
`You say if it is a linear search?
`
`If it's a linear search. Right.
`
`So let me give you a different question.
`
`Only in this example, yes.
`
`Let me give you a different question so we
`
`have a clean record.
`
`If we have an algorithm that is a linear
`
`search,
`
`is it the case that it will have a constant
`
`slope if we plot the search time compared to the
`
`size of the database?
`
`A
`
`Q
`
`Yes.
`
`Is it the case that if we have a sublinear
`
`search,
`
`then the slope will curve down and approach
`
`zero if we plot search time compared to the size of
`
`TSG Reporting H Worldwide - 8??—?fl2-958$
`Page II] of 334
`
`
`
`the database?
`
`A
`
`Not necessarily.
`
`Q When wouldn't it do that?
`
`A
`
`Because this is an example that shows only
`
`how search time is as a function of number of
`
`entries in the search database. But that's not the
`
`only criterion.
`
`Q What's the other criteria?
`
`A Well, it's the size of the database that
`
`matters.
`
`So number of entries is only one factor
`
`that affects the size of the database.
`
`Q
`
`Let's -- let's talk about the size of the
`
`database,
`
`then.
`
`Is it the case that if we have a sublinear
`
`search as it's used in the Cox —— withdrawn.
`
`When we're talking about the Cox patents,
`
`do you understand we're talking about the four
`
`patents that you filed declarations for in
`
`connection with these proceedings before the PTAE?
`
`A
`
`Q
`
`Yes.
`
`If we have a sublinear search as it's used
`
`in the Cox patents,
`
`is it the case that if we plot
`
`search time compared to the size of the database
`
`over which we are searching,
`
`then the —— it will
`
`produce a curve such that it curves downward and
`
`TSG Reporting H Worldwide - 8T?—Tfl2-958$
`Pagell of3H4
`
`
`
`approaches zero?
`
`A
`
`You need to be more specific. Sublinear
`
`is mentioned in many places in all four patents in
`
`slightly different contexts.
`
`So I would like you to
`
`be more specific.
`
`Q
`
`Are you —— is it your testimony --
`
`withdrawn.
`
`We're talking about suhlinear as it's used
`
`in the claims of the patents.
`
`A
`
`Q
`
`Right.
`
`You understand that some of the claims
`
`have the phrase "sublinear search," some of them
`
`have the phrase "sublinear time search"?
`
`A
`
`Q
`
`That‘s my recollection.
`
`Is it the case that suhlinear search and
`
`sublinear time search mean the same thing in the
`
`patents?
`
`A
`
`I would have to check every instance of
`
`sublinear data. Used in different contexts,
`
`sometimes not defined precisely, you would have to
`
`refer me to a specific instance.
`
`Q
`
`As the phrase "sublinear search“ is used
`
`in the claims of the patents,
`
`is it used
`
`consistently, or does it mean different things in
`
`the claims?
`
`TSG Reporting H Worldwide - 8T?—Tfl2-95Bfl
`Page [2 of 33.4
`
`
`
`A
`
`Q
`
`It's used somewhat vaguely.
`
`I didn't ask whether it was vague.
`
`I want
`
`to know does it mean the same thing or does it mean
`
`different things?
`
`A
`
`I don't know. Because it's done vaguely,
`
`I cannot know for sure.
`
`Q
`
`You don't know one way or the other --
`
`withdrawn.
`
`When you did your analysis and decided
`
`that the prior art anticipates --
`
`A
`
`0
`
`Right.
`
`—— and you decided that it disclosed a
`
`sublinear time search, what definition did you use?
`
`A
`
`It's in relation to the size of the
`
`database, which itself depends both on the number of
`
`entries in the database and on the size of each
`
`entry, each record. That's the standard definition.
`
`Q
`
`A
`
`That's the standard definition: right?
`
`Yes.
`
`Q When you say "standard," you're talking
`
`about
`
`the standard, well—known definition in the
`
`art?
`
`A
`
`Yes
`
`TSG Reporting — Worldwide — 3T7*Tfl2~95Bfl
`Page I3 of 334
`
`
`
`Q
`
`and we can increase the size of the
`
`database either by increasing the number of entries
`
`or by increasing the size of each entry in the
`
`database?
`
`A
`
`Q
`
`That is correct.
`
`Is it the case that if we have a sublinear
`
`search —e withdrawn.
`
`Is it your understanding that the term
`
`"suhlinear search" and "sublinear time search" is
`
`used in the patent claims to have that definition
`
`that you just gave,
`
`the standard definition?
`
`A
`
`Again, it has often not been defined
`
`precisely.
`
`The word "sublinear" is used in a
`
`slightly different context
`
`in the different patents.
`
`When they say "sublinear," my
`
`understanding is, again, consistent with the art.
`
`I
`
`understand that to mean what we just discussed.
`
`So
`
`it would mean what you just discussed.
`
`So every time I read "sublinear“ in the
`
`patents,
`
`that's my understanding of it.
`
`Even though
`
`it was not clearly defined.
`
`TSG Reporting - Worldwide - 3TT*'?fl2~E+5Eifl
`F'ag¢|4of3$4
`
`
`
`MR. DDVEL:
`
`I'm going to place in front of the
`
`witness another exhibit which I'm going to mark as
`
`Exhibit
`
`lDfll—23?. This is the '23? patent.
`
`{Exhibit
`
`lflfll-23? was marked for
`
`identification by the court reporter and is
`
`attached hereto.}
`
`BY MR . DCWEL:
`
`Q
`
`I'd like you to turn to the claims of the
`
`'23? patent.
`
`Do you see Claim 1 uses the phrase
`
`“suhlinear time search"?
`
`A
`
`Q
`
`Yes.
`
`Do you see Claim 5 uses the term
`
`"suhlinear time search"?
`
`A
`
`Q
`
`res.
`
`Does the phrase “sublinear time search,"
`
`as it's used in the '23? patent claims, refer to a
`
`search where the search time decreases at less than
`
`a linear -- or increases at less than a linear rate
`
`as we increase the size of the dataset over which
`
`we're searching?
`
`A
`
`The claims do not say "as you increase the
`
`size of the database."
`
`If I read Claim 5, it reads,
`
`“A suhlinear
`
`time search of extracted features of identified
`
`TSG Reporting H Worldwide - 8T?—Tfl2-95Bfl
`Page [5 of 33.4
`
`
`
`media works," by which ene eeuld understand that it
`
`means in terms ef the database size. But it's
`
`not -— it does not read that explicitly.
`
`I
`
`F—"
`
`2 3 I
`
`C
`
`I
`
`I
`
`I
`
`I
`
`-—
`
`C I
`
`_ C
`
`I
`
`C
`
`C
`
`C
`
`_ -
`
`II
`
`C I—
`
`- I
`
`-—
`
`D I
`
`--
`
`C I-
`
`!'\J ILJ'|
`
`MR. DU?EL:
`
`I'm going to mark as Exhibit 2DU5
`
`TSG Reporting - Worldwide - 3?"!-'?C|2~E+5Eifl
`Pagclfioflfl
`
`
`
`a blank piece of notebook paper.
`
`and we‘re going to
`
`make some notations on it.
`
`{Exhibit 2DD5 was marked for identification
`
`by the court reporter and is attached
`
`hereto.}
`
`MR. DQVEL:
`
`and the first thing I'm going to
`
`write is "DEHI." I'm going to stick that in front of
`
`the witness.
`
`THE WITNESS: Qkay-
`
`BY MR. DQVEL:
`
`Q
`
`A
`
`are you familiar with that notation?
`
`Yes.
`
`Q What does that indicate to you, as one of
`
`ordinary skill in the art?
`
`A
`
`So there's a parameter, N, which is a
`
`number. And one, let's say,
`
`looks at computational
`
`time as a function of N.
`
`So if N grows, order N
`
`means that the search time will not increase faster
`
`than linearly.
`
`so it could increase linearly, or it
`
`could increase sublinearly.
`
`Q What that tells us is that the upper bound
`
`for the increase in the execution time is going to
`
`be linear; right?
`
`A
`
`Q
`
`At most linear.
`
`Is it the case that —— withdrawn.
`
`TSG Reporting H Worldwide - 8T?—Tfl2-95Bfl
`Pagal?of334
`
`
`
`5Ioouoonuu~
`
`Ir-' I\J
`
`and there. when we see that —— withdrawn.
`
`Q
`
`If N refers to the size of the dataset
`
`over which we're searching,
`
`then if we've got a
`
`database and what we know about it —— withdrawn.
`
`If N refers to the size of the database
`
`over which we're searching, and if we have an
`
`algorithm or search that performs at —— Din), as
`
`we've written there in Exhibit 2flfl5, does —— what
`
`does that tell us about whether it's linear or
`
`sublinear?
`
`A
`
`It says -- it is at most linear. That's
`
`often a source of confusion, by the way.
`
`It means
`
`at most linear.
`
`It does not mean necessarily
`
`linear.
`
`Q
`
`That would indicate -— withdrawn.
`
`Is it the case that when scientists in
`
`TSG Reporting - Worldwide - 3T":'*'?fl2~E+5Eifl
`Pagclfloflfl
`
`
`
`your field are assessing the complexity of an
`
`algorithm and how its execution time scales,
`
`that
`
`it's based upon using a hypothetical dataset?
`
`A
`
`If you apply that notation to -— to a
`
`dataset and you say N is the size of the datsset,
`
`that would mean that the function on the left side,
`
`which is a search time in your example, grows at
`
`most linearly with E.
`
`Q
`
`If we have a -- let's assume we've got
`
`a -- another algorithm and what we know about it is
`
`that its search time, compared to the size of the
`
`database, N,
`
`is that it's O{kn}, where K is a
`
`constant.
`
`What does that indicate to you?
`
`A
`
`The constant —— if K is a constant,
`
`the
`
`two equations you've written are equivalent, because
`
`U{n} or order of, say,
`
`2N is the same thing
`
`mathematically.
`
`Q
`
`Does it,
`
`in both instances,
`
`indicate that
`
`the search time is on the order of linear?
`
`A
`
`Q
`
`At most linear.
`
`If all we know about a search is that its
`
`search time oompared to the size of the database
`
`over which we're searching grows D{n} or {kn}, do we
`
`know that it's sublinear?
`
`TSG Reporting H Worldwide - 8T?—Tfl2-958$
`Page [9 of 334
`
`
`
`Pu.
`
`We don't know because the notation is not
`
`refined enough to indicate that.
`
`You would have to
`
`use another notation.
`
`Q What other notation?
`
`The theta of N notation.
`
`What's the "theta alpha notation"?
`
`"Theta of N" notation.
`
`Theta of H notation.
`
`So if instead of big 0 you had written
`
`A
`
`Q A
`
`Q A
`
`theta,
`
`that would mean linear N.
`
`Q
`
`Why don't you go ahead and write that down
`
`for me on Exhibit 2DO5.
`
`and what you've written there is,
`
`just for
`
`the record, something that looks like an H with a
`
`circle around it,
`
`in}.
`
`And that's pronounced theta
`
`of N?
`
`It's capital letter theta. Greek letter.
`
`and it's pronounced "theta N"?
`
`Theta of N.
`
`Theta of N.
`
`Now, if we have something that‘s theta of
`
`RN, what does that indicate?
`
`A
`
`Again, if K is a constant,
`
`like 2,
`
`there
`
`is no difference between theta of N and theta of KM.
`
`They mean the same thing mathematically.
`
`TSG Reporting H Worldwide - 8T?—Tfl2-95Bfl
`Page Efl of 33.4
`
`
`
`Q When we're assessing whether or not a
`
`given search is a suhlinear search or suhlinear time
`
`search, do we determine it based upon whether or not
`
`the search time grows compared to the size of the
`
`query?
`
`A
`
`You have said —— okay.
`
`We need to be
`
`specific here.
`
`You say the search time.
`
`okay. You're
`
`looking at the search time as a function of -- now
`
`this has to do with query: before you talked about
`
`the size of the database. Which one is it?
`
`Q
`
`Let me back up and ask you another couple
`
`of questions.
`
`When we're -- in this field when we're
`
`talking about a -- using a search, what we're doing
`
`is we're comparing a query or a pattern against a
`
`database of data;
`
`is that right?
`
`A
`
`Q
`
`Yes.
`
`and if we talk -- is it -- are there other
`
`words for "query" or "pattern"?
`
`What's the —— what's the best one to use?
`
`A
`
`"Query" is fine.
`
`one could ~- could say
`
`"probe" as well .
`
`TSG Reporting - Worldwide - 3".I'7"*-'?fl2~E+5Eifl
`F'ag¢2Iof3$4
`
`
`
`Q
`
`In —— in looking at some of the prior art,
`
`they refer to a w- trying ~~ having a song or a
`
`melody that is unknown and then trying to determine
`
`what that melody actually is.
`
`You're familiar with that sort of prior
`
`A
`
`Q
`
`YES.
`
`Is the unknown melody the equivalent of
`
`the query or the pattern that we're searching for?
`
`A
`
`So the —— the —— what's submitted by the
`
`user is the query; what you are comparing it against
`
`is —— is the database.
`
`So it --
`
`Q
`
`Now, if we're trying to determine whether
`
`a given algorithm is sublinear or linear. do we
`
`assume that the query size is fixed or does the
`
`query size vary when we're trying to assess whether
`
`it's sublinear?
`
`A
`
`It depends on the problem considered,
`
`the
`
`different flavors of these problems.
`
`Q
`
`If we're trying to determine whether
`
`something is sublinear as it's used in the olaims of
`
`TSG Reporting — Worldwide — 3T7*Tfl2~95Bfl
`Pag¢22of334
`
`
`
`the —— claims of the patents —— withdrawn.
`
`If we're talking about
`
`the concept of
`
`sublinear search or sublinear time search as it's
`
`used in the '23? patent, does that refer to a search
`
`time that grows at a sublinear rate as we increase
`
`the size of the pattern, or —— or does it refer to a
`
`search that increases at a sublinear rate as we
`
`increase the size of the database?
`
`A Usually,
`
`the one that matters is the size
`
`of the database, because that's a big one.
`
`Q When the —— in your definition that you
`
`set forth on page 19, where you said,
`
`"A sublinear
`
`search means a search whose execution time has a
`
`sublinear relationship to database size," you're
`
`referring to "sublinear" as it's used in the '23?
`
`patent;
`
`is that right?
`
`A
`
`Let me check the '23? patent.
`
`What I gave in my Declaration is a general
`
`definition of sublinear search.
`
`In the patent
`
`here —— for instance, if you look at Claim 5 that
`
`you -- we just discussed, sublinear time is used.
`
`It does not say what
`
`the reference is.
`
`Again,
`
`in those problems,
`
`the parameter
`
`that's very big that's of concern is the size of the
`
`database.
`
`TSG Reporting H Worldwide - 8T?—Tfl2-958$
`Page 23 of 334
`
`
`
`I-"‘ LU
`
`i--" n-'|'-‘I
`
`I--" U'|
`
`|—" CT‘:
`
`In-F --J
`
`1-‘ CO
`
`v|—|
`
`‘-53
`
`1'\J (II
`
`Ix]
`
`|~—‘
`
`l\) |'\.'|I
`
`|'\) LIJ
`
`1\J in
`
`!'\J ILJ'|
`
`Q Would it be wrong to apply a definition
`
`that said, "I'm going to determine if it's sublinear
`
`based upon whether or not
`
`the search time grows
`
`compared to the size of the query or the pattern?
`
`A Mathematically,
`
`this could be done.
`
`Whether it's relevant from an engineering point of
`
`View is a different matter.
`
`My opinion here is as an engineer. Okay?
`
`The parameter that's big that's of concern is the
`
`database size.
`
`Q
`
`In trying to determine whether or not the
`
`‘23T patent is anticipated,
`
`is it your opinion that
`
`the definition you've set forth in paragraph 53 is
`
`TSG Reporting - Worldwide - 3TT*'?fl2~E+5Eifl
`Pag¢24of3$4
`
`
`
`F—"
`
`the correct cne?
`
`A
`
`That's the definition I have applied.
`
`and
`
`1, yes, believe it's correct. That's my epinicn.
`
`I
`
`2 3 I I I I I I
`
`-
`
`Q
`
`It wculdn‘t be relevant to the ——
`
`assessing the '23? claims;
`
`is that right?
`
`A
`
`In the field of database search in
`
`- D I
`
`-"‘ LU
`
`14
`
`15
`
`16
`
`general —— and this includes the —— the patents
`
`1? we're discussing —— it's the database size that is
`
`l8
`
`the large number.
`
`and when you say "order of,“
`
`typically you refer to that.
`
`Q
`
`If we're trying to determine whether the
`
`'23? —— withdrawn.
`
`TSG Reporting — Worldwide — 3TT*Tfl2~95Bfl
`Pag¢25nf3£4
`
`
`
`IO
`
`Is it the case that for something to be --
`
`I I I U C . I C 9
`
`1D
`
`withdrawn.
`
`Q
`
`If we were doing —- withdrawn.
`
`If semeene was doing an assessment --
`
`withdrawn.
`
`TSG Reporting — Worldwide — 3??-Tfl2~95Bfl
`Page 26 of 334
`
`I I I - - - - . - I I l
`
`\) |\.'|I
`
`|'\) LIJ
`
`24
`
`
`
`lfl
`
`11
`
`12
`
`13
`
`14
`
`15
`
`lfi
`
`1?
`
`Appeal Board was presented with prior art that
`
`presented a search that was linear with respect to
`
`the size of the database, but it was suhlinear with
`
`respect to the size of the pattern.
`
`would that prior art demonstrate a
`
`suhlinear search as it's used in Claim 25?
`
`A
`
`People say it's a linear search, again,
`
`because it's in relation with the size of the
`
`database. And as you just said,
`
`that complexity is
`
`still linear; so people would say it is a linear
`
`search.
`
`Q
`
`A
`
`It is not a suhlinear search?
`
`It's only sublinear in terms of the size
`
`of the query, which is generally not
`
`the
`
`parameter of -- the relevant parameter.
`
`Q
`
`Is it the case that if we had a piece of
`
`prior art that was linear with respect to the size
`
`of the database but suhlinear with respect to the
`
`size of the query or the pattern,
`
`that that prior
`
`art would not
`
`teach a sublinear search as it's used
`
`in Claim 25?
`
`A Again, if one understands suhlinear to be
`
`in terms in relation to the size of the database,
`
`that would he a -— a linear search.
`
`Q
`
`My question wasn't "if one understands";
`
`I
`
`TSG Reporting - Worldwide - ST?-Tfl2—95Bfl
`Pag¢27 of3$4
`
`
`
`want
`
`to get your understanding of Claim 25.
`
`so you
`
`still haven't answered my question.
`
`I'll ask you
`
`again.
`
`3 I I I I I I - D C C C C - C - C C - D - - C
`
`TSG Reporting - Worldwide - ST?-Tfl2—95Bfl
`Pag¢2EI of3$4
`
`
`
`Q
`
`Let's assume we have a ~— withdrawn.
`
`what I've tried to write there -~ and see
`
`if I wrote it correctly -- is we've got a search,
`
`and the search time is Oifimln}.
`
`Does that —— do you understand what that
`
`refers to?
`
`A
`
`Yes.
`
`Q What would that indicate?
`
`A Well,
`
`that the search time, as a function
`
`of that quantity in parentheses, grows at most
`
`linearly.
`
`Q
`
`Is it the case that if N,
`
`in that example,
`
`refers to the size of the database, do we have,
`
`then, a suhlinear search?
`
`A Well, you have to tell me if M grows too,
`
`or if it's a constant like in your —- in your
`
`previous example?
`
`Q
`
`Let's assume that M is the size of the
`
`query.
`
`359.
`
`Q
`
`Uh-huh .
`
`M, as in Mary. And that N, as in Nancy,
`
`is the size of the database.
`
`A
`
`Okay.
`
`TSG Reporting - Worldwide - ET?“-Tfl2~95Eifl
`F'agc2E|of3$4
`
`
`
`Q
`
`In that instance, does this describe a
`
`search that has -— that is -- has sublinear
`
`execution time when compared to the size of the
`
`database?
`
`A
`
`Your question is incomplete. There's an
`
`assumption you need to specify- Does M grow, or
`
`does N grow, or is it both?
`
`Q Well, my question is if we're presented
`
`with this information, and we want to know is this
`
`search sublinear or linear with respect to the size
`
`of the database, where N is the size of the
`
`database, does that tell us?
`
`A
`
`No. Because you have not told me how
`
`either M or N grows.
`
`The product of f{m}n has to
`
`grow.
`
`For that to grow, either M or N has to grow,
`
`or both. But you need to tell me which one.
`
`Q
`
`If N refers to the size of the database,
`
`and we're trying to assess whether that describes a
`
`search that is sublinear with respect to the size of
`
`the database, can we —— what does that tell us?
`
`A
`
`This tells us that the search time grows
`
`at most linearly in terms of the product
`
`f{m}n.
`
`You
`
`have not told me whether it is M that grows or N
`
`that grows.
`
`The product has to grow, but there are
`
`different ways in which it can grow.
`
`N alone can
`
`TSG Reporting H Worldwide - 8T?—Tfl2-958$
`Page 3:11 of 334
`
`
`
`grow and M is fixed, or M can grow and N grows.
`
`So the answer depends on your assumption.
`
`You need to specify your assumptions.
`
`Q
`
`If we're trying to determine or assess
`
`whether or not this search is sublinear with respect
`
`to database size,
`
`and if N, as in Nancy,
`
`refers to
`
`database size,
`
`then would that indicate that we're
`
`going to be assessing this assuming that N grows and
`
`that M is fixed?
`
`A
`
`It depends on the problem.
`
`In some
`
`problems,
`
`indeed, M could be fixed and N grows.
`
`That's a —e a possibility.
`
`v|—*
`
`'-D
`
`1'\J (II
`
`Ix]
`
`|~—‘
`
`l\) |'\.'|I
`
`|'\) LIJ
`
`1\J uh.
`
`1'\J ILJ'|
`
`Q
`
`If that's the case when we're presented
`
`with this information,
`
`then is the assumption that M
`
`is fixed if we're trying to determine whether it's
`
`suhlinear with respect to the growth of N?
`
`a Different applications could have
`
`different M.
`
`Some applications could have fixed M;
`
`other applications could have M grow like M.
`
`It
`
`TSG Reporting - Worldwide - 3TT*'?fl2~E+5Eifl
`F'agc3Iof3$4
`
`
`
`depends on the applioation.
`
`Q
`
`If we're trying to -- suppose I present
`
`you with an algorithm, and I say to you,
`
`"I want to
`
`know,
`
`in your opinion, does this describe a linear
`
`or a sublinear algorithm with respect to the
`
`database time?"
`
`And I --
`
`A
`
`"Size," you mean.
`
`Right. With respect to the database size.
`
`And I present -- let's take Algorithm 1,
`
`the one that says "O{mn}.“ I present that
`
`Yes.
`
`Do you have an opinion?
`
`Can you repeat your question.
`
`Q
`
`Yeah.
`
`If —— so just to be olear,
`
`in fact,
`
`I'm going to take Exhibit EDUE, and just for
`
`clarity,
`
`I'm going to put a number next
`
`to each of
`
`these formulas we've written down. Starting at the
`
`top. it will be 1, 2, 3, 4. 5.
`
`Let‘s take a look at Formula Number 4.
`
`Assume you're presented that information about a
`
`given search.
`
`and the question is -- withdrawn.
`
`Assume you're given number —— Formula
`
`Number 4 and told that M, as in mother, refers to
`
`TSG Reporting H Worldwide - 8T?—Tfl2-95Bfl
`Page 32 of 33.4
`
`
`
`the size of the query; N, as in Nancy, refers to the
`
`size of the dataset that we're searching over.
`
`And you're asked the question,
`
`"Does that
`
`tell us anything about whether or not
`
`the search is
`
`sublinear with respect to the size of the database?"
`
`A
`
`I don't have enough information to answer
`
`this.
`
`It's really exactly like if you told me,
`
`"Ten
`
`is the sum of two numbers; tell me which ones."
`
`Q
`
`If we know that M refers to the size of
`
`the query and N refers to the size of the database,
`
`and we're interested in whether or not
`
`the —— a
`
`search is sublinear with respect to the size of the
`
`database, does that tell us that it —- with respect
`
`to the size of the database —— that it grows on the
`
`order of N, as in Nancy?
`
`A
`
`M and N oould be related.
`
`You have not
`
`defined the relationship between them.
`
`If M is
`
`fixed,
`
`there's one answer, and -- which I've given
`
`earlier -- it is:
`
`The growth is at most linear.
`
`But if M grows with N as well,
`
`then the
`
`answer is different.
`
`Q
`
`Let's -- I want you to assume that M
`
`refers to the size of the query, N refers to the
`
`size of the database, and that there is no
`
`relationship between them except that N is greater
`
`TSG Reporting H Worldwide - 8T?—Tfl2-958$
`Page 33 of 334
`
`
`
`than M.
`
`The size of the database is greater than M.
`
`A
`
`Okay.
`
`so when you say there's no
`
`relationship, do you assume that M is fixed?
`
`Q Well,
`
`if we're trying to answer this
`
`question,
`
`is that the assumption that should be
`
`made?
`
`A
`
`The way you have said it, mathematically,
`
`to suggest M is fixed.
`
`so I want
`
`to make sure we're
`
`on the same page.
`
`Q
`
`Okay. What about the way I've said it
`
`suggests that M is fixed?
`
`A
`
`Because you said there's no relation
`
`between them.
`
`So that suggests to me that if one --
`
`say N increases, M does not because it's not
`
`related. That's my assumption from what you said.
`
`Q
`
`Okay. Let's assume they're not related.
`
`In other words, were -— is that the
`
`typical problem we're facing,
`
`is that we've got a
`
`database of a certain size that may change, and
`
`we've got different queries of different lengths,
`
`whether the -- the query length is not going to
`
`affect the database size in a typical problem --
`
`A
`
`Q
`
`A
`
`There may be a relationship.
`
`It's possible?
`
`Depends on the problem.
`
`TSG Reporting H Worldwide - 8T?—Tfl2-958$
`Page 34 of 334
`
`
`
`Q
`
`In the typical cases,
`
`is it that they do
`
`not have a relationship?
`
`A
`
`I've encountered both types of problems.
`
`Q Well,
`
`the question isn't whether you've
`
`encountered them.
`
`What's typical?
`
`A Well, both are typical,
`
`I would say.
`
`It
`
`depends on the problem.
`
`Q
`
`Okay.
`
`Now, let's assume that we have a --
`
`a problem we're dealing with where the size of the
`
`query and the size of the dataset are unrelated.
`
`And you're presented with the information
`
`that's in Formula 4,
`
`that the search time is on the
`
`order of M, as in mother,
`
`times N, as in Nancy,
`
`where M refers to the size of the query, N refers to
`
`the size of the data set?
`
`what
`
`information does that tell you about
`
`whether it's linear or sublinear?
`
`A
`
`So based on your assumptions that you laid
`
`out.
`
`I treat M as a fixed number.
`
`Then the answer
`
`is the same I gave earlier:
`
`It would tell me that
`
`the search time is at most linear in N, as Nancy.
`
`Q
`
`Let's assume we've got a search that's
`
`D{f{m}n}, where M and N are unrelated. What does
`
`that -— where N refers to the size of the database.
`
`TSG Reporting H Worldwide - 8T?—Tfl2-958$
`Page 35 of 334
`
`
`
`What
`
`information does that tell us about
`
`whether it's linear or sublinear?
`
`A
`
`Q
`
`A
`
`Same answer.
`
`which is what?
`
`That, again, it would be -- the search
`
`time would be at most linear in M.
`
`Q
`
`Linear as to the size of the dataset that
`
`we're searching over?
`
`A
`
`Exactly.
`
`res.
`
`and that's because you
`
`have treated M as fixed.
`
`So whether it's {m} or
`
`f{m} that appears in the equation is irrelevant.
`
`Q
`
`I've written down Equation or Formula
`
`Number 6, which I'm going to read it as on the order
`
`of N, as in Nancy,
`
`times log of M;
`
`is that right?
`
`A
`
`0
`
`Yes.
`
`Let's aqain assume that N refers to the
`
`size of the database, M refers to the size of the
`
`query.
`
`Does that -- if we have a -- withdrawn.
`
`TSG Reporting - Worldwide - 3TT*'?fl2~E+5Eifl
`Pagc3¢:’:of3$4
`
`
`
`Q
`
`Let me ask you a different problem.
`
`Let's assume we have a search algorithm,
`
`and what it does, it is able to perform its
`
`search —— withdrawn.
`
`Let's assume we've got a search algorithm,
`
`and we're trying to take a pattern or query and see
`
`if it matches any portion of a dataset. And in that
`
`process, our particular algorithm operates such that
`
`it doesn't need to look at every single character in
`
`the dataset.
`
`are you familiar with algorithms of that
`
`i--" n-'|'-‘I
`
`I--" U'|
`
`|—" CT‘:
`
`In-F --J
`
`1-‘ CO
`
`v|—|
`
`‘-53
`
`1'\J (II
`
`Ix]
`
`|~—‘
`
`l\) |'\.'|I
`
`|'\) LIJ
`
`1\J in
`
`!'\J ILJ'|
`
`TSG Reporting - Worldwide - 3TT*'?fl2~E+5Eifl
`Pagc3'.u'of3$4
`
`
`
`A
`
`Q
`
`Yes.
`
`Knowing just that information and no more,
`
`does that tell you one way or the other whether it's
`
`linear or suhlinear?
`
`A
`
`Q
`
`A
`
`No, it does not.
`
`Why not?
`
`Because you have -- when you tell me it
`
`does not
`
`look at every oharaoter, you don't tell
`
`me -- you know, does it look at only half the
`
`characters? Does it look at the square root of
`
`number of characters?
`
`So many possibilities.
`
`You need to
`
`specify that.
`
`Q
`
`If it's the ease that it looks at a
`
`fraction of the characters, one —- one out of eight,
`
`one half, something like that —— does that tell you
`
`whether or not the algorithm is sublinear?
`
`A
`
`If it's a fixed fraotion -— for instance,
`
`you tell me one eighth -- so if the algorithm looks
`
`at one eighth of the number, if it looks at one
`
`eighth of the size of the dataset,
`
`that would be
`
`linear. Again, as the dataset -- as the data size
`
`goes to infinity, if you keep looking at one eighth,
`
`it would he a linear relationship.
`
`It's one eighth
`
`of M.
`
`TSG Reporting H Worldwide - 8T?—Tfl2-958$
`Page 35 of 334
`
`
`
`Q
`
`It would be something like Formula
`
`Number 2, Qikn}?
`
`A
`
`No- Because Formula Number 2 uses the
`
`order of notation:
`
`I would need to use the theta of
`
`N notation.
`
`Q
`
`So you would say that this one is not just
`
`Qinl, it would actually be --
`
`It behaves as a constant times N.
`
`and th
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
