throbber
Page 97
`
` 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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

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.

throbber

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.

Become a Member

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

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket