1
`
`2
`3
`
`4
`
`5
`
`6
`7
`8
`
`9
`
`10
`
`11
`12
`
`13
`
`14
`15
`16
`17
`18
`
`19
`20
`21
`22
`23
`24
`25
`
`Page 1
`
` UNITED STATES PATENT AND TRADEMARK OFFICE
` BEFORE THE PATENT AND TRIAL AND APPEAL
` BOARD
` -----------------------------x
` GOOGLE, INC.,
` Petitioner, IPR-2015-00343
` IPR-2015-00345
` vs. IPR-2015-00347
` IPR-2015-00348
` NETWORK-1 TECHNOLOGIES,
` Patent Owner.
` -----------------------------x
` Patent Nos. 8,640,179
` 8,205,237
` 8,010,988
` 8,056,441
` -----------------------------x
`
` VIDEOTAPED DEPOSITION OF GEORGE KARYPIS
` New York, New York
` Thursday, November 12, 2015
` 9:05 a.m.
`
` Reported by:
` Jennifer Ocampo-Guzman, CRR, CLR
`
` Job No. CS2183243
`
`800-567-8658
`
`973-410-4040
`
`Veritext Legal Solutions
`
`Google Ex. 1020
`
`

`
`Page 2
`
`Page 4
`
`1 APPEARANCES (CONTINUED):
`
`2 3
`
` AMSTER ROTHSTEIN & EBENSTEIN, LLP
`4 Attorneys for Patent Owner
`5 90 Park Avenue
`6 New York, New York 10016
`7 (212) 336-8074
`8 BY: CHARLES R. MACEDO, ESQ.
`9 cmacedo@arelaw.com
`10 COREY HOROWITZ, ESQ.
`11 (p.m. session)
`12
`13
`14 ALSO PRESENT:
`15 CHRISTOPHER HANLON, Videographer
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`
`12345678
`
` November 11, 2015
`9 9:05 a.m.
`10
`11 Videotaped Deposition of GEORGE
`12 KARYPIS, held at the offices of Amster
`13 Rothstein & Ebenstein LLP, 90 Park
`14 Avenue, New York, New York, New York,
`15 pursuant to notice, before Jennifer
`16 Ocampo-Guzman, a Certified Real-Time
`17 Shorthand Reporter and Notary Public of
`18 the State of New York.
`19
`20
`21
`22
`23
`24
`25
`
`Page 3
`
`Page 5
`
`1 I N D E X
`2 WITNESS EXAMINATION BY PAGE
`3 GEORGE KARYPIS MR. NEMEC 7
`4 --------------- EXHIBITS ------------------
`5 KARYPIS FOR I.D.
`6 Exhibit 1 Declaration of George
` Karypis 23
`
`7
`
` Exhibit 2 Photocopy of U.S. Patent
`8 No. 8,010,988 68
`9 Exhibit 3 Photocopy of U.S. Patent
` No. 8,205,237 69
`
`10
`
` Exhibit 4 Photocopy of U.S. Patent
`11 No. 8,640,179 69
`12 Exhibit 5 Photocopy of U.S. Patent
` No. 8,656,441 69
`
`13
`
` Exhibit 6 Wikipedia entry entitled,
`14 "Big O notation" 108
`15 Exhibit 7 Photocopy of U.S. Patent
` No. 6,188,010 112
`
`16
`
`17
`
`18
`
`19
`
` Exhibit 8 Single-page chart 123
`
` Exhibit 9 Single-page chart 128
`
` Exhibit 10 Single-page chart 146
`
` Exhibit 11 Photocopy of U.S. Patent
`20 No. 5,874,686 160
`21 Exhibit 12 Photocopy of U.S. Patent
` No. 6,970,886 178
`
`22
`23
`24
`25
`
` A P P E A R A N C E S:
`
`1 2
`
`3 4
`
` SKADDEN ARPS SLATE MEAGHER & FLOM LLP
`5 Attorneys for Petitioner
`6 4 Times Square
`7 New York, New York 10038
`8 (212) 735-2419
`9 BY: DOUGLAS R. NEMEC, ESQ.
`10 douglas.nemec@skadden.com
`11 ANDREW GISH, ESQ.
`12 Andrew.gish@skadden.com
`13
`14 DOVEL & LUNER
`15 Attorneys for Patent Owner
`16 201 Santa Monica Boulevard
`17 Santa Monica, California 90401
`18 (310) 656-7066
`19 BY: SEAN LUNER, ESQ.
`20
`21
`22
`23
`24
`25
`
`800-567-8658
`
`Veritext Legal Solutions
`
`2 (Pages 2 - 5)
`
`973-410-4040
`
`Google Ex. 1020
`
`

`
`Page 6
`1 THE VIDEOGRAPHER: Good morning.
`2 We are now on the record. Please note
`3 that the microphones are sensitive and
`4 may pick up whispering and private
`5 conversations. Please turn off all
`6 cellphones or place them away from the
`7 microphones, as they can interfere with
`8 the deposition audio. Recording will
`9 continue until all parties agree to go
`10 off the record.
`11 My name is Christopher Hanlon
`12 representing Veritext. The date today
`13 is November 12, 2015. The time is
`14 approximately 9:05 a.m. This deposition
`15 is being held at Amster Rothstein &
`16 Ebenstein located at 90 Park Avenue, New
`17 York, New York and is being taken by
`18 counsel for the petitioner.
`19 The caption in this case is Google
`20 Incorporated versus Network-1
`21 Technologies, being held before The
`22 Patent Trial and Appeal Board, case
`23 numbers 343, 345, 347, and 348.
`24 The name of the witness today is
`25 Dr. George Karypis. At this time I
`
`Page 7
`
`1 would ask counsel to please state your
`2 appearances for the record.
`3 MR. NEMEC: Douglas Nemec of
`4 Skadden Arps for the petitioner, Google.
`5 And with me is Andrew Gish, also with
`6 Skadden Arps for the petitioner.
`7 MR. LUNER: Sean Luner for Patent
`8 Owner Network-1 Technologies from Dovel
`9 & Luner.
`10 MR. MACEDO: Charles Macedo from
`11 Amster Rothstein & Ebenstein, also for
`12 the Patent Owner, Network-1
`13 Technologies.
`14 THE VIDEOGRAPHER: Thank you.
`15 Our court reporter today is
`16 Jennifer Ocampo-Guzman, representing
`17 Veritext. She will now swear in
`18 Dr. Karypis and we can proceed.
`19 G E O R G E K A R Y P I S, called as a
`20 witness, having been duly sworn, was examined
`21 and testified as follows:
`22 EXAMINATION BY
`23 MR. NEMEC:
`24 Q. Good morning, Dr. Karypis.
`25 A. Good morning.
`
`Page 8
`
`1 Q. You understand you've just been
`2 sworn to testify under oath in the same
`3 manner you would if you were testifying in a
`4 court of law?
`5 A. Yes.
`6 Q. And do you feel there's any reason
`7 that you can't testify fully and accurately
`8 today?
`9 A. No.
`10 Q. No medical conditions or health
`11 issues that would interfere with your ability
`12 to testify?
`13 A. No.
`14 Q. Have you ever given a deposition
`15 before?
`16 A. No, I have not.
`17 Q. Have you ever served as an expert
`18 witness in a litigation before?
`19 A. No, I have not.
`20 Q. Just a couple of general background
`21 comments, then.
`22 Jennifer will be taking down
`23 everything we say today on the record. I'm
`24 going to try, against my normal tendency, to
`25 speak slowly and clearly; but if my questions
`
`Page 9
`1 are not clear to you either because you can't
`2 hear them or can't understand them, feel free
`3 to ask me to clarify.
`4 Is that fair?
`5 A. Yes.
`6 Q. And likewise so as to avoid talking
`7 over each other and making Jennifer's even
`8 more difficult than it already is, I would
`9 ask you to wait to answer until I've finished
`10 my question; and I in turn will wait for your
`11 answer before I ask another question. Fair?
`12 A. Fair.
`13 Q. If you would like to take a break
`14 during the course of today's proceedings,
`15 feel free to speak up. I generally break
`16 every 90 minutes or so, but this is not a
`17 forced march, so if you need to step out,
`18 please speak up.
`19 A. I will.
`20 Q. You understand that you are here to
`21 testify today in connection with a
`22 declaration that you submitted on behalf of
`23 Network-1 Technologies, correct?
`24 A. Correct.
`25 Q. And that declaration was submitted
`
`800-567-8658
`
`Veritext Legal Solutions
`
`3 (Pages 6 - 9)
`
`973-410-4040
`
`Google Ex. 1020
`
`

`
`Karypis
`
`Page 10
`1 in connection with four inter partes review
`2 proceedings that were instituted at the
`3 request of Google?
`4 A. Yes.
`5 Q. And there are four U.S. patents at
`6 issue in those IPR proceedings, right?
`7 A. Yes.
`8 Q. And you've referred to those as the
`9 IPR patents in your declaration?
`10 A. I believe so.
`11 Q. And the inventor on each of those
`12 patents is a man named Dr. Cox, correct?
`13 A. Correct.
`14 Q. So if I occasionally refer to the
`15 patents today as the Cox patents, will you
`16 understand what I'm talking about?
`17 A. Yes.
`18 Q. Just a couple of other terminology
`19 points before we move on. I may refer to the
`20 board or the P tab.
`21 Are those terms that you've heard?
`22 A. Yes, I have.
`23 Q. The P tab is the Patent Trial and
`24 Appeal Board. You understand that that's the
`25 tribunal that will be, in the first instance,
`
`Page 11
`1 deciding the matters in dispute in this case?
`2 A. Yes.
`3 Q. Okay. In the declaration that you
`4 submitted on behalf of Network-1, you
`5 expressed certain technical expert opinions,
`6 correct?
`7 A. Correct.
`8 Q. And you expressed the opinion that
`9 the challenged claims of the Cox patents are
`10 not unpatentable, correct?
`11 A. Correct.
`12 Q. You've expressed the opinion that
`13 the challenged claims of the Cox patents are
`14 not anticipated by the prior art, correct?
`15 A. Correct.
`16 Q. You've also expressed the opinion
`17 that the challenged claims of the Cox patents
`18 are not obvious, in view of the prior art; is
`19 that right?
`20 A. Correct.
`21 Q. Under the umbrella of those
`22 opinions would it be fair to say that the,
`23 the opinions you've expressed fall roughly
`24 into two categories, the first being opinions
`25 with regard to how the claim language in the
`
`Page 12
`1 Cox patents should be interpreted, and the
`2 second category being the teachings of the
`3 prior art?
`4 A. Correct.
`5 Q. In connection with forming your
`6 opinions, what information did you rely upon?
`7 A. The specific information I rely
`8 upon I believe is listed in my declaration.
`9 I can give you the exact list, if you give me
`10 a copy of it.
`11 But on top of my head, it involves
`12 what you referred to as the Cox patents, the
`13 -- the patents that was submitted by Google
`14 as part of the IPR, specifically the Ghias
`15 patent, the Iwamura patent, Conwell patent,
`16 the Dr. Moulin's declaration and deposition
`17 and the IPR filings that Google filed.
`18 Q. The last item, I'm sorry, was the
`19 actual filings?
`20 A. Correct.
`21 Q. So the petitions?
`22 And were there also some Wikipedia
`23 pages to which you referred?
`24 A. Correct. I believe there were two
`25 or three Wikipedia pages. Everything is
`
`Page 13
`
`1 fully detailed in my declaration.
`2 Q. Okay. Let me focus for a moment on
`3 the Moulin declaration. That's a set of
`4 declarations submitted by Dr. Pierre Moulin
`5 in support of Google's petitions; is that
`6 right?
`7 A. Correct.
`8 Q. In what fashion, generally
`9 speaking, did you rely upon Dr. Moulin's
`10 declarations in forming your opinions?
`11 A. I read the declarations. I just
`12 tried to understand some of the context, you
`13 know, behind the IPR filings, and that's
`14 about it.
`15 Q. Did the -- aside from providing
`16 context for the matters in dispute, did the
`17 information presented in the Moulin
`18 declaration influence your technical opinions
`19 one way or the other?
`20 A. I do not believe so.
`21 Q. And with regard to the deposition
`22 testimony of Dr. Moulin, in what fashion did
`23 you rely upon that in forming your opinions?
`24 A. I read the deposition and I don't
`25 think it affected, you know, my opinions.
`
`800-567-8658
`
`Veritext Legal Solutions
`
`4 (Pages 10 - 13)
`
`973-410-4040
`
`Google Ex. 1020
`
`

