Northeastern University et al v. Google, Inc.,

Filing 71

CLAIM CONSTRUCTION BRIEF filed by Northeastern University, Jarg Corporation. (Attachments: # 1 Exhibit A, # 2 Exhibit B, # 3 Exhibit C, # 4 Exhibit D, # 5 Exhibit E, # 6 Exhibit F, # 7 Exhibit G, # 8 Exhibit H)(Stout, Stephen)

Northeastern University et al v. Google, Inc.,

Doc. 71 Att. 2

EXHIBIT B

Dockets.Justia.com

Case 2:07-cv-00486-CE

Document 62

Filed 08/28/2009

Page 1 of 5

IN THE UNITED STATES DISTRICT COURT EASTERN DISTRICT OF TEXAS MARSHALL DIVISION NORTHEASTERN UNIVERSITY and JARG CORP., Plaintiffs, v. GOOGLE INC., Defendant. Civil Action No. 2:07-CV-486 (TJW) Jury Trial Demanded

JOINT CLAIM CONSTRUCTION AND PREHEARING STATEMENT Pursuant to Eastern District of Texas Patent Rule 4-3, Plaintiffs Northeastern University and Jarg Corporation and Defendant Google Inc. hereby provide their Joint Claim Construction and Prehearing Statement. I. AGREED CLAIM CONSTRUCTIONS The parties have met and conferred regarding their Rule 4-2 exchange and have agreed to the meaning of certain claim terms, phrases or clauses. These terms, and their agreed meanings, are set forth in Exhibit A (attached). II. DISPUTED CLAIM CONSTRUCTIONS With respect to those terms, phrases, or clauses on which the parties could not reach agreement, the parties have set forth their respective proposed constructions, including the intrinsic and extrinsic evidence relied upon in support thereof, in Exhibits B and C (attached). The parties reserve the right to rely on and rebut any evidence cited by any party. III. ANTICIPATED LENGTH OF CLAIM CONSTRUCTION HEARING The parties believe that it would be appropriate for the Court to allocate two hours for the claim construction hearing, with one hour allocated to each side (including reserved rebuttal time).
JOINT CLAIM CONSTRUCTION & PREHEARING STATEMENT Case No. 2:07-CV-486 (TJW)

Case 2:07-cv-00486-CE

Document 62

Filed 08/28/2009

Page 2 of 5

IV.

CLAIM CONSTRUCTION LIVE WITNESSES The parties do not anticipate calling live witnesses at the claim construction hearing.

V.

CLAIM CONSTRUCTION PREHEARING CONFERENCE The parties do not believe a claim construction prehearing conference is needed.

2
JOINT CLAIM CONSTRUCTION & PREHEARING STATEMENT Case No. 2:07-CV-486 (TJW)

Case 2:07-cv-00486-CE

Document 62

Filed 08/28/2009

Page 3 of 5

Dated: August 28, 2009

Respectfully submitted, VINSON & ELKINS L.L.P.

By:

/s/ Michael A. Valek William B. Dawson (TX Bar No. 05603600) VINSON & ELKINS L.L.P. 2001 Ross Avenue, Suite 3700 Dallas, Texas 75201-2975 Telephone: [phone] Facsimile: [phone] E-mail: [e-mail] David B. Weaver (TX Bar No. 00798576) Christopher V. Ryan (TX Bar No. 24037412) Michael Valek (TX Bar No. 24044028) R. Floyd Walker (TX Bar No. 24044751) Stephen C. Stout (TX Bar No. 24060672) Meredith J. Fitzpatrick (TX Bar No. 24059753) VINSON & ELKINS L.L.P. 2801 Via Fortuna, Suite 100 Austin, Texas 78746 Telephone: [phone] Facsimile: [phone] E-mail: [e-mail] [e-mail] [e-mail] [e-mail] [e-mail] [e-mail] Otis W. Carroll, Jr. (TX Bar No. 03895700) Collin Maloney (TX Bar No. 00794219) IRELAND CARROLL & KELLEY 6101 S. Broadway, Suite 500 Tyler, TX 75703 Telephone: [phone] Facsimile: [phone]

Attorneys for Plaintiffs NORTHEASTERN UNIVERSITY AND JARG CORPORATION

3
JOINT CLAIM CONSTRUCTION & PREHEARING STATEMENT Case No. 2:07-CV-486 (TJW)

Case 2:07-cv-00486-CE

Document 62

Filed 08/28/2009

Page 4 of 5

Dated: August 28, 2009

FISH & RICHARDSON P.C.

By: /s/ Shelley K. Mack Michael E. Jones (SBN 10929400) [e-mail] POTTER MINTON A Professional Corporation 110 N. College, Suite 500 Tyler, TX 75702 Telephone: [phone] Facsimile: [phone] Ruffin B. Cordell (SBN 04820550) [e-mail] FISH & RICHARDSON P.C. 1425 K Street, N.W., 11th Floor Washington, DC 20005-3500 Telephone: [phone] Facsimile: [phone] Jason W. Wolff (CA SBN 215819) [e-mail] FISH & RICHARDSON P.C. 12390 El Camino Real San Diego, CA 92130 Telephone: [phone] Facsimile: [phone] Howard G. Pollack (Admitted Pro Hac Vice) [e-mail] Shelley K. Mack (Admitted Pro Hac Vice) [e-mail] Jerry T. Yen (CA SBN 247988) [e-mail] FISH & RICHARDSON P.C. 500 Arguello Street, Suite 500 Redwood City, CA 94063 Telephone: [phone] Facsimile: [phone] Attorneys for Defendant GOOGLE INC.

4
JOINT CLAIM CONSTRUCTION & PREHEARING STATEMENT Case No. 2:07-CV-486 (TJW)

Case 2:07-cv-00486-CE

Document 62

Filed 08/28/2009

Page 5 of 5

CERTIFICATE OF SERVICE The undersigned certifies that the foregoing document was filed electronically in compliance with Local Rule CV-5(a). As such, this document was served on all counsel who are deemed to have consented to electronic service. Local Rule CV-5(a)(3)(A). Pursuant to Fed. R. Civ. P. 5(d) and Local Rule CV-5(d) and (e), all other counsel of record not deemed to have consented to electronic service were served with a true and correct copy of the foregoing by email and/or fax, on this the 18th day of December, 2008.

/s/ Michael A. Valek Michael A. Valek

5
JOINT CLAIM CONSTRUCTION & PREHEARING STATEMENT Case No. 2:07-CV-486 (TJW)

Case 2:07-cv-00486-CE

Document 62-2

Filed 08/28/2009

Page 1 of 2

EXHIBIT A PARTIES' AGREED CONSTRUCTIONS

Case 2:07-cv-00486-CE

Document 62-2

Filed 08/28/2009

Page 2 of 2

No. 1.

Term fuzzy queries

Claim(s) claim 1

Agreed Construction imprecise or inexact requests for information from a database, the result of which does not necessarily contain each term in the query

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 1 of 13

EXHIBIT B PLAINTIFFS' PROPOSED CONSTRUCTIONS FOR DISPUTED CLAIM TERMS AND EVIDENTIARY SUPPORT

US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 2 of 13

No. Term 1. non-relational, distributed database system

Claim(s) claims 1, 8, 13

Plaintiffs' Proposed Construction & Evidentiary Support Construction: a database not using a relational model that is distributed among a plurality of interconnected computer nodes Intrinsic Support: Abstract; Fig. 1; 1:5-6; 1:10-62; 1:65-2:2; 2:3-18; 2:56-3:16; 3:17-3:36; 3:4650; 4:15-21; 4:22-55; 7:50-65; 10:4-17; 10:18-20 June 7, 1996 Amendment p. 7-19; December 4, 1996 Amendment p. 7-9; May 14, 1997 Amendment p. 3-4;

2.

a plurality of home nodes and a plurality of query nodes connected by a network a plurality of home nodes; and a plurality of query nodes; said plurality of home nodes and said plurality of query nodes connected by a network

claim 1

Construction: The claim language has its plain and ordinary meaning; no further construction necessary.

claims 8, 13

Intrinsic Support: Fig. 1-2; Abstract; 1:65-2:18; 2:66-3:36; 3:51-59; 4:8-14; 4:22-35; 7:23-49; 10:4-20. June 7, 1996 Amendment p. 16; May 14, 1997 Amendment p. 2-3;

2
US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 3 of 13

No. Term 3. randomly selecting

Claim(s) claim 1

Plaintiffs' Proposed Construction & Evidentiary Support Construction: selecting without an apparent pattern Intrinsic Support:

Fig. 1; June 7, 1996 Amendment p. 13, 16. "High-Performance, Distributed Information Retrieval," Kenneth Baclawski and J. Elliott Smith. p. 3. "A distributed approach to high-performance information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 4 "A unified approach to high-performance, vector-based information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 4, 9, 13. "KEYNET: An architecture and protocol for high-performance semantically rich information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 14, 19-20. "An abstract model for semantically rich information retrieval," Kenneth Baclawski and Dan A. Simovici, p. 4.

Extrinsic Support: 3
US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 4 of 13

No. Term

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support "random adj 1 : lacking or seeming to lack a regular plan, purpose or pattern" WEBSTER'S THIRD NEW INTERNATIONAL DICTIONARY OF THE ENGLISH LANGUAGE 1880 (Phillip Babcock Gove ed., 1993).

4.

query fragment

claims 1, 8, 13

Construction: a sub-part or piece of a query Intrinsic Support: Figs. 4, 7, 8; Abstract; 2:4-17; 3:25-50; 4:60-66; 7:23-49; 8:66-9:5; 9:30-53; 9:61-10:3. May 4, 1997 Amendment at p. 2-3. Dec. 4, 1996 Amendment at p. 7. June 7, 1996 Amendment p. 7-17. "High-Performance, Distributed Information Retrieval," Kenneth Baclawski and J. Elliott Smith. p. 2. "A distributed approach to high-performance information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 8-9

4
US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 5 of 13

No. Term

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support "A unified approach to high-performance, vector-based information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 4, 8-9, 14. "KEYNET: An architecture and protocol for high-performance semantically rich information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 14, 19-21. "An abstract model for semantically rich information retrieval," Kenneth Baclawski and Dan A. Simovici, p. 17-26. "KEYNET: Fast indexing for semantically rich information retrieval," Kenneth Bac1awski and J. Elliott Smith, p. 10-15. "High-Performance Indexing and Retrieval for Object-Oriented Databases," Kenneth Baclawski, p. 7, 10, 19 Extrinsic Support: "fragment n 1 : a part broken off : a small detached portion : an imperfect or incomplete part" WEBSTER'S THIRD NEW INTERNATIONAL DICTIONARY OF THE ENGLISH LANGUAGE 901 (Phillip Babcock Gove ed., 1993) Construction: a computer technique whereby one or more functions are used to transform values into corresponding values Intrinsic Support:

5.

hashing / hashes

claims 1, 8, 13

5
US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 6 of 13

No. Term

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support Figs. 4, 7a, 8; Abstract; 2:3-11; 3:25-50; 3:60-62; 5:2-5; 6:65-67; 7:23-38. June 7, 1996 Amendment, p. 7, 14-16. Dec. 4, 1996 Amendment, p. 7. May 14, 1997 Amendment, p. 4. "High-Performance, Distributed Information Retrieval," Kenneth Baclawski and J. Elliott Smith. p. 3. "A distributed approach to high-performance information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 4-5 "A unified approach to high-performance, vector-based information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 10, 17 "KEYNET: An architecture and protocol for high-performance semantically rich information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 6., 1415, 21 "An abstract model for semantically rich information retrieval," Kenneth Baclawski and Dan A. Simovici, p. 5. "KEYNET: Fast indexing for semantically rich information retrieval," Kenneth Bac1awski and J. Elliott Smith, p. 3, 8-15.

6
US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 7 of 13

No. Term

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support Extrinsic Support: "Hashing (or hash coding) is a word coined by computer programmers to describe a general class of operations done to transform one or more fields (usually a key) into a different (usually more compact) arrangement. Probably, "hashing" was first coined because it seemed that "hash" was being made out of integral pieces of data. The rationale for hashing is developed more fully in the article on table lookup, dealing with key transformation to convert naturally occurring, diverse, ill-structured, scattered key fields into compact, easily manipulated fields--usually some numeric, computer oriented field such as a word or double word, or a computer memory address to facilitate subsequent references. The transformation from the natural field to the hash address is only a one-way process, however; the natural field cannot be decoded or reconstructed from the hash. Also, the hashed field may not represent only one unique natural field; many natural fields could hash into the same value." ENCYCLOPEDIA OF COMPUTER SCIENCE AND ENGINEERING 681 (Anthony Ralston & Edwin D. Reilly, Jr. eds.,1983). "Hashing (1) (* Processing) A technique for converting the values within fields into more `compact' representations of the same values. Usually, the values being converted are keys. (2) (* Addressing) An addressing technique used to store and retrieve data in a file. Hashing uses keys in an index to determine the location of the data in the file." ROBERT A EDMUNDS, THE PRENTICE-HALL STANDARD GLOSSARY OF COMPUTER TERMINOLOGY, 191-192 (1985). "Hashing: Hashing refers to a storage mechanism where data items are stored at locations that are determined by a mathematical function of the data. For example, suppose you need to store a list of 100 numbers in memory locations whose addresses run from 1 to 100. One example of a hashing 7

US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 8 of 13

No. Term

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support function is to calculate the remainder when the number is divided by 100 and then store it at that location. For example, the number 538 would be stored at memory location 38. The use of hashing makes it possible to store and retrieve the data items quickly since it is not necessary to search through the list in order to find the item. However, there is one complication: A hashing function will sometimes assign more than one data item to the same address. For example, using the rule given above, the number 638 would also be stored in location 38. To avoid that problem, a hashing system needs to be able to resolve collisions by storing the new data item in a separate place." DOUGLAS DOWNING & MICHAEL COVINGTON, BARRON'S DICTIONARY OF COMPUTER TERMS 158 (3d ed. 1992). "Hashing: (1) Key-to-address transformation in which the keys determine the location of the data. (2) The process of applying a formula to a record key to yield a number that represents a disk address." DONALD D. SPENCER, COMPUTER DICTIONARY (3d ed. 1992). "Hashing: In database management, an indexing technique in which the value of a key (record identifier) is numerically manipulated to directly calculate either the location of its associated record in a file or the starting point for a search for the associated record." MICROSOFT COMPUTER DICTIONARY 193 (2d ed. 1994).

6.

a first portion and a second portion

claims 1, 8, 13

Construction: The claim language has its plain and ordinary meaning; no further construction necessary. Intrinsic Support: 8

US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 9 of 13

No. Term

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support 3:36-50; 4:64-5:2; 6:59-65; 7:23-38; 7:50-55.

7.

claim 1 transmitting, by said selected home node, each said hashed query fragment of said plurality of query fragments to a respective one of said plurality of query nodes indicated by said first portion of each said hashed query fragment transmits each said hashed query fragment to a claim 8 respective one of said plurality of query nodes indicated by said first potion of said hashed query fragment transmitting a query message containing every said hashed query fragment to a respective one of said claim 13 plurality of query nodes indicated by said first portion of said hashed query fragment using, by said query node, claim 1

Construction: The claim language has its plain and ordinary meaning; no further construction necessary. Intrinsic Support: Figs. 1, 2, 3, 8, 8a; Abstract; 2:3-18; 3:17-50; 4:23-36; 7:23-49. "KEYNET: An architecture and protocol for high-performance semantically rich information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 3. "KEYNET: Fast indexing for semantically rich information retrieval," Kenneth Bac1awski and J. Elliott Smith, p. 9, 13. June 7, 1996 Amendment, p. 14.

8.

Construction: 9

US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 10 of 13

No. Term said second portion of said respective hashed query fragment to access data according to a local hash table located on said query node each said query node uses said second portion of said hashed query fragment to access data according to a local hash table located on said query node said query node, upon receipt of said query message, using said second portion of said hashed query fragment to access data according to a local hash table located on said query node 9. local hash table

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support The claim language has its plain and ordinary meaning; no further construction necessary. Intrinsic Support: Figs. 1, 2, 3a; 2:12-18; 3:37-59; 6:1-28; 7:50-65

claim 8 "A distributed approach to high-performance information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 4-5. "A unified approach to high-performance, vector-based information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 10. claim 13 "KEYNET: An architecture and protocol for high-performance semantically rich information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 14-15. "An abstract model for semantically rich information retrieval," Kenneth Baclawski and Dan A. Simovici, p. 5. June 7, 1996 Amendment, p. 14. Construction: a table that associates hash values with other data Intrinsic Support:

claims 1, 8, 13

10
US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 11 of 13

No. Term

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support Figs. 1, 2, 3a; 2:12-18; 3:37-59; 6:1-28; 7:50-65; 8:64-66; "A distributed approach to high-performance information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 2, 4, 5 "A unified approach to high-performance, vector-based information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 2, 3, 10. "KEYNET: An architecture and protocol for high-performance semantically rich information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 10, 12, 14-15. "An abstract model for semantically rich information retrieval," Kenneth Baclawski and Dan A. Simovici, p. 3, 5. "KEYNET: Fast indexing for semantically rich information retrieval," Kenneth Bac1awski"and J. Elliott Smith, p. 6, 12, 17. May 14, 1997 Amendment, p. 4. June 7, 1996 Amendment, p. 14. Extrinsic Support: "Hash table: A table of information that is accessed by way of a shortened search key (the hash value). Using a hash table minimizes average search time." IBM DICTIONARY OF COMPUTING 309 (George McDaniel ed., 10th ed. 1994). 11

US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 12 of 13

No. Term

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support "Hash Table: A data structure that maps a set of keys to slots from a hashing function." Ricardo A. Baeza-Yates, Introduction to Data Structures and Algorithms Related to Information Retrieval, in INFORMATION RETRIEVAL: DATA STRUCTURES AND ALGORITHMS 13, 20 (William B. Frakes & Ricardo A. Baeza-Yates, eds., 1992). Construction: The claim language has its plain and ordinary meaning; no further construction necessary. Intrinsic Support:

10.

returning, by each said query node each said query node ... returns said query node ... returning

claim 1

claim 8

claim 13 Figs. 1, 2, 3a; 2:12-18; 3:55-65; 4:2-7; 7:50-65; 8:8-15 June 7, 1996 Amendment, p. 18. Construction: a degree of relevance that is determined before returning accessed data to the user Intrinsic Support: 3:60-4:21; 9:44-47. "High Performance, Distributed Information Retrieval," by Kenneth Baclawski and J. Elliott Smith, p. 2.

11.

predetermined degree of relevance

claims 3, 9

12
US 53837v.1

Case 2:07-cv-00486-CE

Document 62-3

Filed 08/28/2009

Page 13 of 13

No. Term

Claim(s)

Plaintiffs' Proposed Construction & Evidentiary Support "High-Performance Indexing and Retrieval for Object-Oriented Databases," Kenneth Baclawski, p. 24. "A distributed approach to high-performance information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 5, 7, 9. "A unified approach to high-performance, vector-based information retrieval," Kenneth Baclawski and J. Elliott Smith, p. 9, 10. "KEYNET: An architecture and protocol for high-performance semantically rich information retrieval," Kenneth Baclawski* and J. Elliott Smith, p. 4, 68, 10, 15, 20. "An abstract model for semantically rich information retrieval," Kenneth Baclawski and Dan A. Simovici, p. 1, 5, 14. "KEYNET: Fast indexing for semantically rich information retrieval," Kenneth Bac1awski and J. Elliott Smith, p. 2, 4-7, 9, 11, 14. June 7, 1996 Amendment, p. 16. December 4, 1996 Amendment at p. 8-9.

13
US 53837v.1

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 1 of 26

EXHIBIT C GOOGLE, INC.'S PROPOSED CONSTRUCTIONS OF DISPUTED CLAIM TERMS

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 2 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term 1. non-relational, distributed database system Claim(s) claims 1, 8, 13 a database, stored across multiple computers on a network, wherein data objects exist independently of their attribute values, and wherein data is not extracted using relational algebra Intrinsic Support: '593 patent at Abstract; col. 1:10-37; col. 1:65-2:18; col. 2:66-3:59; col. 4:237:38; col. 10:25-51; col. 11:24-44; col. 12:6-33; Fig. 1, Fig. 2, Fig. 8, and Fig. 8a. '593 Prosecution History, June 7, 1996 Amendment at 7-14, 16-19; Dec. 11, 1996 Amendment at 8-9; May 14, 1997 Amendment at 3. Chaturvedi et al., Scheduling the Allocation of Data Fragments in a Distributed Database Environment: A Machine Learning Approach, IEEE TRANS ON ENG'G MGMT., vol. 41, no. 2, 1994, pp. 194-206. (GN 524 ­ 537) Houtsma et al., Parallel Hierarchical Evaluation for Transitive Closure Queries, IEEE Apr. 1991. (GN 4932 ­ 4941) U.S. Patent 4,811,199. (GN 7147 ­ 7162) Extrinsic Support: "Relational database: A database in which the data are organized and accessed according to relations." Dictionary of Computing. Research Triangle Park, NC: International Business Machines Corporation, 1991, p. 475. (GN 292968) "Relational database: A database is which data are organized into one or more relations that may be manipulated using a relational algebra." Christopher Booth, ed. The New IEEE Standard Dictionary of Electrical and Electronics Terms (5th Ed.: Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 1106. 2

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 3 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) (GN 300219) "Relational database: A database is which data are organized into one or more relations that may be manipulated using a relational algebra." IEEE Standard Computer Dictionary: A Compilation of IEEE Standard Computer Glossaries (Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 170. (GN 300234) "Relation: (1) In a relational database, a set of entity occurrences that have the same attributes ... (3) In a relational database, a table that identifies entities and their attributes. Synonymous with flat file ...." Dictionary of Computing. Research Triangle Park, NC: International Business Machines Corporation, 1991, p. 475. (GN 292968) "Relation: In a relational data model or relational database, a set of tuples, each of which has the same attributes." Christopher Booth, ed. The New IEEE Standard Dictionary of Electrical and Electronics Terms (5th Ed.: Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 1106. (GN 300219) "Relation: In a relational data model or relational database, a set of tuples, each of which has the same attributes." IEEE Standard Computer Dictionary: A Compilation of IEEE Standard Computer Glossaries (Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 170. (GN 300234) "Relational database management system: A database organization scheme that treats files as tables of data in which the rows represent fixed-length records and columns represent fields. Multiple keys can be used for retrieving the data stored within the database. A database in which some data items in one type of record refer to records of a different type. Relational databases give the user the flexibility to link (join, or create a relationship between) information stored in many disk files. It allows users to interchange and cross-reference information between two different types of records, such as comparing the

3

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 4 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) information in a group of invoices to the information in an inventory. Most people do not need relational databases. To merely keep track of a mailing list doesn't require a relational database, nor is such a database needed to keep a simple inventory of something. However, those who want to print out a mailing list of people who ordered products from their inventory will need a relational database. Relational databases are more powerful, more complex, more difficult to use, and more expensive than other database systems." Webster's New World Dictionary of Computer Terms (4TH ed.) (Prentice Hall: New York, NY), 1992, p. 353. "Relational database management system (RDBMS): A database management system based on the relational model. This claim is often made (particularly for personal computer packages) principally on the grounds that the data is treated as a series of two-dimensional tables, known as relations. Stricter criteria would require also that algebraic operations, such as JOIN or PROJECT, could be used to manipulate the data and to create new tables based on various combinations of the original tables." Gunton, Tony. A Dictionary of Information Technology and Computer Science, 257, 2nd ed. Oxford, UK: NCC Blackwell Ltd. 1993, p. 257. (GN 292982) Kenneth Baclawski and J. Elliott Smith, A Unified Approach to HighPerformance, Vector-Based Information Retrieval, March 21, 1994. (JAR 294­313) a plurality of home nodes and query nodes connected by a network arranged with no central server and wherein, for any given query, any node may be defined as a home node or a query node Intrinsic Support: '593 patent at Abstract; col. 1:65-2:18; col. 2:66-3:59; col. 4:8-7:38; col. 10:2551; col. 11:24-44; col. 12:6-33; Fig. 1, Fig. 2, Fig. 8, Fig. 8a.

2.

a plurality of home nodes and a plurality of query nodes connected by a network a plurality of home nodes; and a plurality of query nodes; said plurality of

claim 1

claims 8, 13

4

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 5 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term home nodes and said plurality of query nodes connected by a network Claim(s) `593 Prosecution History, April 16, 1996 Office Action at 2-3; June 7, 1996 Amendment at 13, 16; May 14, 1997 Amendment at 2-3. Chaturvedi et al., Scheduling the Allocation of Data Fragments in a Distributed Database Environment: A Machine Learning Approach, IEEE TRANS ON ENG'G MGMT., vol. 41, no. 2, 1994, pp. 194-206. (GN 524 ­ 537) Houtsma et al., Parallel Hierarchical Evaluation for Transitive Closure Queries, IEEE Apr. 1991. (GN 4932 ­ 4941) U.S. Patent 4,811,199. (GN 7147 ­ 7162) Extrinsic Support: Kenneth Baclawski and J. Elliott Smith, A Unified Approach to HighPerformance, Vector-Based Information Retrieval, March 21, 1994. (JAR 294­313) selecting by chance, independently of preceding selections, where each item in the set has equal probability of being chosen Intrinsic Support: '593 patent at col. 3:17-25; col. 10:25-51; col. 11:24-44; col. 12:6-33; Fig. 1, Fig. 2. '593 Prosecution History, June 7, 1996 Amendment at p. 13, 16; September 11, 1996 Office Action at 2; March 13, 1997 Office Action at 2; May 14, 1997 Response to Office Action at 2. Chaturvedi et al., Scheduling the Allocation of Data Fragments in a Distributed Database Environment: A Machine Learning Approach, IEEE TRANS ON ENG'G MGMT., vol. 41, no. 2, 1994, pp. 194-206. (GN 524 ­ 537)

3.

randomly selecting

claim 1

5

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 6 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) Houtsma et al., Parallel Hierarchical Evaluation for Transitive Closure Queries, IEEE Apr. 1991. (GN 4932 ­ 4941) Extrinsic Support: "Random: 1. occurring or done without definite aim, reason, or pattern: random examples. 2. Statistics. of or characterizing a process of selection in which each item of a set has an equal probability of being chosen. . . . 5. at random, without regard to rules, schedules, etc.; haphazardly." Random House Webster's College Dictionary, New York, NY: Random House Inc. 1991, p. 1116. (GN 300206) "Random: . . . b. Statistics. Governed by or involving equal chances for each of the actual or hypothetical members of a population; also, produced or obtained by a random process (and therefore completely unpredictable in detail) . . . . the movement of something in successive steps ... each step being governed by chance independently of preceding steps." J.A. Simpson & E.S.C. Wiener, eds. Oxford English Dictionary, 2d ed., vol. 13, 1989 (Clarendon Press: Oxford, UK), p. 168. (GN 300405) "Random: (3) (modeling and simulation). Pertaining to a process or variable whose outcome or value depends on chance or on a process that simulates chance, often with the implication that all possible outcomes or values have an equal probability of occurrence; for example, the outcome of flipping a coin or executing a computer-programmed random number generator." Christopher Booth, ed. The New IEEE Standard Dictionary of Electrical and Electronics Terms (5th Ed.: Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 1064. (GN 300218) "Random: Pertaining to a process or variable whose outcome or value depends on chance or on a process that simulates chance, often with the implication that all possible outcomes or values have an equal probability of occurrence; for

6

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 7 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) example, the outcome of flipping a coin or executing a computer-programmed random number generator." IEEE Standard Computer Dictionary: A Compilation of IEEE Standard Computer Glossaries (Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 167. (GN 300233) Kenneth Baclawski and J. Elliott Smith, A Unified Approach to HighPerformance, Vector-Based Information Retrieval, March 21, 1994. (JAR 294­313) a part of a query consisting of a limited number of attributes and attribute values joined by relationships, specified in the same formal, artificial language and ontology which describes the attribute values of objects of the database Intrinsic Support: '593 patent at Abstract; col. 1:10-31; col. 2:3-18; col. 3:25-4:7; col. 4:22-36; col. 4:60-5:29; col. 10:25-51; col. 11:24-44; col. 12:6-33; Fig. 2, Fig. 8, Fig. 8a. '593 Prosecution History, June 7, 1996 Amendment at 9-16; Dec. 11, 1996 Amendment at 8-9; May 14, 1997 Response to Office Action at 2-3. Chaturvedi et al., Scheduling the Allocation of Data Fragments in a Distributed Database Environment: A Machine Learning Approach, IEEE TRANS ON ENG'G MGMT., vol. 41, no. 2, 1994, pp. 194-206. (GN 524 ­ 537) Houtsma et al., Parallel Hierarchical Evaluation for Transitive Closure Queries, IEEE Apr. 1991. (GN 4932 ­ 4941) U.S. Patent 4,811,199. (GN 7147 ­ 7162) Extrinsic Support: "The '593 query fragments are defined at '593 column 1, lines 27-31, and consist of a part of the query with a limited number of attribute values joined by

4.

query fragment

claims 1, 8, 13

7

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 8 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) relationships." U.S. Patent No. 6,505,191 Prosecution History, July 3, 2002 Response to office action at 5. (GN 299941 ­ 300172) Kenneth Baclawski and J. Elliott Smith, A Unified Approach to HighPerformance, Vector-Based Information Retrieval, March 21, 1994. (JAR 294­313) Kenneth Baclawski and J. Elliott Smith, KEYNET: Fast Indexing for Semantically Rich Information Retrieval, December 7, 1993 (JAR 828­845) "Prototype Specifications . . . The hash algorithm is taken from Knuth, volume 3, section 6.4." (JAR 219469) performing a mathematical function on a key value to generate the address of the location of data associated with the key value Intrinsic Support: '593 patent at Abstract; col. 1:33-62; col. 2:3-12; col. 3:25-4:7; col. 4:60-5:29; col. 6:39-7:38; col. 8:61-9:2; col. 10:25-51; col. 11:24-44; col. 12:6-33; Fig. 8, Fig. 8a. '593 Prosecution History, June 7, 1996 Amendment at 12, 14-16; May 14, 1997 Amendment at 3-4. Chaturvedi et al., Scheduling the Allocation of Data Fragments in a Distributed Database Environment: A Machine Learning Approach, IEEE TRANS ON ENG'G MGMT., vol. 41, no. 2, 1994, pp. 194-206. (GN 524 ­ 537) Houtsma et al., Parallel Hierarchical Evaluation for Transitive Closure Queries, IEEE Apr. 1991. (GN 4932 ­ 4941) U.S. Patent 4,811,199. (GN 7147 ­ 7162)

5.

hashing / hashes

claims 1, 8, 13

8

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 9 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) Extrinsic Support: "hashing: (1) a key-to-address transformation in which the keys determine the location of the data. (2) The process of applying a formula to a record key to yield a number that represents a disk address." Webster's New World Dictionary of Computer Terms (4TH ed.) (Prentice Hall: New York, NY), 1992, p. 187. (GN 300244) "hashing: A technique for arranging a set of items, in which a hash function is applied to the key of each item to determine its hash value. The hash value identifies each item's primary position in a hash table, and if this position is already occupied, the item is inserted wither in an overflow table or in another available positioning the table." Christopher Booth, ed. The New IEEE Standard Dictionary of Electrical and Electronics Terms (5th Ed.: Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 586. (GN 300215) "hashing: A technique for arranging a set of items, in which a hash function is applied to the key of each item to determine its hash value. The hash value identifies each item's primary position in a hash table, and if this position is already occupied, the item is inserted wither in an overflow table or in another available positioning the table." IEEE Standard Computer Dictionary: A Compilation of IEEE Standard Computer Glossaries (Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 99. (GN 300228) "hashing algorithm: An algorithm used to derive an address within a specified range from a key value. A hashing algorithm is used with a random file to determine the address of the block in which a given record should be stored." Gunton, Tony, A Dictionary of Information Technology and Computer Science (2nd ed.) (Oxford, UK: NCC Blackwell Ltd.), 1993, p. 136. (GN 292980) "Section 6.3 treats digital searching, and Section 6.4 discusses an important

9

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 10 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) class of methods called hashing techniques, based on arithmetic transformations of the actual keys." Donald Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching, Addison-Wesley, 1973, p. 390. "6.4: Hashing. So far we have considered search methods based on comparing the given argument K to the keys in the table, or using its digits to govern a branching process. A third possibility is to avoid all this rummaging around by doing some arithmetical calculation on K, computing a function f(K) which is the location of K and the associated data on the table. . . . These considerations lead to a popular class of search methods commonly known as hashing or scatter storage techniques. The verb "to hash" means to chop something up or to make a mess out of it; the idea in hashing is to chop off some aspects of the key and to use this partial information as the basis for searching. We compute a hash function h(K) and use this value as the address where the search begins." Donald Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching, Addison-Wesley, 1973, p. 506-07. "Prototype Specifications . . . The hash algorithm is taken from Knuth, volume 3, section 6.4." (JAR 219469) "hash: An associative access technique that maps the key via a hash function uniformly among a partitioned set of hash buckets. A key search consists of hashing the key to a bucket address and then examining the small hash bucket for records with the desired key." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 120; see also generally pp. 831-851. "Associative access on a single relation can be supported by two types of access paths that use fundamentally different approaches to solving the problem of translating attribute values into tuple addresses. These approaches, which yield fundamentally different functionality, are generally referred to as hashing

10

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 11 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) (key transformation) and key comparison." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 833. "Hashing is based on the idea of using the primary key value as a parameter to a function which returns the storage location of the tuple as a result. This is the very principle of hashing, and it has a number of interesting properties. If the transformation function can be kept simple--that is, if it does not need large data structures with search paths and routing data--then the access cost to retrieve a tuple via its key is minimal: take the key value, do some arithmetic, and find the tuple at the address delivered by the function. Ideal hash algorithms allow for one-access retrieval, which is to say that only the page holding the tuple needs to be read when accessing via the primary key. The functional principle of simple hashing is to relate to key value of a tuple and the page number in which it is stored, through a predefined function; because of this, simple hashing is not just an access method, but also a file organization technique. (This was explained in Chapter 14.) As such, it needs page address spaces with special properties, as with become obvious during the detailed description. Hash-based access paths support only queries of the type (keyattribute = const). They do not efficiently support range predicates such as keyattribute between A and B. The attribute used for hashing typically is a primary key of the relation, but can also be used for nonunique attributes." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 833. "Key comparison comprises all methods for maintaining a dynamic search structure on the set of values in the key attribute. These values (or compressed versions of them) can be organized into tables, lists, trees, and so on, depending on the amount of data, the type of search operations to be supported, and the storage size that is available for maintaining the search structure. If such a technique is used for a primary access path, the entire tuple can be stored in

11

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 12 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) search structure (see Section 14.4.5, on key-sequenced files, in Chapter 14); otherwise, it will contain pointers to the tuples (e.g., TIDs). Sorting a file along some attribute and keeping it sorted under updates is a very simple example of a search structure based on key comparison--in this case, it is a sequential sorted list of tuples. If records are clustered within blocks according to the key attribute values, searching and scanning in sorted order can be performed efficiently." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 833. "Algorithms to implement associative access come in two flavors. The first one, hashing, supports access based on value equality only; it uses a transformation function that turns the attribute value into a page address where the tuple can be found." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 835. "As in hash-based memory organizations, there has to be a function to transform the attribute value into a file address, where the tuple will (most likely) be found." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 835. "[A] good hash function H has to map primary key values, which are very unevenly distributed over a large value range, into a tuple address space that is much smaller (proportional to the number of existing tuples), such that the resulting addresses are evenly distributed over the address range." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 839. "[i]f the hash function h(p) is properly chosen, then the hash values will be approximately uniformly distributed over their range." (JAR 108483) Kenneth Baclawski and J. Elliott Smith, A Unified Approach to High-

12

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 13 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) Performance, Vector-Based Information Retrieval, March 21, 1994 (JAR 294­ 313) Kenneth Baclawski and J. Elliott Smith, KEYNET: Fast Indexing for Semantically Rich Information Retrieval, December 7, 1993 (JAR 828­845) JAR0146229-146266 "The examination node 102 then encodes each feature fragment of the object by using a predefined hashing function. Data in the system was previously stored locally on the various index nodes using this hashing function to generate an index to the data in the local database. Thus, the use of the same hashing function to generate an index for data storage and to generate hashed feature fragments for an information object assures that (1) data is distributed uniformly over the index nodes of the routing search engine during the storing of data and (2) the feature fragments are scattered uniformly over the index nodes during the processing of an object." U.S. Patent No. 6,192,364, col. 6:46-58. (GN 299812 ­ 831) "The home node 107 then encodes each feature of the query by using a predefined hashing function. Data in the system was previously stored locally on the various query nodes 109 using this hashing function to generate an index to the data in the local database. Thus, the use of the same hashing function to generate an index for data storage and to generate hashed probes for a data query assures that (1) data is distributed uniformly over the query nodes 109 of the search engine during the storing of data and (2) the probes are scattered uniformly over the query nodes 109 during the processing of a query." U.S. Patent No. 6,424,973, col. 7:58-8:2. (GN299832 ­ 854) "The home node encodes each fragment of the query by using a predefined hashing function. The same hashing function preferably is also used in

13

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 14 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) generating indexes to storage locations for storing data locally in local databases on the various query nodes. The use of the same hashing function to generate an index for data storage and to generate hashed probes for a query assures that data is distributed uniformly over the query nodes of the search engine during the storing of data, and that the probes are scattered uniformly over the query nodes during the processing of a query." U.S. Patent No. 6,463,433, col. 11:18-29. (GN 299855 ­ 877) "Thus, the use of the same hashing function to generate an index for data storage and to generate hashed probes for an object assures that data is distributed uniformly over the index nodes 106 of the data warehouse during the storing of data." U.S. Patent No. 6,470,333 Col. 7:36-41. "The home node 105 encodes each fragment of the query by using a predefined hashing function. Data in the distributed computer database system was previously stored locally on the various index nodes 112 using this hashing function to generate an index to the data in the local database. In particular, if a fragment includes a link then it is hashed and stored as a link fragment, while if a fragment does not include a link then it is hashed and stored as an index fragment. Thus, the use of the same hashing function to generate an index for data storage and to generate hashed probes for a query assures that 1. data is distributed uniformly over the index nodes of the search engine during the storing of data and 2. the probes are scattered uniformly over the index nodes during the processing of a query." U.S. Patent No. 6,505,191, col. 8:61-9:8. (GN 299917 ­ 940) "The examination node 102 then encodes each feature fragment of the object by using a predefined hashing function. Data in the system was previously stored locally on the various index nodes using this hashing function to generate an index to the data in the local database. Thus, the use of the same hashing function to generate an index for data storage and to generate hashed feature

14

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 15 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) fragments for an information object assures that (1) data is distributed uniformly over the index nodes of the routing search engine during the storing of data and (2) the feature fragments are scattered uniformly over the index nodes during the processing of an object." U.S. Patent No. 6,535,881, col. 6:59-7:3. (GN 299898 ­ 916) U.S. Patent No. 6,505,191 Prosecution History, July 3, 2002 Response to Office Action at 5. (GN 299941 ­ 300172) See generally Gerald Salton, Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer, Addison-Wesley, pp. 159226 (1989). (GN 005396 ­ 5463) See generally Gerald Salton, Michael McGill, Introduction to Modern Information Retrieval, McGraw-Hill, 1983, pp. 329-48. See generally William B. Frakes, Ricardo Baeza-Yates, ed., Information Retrieval / Data Structures & Algorithms, Prentice Hall (1992) (GN 4430 ­ 60) a first part separate and distinct from a second part Intrinsic Support: '593 patent at col. 2:3-2:12; col. 3:37-50; col. 4:60-5:29; col. 6:39-7:55; col. 10:25-51; col. 10:63-64; col. 11:24-44; col. 11:52-54, col. 12:6-33. Extrinsic Support: "portion: a part of a whole, either separated from or integrated with it; segment." Random House Webster's College Dictionary, Random House, New York, 1991, p. 1052. (GN 300204) "The logical, plain meaning of 'first and second part' is that the item described must have two components: a first and a second. . . . The figure drawings . . .

6.

a first portion and a second portion

claims 1, 8, 13

15

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 16 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) affirm this common sense and undisputed interpretation." Anchor Wall Systems, Inc. v. Concrete Products of New London, Inc., 2003 WL 1589532 at *3, No. Civ. 01-465 ADM/AJB (D. Minnesota, March 26, 2003). (GN 299783 ­ 789) "Menu options from a region are placed into specific location in another region. . . . There is no clearer way to interpret `a first region' and `a second region' than the language of the claim itself. The clear and unambiguous meaning is they are two different regions. No further construction is necessary." Merit Indust. v. JVL Corp., 2007 WL 2463377 at *6-8, Civ. No. 03-1618 (E.D.Pa. Aug. 27, 2007). (GN 299790 ­ 811) Kenneth Baclawski and J. Elliott Smith, A Unified Approach to HighPerformance, Vector-Based Information Retrieval, March 21, 1994 (JAR 294 ­ 313) the selected home node sends each hashed query fragment to exactly one node on the network, that node being identified by said first portion of the hashed query fragment Intrinsic Support: '593 patent at Abstract; col. 2:3-2:12; col. 2:66-3:56; col. 4:22-36; col. 4:565:29; col. 7:24-65; col. 10:25-51; col. 11:24-44; col. 12:6-33; Fig. 1, Fig. 2, Fig. 8, Fig. 8a. '593 Prosecution History, June 7, 1996 Amendment at 12; March 13, 1997 Office Action at 2; May 14, 1997 Amendment at 2-3. Chaturvedi et al., Scheduling the Allocation of Data Fragments in a Distributed Database Environment: A Machine Learning Approach, IEEE TRANS ON ENG'G MGMT., vol. 41, no. 2, 1994, pp. 194-206. (GN 524 ­ 537)

7.

transmitting, by said claim 1 selected home node, each said hashed query fragment of said plurality of query fragments to a respective one of said plurality of query nodes indicated by said first portion of each said hashed query fragment transmits each said hashed claim 8 query fragment to a respective one of said plurality of query nodes indicated by said first potion of said hashed query

16

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 17 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. fragment transmitting a query claim 13 message containing every said hashed query fragment to a respective one of said plurality of query nodes indicated by said first portion of said hashed query fragment using, by said query node, claim 1 said second portion of said respective hashed query fragment to access data according to a local hash table located on said query node each said query node uses said second portion of said hashed query fragment to access data according to a local hash table located on said query node said query node, upon receipt of said query message, using said second portion of said hashed query fragment to access data according to a local claim 8 '593 Prosecution History, May 14, 1997 Amendment at 2-3. U.S. Patent 4,811,199. (GN 7147 ­ 7162) Extrinsic Support: Kenneth Baclawski and J. Elliott Smith, A Unified Approach to HighPerformance, Vector-Based Information Retrieval, March 21, 1994. (JAR 294 ­313) Term Claim(s) U.S. Patent 4,811,199. (GN 7147 ­ 7162) Extrinsic Support: Kenneth Baclawski and J. Elliott Smith, A Unified Approach to HighPerformance, Vector-Based Information Retrieval, March 21, 1994. (JAR 294 ­313)

8.

each query node receiving a hashed query fragment uses the second portion of the hashed query fragment as a key value to identify the address of data according to a local hash table stored on that query node Intrinsic Support: '593 patent at Abstract; col. 2:13-18; col. 2:66-3:16; col. 3:17-4:7; col. 4:238:7; col. 8:45-9:60; col. 10:25-51; col. 11:24-44; col. 12:6-33; Fig. 1, Fig. 2. Figs. 3, 3a, 3b, 4, 5, 6, 7, 7a, 8, and 8a.

claim 13

17

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 18 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. 9. Term hash table located on said query node local hash table Claim(s) claims 1, 8, 13 a table resident on and unique to a particular query node in which the unique location of the information in the table is determined by hashing a key value Intrinsic Support: '593 patent at col. 1:33-62; col. 3:26-4:7; col. 5:30-39; col. 6:1-27; col. 7:5065; col. 10:25-51; col. 11:24-44; col. 12:6-33. '593 Prosecution History, May 14, 1997 Amendment at 5. Chaturvedi et al., Scheduling the Allocation of Data Fragments in a Distributed Database Environment: A Machine Learning Approach, IEEE TRANS ON ENG'G MGMT., vol. 41, no. 2, 1994, pp. 194-206. (GN 524 ­ 537) Houtsma et al., Parallel Hierarchical Evaluation for Transitive Closure Queries, IEEE Apr. 1991. (GN 4932 ­ 4941) U.S. Patent No. 4,811,199 (GN 7147 ­ 7162) Extrinsic Support: "hashing: 1) a key-to-address transformation in which the keys determine the location of the data. (2) The process of applying a formula to a record key to yield a number that represents a disk address." Webster's New World Dictionary of Computer Terms, 4th ed., Prentice Hall, 1992, p. 187. (GN 300244) "hashing: A technique for arranging a set of items, in which a hash function is applied to the key of each item to determine its hash value. The hash value identifies each item's primary position in a hash table, and if this position is already occupied, the item is inserted wither in an overflow table or in another

18

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 19 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) available positioning the table." Christopher Booth, ed. The New IEEE Standard Dictionary of Electrical and Electronics Terms (5th Ed.: Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 586. (GN 300215) "hashing: A technique for arranging a set of items, in which a hash function is applied to the key of each item to determine its hash value. The hash value identifies each item's primary position in a hash table, and if this position is already occupied, the item is inserted wither in an overflow table or in another available positioning the table." IEEE Standard Computer Dictionary: A Compilation of IEEE Standard Computer Glossaries (Inst. of Electrical & Electronics Engineers, Inc.), 1991, p. 99. (GN 300228) "hashing algorithm: An algorithm used to derive an address within a specified range from a key value. A hashing algorithm is used with a random file to determine the address of the block in which a given record should be stored." Gunton, Tony, A Dictionary of Information Technology and Computer Science (2nd ed.) (Oxford, UK: NCC Blackwell Ltd.), 1993, p. 136. (GN 292980) "Section 6.3 treats digital searching, and Section 6.4 discusses an important class of methods called hashing techniques, based on arithmetic transformations of the actual keys." Donald Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching, Addison-Wesley, 1973, p. 390. "6.4: Hashing. So far we have considered search methods based on comparing the given argument K to the keys in the table, or using its digits to govern a branching process. A third possibility is to avoid all this rummaging around by doing some arithmetical calculation on K, computing a function f(K) which is the location of K and the associated data on the table. . . . These considerations lead to a popular class of search methods commonly known as hashing or scatter storage techniques. The verb "to hash" means to chop something up or to make a mess out of it; the idea in hashing is to chop off some aspects of the

19

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 20 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) key and to use this partial information as the basis for searching. We compute a hash function h(K) and use this value as the address where the search begins." Donald Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching, Addison-Wesley, 1973, p. 506-07. "Prototype Specifications . . . The hash algorithm is taken from Knuth, volume 3, section 6.4." (JAR 219469) "hash: An associative access technique that maps the key via a hash function uniformly among a partitioned set of hash buckets. A key search consists of hashing the key to a bucket address and then examining the small hash bucket for records with the desired key." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 120; see also generally pp. 831-851. "Associative access on a single relation can be supported by two types of access paths that use fundamentally different approaches to solving the problem of translating attribute values into tuple addresses. These approaches, which yield fundamentally different functionality, are generally referred to as hashing (key transformation) and key comparison." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 833. "Hashing is based on the idea of using the primary key value as a parameter to a function which returns the storage location of the tuple as a result. This is the very principle of hashing, and it has a number of interesting properties. If the transformation function can be kept simple--that is, if it does not need large data structures with search paths and routing data--then the access cost to retrieve a tuple via its key is minimal: take the key value, do some arithmetic, and find the tuple at the address delivered by the function. Ideal hash algorithms allow for one-access retrieval, which is to say that only the page

