`
`By: Charles R. Macedo (Reg. No. 32,781)
`Brian A. Comack (Reg. No. 45,343)
`Amster, Rothstein & Ebenstein LLP
`90 Park Avenue
`New York, NY 10016
`Telephone: (212) 336–8074
`cmacedo@arelaw.com
`N1-Google-IPR@arelaw.com
`
`Gregory Dovel (admitted pro hac vice)
`Dovel & Luner, LLP
`201 Santa Monica Blvd., Suite 600
`Santa Monica, CA 90401
`Telephone: (310) 656-7066
`greg@dovellaw.com
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`____________________
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`____________________
`
`GOOGLE INC.
`Petitioner
`
`v.
`
`NETWORK-1 TECHNOLOGIES
`Patent Owner
`_______________
`
`Cases IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Patents 8,640,179, 8,205,237, 8,010,988, and 8,656,441
`
`____________________
`
`DECLARATION OF DR. GEORGE KARYPIS
` NETWORK-1 EXHIBIT A2005
` Google Inc. v. Network-1 Technologies, Inc.
` IPR2015-00345
`Page 1 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Table of Contents
`
`2.
`
`I.
`
`Background to my opinions in this Declaration.............................................. 1
`A. Expertise................................................................................................ 1
`B. Assignment............................................................................................ 3
`C. Approach. .............................................................................................. 4
`D. Understanding of the law. ..................................................................... 5
`II. Summary of the IPR Patents and asserted art.................................................. 8
`A. The IPR Patents..................................................................................... 8
`1.
`‘237 patent (Ex. 1001 ‘237 IPR)................................................. 8
`2.
`‘988 patent (Ex. 1001 ‘988 IPR)...............................................10
`3.
`‘179 patent (Ex. 1001 ‘179 IPR)...............................................11
`4.
`‘441 patent (Ex. 1001 ‘441 IPR)...............................................13
`B. The asserted art....................................................................................16
`Overview of Ghias—Ex. 1010 (addressed in the ‘237, ‘988,
`1.
`‘179, and ‘441 IPRs).................................................................16
`Overview of Iwamura—Ex. 1012 (addressed in the ‘237 and
`‘988 IPRs). ................................................................................19
`3. Overview of Conwell—Ex. 1009 (addressed in the ‘179 and
`‘441 IPRs). ................................................................................22
`4. Overview of Philyaw—Ex. 1014 (addressed in the ‘179 and
`‘441 IPRs as a secondary reference).........................................24
`5. Overview of Chen—Ex. 1008 (addressed in the ‘237 IPR as a
`secondary reference). ................................................................25
`III. General Findings............................................................................................27
`IV. General concerns with the IPR Petitions and Dr. Moulin’s
`Declarations (Exs. 1004 in each IPR)............................................................30
`V. Claim Constructions. .....................................................................................38
`A. sub-linear (‘237 patent). ......................................................................40
`1.
`the words used in the construction: “size of the dataset” ........41
`2.
`‘237 specification......................................................................43
`3.
`Petitioner’s Declarant................................................................47
`B. non-exhaustive search (‘237, ‘988, ‘179, and ‘441 patents)...............54
`
`i
`
`Page 2 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`1. The Board’s preliminary construction of “non-exhaustive
`search” is consistent with the understanding of one of ordinary
`skill in the art: “a search that locates a match without a
`comparison of all possible matches.” .......................................54
`2. The Board properly rejected Petitioner’s assertion that a “non-
`exhaustive search” should be construed as “a search that locates
`a match without conducting a brute force comparison of all
`possible matches, and all data within all possible matches.” ...56
`C. neighbor search / identifying a neighbor / neighbor / near neighbor
`(‘237, ‘988, ‘179, and ‘441 patents)....................................................58
`approximate nearest neighbor search (‘237 patent). ...........................60
`“identifying a close match that is not necessarily the closest
`1.
`match” .......................................................................................61
`“sublinear” ................................................................................62
`2.
`VI. ‘237 patent. ....................................................................................................65
`A. ‘237 Ground 1: The instituted claims of the ‘237 patent are not
`anticipated by Iwamura. ......................................................................65
`1.
`sub-linear time search (claims elements 1(b) and 5(b.2)).........66
`2.
`approximate nearest neighbor search (claim elements 9(b) and
`13(b.2))......................................................................................85
`nonexhaustive search (claim element 25(b)). ...........................95
`identify a neighbor / near neighbor (claims elements 1(b), 5(b),
`and 25(b))................................................................................126
`sublinear approximate nearest neighbor search (claim element
`33(b)).......................................................................................132
`‘237 Ground 2: The instituted claims of the ‘237 patent are not
`anticipated by Ghias..........................................................................134
`1.
`sublinear time search (claim elements 1(b) and 5(b.2)). ........134
`2.
`approximate nearest neighbor search (claim elements 9(b) and
`13(b.2))....................................................................................155
`‘237 Ground 3: The instituted claims of the ‘237 patent are not
`obvious over Iwamura and Chen.......................................................166
`VII. ‘988 patent. ..................................................................................................168
`
`D.
`
`3.
`4.
`
`5.
`
`B.
`
`C.
`
`ii
`
`Page 3 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`A.
`
`B.
`
`C.
`
`‘998 Ground 1: The instituted claims of the ‘988 Patent are not
`anticipated by Ghias..........................................................................168
`1.
`non-exhaustive search (claim element 15(b)).........................169
`2.
`search identifying a neighbor (claim element 15(b))..............186
`3.
`determining an action based on the identification (claim
`element 15(c)). ........................................................................190
`‘988 Ground 2: The instituted claims of the ‘998 patent are not
`obvious over Ghias............................................................................193
`‘988 Ground 3: The instituted claims of the ‘998 patent are not
`anticipated by Iwamura. ....................................................................194
`1.
`non-exhaustive search (claim 15(b)).......................................194
`2.
`identifying a neighbor (claim 15(b)).......................................203
`VIII. ‘179 patent. ..................................................................................................204
`A. ‘179 Ground 1: The instituted claims of the ‘179 patent are not
`anticipated by Conwell......................................................................204
`1.
`neighbor search (claims 1, 13, 25)..........................................205
`2. non-exhaustive search (claims 1, 13, 25)................................231
`‘179 Ground 2: The instituted claims of the ‘179 Patent are not
`obvious in view of Ghias and Philyaw..............................................244
`1.
`non-exhaustive search (claims 1, 13, 25)................................245
`2. neighbor search (claims 1, 13, 25)..........................................251
`‘441 Patent...................................................................................................256
`‘441 Ground 1: The instituted claims of the ‘441 Patent are not
`A.
`anticipated by Conwell......................................................................256
`1.
`neighbor search (claims 1, 13, 25)..........................................256
`2.
`non-exhaustive search (claims 1, 13, 25)................................259
`‘441 Ground 2: The instituted claims of the ‘441 Patent are not
`obvious over Ghias and Philyaw.......................................................260
`1. non-exhaustive search (claims 1, 13, 25)................................261
`2.
`neighbor search (claims 1, 13, 25)..........................................264
`
`IX.
`
`B.
`
`B.
`
`iii
`
`Page 4 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`I, George Karypis, declare:
`
`I am making this Declaration at the request of Patent Owner Network-1
`
`Technologies, Inc. in the following Inter Partes Reviews of U.S. Patent Nos.
`
`8,205,237 (‘237 patent), 8,010,988 (‘988 patent), 8,640,179 (‘179 patent), and
`
`8,656,441 (‘441 patent) (collectively the “IPR Patents”):
`
`(cid:120) IPR2015-00345 (‘237 patent),
`
`(cid:120) IPR2015-00347 (‘988 patent),
`
`(cid:120) IPR2015-00343 (‘179 patent), and
`
`(cid:120) IPR2015-00348 (‘441 patent),
`
`(collectively the “IPRs”), all initiated by petitioner Google Inc. (“Petitioner”).
`
`I.
`
`Background to my opinions in this Declaration.
`
`A. Expertise.
`
`1.
`
`I am a Professor in the Department of Computer Science and
`
`Engineering at the University of Minnesota. I hold a Ph.D. in Computer Science
`
`from the University of Minnesota, granted in 1996. I began my post-graduate
`
`school career as a Research Associate in my current department. I became an
`
`Assistant Professor in 1999, an Associate Professor in 2004, and a Professor in
`
`2009. I teach courses in Algorithms and Data Structures, Parallel Programming,
`
`and Data Mining, among other subjects.
`
`1
`Page 5 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`2.
`
`I am a member of the Editorial Board of a number of academic
`
`journals, and I have chaired a number of academic conferences.1 I am a co-author
`
`of the books Introduction to Parallel Computing, and Introduction to Parallel
`
`Computing: Design and Analysis of Algorithms. I am an author of more than 80
`
`published journal papers, and more than 115 published conference papers.2
`
`1
`
`Representative academic conferences include:
`
`(cid:120) Program Committee co-Chair of the ACM Recommender Systems
`
`Conference (RecSys’13), Hong Kong, China (2013);
`
`(cid:120) Program Committee co-Chair of the 13th International Conference on Data
`
`Mining (ICDM), Dallas, Texas (December 2013); and
`
`(cid:120) Program Committee Co-Chair of the International Conference on Data
`
`Science and Advanced Analytics (DSAA 2014), Shanghai, China, (November
`
`2014).
`
`2
`
`Representative papers include:
`
`(cid:120) “L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-
`
`Norm Pruning” David C. Anastasiu and George Karypis, 24th ACM
`
`International Conference on Information and Knowledge Management
`
`(CIKM), Melbourne, Australia (2015).
`
`2
`Page 6 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`3.
`
`I have also developed a number of software systems for a variety of
`
`functions, including software for analyzing high-dimensional data sets. A copy of
`
`my curriculum vitae is attached as Exhibit A to this Declaration. It contains a
`
`more complete listing of my professional activities and background.
`
`B. Assignment.
`
`4.
`
`I have been retained by Patent Owner Network-1 Technologies, Inc.
`
`as a technical consultant. I am being compensated for my time at my standard
`
`consulting rate of $350 per hour. I am not receiving any compensation that
`
`depends on the outcome of the IPRs.
`
`5.
`
`This declaration addresses the validity of:
`
`(cid:120) “L2AP: Fast Cosine Similarity Search with Prefix L-2 Norm Bounds” David
`
`Anastasiu and George Karypis, 30th IEEE International Conference on Data
`
`Engineering (ICDE), pp. 784—795 (2014).
`
`(cid:120) “Comparison of Descriptor Spaces for Chemical Compound Retrieval and
`
`Classification” Nikil Wale and George Karypis, IEEE International
`
`Conference on Data Mining (ICDM), pp. 678—689 (2006).
`
`(cid:120) “Empirical and Theoretical Comparisons of Selected Criterion Functions for
`
`Document Clustering” Ying Zhao and George Karypis, Machine Learning, 55,
`
`pp. 311-331 (2004).
`
`3
`Page 7 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`(cid:120) claims 1, 3–5, 7–9, 11–13, 15, 16, 21–27, 29, 30, 33, 34, 35, 37, and 38 of
`
`the ‘237 patent;
`
`(cid:120) claims 15–17, 21–28, 31–33, 51, and 52 of the ‘998 patent;
`
`(cid:120) claims 1-3, 6, 8–14, 18, 19, 21–27, 29–31, and 34–37 of the ‘179 patent; and
`
`(cid:120) claims 1–3, 6, 8–14, 18, 19, 21–27, 29, and 30 of the ‘441 patent.
`
`C. Approach.
`
`6.
`
`To develop my opinions, I have read:
`
`(cid:120) the four IPR Patents (the ‘237, ‘988, ‘179, and ‘441 patents);
`
`(cid:120) the four Petitions for Inter Partes Reviews;
`
`(cid:120) the exhibits accompanying the Petitions, including the four Declarations of
`
`Dr. Pierre Moulin (Exs. 1004 in each IPR);
`
`(cid:120) the four Decisions Instituting the IPRs; and
`
`(cid:120) the testimony of Dr. Pierre Moulin, dated August 19-20, 2015 (Ex. 2006).3
`
`3
`
`In this Declaration, I identify the specific Petition, Declaration, and Decision
`
`that I am citing by including the corresponding patent abbreviation in a
`
`parenthetical. For example, I refer to the Petition addressing the ‘237 patent as Pet.
`
`(‘237) at X; and the Moulin Declaration addressing the ‘179 patent as Moulin
`
`Decl. (‘179) ¶X. Because there is only one Dr. Moulin Deposition transcript for all
`
`4
`Page 8 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`7.
`
`In addition, I relied on my personal knowledge and experience with
`
`both research and development in the technology underlying the IPR Patents and
`
`the art asserted against the IPR Patents.
`
`D. Understanding of the law.
`
`8. My understanding regarding the law as applicable to this Declaration
`
`is based on my discussions with counsel. I have included in the text of my
`
`Declaration quotations from or references to certain legal cases or statutes that
`
`were provided to me by counsel to provide me with an understanding of the
`
`relevant law.
`
`E.
`9.
`
`Person of ordinary skill in the art.
`Through my education, experience and training, in academia and
`
`industry, and my analysis of the IPR Patents, I am familiar with the knowledge of a
`
`person of ordinary skill in the field of the IPR Patents at the time of invention in
`
`2000.
`
`10. For the purposes of this Declaration, I am of the opinion that a person
`
`of ordinary skill in the art with respect to the IPR Patents is a person with a
`
`Bachelor’s degree in computer science, mathematics, or a similar discipline and
`
`two to three years of relevant experience, or a graduate degree in the same area.
`
`four IPRs (Ex. 2006), I simply refer to Dr. Moulin’s deposition testimony as
`
`Moulin Depo. Z.
`
`5
`Page 9 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`In determining what would be the level of ordinary skill in the field as of the 2000
`
`time frame, I considered the following:
`
`(a)
`
`the educational level of the inventor, Ingemar J. Cox (it is my
`
`understanding that Dr. Cox has a bachelor’s degree in electronics and
`
`computer science from University College London (1980) and a Ph.D.
`
`from Oxford (1983));
`
`(b)
`
`the type of problems encountered in the art—i.e., how to identify a digital
`
`work without modifying the work (see e.g., ‘237, 1:30-36);
`
`(c)
`
`the prior art solutions to those problems (see e.g., ‘237, 1:37-4:4, and the
`
`prior art asserted by the Petitioner in the IPRs addressing related problems
`
`involving searching, matching, and identifying melodies, audio files, and
`
`other digital files within databases—Conwell, Ghias, Iwamura, Chen, and
`
`Philyaw);
`
` (d) the rapidity with which innovations are made (based on my observations
`
`over the past 20 plus years, major innovations in content identification
`
`occur about every 5 to 10 years);
`
` (e) the sophistication of the technology (developing content identification
`
`solutions is a moderately sophisticated technology); and
`
`6
`Page 10 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
` (f) the educational level of workers in the field (workers in the field generally
`
`had have at least a bachelor’s degree in computer science, mathematics or
`
`a similar discipline and at least two to three years of relevant experience).
`
`
`
`11. Based on these factors, it is my conclusion that a person of ordinary
`
`skill in the art at the time would have been a person with a Bachelor’s degree in
`
`computer science, mathematics, or a similar discipline and two to three years of
`
`relevant experience, or a graduate degree in the same or related area.
`
`12.
`
`I note that Dr. Moulin suggests that the person of ordinary skill in the
`
`art “would have been highly skilled, and typically would have possessed at least an
`
`M.S. in computer science, electrical engineering, or mathematics; knowledge of
`
`video and audio processing techniques; and 1-2 years of experience in audio,
`
`video, or image processing.” See e.g., Moulin Decl. (‘237) ¶7; Pet. (‘237) at 4. Dr.
`
`Moulin’s opinion as to the person of ordinary skill in the art is similar to mine with
`
`respect to the degrees and years of experience, but I note that: (1) Dr. Moulin does
`
`not provide any rational underpinnings for his opinion; and (2) the phrase “highly
`
`skilled” used by Dr. Moulin in his description is a relative term and Dr. Moulin
`
`does not provide the context for this phrase.
`
`7
`Page 11 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`II. Summary of the IPR Patents and asserted art.
`
`13.
`
`In this Declaration:
`
`(cid:120) I use the term “work” to mean the item (e.g., a digital audio or image file) to
`
`be identified using the search (see e.g., ‘237, 6:51-56; ‘988, 7:17-20; ‘179,
`
`6:18-21; ‘441, 6:49-52);
`
`(cid:120) I use the term “record” to mean one of the units in the reference database
`
`that the extracted features of the work may be compared to (see e.g., ‘237,
`
`6:16-20; ‘988, 6:46-50; ‘179, 6:21-24; ‘441, 6:15-18); and
`
`(cid:120) I use the term “database,” “data set,” or “library” to mean the collection of
`
`all records to be searched (see e.g., ‘237, 6:23-30; ‘988, 6:50-60; ‘179, 6:30-
`
`36; ‘441, 6:24-30).
`
`A. The IPR Patents.
`
`14.
`
`Each IPR Patent (the ‘237, ‘179, ‘988, and ‘441 patents) involves a
`
`search that compares features from a given work to records in a reference database
`
`of potential matches to identify an action to be taken.
`
`1.
`
`‘237 patent (Ex. 1001 ‘237 IPR).
`
`15. The independent claims of the ‘237 patent include the following
`
`elements:
`
`[1] receiving or obtaining features extracted from a work;
`
`8
`Page 12 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`[2] identifying the work using the extracted features to perform a search of
`
`the database, where the search is:
`
`(cid:120) a sub-linear time search to identify a neighbor (claims 1 and 5);
`
`(cid:120) an approximate nearest neighbor search (claims 9 and 13);
`
`(cid:120) a non-exhaustive search … to identify a near neighbor (claim 25); or
`
`(cid:120) a sublinear approximate nearest neighbor search (claim 33); and
`
`[3] either (i) transmitting information about the identified work to the client
`
`device, or (ii) determining an action based on the identity of the work.
`
`16.
`
`The invention claimed in the ‘237 patent includes two key features:
`
`17. Feature 1: Although the language varies among the claims, each
`
`claim requires that the “identifying” be performed based on a search that has two
`
`properties:
`
`(1) a sub-linear or non-exhaustive property (reflected in the underlined
`
`language):
`
`(cid:120) sub-linear time search … to identify a neighbor (claims 1 and 5);
`
`(cid:120) approximate nearest neighbor search (claims 9 and 13);
`
`(cid:120) non-exhaustive search … to identify a near neighbor (claim 25); and
`
`(cid:120) sublinear approximate nearest neighbor search (claim 33).
`
`(2) a neighbor property (reflected in the underlined language):
`
`9
`Page 13 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`(cid:120) identify a neighbor (claims 1 and 5);
`
`(cid:120) approximate nearest neighbor search (claims 9 and 13);
`
`(cid:120) non-exhaustive search … to identify a near neighbor (claim 25); and
`
`(cid:120) sublinear approximate nearest neighbor search (claim 33).
`
`18. Feature 2: The system must either determine an “action” based on the
`
`identification (claims 25 and 33); or transmit information about the identified
`
`media work to a “client device” (claims 1, 5, 9, and 13). It is not sufficient to
`
`simply identify a match. Rather, an action must also be identified or information
`
`about the identified work must be transmitted to the client device.
`
`2.
`
`‘988 patent (Ex. 1001 ‘988 IPR).
`
`19. The independent claims of the ‘988 patent include the following
`
`elements:
`
`[1] extracting features from a work;
`
`[2] identifying the work based on the extracted features by performing “a
`
`non-exhaustive search identifying a neighbor;”
`
`[3] determining an action based on the identity of the work; and
`
`[4] performing the action.
`
`20.
`
`The invention claimed in the ‘988 patent includes two relevant
`
`distinguishing features:
`
`10
`Page 14 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`(1) the “identifying” must be performed using a “non-exhaustive search
`
`identifying a neighbor;” and
`
`(2) the system must “determin[e] an action” and “perform[] the action”
`
`based on the identity of the work. It is not sufficient to identify a match.
`
`Rather, “an action” associated with the match must be “determin[ed]”
`
`and “perform[ed].” ‘988, claim 15.
`
`21.
`
`I note that the Board did not institute trial for independent claim 1 of
`
`the ‘988 patent and any claims dependent on claim 1. Accordingly, I do not
`
`address these claims in this Declaration.
`
`3.
`
`‘179 patent (Ex. 1001 ‘179 IPR).
`
`22. The independent claims of the ‘179 patent (claims 1, 13, and 25)
`
`include the following five elements for identifying a work and performing a
`
`corresponding action:
`
`[1] a database comprising: (a) electronic representations of works; and (b)
`
`electronic data related to an action corresponding to works;
`
`[2] obtaining extracted features of an unknown work;
`
`[3] identifying the unknown work by comparing the extracted features and
`
`electronic representations using a “non-exhaustive neighbor search;”
`
`11
`Page 15 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`[4] determining an appropriate action based on the electronic data related to
`
`an action; and
`
`[5] associating the determined action with the identified work.
`
`‘179, claims 1, 13, and 25.
`
`23. The claimed steps are illustrated in Figure 1:
`
`Figure 1 illustrates (“for work @t2”):
`
`(cid:120) “feature (vector) extraction operation(s)” (140) that extract features from the
`
`work (‘179, 6:45-47);
`
`12
`Page 16 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`(cid:120) “feature (vector) lookup operation(s)” (150) that identify the work by
`
`searching for a matching feature vector (‘179, 6:50-52);
`
`(cid:120) “work-associated information lookup operation(s)” (160) that retrieve(s)
`
`associated information, such as an action (‘179, 6:55-58); and
`
`(cid:120) “action initiation operation(s)” (170) that perform(s) some action based on
`
`the associated information (‘179, 6:58-60).
`
`24.
`
`The invention claimed in the ‘179 patent includes two relevant
`
`distinguishing features:
`
`(1) the “identifying” must be performed by comparing the extracted features
`
`to the electronic representations using a “non-exhaustive neighbor
`
`search;” and
`
`(2) the system must determine or associate an “action” based on the
`
`identified work. It is not sufficient to simply identify a match. Rather,
`
`“an action” associated with the match must be “determined” or
`
`“associated.”
`
`‘179, claims 1, 13, and 25.
`
`4.
`
`‘441 patent (Ex. 1001 ‘441 IPR).
`
`25. The independent claims of the ‘441 patent (claims 1, 13, and 25)
`
`include the following five elements for identifying a work and performing a
`
`13
`Page 17 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`corresponding action:
`
`[1] a database with (a) first data related to records, and (b) second data
`
`related to action information corresponding to the records;
`
`[2] extracting features from a work;
`
`[3] identifying the work by comparing the extracted features and the data
`
`related to the records using “a non-exhaustive neighbor search;”
`
`[4] determining an action based on the identity of the electronic work; and
`
`[5] performing the action.
`
`‘441, claims 1, 13, and 25.
`
`26.
`
`The claimed steps are illustrated in Figure 1:
`
`14
`Page 18 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Figure 1 illustrates (“for work @t2”):
`
`(cid:120) “feature (vector) extraction operation(s)” (140) that extract(s) features from
`
`the work (‘441, 6:39-41);
`
`(cid:120) “feature (vector) lookup operation(s)” (150) that identify the work by
`
`searching for a matching feature vector (‘441, 6:44-48);
`
`(cid:120) “work-associated information lookup operation(s)” (160) that retrieve(s)
`
`associated information, such as an action (‘441, 6:49-51); and
`
`(cid:120) “action initiation operation(s)” (170) that perform(s) some action based on
`
`the associated information (‘441, 6:52-54).
`
`15
`Page 19 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`27.
`
`The invention claimed in the ‘441 patent includes two relevant
`
`distinguishing features:
`
`(1) the “identifying” must be performed by comparing the extracted features
`
`to the electronic representations using a “non-exhaustive neighbor
`
`search;” and
`
`(2) the system must determine or associate an “action” based on the
`
`identified work. It is not sufficient to simply identify a match. Rather,
`
`“an action” associated with the match must be “determined” or
`
`“associated.”
`
`‘441, claims 1, 13, and 25.
`
`B. The asserted art.
`
`28.
`
`The four IPRs address three primary references and two secondary
`
`references. I address each reference in turn, starting with the primary references
`
`and then turning to the secondary references.
`
`1.
`
`Overview of Ghias—Ex. 1010 (addressed in the ‘237, ‘988,
`‘179, and ‘441 IPRs).
`
`29. Ghias (Patent No. 5,874,686) discloses “an apparatus [for] searching
`
`melodies.” Ghias, Abstract. As illustrated in Figure 1 of Ghias, a “tune 12 is
`
`hummed by a person 18 into a microphone 20.” Ghias, 2:41-42.
`
`16
`Page 20 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`The data from the microphone is fed into “a pitch tracking module 22 in computer
`
`16” which extracts “a contour representation” of the melody (23). Ghias, 2:41-50.
`
`The computer uses a “query engine 24” which “searches the melody database 14.”
`
`Ghias, 2:50-52. The disclosed search can produce a ranked list of matching
`
`melodies—“ranked by how well they matched the query” (Ghias, 6:60-63) as
`
`illustrated at 26.
`
`30. As I explain below in detail, all searches disclosed in Ghias are linear
`
`(not sub-linear) with respect to the size of the data set being searched. In
`
`addressing “the problem of approximate string matching,” Ghias identifies the
`
`running times of several algorithms:
`
`17
`Page 21 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`Ghias, 6:23-28. In each identified instance, the running time of the search is not
`
`sub-linear with respect to the data set. As clarified in this passage from Ghias (and
`
`as I address in detail below):
`
`(cid:120) “m is the number of pitch differences in the query” corresponding to the
`
`length of the query (highlighted in green in the passage above); and
`
`(cid:120) “n is the size of the string (song)” corresponding to the size of a record being
`
`searched (highlighted in orange in the passage above).
`
`31.
`
`The disclosed searches may be sub-linear with respect to the length of
`
`the query being searched “m … the number of pitch differences in the query.”
`
`Specifically, the referenced search with a running time of O(nlog(m)) is sublinear
`
`with respect to “m” because it is a function of log(m)). The disclosed searches,
`
`however, are never sub-linear with respect to “n…the size of the string (song)” or
`
`the size of the data set (N) (i.e., the number of songs to be compared). Rather, the
`
`search time will grow linearly with each additional song to be searched and the
`
`length of the song.
`
`32. Also as I describe in detail below, the searches disclosed in Ghias are
`
`exhaustive rather than “nonexhaustive.” The “query engine 24” compares the
`
`18
`Page 22 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`work (user input 23) to “all the songs” in the melody database 14 (the library).
`
`Ghias, 5:66-6:2. After searching all possible matches, the system “output[s] a
`
`ranked list of approximately matching melodies.” Ghias, 2:50-53.
`
`33.
`
`Finally, as I describe in detail below, the searches disclosed in Ghias
`
`are not “neighbor” searches because the searches always necessarily identify the
`
`exact or closest match—they are guaranteed to identify an exact match or the
`
`closest match. Ghias does not identify any search in which an exact or the closest
`
`match is not guaranteed to be identified.
`
`2.
`
`Overview of Iwamura—Ex. 1012 (addressed in the ‘237 and
`‘988 IPRs).
`
`34.
`
`Iwamura (Patent No. 6,188,010) discloses a “method to enable one to
`
`search for a song title when only its melody is known.” Iwamura, Abstract. “A
`
`remote music database with melody information is searched for the melody entered
`
`by the user, using for example, a peak or differential matching algorithm.”
`
`Iwamura, Abstract. Figure 1 illustrates “an example of a search interface”
`
`(Iwamura, 2:45-46):
`
`19
`Page 23 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`35.
`
`Iwamura discloses a searching algorithm that is designed to be more
`
`efficient than alternatives by matching up peak notes from the work to be identified
`
`with the peak notes of the records in the database when comparing the notes from
`
`the work to be identified with the notes in the records. “Peak notes are also
`
`detected and marked when the data base is built.” Iwamura, 6:59-60. “A fast
`
`search is performed by using a peak or differential matching algorithm.” Iwamura,
`
`12:1-2.
`
`36. As I explain in detail below, the search disclosed in Iwamura is
`
`exhaustive rather than the claimed “non-exhaustive,” “sublinear,” or “approximate
`
`nearest neighbor” search. While the individual comparisons of a work and a
`
`record in the library can be more efficient using the “peak note” approach
`
`20
`Page 24 of 292
`
`
`
`IPR2015-00343, IPR2015-00345, IPR2015-00347, and IPR2015-00348
`Declaration of George Karypis
`
`disclosed in Iwamura (search speed can be increased), in doin