throbber
Page 97
`
`1
`
`Q
`
`Okay . Now ,
`
`i f we have a certain number of
`
`2 mismatches , that means we ' re -- allow -- say K
`
`] mismatches . That means we ' re going to assume t ha t
`
`4
`
`5
`
`6
`
`7
`
`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
`
`8 matches except in three positions .
`
`9
`
`10
`
`Q
`
`If you set K equal to M, that means we 're
`
`going to accept a situa t ion where every letter is
`
`11 mismatched ; righ t ?
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`A
`
`Q
`
`is it?
`
`A
`
`Q
`
`Yes .
`
`That ' s not really a very practical search ,
`
`Well , these -- these problems e x ist .
`
`Well , not in terms of math . Bu t 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 sen t ence like that , when the
`
`engineer gives it , it means you look -- you have to
`
`know that in the case o f a large number of
`
`23 mismatches , the algorithm would be very , very fast .
`
`24
`
`So this is very useful .
`
`Q
`
`25
`
`Is it the case that if we have -- that
`NETWO RK- I EXHIBIT 2006
`L . . , - - - - - - - - - - - - - - - - - - - - 'Google Inc. v. Network- I Technologies, Inc.
`IPR2015-OO345
`TSG Reporting - Wor1dwidt
`Pa~97of3S4
`
`

`
`Page 97
`
`1
`
`Q
`
`Okay . Now ,
`
`i f we have a certain number of
`
`2 mismatches , that means we ' re -- allow -- say K
`
`] mismatches . That means we ' re going to assume t ha t
`
`4
`
`5
`
`6
`
`7
`
`there are three mismatches someplace in the string?
`
`A
`
`Yes . We recognize there are three errors ,
`
`and we seek a match tha t differs in three positions .
`
`That would be the definition of a match .
`
`So it
`
`8 matches except in three positions .
`
`9
`
`10
`
`Q
`
`If you set K equal to M, that means we ' re
`
`going to accept a situa t ion where every letter is
`
`11 mismatched ; righ t ?
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`A
`
`Q
`
`is it?
`
`A
`
`Q
`
`Yes .
`
`That ' s not really a very practical search ,
`
`Well , these -- these problems e x ist .
`
`Well , not in terms of math . Bu t 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 sen t ence like that , when the
`
`engineer gives it , it means you look -- you have to
`
`know that in the case o f a large number of
`
`23 mismatches , the algorithm would be very , very fast .
`
`24
`
`25
`
`So this is very useful .
`
`Q
`
`Is it the case that if we have -- that
`
`TSG Reporting - Worldwide - 877-702-9580
`Pa~97 of 3S4
`
`

`
`Page 98
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`this algorithm , as disclosed here , would be
`
`sublinear with respect to the size of the dataset
`
`being searched, it we wan t to have a t least some
`
`ma t ches -- some matching between our actual query
`
`and our actual string?
`
`A
`
`Your question is vague . So you need to
`
`specify K.
`
`Q
`
`A
`
`K is going to be some number less than M.
`
`I can 't answer it .
`
`If , say , all they
`
`disclose here is if K is equal to M, the answer is
`
`obt ained immedia te ly .
`
`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
`
`16 where we 're trying to search where the -- where K is
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`less than M?
`
`A
`
`Again, sublinearity here ~ n that paragraph
`
`is with respect to the brute-force search algorithm .
`
`Q When you read Column 6, lines 36 t hrough
`
`59 , did you conclude i t disclosed a sublinear time
`
`search with res pect to t he size of the dataset being
`
`searched if K,
`
`t he number of mismatches , is less
`
`than M, the size of the st r ing?
`
`A
`
`I don ' t conc l ude that , no .
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 98 of384
`
`

`
`Page 99
`
`1
`
`2
`
`]
`
`4
`
`5
`
`6
`
`7
`
`Q
`
`Does -- withdrawn .
`
`If -- would it be fair to read Columns 6,
`
`lines 36 through 59 , as disclosing a $ublinear time
`
`search with respect to the dataset for K less than
`
`M?
`
`A
`
`I don ' t know . They don ' t -- they only
`
`comment on speci al values of K, which are 0 , 1 and
`
`8 M; right? They don ' t comment about anything else .
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`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 suhlinear time search?
`
`A
`
`If K is 0, it ' s the same as the
`
`Boyer-Moore prob lem . 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 e xactly the same as our discussion on
`
`Boyer-Moore .
`
`I f you compare it with a brute-fo r ce
`
`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 Declara ti on , we discussed that; so I
`
`can , again , answer exactly .
`
`1 quoted , when it came
`
`to Boye r-Moore , a reference that e xplains the
`
`TSG Reporting - Worldwide - 877 - 702-9580
`Pa~99of3S4
`
`