20

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 21 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) holding the tuple needs to be read when accessing via the primary key. The functional principle of simple hashing is to relate to key value of a tuple and the page number in which it is stored, through a predefined function; because of this, simple hashing is not just an access method, but also a file organization technique. (This was explained in Chapter 14.) As such, it needs page address spaces with special properties, as with become obvious during the detailed description. Hash-based access paths support only queries of the type (keyattribute = const). They do not efficiently support range predicates such as keyattribute between A and B. The attribute used for hashing typically is a primary key of the relation, but can also be used for nonunique attributes." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 833. "Key comparison comprises all methods for maintaining a dynamic search structure on the set of values in the key attribute. These values (or compressed versions of them) can be organized into tables, lists, trees, and so on, depending on the amount of data, the type of search operations to be supported, and the storage size that is available for maintaining the search structure. If such a technique is used for a primary access path, the entire tuple can be stored in search structure (see Section 14.4.5, on key-sequenced files, in Chapter 14); otherwise, it will contain pointers to the tuples (e.g., TIDs). Sorting a file along some attribute and keeping it sorted under updates is a very simple example of a search structure based on key comparison--in this case, it is a sequential sorted list of tuples. If records are clustered within blocks according to the key attribute values, searching and scanning in sorted order can be performed efficiently." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 833. "Algorithms to implement associative access come in two flavors. The first one, hashing, supports access based on value equality only; it uses a transformation function that turns the attribute value into a page address where

21

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 22 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) the tuple can be found." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 835. "As in hash-based memory organizations, there has to be a function to transform the attribute value into a file address, where the tuple will (most likely) be found." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 835. "[A] good hash function H has to map primary key values, which are very unevenly distributed over a large value range, into a tuple address space that is much smaller (proportional to the number of existing tuples), such that the resulting addresses are evenly distributed over the address range." Jim Gray, Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufman, 1993, p. 839. "[i]f the hash function h(p) is properly chosen, then the hash values will be approximately uniformly distributed over their range." (JAR 108483) Kenneth Baclawski and J. Elliott Smith, A Unified Approach to HighPerformance, Vector-Based Information Retrieval, March 21, 1994 (JAR 294­ 313) Kenneth Baclawski and J. Elliott Smith, KEYNET: Fast Indexing for Semantically Rich Information Retrieval, December 7, 1993 (JAR 828­845) JAR0146229-146266 "The examination node 102 then encodes each feature fragment of the object by using a predefined hashing function. Data in the system was previously stored locally on the various index nodes using this hashing function to generate an index to the data in the local database. Thus, the use of the same hashing

22

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 23 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) function to generate an index for data storage and to generate hashed feature fragments for an information object assures that (1) data is distributed uniformly over the index nodes of the routing search engine during the storing of data and (2) the feature fragments are scattered uniformly over the index nodes during the processing of an object." U.S. Patent No. 6,192,364, col. 6:46-58. (GN 299812 ­ 831) "The home node 107 then encodes each feature of the query by using a predefined hashing function. Data in the system was previously stored locally on the various query nodes 109 using this hashing function to generate an index to the data in the local database. Thus, the use of the same hashing function to generate an index for data storage and to generate hashed probes for a data query assures that (1) data is distributed uniformly over the query nodes 109 of the search engine during the storing of data and (2) the probes are scattered uniformly over the query nodes 109 during the processing of a query." U.S. Patent No. 6,424,973, col. 7:58-8:2. (GN299832 ­ 854) "The home node encodes each fragment of the query by using a predefined hashing function. The same hashing function preferably is also used in generating indexes to storage locations for storing data locally in local databases on the various query nodes. The use of the same hashing function to generate an index for data storage and to generate hashed probes for a query assures that data is distributed uniformly over the query nodes of the search engine during the storing of data, and that the probes are scattered uniformly over the query nodes during the processing of a query." U.S. Patent No. 6,463,433, col. 11:18-29. (GN 299855 ­ 877) "Thus, the use of the same hashing function to generate an index for data storage and to generate hashed probes for an object assures that data is distributed uniformly over the index nodes 106 of the data warehouse during the storing of data." U.S. Patent No. 6,470,333 Col. 7:36-41.

23

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 24 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) "The home node 105 encodes each fragment of the query by using a predefined hashing function. Data in the distributed computer database system was previously stored locally on the various index nodes 112 using this hashing function to generate an index to the data in the local database. In particular, if a fragment includes a link then it is hashed and stored as a link fragment, while if a fragment does not include a link then it is hashed and stored as an index fragment. Thus, the use of the same hashing function to generate an index for data storage and to generate hashed probes for a query assures that 1. data is distributed uniformly over the index nodes of the search engine during the storing of data and 2. the probes are scattered uniformly over the index nodes during the processing of a query." U.S. Patent No. 6,505,191, col. 8:61-9:8. (GN 299917 ­ 940) "The examination node 102 then encodes each feature fragment of the object by using a predefined hashing function. Data in the system was previously stored locally on the various index nodes using this hashing function to generate an index to the data in the local database. Thus, the use of the same hashing function to generate an index for data storage and to generate hashed feature fragments for an information object assures that (1) data is distributed uniformly over the index nodes of the routing search engine during the storing of data and (2) the feature fragments are scattered uniformly over the index nodes during the processing of an object." U.S. Patent No. 6,535,881, col. 6:59-7:3. (GN 299898 ­ 916) U.S. Patent No. 6,505,191 Prosecution History, July 3, 2002 Response to Office Action at 5. (GN 299941 ­ 300172) See generally Gerald Salton, Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer, Addison-Wesley, pp. 159226 (1989). (GN 005396 ­ 5463)

24

Case 2:07-cv-00486-CE

Document 62-4

Filed 08/28/2009

Page 25 of 26

Google, Inc.'s Proposed Construction & Evidentiary Support No. Term Claim(s) See generally Gerald Salton, Michael McGill, Introduction to Modern Information Retrieval, McGraw-Hill, 1983, pp. 329-48. See generally William B. Frakes, Ricardo Baeza-Yates, ed., Information Retrieval / Data Structures &