`
`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 '