`
`Page 100
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`1
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`complexity of this . And in this contex t 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 O.
`
`You say that ' 5 the same as the Boyer-Moore
`
`problem; right?
`
`A Right.
`
`Q When K is equal to O. then does this
`
`disclose a sublinear time search as you used
`
`" sublinear time search " in your Declaration?
`
`A
`
`Q
`
`No , it does not .
`
`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 -- r have no way of
`
`knowing . Again , it says "order of . " So it means at
`
`17 most linear .
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`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
`
`Q
`
`Yes . Yes .
`
`Now , 1n here ,
`
`in paragraph 123 , this is
`
`the portion of your Declaration where you present
`
`TSG Reporting - Worldwide - 877-702-9580
`P3ge 100 oDS4
`
`

`
`Page 101
`
`1
`
`2
`
`]
`
`•
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`your opinions about whe ther Ghias discloses a
`
`sub1inea r search ; right?
`
`A
`
`Q
`
`Yes .
`
`And in paragraph 123 , you say that , "Ghias
`
`discloses sea r ches whose e xecution times are
`
`proportional to the logarithm of the size of the
`
`dataset , which as e x pla i ned above , are subl inear ."
`
`Do you see that?
`
`A
`
`1 don ' t see " proportional to ." It says
`
`"order of ."
`
`Q Well
`
`A
`
`If I ' m just quoting from Ghias , it says
`
`"order of ." It d oesn ' t say " proportional ."
`
`Q What you wrote is , MGhias discloses
`
`searches whose e xecution times are proport i onal to
`
`the logarithm o f the size of the dataset ."
`
`Do you see that?
`
`Yes . Okay .
`
`And then you q uote a particular clause
`
`A
`
`Q
`
`that appea r s in Ghias ; right?
`
`A
`
`Q
`
`That is correct .
`
`Now , what you quote from Ghias
`
`discloses
`
`e xecution
`
`" searches whose e xecution
`
`times are on the order of linear to the size of the
`
`dataset "; right?
`
`TSG Re porting - Worldwide - 877 - 702-9580
`PaS'-' 10 1 ofJ84
`
`

`
`Page 102
`
`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
`
`Okay .
`
`So it says log (m) - -
`
`let me just
`
`ma ke s u re I get my N and M stra ight .
`
`N is t he si z e o f the son g ; M is t he si z e
`
`of t h e query . So yeah , this should have read
`
`" log(m )," which is the size of the query .
`
`So jus t not t o confuse , o kay , there ' s two
`
`differen t datase t s . So it should have been the size
`
`of the query .
`
`Q
`
`In other words, what it discloses is
`
`searches whose e xecution times are proportional to
`
`the logarithm of the size of the query ; right?
`
`A
`
`Yeah .
`
`It -- because it ' s log(m) that
`
`appears on the right side .
`
`Q
`
`Does t his disclose a sea r ch whose
`
`e xecution time is proportiona l to the logarithm of
`
`the size of the datase t ?
`
`A
`
`So when you say " da t aset , " you - -
`
`r assume
`
`you ' re re f erring to the size of the string , which i s
`
`N in Ghias -- in the Ghias pate n t?
`
`Is that what you 're referring to?
`
`Q Well
`
`A When you say -- there are t wo da t asets ;
`
`right? There ' s
`
`t he que r y , which is size M, and
`
`there ' s the string or the song that is size N.
`
`50
`
`it should have -- it is the l og (m) .
`
`T5G Re porting - Worldwide - 877-702-9580
`Page 102 of384
`
`

`
`Page 103
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`19
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`Q
`
`Is it the case that Ghias discloses a
`
`search whose e xecution time is proportional to the
`
`log of the size ot 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 t he 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
`
`Q
`
`A
`
`Yes . Yes.
`
`Not the -- not the database?
`
`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
`
`" sublinear " as it ' s used in t he patent , it ' s abou t
`
`the execu t ion time as we increase the size of the
`
`database ; is that right?
`
`A
`
`Q
`
`A
`
`Q
`
`10 the patent ,
`
`yes .
`
`Yes .
`
`Yes .
`
`When yoo were
`
`writing your oplnlons io
`
`paragraph
`
`123, were yoo
`
`using the term " sub l inear "
`
`to refer to a search whose e xecution time scaled at
`
`TSG Reporting - Worldwide - 877-702-9580
`Page 103 of384
`
`