`
`Karypis
`
`Page 14
`
`1 Just, you know, fed them.
`2 Q. So once again, with respect to the
`3 deposition, would it be fair to say that you
`4 relied upon it for contextual purposes?
`5 A. There are a few places my
`6 declaration which I specifically, you know,
`7 point to certain aspects of documents,
`8 declarations, to confirm, you know, some of
`9 my beliefs. And I think, you know, to a
`10 large extent that's about it, so.
`11 Q. Okay. So for example, in instances
`12 where you agreed with what Dr. Moulin had
`13 testified, you might point to his deposition
`14 for that purpose, right?
`15 A. That would be correct.
`16 Q. If you didn't have Dr. Moulin's
`17 deposition testimony, do you think your
`18 opinions in this case would be any different?
`19 A. I do not think so.
`20 Q. And you indicated that you had also
`21 relied upon the actual filings, the IPR
`22 petitions.
`23 In what fashion did you rely upon
`24 those materials?
`25 A. I just looked at, you know, the
`
`Page 15
`1 claim constructions I believe that's what you
`2 call it, that the IPR petitions, you know,
`3 put forth and how alleged the claims of the
`4 Cox patents are anticipated by the prior art.
`5 Q. Have you ever read any deposition
`6 testimony from Dr. Cox?
`7 A. No, I do not -- I have not.
`8 Q. Is it correct that your
`9 understanding of the law applicable to these
`10 inter partes review petitions that you have
`11 is derived strictly from your discussions
`12 with counsel in the case?
`13 A. I don't think I follow the
`14 question.
`15 Q. Is it correct that your
`16 understanding of the patent law applicable to
`17 the decision in the IPR proceedings is
`18 derived strictly from your discussions with
`19 counsel?
`20 A. Yes, and also some reading that
`21 I've done, you know, kind of cursory notes
`22 about some of the material.
`23 Q. In connection with this proceeding
`24 or separately?
`25 A. Just in general.
`
`Page 16
`1 Q. Do you consider yourself to be an
`2 expert on patent law?
`3 A. No.
`4 Q. Do you consider yourself to be an
`5 expert on patent office procedures?
`6 A. No.
`7 Q. So you wouldn't be qualified to
`8 offer expert opinions on legal issues, then;
`9 is that fair to say?
`10 A. I think that's a fair statement.
`11 Q. For example, independent of
`12 information that may have been conveyed to
`13 you by counsel, you have no expertise on what
`14 the various burdens of proof are in an inter
`15 partes review petition, correct?
`16 A. That is correct.
`17 Q. And you have no independent
`18 knowledge of the legal standards for
`19 determining anticipation of a patent claim,
`20 correct?
`21 A. Not prior to --
`22 (Discussion off the record.)
`23 A. Not prior to --
`24 (Discussion off the record.)
`25 A. Not prior, I said, the answer to
`
`Page 17
`
`1 that is yes.
`2 MR. MACEDO: "Not prior to talking
`3 to the counsel, yes."
`4 (Discussion off the record.)
`5 Q. And finally, independent of
`6 discussions with counsel, you have no
`7 expertise in the legal standards governing
`8 whether a patent claim is obvious over the
`9 prior art or not, correct?
`10 A. I'm familiar with the patent law
`11 that has to do with what something is
`12 obvious; and if the familiarity is what you
`13 refer as expertise, then, yes, if that's just
`14 familiarity, then I'm familiar with the law.
`15 Q. My question was limited to the
`16 legal standards, and I will ask it a little
`17 bit differently.
`18 A. Okay.
`19 Q. Do you purport to be an expert in
`20 the legal standards governing whether a
`21 patent claim is obvious or not?
`22 A. I will not qualify myself as being
`23 an expert in legal standards.
`24 Q. I take it, in the process of your
`25 work, you've studied the disclosure of the
`
`800-567-8658
`
`Veritext Legal Solutions
`
`5 (Pages 14 - 17)
`
`973-410-4040
`
`Google Ex. 1020
`
`

`
`Karypis
`
`Page 18
`
`1 Cox patents, correct?
`2 A. By "disclosure," you mean
`3 specification?
`4 Q. That's a good point, so another
`5 terminology issue: If I refer to the
`6 specification of prior art or the Cox
`7 patents, I'm referring to the text that
`8 precedes the claims in the patents.
`9 Is that consistent with your
`10 understanding?
`11 A. Yes.
`12 Q. Okay. So have you -- excuse me --
`13 have you studied the specification in the Cox
`14 patents in connection with your work on this
`15 case?
`16 A. Yes, I have.
`17 Q. How would you characterize the
`18 field of the Cox invention?
`19 A. So the general field of the Cox
`20 invention falls in the general area of, I
`21 would say information retrieval and from a
`22 technical point, and, you know, that's about
`23 it.
`24 Q. Do you think content recognition
`25 would be an accurate characterization of the
`
`Page 20
`1 to develop any kind of system to identify
`2 records in a database that are similar or
`3 very similar to a particular query?
`4 A. My recollection from the
`5 specification is that the answer to that is
`6 no. The specification I believe discloses a
`7 bunch of methods to solve the problem.
`8 Q. And generally speaking what is it
`9 that distinguishes the method for identifying
`10 or system for identifying records that Dr.
`11 Cox purports to have invented from those that
`12 came before?
`13 MR. LUNER: Can you repeat the
`14 question?
`15 MR. NEMEC: Sure. You want it just
`16 read back. Why don't you go ahead and
`17 read back.
`18 (A portion of the record was read.)
`19 MR. LUNER: Objection to form.
`20 A. So this is a very broad question.
`21 So, and I believe in my declaration I kind
`22 of, you know, tried to summarize what are the
`23 key distinguishing features of the invention
`24 that is disclosed.
`25 Now going, I can read you that
`
`Page 19
`
`1 field of the Cox patents?
`2 A. No -- content recognition, content
`3 retrieval, yeah, those would be, you know,
`4 the fields.
`5 Q. And based on your review of the Cox
`6 patents, what problem or problems do you
`7 understand Dr. Cox to have been addressing
`8 with his inventions?
`9 A. So the general problem that, you
`10 know, the invention addresses is, from the
`11 disclosure, has to do on how to identify
`12 records in a database that are similar or
`13 very similar to a particular query, and how
`14 to take actions based on that identification.
`15 Q. Do you understand one of Dr. Cox'
`16 goals of his invention to be an efficient
`17 search process?
`18 A. I believe I'm recollecting the
`19 claims, and again, if the question has to do
`20 with the claims, I don't think the specific
`21 claim that -- talks about a search process.
`22 Q. So let me ask a somewhat different
`23 question, then.
`24 Do you understand Dr. Cox to be
`25 asserting in his patents that he's the first
`
`Page 21
`1 section, but off the top of my head there are
`2 a bunch of different components. One has to
`3 do with a nonlinear search. The other one
`4 has to do with a non-exhaustive search.
`5 Another one has to do with a near neighbor
`6 search. So those are the three that I can
`7 recall.
`8 Q. And why is it, in the context of
`9 these inventions, that Dr. Cox was setting
`10 out to identify similar works as opposed to
`11 exactly matching works?
`12 MR. LUNER: Objection to form.
`13 A. So I believe the, you know, the
`14 specification, you know, put forth certain
`15 scenarios in which things like that would be
`16 desirable. I don't remember the specific
`17 example that they provided, but I can, you
`18 know, you know, hypothesize that finding, you
`19 know, similar or not necessarily exact, like,
`20 would be something that would be tolerant to
`21 some, you know, small changes or some
`22 transmission error.
`23 Q. So for example, a distortion in an
`24 audio file?
`25 A. That can be an example.
`
`800-567-8658
`
`Veritext Legal Solutions
`
`6 (Pages 18 - 21)
`
`973-410-4040
`
`Google Ex. 1020
`
`

`
`Karypis
`
`Page 22
`1 Q. Is it your understanding from the
`2 disclosure in the Cox patents that Dr. Cox
`3 found it undesirable to find an exact match?
`4 A. I don't recall if it was explicitly
`5 stated it's undesirable or not, but -- yeah,
`6 actually I don't recall if it's saying it's
`7 undesirable to find an exact match.
`8 Q. A moment ago you used the term
`9 "nonlinear," I believe.
`10 Do you mean that to be synonymous
`11 with sublinear?
`12 A. Well, nonlinear is not synonymous
`13 with sublinear, but in the context of the Cox
`14 patents the nonlinearity that they're talking
`15 about is sublinearity.
`16 Q. So you mean in general nonlinearity
`17 is not synonymous with sublinearity, separate
`18 from the Cox patents?
`19 A. Yes.
`20 Q. What, then separate from the Cox
`21 patents, what do you understand nonlinearity
`22 to mean?
`23 A. Something that is not linear. I
`24 believe I have a precise definition of
`25 linearity in my disclosure, but, you know, a
`
`Page 24
`
`1 A. I cannot find the exact place, but
`2 repeat your question and I can answer it from
`3 my head.
`4 Q. Sure. So the question that I had
`5 posed was, what is your understanding of the
`6 term "nonlinear," separate and apart from the
`7 Cox patents?
`8 A. Sure. So the term "nonlinear," you
`9 know, first, you usually do, you know, I have
`10 a function that is a parameter of a certain
`11 variable, let's say N. Like if I increase
`12 that variable by certain fraction, like, so I
`13 look at 2N or 4N; if I have an increase in
`14 the amount of the value of that function,
`15 right, that is not the same proportion,
`16 right. It's not 2, a factor of 2 or a factor
`17 of 4. If I have the corresponding increase
`18 on the integer variable, but then that would
`19 be a nonlinear function.
`20 Q. How does the definition that you
`21 just gave differ from the definition of
`22 sublinear, as you understand it, separate
`23 from the Cox patents?
`24 A. I think it is exactly the same
`25 definition. The notion of sublinear is a
`
`Page 23
`
`1 function, you know, of, you know, that
`2 increases at a rate that is either higher,
`3 greater or smaller than linear is a nonlinear
`4 function. For example, a function that is
`5 quadratic would be a nonlinear function.
`6 Q. By "rate," do you mean to imply
`7 speed?
`8 A. So this is very precisely described
`9 in my declaration. I can give you the
`10 definition.
`11 Actually, can you give me a copy of
`12 the declaration?
`13 MR. NEMEC: Sure. We can go ahead
`14 and mark it. We will mark as Karypis 1
`15 the declaration of Dr. George Karypis
`16 submitted in the four IPR proceedings.
`17 (Karypis Exhibit 1, Declaration of
`18 George Karypis, marked for
`19 identification, this date.)
`20 (Discussion off the record.)
`21 THE WITNESS: At some point in time
`22 we'll switch to iPad with those?
`23 MR. NEMEC: Yes, that's been tried.
`24 I find it difficult in the deposition
`25 context, but some people like it.
`
`Page 25
`1 function in which you find increase by let's
`2 say a factor of 2 or a factor of 4, right, an
`3 increase in the output of that function would
`4 be less than a factor of 2 or a factor of 4.
`5 Q. Now, in your view is the term
`6 "sublinear" used differently in the Cox
`7 patents?
`8 A. No, I believe this is the use of,
`9 this is how the term is used.
`10 Q. You mentioned the term
`11 "non-exhaustive" a new moments ago as well,
`12 correct?
`13 A. That's correct.
`14 Q. Non-exhaustive is one of the terms
`15 that appears in the claims of the Cox
`16 patents, right?
`17 A. I believe so.
`18 Q. The actual term "non-exhaustive" is
`19 not used in the specification of the Cox
`20 patents, though, right?
`21 A. I don't recall.
`22 Q. Dr. Cox, in his disclosure in his
`23 patents, doesn't purport to have invented the
`24 concept of non-exhaustive searching, right?
`25 A. I believe so.
`
`800-567-8658
`
`Veritext Legal Solutions
`
`7 (Pages 22 - 25)
`
`973-410-4040
`
`Google Ex. 1020
`
`

