`
` Q Okay. Now, if we have a certain number of
`mismatches, that means we're -- allow -- say K
`mismatches. That means we're going to assume that
`there are three mismatches someplace in the string?
` A Yes. We recognize there are three errors,
`and we seek a match that differs in three positions.
`That would be the definition of a match. So it
`matches except in three positions.
` Q If you set K equal to M, that means we're
`going to accept a situation where every letter is
`mismatched; right?
` A Yes.
` Q That's not really a very practical search,
`is it?
` A Well, these -- these problems exist.
` Q Well, not in terms of math. But in terms
`of actual using, if you're trying to find songs, you
`wouldn't -- it wouldn't be acceptable to have
`everything mismatched; right?
` A No. So a sentence like that, when the
`engineer gives it, it means you look -- you have to
`know that in the case of a large number of
`mismatches, the algorithm would be very, very fast.
` NETWORK-1 EXHIBIT A2006
`So this is very useful.
` Google Inc. v. Network-1 Technologies, Inc.
` Q Is it the case that if we have -- that
` IPR2015-00345
`
`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
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 97 of 384
`
`
`
`Page 98
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`14
`15
`16
`17
`18
`19
`20
`20
`21
`21
`22
`22
`23
`23
`24
`24
`25
`25
`
`this algorithm, as disclosed here, would be
`sublinear with respect to the size of the dataset
`being searched, if we want to have at least some
`matches -- some matching between our actual query
`and our actual string?
` A Your question is vague. So you need to
`specify K.
` Q K is going to be some number less than M.
` A I can't answer it. If, say, all they
`disclose here is if K is equal to M, the answer is
`obtained immediately. If K is equal to M minus 1,
`it could be sublinear. I don't know. They don't
`comment on it.
` Q When you read this, did you conclude that
`this disclosed a sublinear time search for a problem
`where we're trying to search where the -- where K is
`less than M?
` A Again, sublinearity here in that paragraph
`is with respect to the brute-force search algorithm.
` Q When you read Column 6, lines 36 through
`Q
`When you read Column 6, lines 36 through
`59, did you conclude it disclosed a sublinear time
`59, did you conclude it disclosed a sublinear time
`search with respect to the size of the dataset being
`search with respect to the size of the dataset being
`searched if K, the number of mismatches, is less
`searched if K, the number of mismatches, is less
`than M, the size of the string?
`than M, the size of the string?
` A I don't conclude that, no.
`A
`I don't conclude that, no.
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 98 of 384
`
`
`
`Page 99
`
`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
`
` Q Does -- withdrawn.
` If -- would it be fair to read Columns 6,
`lines 36 through 59, as disclosing a sublinear time
`search with respect to the dataset for K less than
`M?
` A I don't know. They don't -- they only
`comment on special values of K, which are 0, 1 and
`M; right? They don't comment about anything else.
`I cannot infer the answer from what they wrote.
` Q Well, if K is 0 and K is 1, does it tell
`us that that's a sublinear time search?
` A If K is 0, it's the same as the
`Boyer-Moore problem. You are trying to find an
`exact match of a query in a string.
` Q If K is 0, is that, then, a sublinear time
`search?
` A It's exactly the same as our discussion on
`Boyer-Moore. If you compare it with a brute-force
`search, it is.
` Q What about "sublinear time search" as
`you've used it in your Declaration and as the Board
`used it with comparison to the size of the dataset?
` A In my Declaration, we discussed that; so I
`can, again, answer exactly. I quoted, when it came
`to Boyer-Moore, a reference that explains the
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 99 of 384
`
`
`
`Page 100
`
`1
`2
`3
`4
`5
`6
`7
`8
`8
`9
`9
`10
`10
`11
`11
`12
`13
`14
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`
`complexity of this. And in this context here, when,
`say, K is equal to 1, you cannot use Boyer-Moore
`anymore, but it's a similar reasoning.
` Q Well, let's focus on K is 0.
` You say that's the same as the Boyer-Moore
`problem; right?
` A Right.
`Q
`When K is equal to 0, then does this
` Q When K is equal to 0, then does this
`disclose a sublinear time search as you used
`disclose a sublinear time search as you used
`"sublinear time search" in your Declaration?
`"sublinear time search" in your Declaration?
` A No, it does not.
`A
`No, it does not.
` Q If K is equal to 1, does this disclose a
`sublinear time search?
` A Again, if you use -- with respect to the
`database size, it does not -- I have no way of
`knowing. Again, it says "order of." So it means at
`most linear.
` Q Now, if we look at -- I want you to pull
`out your Declaration. Turn -- turn to page 64.
` A Okay.
` Q This is the portion of your Declaration
`where you're discussing the Ghias reference; right?
` A Yes. Yes.
` Q Now, in here, in paragraph 123, this is
`the portion of your Declaration where you present
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 100 of 384
`
`
`
`Page 101
`
`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
`
`your opinions about whether Ghias discloses a
`sublinear search; right?
` A Yes.
` Q And in paragraph 123, you say that, "Ghias
`discloses searches whose execution times are
`proportional to the logarithm of the size of the
`dataset, which as explained above, are sublinear."
` Do you see that?
` A I don't see "proportional to." It says
`"order of."
` Q Well --
` A If I'm just quoting from Ghias, it says
`"order of." It doesn't say "proportional."
` Q What you wrote is, "Ghias discloses
`searches whose execution times are proportional to
`the logarithm of the size of the dataset."
` Do you see that?
` A Yes. Okay.
` Q And then you quote a particular clause
`that appears in Ghias; right?
` A That is correct.
` Q Now, what you quote from Ghias
`discloses -- execution -- "searches whose execution
`times are on the order of linear to the size of the
`dataset"; right?
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 101 of 384
`
`
`
`Page 102
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`9
`10
`10
`11
`11
`12
`12
`13
`13
`14
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`
` A Okay. So it says log(m) -- let me just
`make sure I get my N and M straight.
` N is the size of the song; M is the size
`of the query. So yeah, this should have read
`"log(m)," which is the size of the query.
` So just not to confuse, okay, there's two
`different datasets. So it should have been the size
`of the query.
` Q In other words, what it discloses is
`Q
`In other words, what it discloses is
`searches whose execution times are proportional to
`searches whose execution times are proportional to
`the logarithm of the size of the query; right?
`the logarithm of the size of the query; right?
` A Yeah. It -- because it's log(m) that
`A
`Yeah. It -- because it's log(m) that
`appears on the right side.
`appears on the right side.
` Q Does this disclose a search whose
`execution time is proportional to the logarithm of
`the size of the dataset?
` A So when you say "dataset," you -- I assume
`you're referring to the size of the string, which is
`N in Ghias -- in the Ghias patent?
` Is that what you're referring to?
` Q Well --
` A When you say -- there are two datasets;
`right? There's the query, which is size M, and
`there's the string or the song that is size N. So
`it should have -- it is the log(m).
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 102 of 384
`
`
`
`Page 103
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`14
`15
`16
`16
`17
`17
`18
`18
`19
`19
`20
`20
`21
`21
`22
`22
`23
`24
`25
`
` Q Is it the case that Ghias discloses a
`search whose execution time is proportional to the
`log of the size of the dataset being searched?
` A No. Okay. Again, if you say the dataset
`being searched, that would be N. Okay?
` What I intended there was the query
`dataset, which is M.
` Q So when you wrote "proportional to the log
`of the size of the dataset," you meant that to mean
`the query dataset?
` A Yes. Yes.
` Q Not the -- not the database?
` A That's -- that's correct. There's no
`database here. It's a problem of matching a query
`to a single song.
` Q Well, as you understood the term
`Q
`Well, as you understood the term
`"sublinear" as it's used in the patent, it's about
`"sublinear" as it's used in the patent, it's about
`the execution time as we increase the size of the
`the execution time as we increase the size of the
`database; is that right?
`database; is that right?
` A In the patent, yes.
`A
`In the patent, yes.
` Q Yes.
`Q
`Yes.
` A Yes.
`A
`Yes.
` Q When you were writing your opinions in
`paragraph 123, were you using the term "sublinear"
`to refer to a search whose execution time scaled at
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 103 of 384
`
`
`
`Page 104
`
`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
`
`a sublinear relationship to the size of the
`database?
` A Okay. So when I wrote -- okay. This
`paragraph 123, okay -- I addressed sublinearity of
`the search as disclosed in Ghias. Again, there are
`many ways, many reasons why the search is sublinear.
` And I would like to supplement my -- my
`opinion. So the issue of, say, improving over brute
`force by using Baeza-Yates is just one of many ways
`in which you can improve performance. And in fact,
`there are ways that clearly show sublinearity in --
`in the patent.
` Q Do you remember my question?
` A Could you restate it.
` Q Do you recall it?
` A Please restate it.
` Q Do you remember it?
` A I remember parts of it. Otherwise I
`wouldn't have asked you to restate.
` Q Well, it's important that you focus on my
`question --
` A Yes.
` Q -- I think you're starting to drift off
`and testify about peripheral matters instead of
`answering my question. So I want you to really
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 104 of 384
`
`
`
`Page 105
`
`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
`
`focus on it.
` A Okay.
` Q When you -- in writing paragraph 123 --
` A Yes.
` Q When you wrote that Ghias discloses
`searches -- withdrawn.
` Do you see this last sentence in
`paragraph 123?
` A Yes.
` Q Were you trying to convey that Ghias
`discloses searches that are sublinear?
` A Yes.
` Q When you use the word "sublinear" there,
`did you mean to have the same definition as you used
`in your Declaration; that is, that it has an
`execution time that scales at a sublinear
`relationship to the size of the database?
` A Okay. So here's what I wrote: "Ghias
`discloses search algorithms that are substantially
`faster than brute-force search." And that includes
`sublinearity in exactly the sense that I wrote in my
`Declaration, in relation to the size of the dataset.
` Now, the following sentence explains how
`one can be faster than brute force. For instance,
`using these Baeza-Yates algorithms or the -- the
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 105 of 384
`
`
`
`Page 106
`
`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
`
`other algorithms that I mentioned there, such as
`Gonnet. So all that is claimed there is basically
`restating a portion of -- of Ghias.
` And, again, just to make it clear, I do
`not claim that that step alone is going to give us a
`search that is sublinear in the size of the
`database. I'm not claiming that.
` Q When you used the word "sublinear" in
`paragraph 123, were you using sublinear to mean
`sublinear compared to the size of the database?
` A On the second line of that paragraph, it
`is sublinear in the size of the database. Okay? So
`Ghias discloses a search that is sublinear in the
`size of the database.
` The second occurrence of "sublinear" is in
`the very last line of that paragraph 123. It is
`quoting from -- from Ghias. And what's written
`there meant sublinear relative to brute-force
`search.
` Q All right. Just to be clear, the second
`"sublinear" you wrote was sublinear with respect to
`brute force, not with respect to the size of the
`dataset; right?
` A I cannot claim that, no.
` Q No. I'm confused now.
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 106 of 384
`
`
`
`Page 107
`
`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
`
` When you wrote "sublinear" in the last
`line of paragraph 123, were you using sublinear to
`mean sublinear to the size of the dataset?
` A I'll just read the full reference. "As
`explained above, Section 5(d)," so let's go to 5(d).
` Q There's no Section 5(d) in your
`Declaration.
` A Well, there's some typo, then.
` Q "Section 5(d)" apparently refers to your
`"Claim Construction" section. And I infer that
`because there's a Section 5(d) in the petition that
`is the "Claim Construction" section.
` A Okay. So you are saying "5(d)" refers to
`what, then? It must be a typo.
` Q Well, I'll tell you this: There's no 5(d)
`in your Declaration.
` A Okay.
` Q There's a 5(d) in the petition.
` A Okay.
` Q The 5(d) in the petition is the "Claim
`Construction" section.
` A Okay.
` Q So perhaps you meant, "as explained above
`in the "Claim Construction" section.
` A If there's a typo, I don't remember. I
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 107 of 384
`
`
`
`Page 108
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`9
`10
`10
`11
`11
`12
`12
`13
`13
`14
`14
`15
`15
`16
`16
`17
`17
`18
`19
`20
`21
`22
`23
`24
`25
`
`would have to -- to see -- to see either Section
`5(d) of the petition, or if you say it's similar to
`my own claim terms, please refer me to the right
`place.
` Q Well, let's -- let's just answer my
`question. Let's go back to my question.
` When you wrote "sublinear" here --
` A Right.
` Q -- were you trying to convey that these
`Q
`-- were you trying to convey that these
`searches here in Ghias were sublinear with respect
`searches here in Ghias were sublinear with respect
`to the size of the dataset?
`to the size of the dataset?
` A No. No. The discussion there was
`A
`No. No. The discussion there was
`relative to brute-force search. And it is only
`relative to brute-force search. And it is only
`sublinear -- it is known to be sublinear in that
`sublinear -- it is known to be sublinear in that
`sense. I do not know whether it would be sublinear
`sense. I do not know whether it would be sublinear
`in the size of the database for that particular
`in the size of the database for that particular
`algorithm.
`algorithm.
` Q Now, if we look at the first sentence in
`paragraph 123, when you used the word "sublinear"
`there, were you using the term "sublinear" to mean
`sublinear compared to brute force or sublinear
`compared to the size of the dataset?
` A Compared with the size of the dataset.
` Q So in this paragraph, the first time you
`used "sublinear," you meant it with respect to the
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 108 of 384
`
`
`
`Page 109
`
`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
`
`size of the dataset, the second time with respect to
`brute force; is that right?
` A The second time was quoting something
`else, and it might have been with respect to brute
`force. Just to make it clear, what I -- what I mean
`is in the first occurrence on the second line,
`sublinear means with respect to the size of the
`dataset. And in the last line, it means relative to
`brute force.
` Q Would you do me a favor and, in your
`Declaration, that copy there, would you annotate
`that. And I'll tell you what you can write here for
`me.
` The first one, can you write, "Sublinear
`with respect to the dataset."
` MR. ELACQUA: I'm going to object. It's asked
`and answered.
` THE WITNESS: I don't feel -- I've just said
`it in words. Why do I need to write this down? I
`don't feel comfortable writing this down.
`BY MR. DOVEL:
` Q Because I'm going to ask you some
`questions about it.
` A Well, I understand very well. So I want
`to add --
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 109 of 384
`
`
`
`Page 110
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`11
`12
`12
`13
`13
`14
`14
`15
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`
` Q If you want me to write it, I'm happy to
`write it.
` A Okay.
` Q I'm going to take Exhibit 237, and I'm
`going to annotate it as follows -- see if I've got
`this right. The first time you used "sublinear" is
`with respect to the size of the dataset?
` A Of the -- let's be clear. This talks
`about Ghias; right? So the dataset there is the
`song, yes.
` Q When you wrote "sublinear" here, you're
`Q
`When you wrote "sublinear" here, you're
`referring to sublinear with respect to the size of
`referring to sublinear with respect to the size of
`the dataset being searched?
`the dataset being searched?
` A Yes. Okay. Just to be clear, the dataset
`A
`Yes. Okay. Just to be clear, the dataset
`is the whole database, okay, the database of songs.
`is the whole database, okay, the database of songs.
` Q So what I've annotated above the first
`"sublinear" is, "With respect to the size of the
`database being searched"; is that right?
` A Yes.
` Q Now, the second time you used it, you used
`it with -- sublinear with respect to brute force?
` A Relative to brute force.
` Q Relative to brute force. I'll write that.
` Now, did the annotations that I've made
`there accurately reflect how you intended to use the
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 110 of 384
`
`
`
`Page 111
`
`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
`
`word "sublinear" in paragraph 123 of your
`Declaration?
` A Let me qualify this about the last one.
`It's certainly sublinear relative to brute force.
`I'll just read this again carefully.
` Well, no. It does not reflect it. Okay?
`Because, again, that last sentence -- I'm going to
`read the last sentence again. It does not talk only
`about using that step we are discussing, which is
`Baeza-Yates instead of brute force; it discloses --
`Ghias discloses searches whose execution time is
`proportional -- which would have been to the
`logarithm -- of the size of the query. Okay?
` Now, in terms of the size of the database
`being searched, it is sublinear. It -- it would be
`for the exact same reason that I mentioned the first
`time.
` Q Well --
` A You see, I agree with you that replacing
`brute force by Baeza-Yates is going to give us a
`sublinear time complexity relative to brute force;
`so for that one specific step. But the sentence
`there in 123, the last sentence, talks about the
`entire method that is disclosed in Ghias.
` Q All right. Well, let's talk about the
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 111 of 384
`
`
`
`Page 112
`
`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
`
`entire method.
` The -- would you agree that the only
`portion of Ghias that you cite to support your
`conclusion that it discloses searches whose
`execution time is proportional to the log of the
`size of the dataset is lines 24 to 28, Column 6?
` A I don't recall if it's the exact -- if
`it's the only one. I just see the -- I just see the
`qualifier on line 3 of paragraph 123 in particular.
` So there are many ways in which the search
`in Ghias can be shown to be sublinear in the size of
`the database. I would be most happy to explain
`those -- those reasons. I have -- in the remainder
`of that paragraph, I have only quoted one part of
`Ghias. But there are other parts that show it.
` Q And my question is this. My question is
`about your testimony and what you chose to present.
`All right?
` A Yes. Yes.
` Q Would you agree that in your discussion of
`whether Ghias discloses sublinearity -- withdrawn.
` Would you agree that in your discussion of
`whether Ghias discloses a sublinear time search, you
`have cited only from Ghias Column 6, 23 through 35?
` A In that paragraph -- okay. Again, there
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 112 of 384
`
`
`
`Page 113
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`14
`15
`15
`16
`16
`17
`17
`18
`18
`19
`19
`20
`20
`21
`21
`22
`23
`24
`25
`
`are other reasons that I implied in this "in
`particular." You know, it does not say it's the
`only reason. Okay?
` So this "in particular," again, refers to
`other reasons that are not listed here. And, again,
`in light of the claim construction by -- by the
`Board, makes it very clear that the search algorithm
`in Ghias is sublinear in the size of the database.
`So that's all implied in this "in particular."
` Q I just need an answer to my question. You
`haven't answered it yet.
` A Okay. So --
` Q I'll ask it again.
` A Yes.
` Q In your discussion of whether Ghias
`Q
`In your discussion of whether Ghias
`discloses a sublinear time search, paragraph 123 --
`discloses a sublinear time search, paragraph 123 --
` A Right.
`A
`Right.
` Q -- would you agree that the only portion
`Q
`-- would you agree that the only portion
`of Ghias that you cite to is Column 6, lines 23
`of Ghias that you cite to is Column 6, lines 23
`through 35?
`through 35?
` A I agree.
`A
`I agree.
` Q Now, if we look at your claim chart.
` A Which page?
` Q Page 66 and 67.
` Do you see the element that contains
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 113 of 384
`
`
`
`Page 114
`
`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
`
`sublinear time search is found at the bottom of 66
`and carries over to 67; right?
` A Uh-huh.
` Q Yes?
` A Let me just read it.
` Okay. So that box in my claim -- in my
`claim chart discusses two issues. Okay. One is the
`one we just discussed with the O(n log(m)), and then
`the other issue is the second sentence, the last
`sentence.
` Q Well, Element (b) covers a number of
`things. It requires a computer system,
`identification of a media work, so on.
` One of the -- one of the limitations in
`Element (b) is this sublinear time search; right?
` A Yes. Yes.
` Q Now, the portion of your analysis that
`discusses the sublinear time search is on page 67;
`is that right?
` A Yes.
` Q And that's the sentence that says, "Ghias
`further discloses that this search is sublinear
`because its execution time may be proportional to
`the logarithm of the dataset."
` Do you see that?
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 114 of 384
`
`
`
`Page 115
`
`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
`
` A Yeah. But that's not the only reason.
` Q Well, that's the only reason you present
`here; right?
` A No. In the last sentence of that box,
`"Ghias further discloses" and so on, that search is
`also sublinear. Because it identifies a list of
`neighbors, the size of that list is typically
`sublinear. So any time you search a list whose size
`is sublinear, your search is sublinear.
` Q In your report, you don't have any
`analysis where you try to link up the term
`"neighbors" to sublinear; right?
` A It is there because it is there in Ghias.
`Okay? So --
` Q Now, my question is in your Declaration --
` A Right.
` Q -- you've got an analysis in which you
`assert that it discloses a search that's sublinear
`because its execution time may be proportional to
`the logarithm of the dataset; right?
` A Yes.
` Q There you're explaining a reason why Ghias
`discloses something that's sublinear; right?
` A Right.
` Q Now, then you've got a comment about, "It
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 115 of 384
`
`
`
`Page 116
`
`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
`
`discloses a search that identifies a list of
`neighbors" --
` A Right.
` Q -- that's another element in this set;
`right?
` A That's right.
` Q In other words, the claim requires that it
`must be a search of extracted features of identified
`media works to identify a neighbor; right?
` A Yeah. But the step itself has a certain
`complexity. This "search" in the last sentence has
`a complexity that is sublinear in the size of the
`database.
` Q You just need to answer my question.
` A I think I just did. Can you repeat.
` Q No. Yeah. The claim has a limitation
`that requires that there be extracted features of
`identified media works to identify a neighbor.
` A Yes. Yes.
` Q Now, in the last part of the box in
`column -- on the right column at page 67 for
`Element (b), you say, "Ghias further discloses that
`this search identifies a list of neighbors, i.e."
`and then you've got a -- you quote from a passage in
`Ghias; right?
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 116 of 384
`
`
`
`Page 117
`
`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
`
` A That's right.
` Q Other than quoting this passage in Ghias,
`do you present any analysis in your Declaration that
`it tends to -- attempts to demonstrate that a rank
`list of approximately matching melodies or the
`single most approximate matching melody would
`constitute a sublinear time search?
` A It is disclosed in Ghias --
` Q That's not my question, sir.
` In your Declaration --
` A I don't write it explicitly, no. I did
`not write it explicitly, but it is disclosed in
`Ghias.
` Q Is it disclosed in -- at Column 2, 50 to
`59?
` A Which column?
` Q Well, you cite to Column 2, 50 to 59 and
`Column 6, 60 to 63.
` A Yes, it is there.
` Okay. So if you look at, say, 60 to 63,
`in particular, if we --
` Q Which column?
` A Column 6.
` Q Okay. I'm at Column 6. I'm looking at
`lines 60 to 63.
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 117 of 384
`
`
`
`Page 118
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`9
`10
`10
`11
`11
`12
`12
`13
`13
`14
`14
`15
`15
`16
`16
`17
`17
`18
`18
`19
`19
`20
`20
`21
`21
`22
`22
`23
`24
`25
`
` A Yes. Yes. So "The computer may be
`programmed such that the database returns a list of
`songs, and the number of matches the database should
`retrieve depends upon the error tolerance used
`during the key search."
` So that error tolerance determines the
`size of the lists, and that's how you get
`sublinearity.
` Q Well, if we take a look here, it says,
`Q
`Well, if we take a look here, it says,
`"The computer may be programmed so that for a given
`"The computer may be programmed so that for a given
`query, the database returns a list of songs ranked
`query, the database returns a list of songs ranked
`by how well they match the query, not just one best
`by how well they match the query, not just one best
`match"; right?
`match"; right?
` A Yes.
`A
`Yes.
` Q In other words, it identifies two
`Q
`In other words, it identifies two
`alternative ways of producing results: One is to
`alternative ways of producing results: One is to
`identify the best match, and the other is to
`identify the best match, and the other is to
`identify a list of the best matches.
`identify a list of the best matches.
` A A list of matches.
`A
`A list of matches.
` Q With -- that are ranked. A ranked list;
`Q
`With -- that are ranked. A ranked list;
`right?
`right?
` A Yes.
`A
`Yes.
` Q Now, there's nothing in this sentence here
`that describes the performance of the algorithm;
`that is, how long it's going to take to execute as
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 118 of 384
`
`
`
`Page 119
`
`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
`
`we scale the size of the dataset; right?
` A Yes, it does. It's obvious. You have the
`size of --
` Q You're saying you could infer from it.
`You could do an analysis to show it; is that right?
` A It's hardly an analysis. It's simply --
` Q Well, is it stated here? Let's start with
`that.
` MR. ELACQUA: I'd like him to answer the
`question first. You interrupted him. He needs
`to --
` MR. DOVEL: I would love him to answer the
`question.
` MR. ELACQUA: Well, he needs to finish first.
`Let him finish, then ask another one.
`BY MR. DOVEL:
` Q I'll give you the question, and see if you
`can answer it.
` Does it say here -- does it have any words
`that describe the performance of the algorithm as
`database increases?
` A The complexity of that search is
`immediately inferred from what's written in this
`document. It is the size of the list, and then
`another factor that depends on the length of each
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 119 of 384
`
`
`
`Page 120
`
`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
`
`string. As soon as the size of that list is
`sublinear, you are done.
` It's -- it's clearly written here. The
`size of the list is a parameter. The list could be
`as small as 1. You know, that -- that does it. I
`mean, if the list -- or it could be 2, any fixed
`number. And then when you search, say, a list of
`two elements, your complexity is sublinear relative
`to the size of the database.
` Q Well, if the list -- are you saying
`that -- are you saying the size of the list that we
`want returned to us?
` A So you always -- when you talk about
`sublinearity, you always compare it with the size of
`the database.
` So in this algorithm, there's a search,
`okay, on the list. If the list is, say, size 2,
`just to give an example, the search has complexity
`which is O(1/n) times a full search on the database.
`So it is sublinear.
` Q Okay. This is not a search on the list.
`This is returning a list as results; is that right?
` A There is a search on the lists.
` Q Okay. We're not searching on the list
`here.
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 120 of 384
`
`
`
`Page 121
`
`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
`
` Does this say search the list?
` A This is in Ghias. Let me find it.
` Q Just -- let's take a look at 60 to 63.
`We've got to take it one step at a time. We'll look
`at all of Ghias before we're done. We're focused
`now on Column 6, lines 60 to 63.
` Do you see that? Yes or no?
` A Yes.
` Q All right.
` A I'm sorry. When I say "yes," I agree with
`your reading. So can you restate your question.
` Q Would you agree, sir, that what this
`describes here is running the query on a database,
`and the results is going to be a list of songs
`ranked by how well they match the query?
` A That is correct.
` Q The list is not a parameter; it is what is
`returned. We might have two songs that match, three
`or five; right?
` A No, that's not true.
` Q All right. Let's do this.
` Let's assume that the list is not a
`parameter.
` A That's not true.
` Q We'll get to that. I want you to assume
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 121 of 384
`
`
`
`Page 122
`
`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
`
`that the list is not a parameter.
` We don't say, "Return to us five songs."
`What we say is, "Return to us any songs that meet
`our matching criteria, and rank them."
` A What's the matching criteria?
` Q The matching criterion will be as set
`forth above. For example, it has no more than two
`errors.
` A No. It says exactly two errors in the
`algorithm.
` Q Okay. Let's assume it says exactly two.
` A Okay.
` Q No. Let's assume -- we'll start it this
`way because I think this is actually reflected.
` Let's assume that we're going to be
`willing to accept anything that's an exact match,
`that has one error or that has two errors. All
`right? And it returns a list of those that match to
`us under those criteria.
` Do you follow me so far?
` A Yes.
` Q In that case, do we have a sublinear time
`search with respect to the size of the dataset?
` A It all depends on what this K was. K, the
`number of mismatches, determines the size of the
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 122 of 384
`
`
`
`Page 123
`
`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
`
`list.
` Q Okay. I understand that. My question --
`I've just said -- I've given you an example.
` We've got K is equal to 2, and wha