`
`Page 104
`
`1
`
`2
`
`]
`
`4
`
`5
`
`a sublinear relationship t o the size of the
`
`database?
`
`A
`
`Okay . So when I wrote - - okay . This
`
`paragraph 123 , okay -- I addressed sublinearity o f
`
`the search as disclosed in Ghias . Again , there are
`
`6 many ways , many reasons why the search is sublinear .
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`And I would li ke 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
`
`A
`
`Q
`
`A
`
`Q
`
`A
`
`DO you remember my question?
`
`Could you restate it.
`
`00 you recall it?
`
`Please restate it .
`
`00 you remember it?
`
`I
`
`remember parts of it . Otherwise I
`
`19 wouldn ' t have asked you to restate .
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`Q
`
`Well , it ' s important that you focus on my
`
`question
`
`A
`
`Q
`
`Yes .
`
`-- I t hink you ' re starting to dri ft of f
`
`and testify about peripheral matters instead of
`
`answering my question . So I want you to really
`
`TSG Reporting - Worldwide - 877 - 702-9580
`PaS'-' ](14 ofJ84
`
`

`
`Page 105
`
`1
`
`2
`
`]
`
`•
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`fOCllS on it .
`
`A
`
`Q
`
`A
`
`Q
`
`Okay .
`
`When you
`
`in writing paragraph 123 --
`
`Ye s .
`
`When you wrote that Ghias discloses
`
`searches
`
`-- withdrawn .
`
`Do you ,ee th is last sentence in
`
`paragraph
`
`123?
`
`A
`
`Q
`
`Yes .
`
`Were you trying to convey that Ghias
`
`discloses searches that are sublinear?
`
`A
`
`Ye s .
`
`Q When you use t he word " $ublinear "
`
`t here ,
`
`did you mean to have the same definition as you used
`
`in your Declara ti on ; that is , that it has an
`
`execution time that scales at a sublinear
`
`relationship to the size o f the database?
`
`A
`
`Okay .
`
`So here ' s what I wrote :
`
`" Ghias
`
`discloses search algorithms that are substantially
`
`fa ster than brut e- f orce search ." And that includes
`
`sublinearity in e xactly the sense that I wrote in my
`
`22 Declaration , in relation to the size of the dataset .
`
`23
`
`24
`
`25
`
`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
`PaS'-' lOS ofJ84
`
`

`
`Page 106
`
`lather algorithms that I mentioned there , such as
`
`2 Gannet .
`
`So all that is claimed there is basically
`
`]
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`restating a port ion of -- of Ghias .
`
`And , again , just to make it clear ,
`
`I do
`
`not claim that t hat 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
`
`sub1inea r compared to the size of the database?
`
`A
`
`On the second line of that parag r aph ,
`
`i t
`
`is sublinear in the size of the database . Okay? So
`
`1] Ghias discloses a search t hat is sublinear in the
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`"
`
`25
`
`size of the database .
`
`The second occurrence of " sublinear " is in
`
`the very last line of that paragraph 12] .
`
`It is
`
`quoting from -- f rom Ghias . And what ' s wri tten
`
`there meant subli near relative to brute - force
`
`search .
`
`Q All ri ght .
`
`Jus t to be clea r, the second
`
`" sublinear " you wrote was sublinear with respect to
`
`brute force , not with respect to the size of the
`
`dataset ; right?
`
`A
`
`Q
`
`I cannot claim that , no .
`
`No .
`
`I ' m con f used now .
`
`TSG Reporting - Worldwide - 877 - 702-9580
`PaS'-' 106 ofJ84
`
`