`
`Karypis
`
`Page 26
`
`1 Q. You believe he does purport to have
`2 invented it?
`3 A. He does not.
`4 Q. He does not. So as of 2000, when
`5 Dr. Cox' patent applications were filed,
`6 non-exhaustive searching was a concept known
`7 in the art, correct?
`8 A. Correct.
`9 Q. As of 2000, had you had exposure to
`10 the concept of non-exhaustive searching in
`11 your work?
`12 A. I believe you mean prior to 2000.
`13 Q. In or prior to, sure.
`14 A. Yes.
`15 Q. In what context?
`16 A. For example, a fairly widely-used
`17 algorithm to research a site array is to do a
`18 binary search. That would be an example of a
`19 non-exhaustive search.
`20 Q. And you've personally worked with
`21 such algorithms in or before 2000?
`22 A. Yes.
`23 Q. Do you recall other instances in
`24 which you had firsthand experience with
`25 non-exhaustive searching in or before 2000?
`
`Page 27
`1 A. Another approach by 2000 used for
`2 non-exhaustive search would be hash tables.
`3 Q. Any other examples that you can
`4 recall of --
`5 MR. NEMEC: Excuse me, I'll start
`6 that over.
`7 Q. Any other examples you can recall
`8 of non-exhaustive search techniques that you
`9 worked with in or before 2000?
`10 A. Not that I can recall finding
`11 techniques that I have worked with.
`12 Q. You mentioned binary search.
`13 A binary search is a non-exhaustive
`14 search; is that correct?
`15 A. That is correct.
`16 Q. Can you explain to me briefly how a
`17 binary search works?
`18 A. So assume you have an array of
`19 let's assume numbers and solving in
`20 increasing order, and the search is trying to
`21 answer the question, is a number in the array
`22 or not. And, you know, what do you is you
`23 check the middle point therein and compare it
`24 with your number. If the number is, your
`25 number is smaller than what's in the middle
`
`Page 28
`1 point, then you disregard the first half of
`2 the array, and you perform the same search on
`3 the second part of the array.
`4 You continue that way until you
`5 either find that value in the array, or your
`6 end result becomes an array, at which point
`7 in time you don't find the value.
`8 Q. Now, if the array you are seeking
`9 to search is not sorted, can you still
`10 perform a binary search on that array?
`11 A. You can perform a binary search,
`12 not and get a correct result. But if your
`13 goal is to get the correct answer, you cannot
`14 perform binary search.
`15 Q. And what do you mean by "the
`16 correct result"?
`17 A. In the example that I gave, if the
`18 number exists in the array, then it will
`19 return true. If the number does not, it will
`20 return false. If the array is not sorted,
`21 there are no guarantees that the algorithm
`22 will explain, will lead to the correct
`23 answer.
`24 Q. So it might return the correct
`25 answer, but it also might not?
`
`Page 29
`
`1 A. A high probability it will not.
`2 Q. Can you use a binary search to find
`3 a near match or only an exact match?
`4 A. The standard binary search on the
`5 sorted array can be modified to find a near
`6 match.
`7 Q. What sort of modification would be
`8 required?
`9 A. There are a couple of ways to
`10 implement it, but I would presume a standard
`11 way of doing that is after you do your binary
`12 search and you get an Mk array, then, you
`13 know, conceptually you backtrack to your
`14 previous step and, you know, that middle
`15 value on your previous step can be returned
`16 plus a, you know, near match.
`17 Q. You also mentioned hash tables.
`18 Was the use of hash tables a form
`19 of non-exhaustive searching?
`20 A. Yes.
`21 Q. Can you explain how a hash table
`22 works? In general terms.
`23 A. So the two prototypical types of
`24 hash tables, I'll just describe one of them,
`25 right. So it consists of an array, and each
`
`800-567-8658
`
`Veritext Legal Solutions
`
`8 (Pages 26 - 29)
`
`973-410-4040
`
`Google Ex. 1020
`
`

`
`Karypis
`
`Page 30
`
`Page 32
`
`1 element in the array has a link list
`2 associated with it. So the way you store the
`3 data there is you have a function that will
`4 map the original, let's say keys into some
`5 range, you know, that is bonded from one to
`6 the length of that array that you use. Then
`7 you apply that function on that key. That
`8 gives you an index in the array. And then
`9 you put the data into that link list
`10 associated with that element of the array.
`11 So this is how you populate a hash
`12 table, and then when you search, you have a
`13 key, you apply exactly the same function, you
`14 get to a link list that is associated with an
`15 element of that array which your hash value
`16 maps to; and then you, you know, sequentially
`17 scan that link list to see if that key is
`18 there or not.
`19 Q. So by -- you used the term "key"
`20 there.
`21 Is key -- what is a key?
`22 A. The key, the equivalent in my
`23 previous example are the numbers that we
`24 store in that, in that sorted array.
`25 Q. So a key is the entirety of the
`
`1 if they're available, the values as was
`2 given, the data associated with the keys.
`3 Q. Okay. So now when it comes time to
`4 search the hash table populated in the
`5 fashion you just described, how does the
`6 search process proceed?
`7 MR. LUNER: Objection to form.
`8 A. So in the typical way, if the --
`9 actually the way the search proceeds was
`10 already explained, you know, prior to that.
`11 But you take the key, you apply the hash
`12 function that maps in the range from one to
`13 the length of the array, and then you go to
`14 the link list and then you do a sequential
`15 scan of the link list, and you compare the
`16 actual key with the key stroke there. And if
`17 they're identical you return back the data,
`18 or the key, it depends on what the values
`19 are.
`20 Q. So each entry on the link list is
`21 associated with a single reference work or
`22 multiple reference works?
`23 A. What do you mean by "reference
`24 works"?
`25 Q. Let's establish another terminology
`
`Page 31
`1 reference that's served in the array, or it's
`2 some representation thereof?
`3 A. I don't think I -- I fully -- I
`4 don't think your question is fully fleshed
`5 out. If -- can you rephrase, repeat it?
`6 Q. Sure, sure.
`7 I'm starting at a very fundamental
`8 point, which is to understand what exactly
`9 the key represents in reference to or in
`10 relation to the items that are stored in this
`11 array.
`12 A. Okay.
`13