`
`Page 107
`
`1
`
`2
`
`]
`
`•
`
`5
`
`6
`
`When you wrot e " sublinear " in the last
`
`line of paragraph 123 , were you using sublinear to
`
`mean sublinear t o 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 Sed) in your
`
`7 Declaration .
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`A
`
`Q
`
`Well , there ' s some typo , then .
`
`" Section 5 (d) " apparently refers to your
`
`"Claim Construc t ion " section . And I infer that
`
`because there ' s a Section 5(d) in the petition tha t
`
`is the "Claim Construction " section .
`
`A
`
`Okay .
`
`So you are saying " S(d) " refers t o
`
`what , then? It must be a typo .
`
`Q Well , I' ll tell you this : There ' s no SId)
`
`in your Declaration .
`
`A
`
`Q
`
`A
`
`Q
`
`Okay .
`
`There ' s a SId) 1n the petition .
`
`Okay .
`
`The 5 (d) in t he petition is the " Claim
`
`21 Construction " section .
`
`22
`
`23
`
`211
`
`25
`
`A
`
`Q
`
`Okay .
`
`50 perhaps you meant , "as e xplained above
`
`in the "Claim Construction " section .
`
`A
`
`I f there ' s a
`
`t ypo ,
`
`I don ' t remember .
`
`I
`
`T5G Reporting - Worldwide - 877 - 702-9580
`PaS'-' 107 o fJ84
`
`

`
`Page 108
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`15
`
`16
`
`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 t o the r ight
`
`place .
`
`Q Well ,
`
`l et ' s -- let ' s just a nswe r my
`
`q uestion . Let ' s go back to my ques t ion .
`
`Whe n you wrote " sub1inear " here
`
`A Right .
`
`Q
`
`-- were you trying to convey that these
`
`searches here in Ghias were sublinear with respect
`
`to the size of the dataset?
`
`A
`
`No. No. The discussion t here was
`
`relative to brute-force search . And it is only
`
`sublinear
`
`it is known to be sublinear in that
`
`sense .
`
`I do no t know whether it would be sublinear
`
`in the size of the database for that particular
`
`algorithm .
`
`Q
`
`Now,
`
`i f we loo k at the first sentence in
`
`paragraph 123 , when you used the word " subl i near "
`
`there , were you using the term " subl inear " to mean
`
`sub1inear compared to brute force or sublinear
`
`compared t o the size o f the dataset?
`
`A
`
`Q
`
`Compared with the size of t he da t aset .
`
`So in this paragraph, the first time you
`
`used " sub l inear , " you meant it with respect to the
`
`TSG Re porting - Worldwide - 877-702-9580
`Page 108 of384
`
`

`
`Page 109
`
`1
`
`2
`
`]
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`size of the dataset , the second time with respect to
`
`brute fo r ce ; is that right?
`
`A
`
`The second time was quoting some t hing
`
`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 .
`
`10
`
`Q Would you do me a favor and , in your
`
`11 Declaration , that copy there, would you annotate
`
`12
`
`13
`
`14
`
`that . And I ' ll tell you what you can write here f or
`
`me .
`
`The first one , can you write , "Sublinear
`
`15 with respect to the dataset ."
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`"
`
`25
`
`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
`PaS'-' 109 ofJ84
`
`

`
`Page 110
`
`1
`
`Q
`
`If you want me to write it , I ' m happy to
`
`2 write it .
`
`3
`
`•
`
`5
`
`6
`
`A Okay .
`
`Q
`
`I ' m going to take Exhibit 237 , and I ' m
`
`going to annotate it as follows -- see if I ' ve got
`
`t.his right. The first time you used " sublinear " is
`
`1 with respect to the size of the dataset?
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`l6
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`A Of the -- let ' s be clear . This talks
`
`about Ghias ; right? So the dataset there is the
`
`song , yes .
`
`Q When you wrote " sub linear " here, you ' re
`
`referring to sublinear with respect t o the size o f
`
`the dataset being searched?
`
`A
`
`Yes . Okay .
`
`Just to be clear , the dataset
`
`is the whole database . okay . the database of songs .
`
`Q
`
`So what I ' ve annotated above the first
`
`" sublinear " is. "With respect t.o the size of the
`
`database being searched": is that right.?
`
`A
`
`Q
`
`Yes.
`
`Now , the second t.ime you used it . you used
`
`it with -- sublinear with respect to brute force?
`
`A
`
`Q
`
`Relative to brute force .
`
`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
`P3ge 11 0 oDS4
`
`

`
`Page 111
`
`1
`
`word " sublinear " in paragraph 123 of you r
`
`2 Declaration?
`
`]
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`A
`
`Let me qualify t his about the last one .
`
`It's certainly sublinear relative to brute force .
`
`I ' ll just read t his 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
`
`10
`
`Baeza-Yates ins tead of brute f orce ; it discloses
`
`11 Ghias discloses searches whose execution time is
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`proportional
`
`which would have been to the
`
`logarithm
`
`of the size of the query . Oka y?
`
`Now , in terms of the size of the database
`
`being searched , it is sublinear .
`
`It -- it would be
`
`for the e xact same reason that I mentioned the first
`
`time .
`
`Q
`
`A
`
`Well --
`
`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 Uhias .
`
`Q All r i ght . Well ,
`
`l et ' s talk about the
`
`TSG Re porting - Worldwide - 877 - 702-9580
`PaS'-' 11 1 of 384
`
`

`
`Page 112
`
`1
`
`2
`
`]
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`1]
`
`14
`
`entire method .
`
`The -- would you agree that the only
`
`portion of Ghias t hat 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 i t ' s the exact -- i f
`
`it's the only one .
`
`I just see the -- I just see the
`
`qualifier on line] of paragraph 123 in particular .
`
`50 there are many ways in which the search
`
`in Ghias can be shown to be sublinear in the size o f
`
`the database .
`
`I would be most happy to e xplain
`
`those -- those reasons .
`
`I have - -
`
`in the remainder
`
`of that paragraph ,
`
`I have only quoted one part of
`
`15 Ghias . But there are other parts that show it .
`
`16
`
`17
`
`18
`
`19
`
`20
`
`Q
`
`~nd my question is this . My question is
`
`about your testimony and what you chose to present .
`
`~ll right?
`
`A
`
`Q
`
`Yes . Yes.
`
`Would you agree that in your discussion o f
`
`21 whether Ghias discloses sublinearity -- withdrawn .
`
`22
`
`Would you agree that in your discussion of
`
`23 whether Ghias discloses a sublinear time search, you
`
`24
`
`25
`
`have cited only from Ghias Column 6 , 23 through 35?
`
`A
`
`In that paragraph -- okay . ~gain ,
`
`there
`
`T5G Reporting - Worldwide - 877-702-9580
`PaS'-' 112 of 384
`
`

`
`Page 113
`
`1
`
`2
`
`3
`
`•
`
`5
`
`6
`
`1
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`I.
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`are other reasons that I implied in this " in
`
`particular ." You know , it does not s a y 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 i n this " in particular ."
`
`Q
`
`I just need an answer to my question . You
`
`haven ' t answered it yet .
`
`A
`
`Q
`
`A
`
`Q
`
`Okay .
`
`So
`
`I ' ll ask it again .
`
`Yes .
`
`In your discussion of whether Ghias
`
`discloses a sub1inear time search , paragraph 123
`
`A
`
`Q
`
`Right .
`
`-- would you agree tha t the only po r tion
`
`of Ghias that you cite to is Column 6, lines 23
`
`through 35?
`
`A
`
`Q
`
`A
`
`Q
`
`I agree .
`
`Now , if we look at your claim chart .
`
`Which page?
`
`Page 66 and 61 .
`
`DO you see the element that contains
`
`T5G Reporting - Worldwide - 877-102-9580
`P3ge 11 3 of384
`
`

`
`1
`
`2
`
`]
`
`•
`
`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?
`
`Page 114
`
`A
`
`Q
`
`A
`
`Uh-huh .
`
`Yes?
`
`Let me just read it .
`
`Okay .
`
`So tha t 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 se ntence , 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
`
`Q
`
`Yes . Yes .
`
`Now , the portion of your analysis that
`
`discusses the sub1inear time search is on page 67 ;
`
`is that right?
`
`A
`
`Q
`
`Yes .
`
`And that ' s the sentence that says , "Ghias
`
`further discloses that this search is sublinear
`
`because its execution time may be p r oportional to
`
`the logarithm of the da t aset . "
`
`Do you see that?
`
`TSG Reporting - Worldwide - 877-702-9580
`PaS'-' 11 4 of 384
`
`

`
`Page 115
`
`1
`
`2
`
`]
`
`•
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`1]
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`"
`
`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 furthe r discloses " and so on , that search is
`
`also sublinear . Because it identifies a list of
`
`neighbo rs, the s i ze of th at l ist 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 sub1inear ; right?
`
`A
`
`It is there because it is the r e in Ghias .
`
`Okay? So
`
`Q
`
`A
`
`Q
`
`Now, my question is in your Decla r ation --
`
`Right.
`
`-- you ' ve got an analysis in which you
`
`assert that it di scloses a search that ' s sub1inear
`
`because its e xecution time may be proportional to
`
`the loga r ithm of the da t aset ; right?
`
`A
`
`Q
`
`Yes .
`
`There you ' re explaining a reason why Ghias
`
`discloses someth i ng tha t ' s sublinear ; ri ght ?
`
`A
`
`Q
`
`Right.
`
`Now , then you ' ve got a comment about, " It
`
`T5G Reporting - Worldwide - 877 - 702-9580
`PaS'-' 11 S of 384
`
`

`
`Page 116
`
`1
`
`2
`
`]
`
`•
`
`5
`
`6
`
`7
`
`discloses a search that identifies a list of
`
`neighbors " --
`
`A
`
`Q
`
`right?
`
`A
`
`Q
`
`Right .
`
`-- that ' s another element in this set ;
`
`That ' 5 right..
`
`In other words , the claim requires that it
`
`8 must be a search of extracted features of identified
`
`9 media works to identify a neighbor ; right?
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`A
`
`Yeah . But the step itself has a certain
`
`complex ity . This " search " in the last sentence has
`
`a complexity that is sublinear in the size of the
`
`database .
`
`Q
`
`A
`
`Q
`
`You just need to answer my question .
`
`I think I just did . Can you repeat .
`
`No . Yeah . The claim has a limitation
`
`that requires that there be extracted features o f
`
`identified media works t o identi f y a neighbor .
`
`A
`
`Q
`
`Yes . Yes .
`
`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 sea r ch identifies a list of neighbors , Le ."
`
`and then you ' ve got a -- you quote from a passage in
`
`25 Ghias ; right?
`
`TSG Reporting - Worldwide - 877-702-9580
`PaS'-' 116 of 384
`
`

`
`Page 117
`
`1
`
`2
`
`]
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`"
`
`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 ran k
`
`list o f approximately matching melodies or the
`
`single most approximate matching melody would
`
`constitute a sub li near time search?
`
`A
`
`Q
`
`It is disclosed in Ghias --
`
`That ' s not my question , sir .
`
`In you r Declara tion --
`
`A
`
`I don ' t write i t explicitly , no .
`
`I did
`
`not write it e xpl icit l y , but it is disclosed in
`
`Ghias .
`
`Q
`
`Is it disclosed in -- at Column 2 , 50 to
`
`59?
`
`A Which column?
`
`Q Well , you c ite to Column 2 , 50 to 59 a nd
`
`Column 6 , 60 to 6] .
`
`A Yes , it is there .
`
`Okay .
`
`So if you look at , say , 60 t o 6] ,
`
`in particular , if we --
`
`Q
`
`A
`
`Q
`
`Which column?
`
`Column 6 .
`
`Okay .
`
`I ' m at Column 6 .
`
`I ' m loo king a t
`
`lines 60 to 63 .
`
`TSG Reporting - Worldwide - 877 - 702-9580
`PaS'-' 11 7 of 384
`
`

`
`Page 118
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`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
`
`re t rieve depends upon t he error tolerance used
`
`during the key search ."
`
`So tha t error tolerance de te rmines the
`
`size of the lists , and that ' s how you get
`
`sublinearity .
`
`Q Well , if we take a look here, it says,
`
`" The computer may be programmed so that for a given
`
`query , the database returns a list of songs ranked
`
`by how well they match the query , not just one bes t
`
`13 match "; right?
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`A Yes .
`
`Q
`
`In other words , it identifies two
`
`alternative ways of producing results ; One is to
`
`identify the best match , and the other is t o
`
`identify a list of the best matches .
`
`A
`
`Q
`
`right?
`
`A
`
`Q
`
`A list of matches .
`
`With -- that are ranked . A ranked list ;
`
`Yes .
`
`Now ,
`
`t here ' s nothing in this sen t ence 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
`
`]
`
`•
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`we scale the size of the dataset ; right?
`
`A
`
`Yes , it does .
`
`It's obvious . You have the
`
`size of
`
`Q
`
`You ' r e saying you could infe r
`
`f r om it .
`
`You could do an analysis to show it ; is that ri ght ?
`
`A
`
`It ' s hardly a n analysis .
`
`It ' s simply
`
`Q Well ,
`
`i s it s tated he re ? Let ' s start with
`
`that .
`
`MR . ELACQUA :
`
`I ' d like him to answer the
`
`question fi r st . You int errupted him . He needs
`
`to-~
`
`MR . DOVEL :
`
`I would l ove him to answe r the
`
`question .
`
`MR . ELACQUA : Well , he needs to finish firs t.
`
`Let him fi nish ,
`
`then as k anothe r one .
`
`16
`
`BY MR . DOVEL :
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`Q
`
`I'll give you the ques t ion , and see if you
`
`c a n answer it .
`
`Does it say here ~~ doe s it have any words
`
`that desc r ibe the performance of the algo ri thm as
`
`database increases?
`
`A
`
`The comp lexity of that search is
`
`immediately infe rred 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 ~ 9SaO
`PaS'>' 119 ofJ84
`
`

`
`Page 120
`
`1
`
`2
`
`]
`
`4
`
`5
`
`string . As soon as the size of that list is
`
`sublinea r, 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
`
`6 mean , if the list -- or it could be 2 , any fixed
`
`7
`
`8
`
`9
`
`10
`
`11
`
`number . And then when you search , say , a list o f
`
`two elements, your comple xity is sublinear relative
`
`to the size of the databa se .
`
`Q Well , if the list -- are you saying
`
`that
`
`are you saying the size of the lis t that we
`
`12 want retu r ned to us?
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`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 t he l i st is, say , s i ze 2 ,
`
`just to give an e xample , the sea r ch has complex i ty
`
`19 which is O(l/n) times a full search on the database .
`
`20
`
`21
`
`22
`
`23
`
`"
`
`25
`
`So it is sublinear.
`
`Q
`
`Okay . This is not a search on the list .
`
`This is returning a lis t a s results ; is that right?
`
`There i s a search on the lists .
`
`Okay . We ' re not searching on the list
`
`A
`o
`
`here .
`
`T5G Reporting - Worldwide - 877 - 702-9580
`PaS'-' 120 ofJ84
`
`

`
`Page 121
`
`1
`
`2
`
`]
`
`Does t his say search the list?
`
`This is in Ghias . Let me find it .
`
`Just
`
`let ' s
`
`t ake a look at 60 t o 63 .
`
`A
`
`Q
`
`4 We ' ve got to take it one step at a time . We ' ll look
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`"
`
`25
`
`at all of Ghias be f ore we ' re done . We ' re focused
`
`now on Column 6, lines 60 to 63 .
`
`Do you see that? Yes or no?
`
`A
`
`Q
`
`A
`
`Yes .
`
`All right .
`
`I ' m so r ry . 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 we l l they match the query?
`
`A That is correct .
`
`Q
`
`The list is not a parameter ; it i s what is
`
`returned . We might have two songs that match , three
`
`or five ; right?
`
`A
`
`Q
`
`No , that ' s not true.
`
`All right . Let ' s do this .
`
`Let ' s assume that the list is not a
`
`parameter .
`
`A
`
`Q
`
`That ' s not true .
`
`We ' ll get to that.
`
`I want you to assume
`
`TSG Reporting - Worldwide - 877-702-9580
`PaS'-' 12 1 ofJ84
`
`

`
`Page 122
`
`1
`
`2
`
`that the list is not a parameter .
`
`We don ' t say , " Return to us five songs ."
`
`] What we say is , " Return t o us any songs that meet
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`our matching cr i teria , a nd rank them. "
`
`A
`
`Q
`
`What ' s the matching crite r ia?
`
`The matching criterion will be as set
`
`forth above .
`
`fo r example, it has no more than two
`
`errors .
`
`A
`
`No .
`
`It says e xactly two errors in the
`
`algorithm .
`
`Q Okay . Let '

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