Northeastern University et al v. Google, Inc.,

Filing 78

REPLY to 71 Claim Construction Brief filed by Google, Inc.,. (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, # 9 Exhibit I, # 10 Exhibit J, # 11 Exhibit K, # 12 Exhibit L, # 13 Exhibit M, # 14 Exhibit N, # 15 Exhibit O, # 16 Exhibit P)(Albert, Francis)

Download PDF
Northeastern University et al v. Google, Inc., Doc. 78 Att. 1 EXHIBIT A Dockets.Justia.com In te application serial o. Filed For Examiner Attorney's Docket t Z i(J)h?th. P. Baclawski 08/3tf'252 s October 5, i94 DISTRIBUTED COMPUTER DATABASE SYSTEM AHI) METHOD - t t C. Lewis NU-360XX Group Art Unit: 2307 ****** ***** ****** ******** **** **** I hereby certify that this correspondence is being deposited with the United States Posts]. Service as f 1st class mail in an envelope addressed to: BOX NON-PEE AMENDMENT, Assi tan,t Commissioner for Patents, Washington, fl.C. 20231 on By Sta ley M. SchurRegistration No. 20,979 Attprney for Applicant(s) ******.*** * ***************** * **** 24 ;& NON-flE AMENDMENT Assistant Commissioner for Patents Washington, D.C. 20231 BOX sfr: In response to the Office Action dated April 16. 1996, please amend the above-identified patent application as follows: WFmNOAtTnl. SORJIOP1. OAONFJIN a IthY 1Fi.I)Sfln1O F (I) $I-033 JA R00028 21 ;ia1 No.: Fl-led: 08/310,252 October 5, 1994 .,GOUP Art unit; 2307 j Please amend claims 1, 6, 8, 22, 13 and )7 as follows: (Amended) 2 A"\Tuethod tor jflfofloatign retriva2,uing fuzzy giis [of access a pJimiSt g dataj in a distributed database system having 3 4 of home nodes [node) and a plurality of query nodes , said method comprising the steps of: connected by a netwo 5 6 7 8 9 ado nodes selet af stone of s.j. lu.it Oe fragmenting, by sai. select4 hone node, a query from a user into a plurality of query ragnents; hashing, by said se ec.'. hernie node, each said query fragment 10 11 12 13 14 of said plurality of query f agments, said hashed query fragment having a first portion and a --cond portion; transmitting, by said sel;cte. home node, eaoh said hashed query fragment of said plurality . f query fragments to a respective one of said plurality of query odes indicated by said first 15 16 li portion of each said hashed query f agnent; using, by said query node, slid second portion of said respective hashed query fragment to .ccess data according to a local hash table located on said query ode; and 18 19 returning, by each said query node a'cessing data according to 20 21 said respective hashed query fragment, an object identifier corresponding to said accessed data to sai- selected heine node. WflIGAflE,I. 5CIWaOI OAGIIPM*4 & (Am Ta(6l (nra FAX 7) 4514317 JAR0002822 Serial No.: 0B/318,252 Filed: October 5, 1994 Group )irt Unit: 2301 L6. (Amend-.) A method of storing data in a manner which 1s 2 .duc - t. ,.tiaioj ttrev- -!' - -- -: in a 3 4 5 6 distributed da abase system having a plurality of home pdes f node) and a plurality of query nodes connected by a network, said method comprising the seps of: a,donl sel- tin, a - st oie of flj r 8 podes fragmenting, by -aid selecte home node, data from a user into 9 a plurality of data f .gments; 10 11 hashing, by said s ec ed heme node, each said data fragment of said plurality of da a fragments, said hashed data fragment having a first portion an. a second portion; 12 13 14 transmitting, by said -e ected home node, each said hashed data fragment of said plurali y of data fragments to a respective LS one of said plurality of que y nodes indicated by said first portion of each said hashed data fragment; and 16 17 18 19 using, by said query node, said second portion of said respective hashed data fragment to - tore data according to a local hash table located on said query nod ributed database system toying anirgonatjqn 2 3 er es - 01e . Ser comprising: a plurality of hom nodes [node); and wv,onno scnua. OACNThDI .Hrnt FM Cfl 4617 fltO JA R00028 23 Serial No.: 08/318,252 Filed: October 5, 1994 Group Art Unit: 2307 4 a plural ty of query nodes; said 5 6 7 - u -1 t of hone nodes tnode] and said plurality of query nodes con ected by a network, wh- ein -- said home node, upon receiving a query from a user, fragments s d query into a plurality of query fragments, 9 hashes each said query fragment of said plurality of query 10 fragments into a ha-lied query fragment having a first portion and a second portion, an. transmits each said hashed query fragment to a respective one of s. id plurality of query nodes indicated by said 11 12 13 first portion of said ashed query fragment, and 14 furt er w ere n e portion 0f said hashed h said query node ,] uses said second 15 16 17 18 ery fragment to access data according to a local flash table 1ocatd on said query node ana returns [,] an object identifier correspo ding to said accessed data to said home 1( 2 12. (Amended i A distributed database system o for floraqe ahi r- neya o a ato. comprising: u a t1 o home nodes Enode]; and 'p 4 a plurality 'f query nodes; said unt J 5 6 7 B of home iodes [node] and said plurality of by a network, query nodes connect- wherein each sai. horas node, upon receiving data from a user, fragments said data m'o a plurality of data fragments, hashes each TflMI 3e-1m FAX 1M wnrnM-rm', wIRPs. GA005IJl aRyu 451.1513 JAR0002824 09/318,252 Filed: October 5, 1994 Group Art unit: 2307 Serial. No.; 9 said ata fragment of said plurality of data fragments into a lO hashed data fragment having a first portion and a second portion, and tra smite each said hashed data fragment to a respective one of fl 12 13 14 said plu ality of query nodes indicated by said first portion of said hashd data fragment, jj4 said query node (,) uses said second portion of 15 said hashed data fragment to store data according to a local hash table 1ocate on said query node. 13. 2 3 4 5 6 7 B 9 (Miended) A distributed database system havinq an tnforuiation tre. ol o ad n .ue -. r.m . us-r comprising home (node] nodes; and query nodes sad u ali o- jede- an nodes connected by a network, ear-h said horn node, upon receiving a command from a med task in response to said command, lis er, engueueing a predete a query task en eued beine resultant in, in response to a query command from said user, fragmenting a query contained in said 10 query command into a p urality of query. fragments, hashing each said query fragment of hashed query fragment hay and transmitting a query s n 12 13 14 aid plurality of query fragrents into a g a first portion and a second portion, sage containing each said hashed query fragment to a respective e of said plurality of query nodes 15 indicated by said first porton of said hashed query fragment, OAON511 a HAm la fll (IO .151.0313 J ARO 002825 Serial No.; 08/318,252 Filed: October 5, 1994 Group Art Unit: 2307 16 said uerY\noaei upon receipt of said query message, using 17 18 said second porti\n of said hashed query fragment to access data according to a ioc hash table located on said query node and 19 20 transmitting a messae returning an object identifier corresponding to said accessed data\o said home node. (Mended) distributed database system for storaqe and J 2 3 4 5 G 7 8 retrieva i o ition o comprisingf a pfljflt home node noces; and a plurality of ery nodes, said plurality of home nesa4 n..es connected by a network, sad ra t of ue each said hone n-.e, upon receiving a command from a user, enqueueing a predetermi -d task in response to said command, an insert task engue ed, in response to an insert command from 9 said user, fragmenting dat; contained in said insert command into a plurality of data fragmen s, hashing each said data fragment of said plurality of data fraque ts into a hashed data fragment having 10 li 12 13 14 a first portion and a second ortion, arid transmitting an insert message containing each said h; -bed data fragment to a respective one of said plurality of que nodes indicated by said first 15 16 17 18 portion of said hashed data fragm-nt, said query node, upon receip. of said insert message, using said second portion of said hashe. data fragment to store data according to a local hash table loca' ed on said query node. w}2loMml, scimRial, OAOlEbaI * hAYS 15. 1411) $Ch Fa 611) &lA)I3 JAR0002S2B Serial No.: 08/316,252 Filed. October 5, 1994 Group Art Unit: 2307 RFMAXS The above-identif led patent application has been amended and reconsideration is respectfully requested. Claims 1-17 are pending and stand rejected. amended. Claims 1, 6, 8, 12, 13 and 17 have been Claims l-17 are rejected under 35 U.S.C. S103 as being unpatentable over Chaturvedi, et al., "Scheduling the Allocation of Data Fragments in a Distributed Database Environment: A Machine Learning Approach", IEEE Transactions on Engineering Managenent, Vol. 41, No. 2, Hay 1994 and Houtsifia et al., "Parallel Hierarchical Evaluation of Transitive Closure Queries", IEEE, 1991. with respect to claims 1, 6, 8, 12-13, and li, the Examiner states that, "It would have been obvious to one of ordinary skill in the art at the time the invention was made to combine the hashinq means of Houtsma's teachings with the teachings of Chaturvedi because the hashing means could enable Chaturvedi's information retrieval means to provide the queried node with a query value and a query identifier during the query nodes hashing process" (Paper 14o. 3, page 3). However, such a combination wquld not provide the distributed database and method of the present invention. Both the Chaturvedi and Houtsma references describe techniques for partitioning tiles in a Distributed Relational Database Systeii. These two references, and each of the papers cited by these two references, are in the field of relational database systems. A GAGNERN A HMPS in. 4fl) 5C2t9C PA 617) 411013 JA ROO 02827 Serial No.: 08(318,252 Filedr October 5, 1994 Group Art unit: 2307 relational database system consists of one or flore relations, also known as tables or files .Xnown as rows or tuples. Each relation is aset of records, also Each record in a relation lias a set of attributes, also known as fields or columns. Every record in a relation has exactly the same number of fields and the fields have the sane types, For example, a customer relation night consist of a 40 character name field, a 60 character address field and a G digit customer identifier. A fundamental characteristic of relational databases is that records de not have ol,jeot ia.ntity. More particularly, each By record is uniquely determined by the values of its fields. contrast, Jata models other than the relational model generally assume that the basic objects do have object identity, i.e., an object exists independently of any attribute values it night have, and changing the attribute values will not change the object identity. Another fundamental characteristic of relational databases is the use of a relational query language called the relational algebra. The relational algebra is roughly equivalent to what mathematicians call the "first order predicate calculus," and is primarily used database system. for extracting information f ron a relational However, the relational algebra may also be used for other purposes. Por example, relational algebra expressions can be used to specify database views, security and authentication w,w4akrTeI, SC)ivaO5, BArnes,. t TEL BI) )C= WI]) Ojo!) JA R 0002828 Serial No.: 08/318,252 Filed: October 5, 1994 Group Art Unit: 2307 conditions, integrity constraints and database partitions. This can be confusing, and has apparently caused confusion in the examination of the present application, since these other uses of the relational algebra have nothing to do with extracting "query" is information from the database, and yet the word frequently used in connection with these other uses. Modern relational databases typically deal with very large relations, i.e., relations that contain several terabytes (miflion megabytes) of data are common. The need to deal with such large relations along with the reduction in cost of computing equipment has driven the development of distributed relational database systems A distributed relational database system is a relational database system that is distributed among a collection of computers which are connected by a communication network, Very large relations are distributed among the conputers in the network by partitioning or otherwise breaking up the relations into disjoint pieces known as "fragments." These fragments are themselves relations, and typically contain in excess of tens or even hundreds of megabytes, even though the fragments are much smaller than the larger relation of which they are parts. relational fragments are disjoint. Significantly, these The fragments Of a distributed relational database system are defined by using the relational algebra. Perhaps as a result, the term "fragment query" is often used to refer to the relational WUNOASTh scflUoD. CAmln1 aHAWJ TE, (l 543.EE lAX 617) 43I4I7 JAR0002829 Serial No.: 08/318,252 Filed: October 5, 1994 Group Art Unitt 2307 algebra expression that defines a relational database fragment. This can be confusing, and has apparently caused contusion in the examination of the present application, since the relational algebra expression "fragment query" does not 4escribe extraction of information, but rather provides the defining condition for the fragment. The present invention does not utilize the relational model, and in particular does not utilize the relational models of Chaturvedi and ffoutsna. A primary purpose of the present invention is to allow information retrieval f nr intonation objects that are nere general than the simple records of a relational model system. For example, documents such as papers, books, World Wide Web pages, annotated images, and other documents can all be indexed using a search engine in accordance of with the present would be invention. Significantly, none these documents considered searchable records according to the relational model. The present invention and the relational model express queries and records differently. The query lanquage used by the present invention is the same language used to express the information objects, or more precisely their content labels, that are indexed by the search engine of the present invention (claims 1, 6, 8, 12, 13 and 17). This has the advantage that no additional language is In contrast, relational database required for expressing queries. system queries are expressed in the relational algebra and the W5NGAt2, s1uRofl, GMN55 a frAye ThL PAX<6fl14fi-O.ir JA ROO 0283 0 08/318,252 Serial No.: Filed: October 5, t994 Group Art Unit: 2307 records are expressed in other ways. The result of a query provided to the search engine of the present-invention is a set of object identifIer. (claim 1, line 17) with weights (claim 3, lines 2-3, claim 9) attached thereto. The weight attached to an object identifier represents ambiguous and fragmentary queries, which are also known as "fuzzy" queries There is no analogous concept in the relational algebra. A relational algebra expression is a Using precise and unambiguous specification of a set of records. colloquial language, there is no "fuzziness" in the relational algebra. The fragmentation technique of the present invention is The present different from fragmentation in the relational model. invention introduces a fragmentation technique that is utilized in the indexing algorithm. Information objects, or flore precisely their content labels, are broken up into a collection of small overlapping fragments (claim 1, lines 4-5). - The size of each By contrast, the fragment may typically be around 20 bytes. fragments cf the relational model never overlap, are millions of times larger, and have a structure that is both conceptually and practically different. Ftlrthermorer the present invention fragments both queries and information objects in the same way. This is iiipossible for relational model database systems, since queries and records have different structures. 11 WUNOASTDI. 3enfl0l. OAGNFRI RTE1 TE'. lIlT) sa FAX (lIT) 4310313 .JAR000Z8SI Serial No.: 09/318,252 Filed: October 5, 1994 2307 Group Art Unit: P11th regard to the comment on Page 2, heading 3, sentence 1, Charturvedi introduces a new algorithm for defining fragments in a partitioned, distributed relational database system. As noted above, these relational fragments are unrelated to the object fragments of the present invention. This difference is illustrated by the cited example which uses the value of an attribute (named c) to break apart a base table (named Pl) into two relation fragments, according to whether the attribute has value 'A' or 'B'. With regard to the comment on Page 2, heading 3, sentence 2, Chaturvedi introduces a variation on the well known senijoin algorithm for computing a join. of The join is one of the operators computing it the relational algebra, and efficiently is important in relational database systems. Significantly, the algorithm for the two-way join described in Chaturvedi is very different from the algorithm used by the present invention. The Chaturvedi join query is split into two single-table sub-queries and then provided to the two nodes containing the base tables specified in the sub-queries. This splitting technique is commonly employed in Distributed Relational Database Systems. It is an algebraic factoring of the relational algebra expression that is the query. Algebraic factoring is a technique unrelated to the More particularly, in the fragmentation of the present invention. present invention each fragment is hashed in its entirety (claim 1, lines 6-8), and the hash value is provided to a node determined by O4OH5&4 * .tyu 12 - 75.16") 10750 'Ix (SIll 4SF-Oil) JAR0002832 Serial No.: 08/318,252 Filed: October 5, 1994 Group Axt Unit: 2307 the hash value itself. In the splitting technique in Chaturvedi, sub-queries are not bashed at all; they arc shipped to the node containing the base table specified in the sub-query This is hardiy surprising as it would not make any sense to hash a relational query because the resulting hash value would not have any uses. with regard to the comments associated with Figs. 2 and 3 of Chaturvedi, the architecture of Chaturvedi shown in those Pigs. is quite different from the architecture of the present invention. More particularly, there is no central server in the present invention, and neither the nodes of the network nor the object fragments in the index have any kind of hierarchical structure. In the present invention the hone node of a query is randomly chosen, and different queries will generally have different home nodes. with regard to the omxnent on Page 2, heading 3, sentence 3, the database fragmentation nentioned by chaturvedi in the Abstract is relational fragmentation and is unrelated to the fragmentation of the present invention. Illustrative txamples The fragment queries in Chaturvedi's (Page 198) are not query fragments, but rather relational algebra expressions used to define relation fragments. Numbers l-4 in Example 2 on page 198 are queries that They are queries that at some are in the query history at Site A. tine in the past ware processed at Site A. they are used by the MLTIF to compute relational algebra expressions for defining 13 cAsHM RkY Tfl 1617) iOni) FAX SU) 4t0363 JAR0002833 Serial No.: 08/318,252 Piled: October 5. 1994 Group Art Unit: 2307 relation fragments that would be better suited for evaluating the queries in the history than the current relation fragments. The presumption is that the past history is a good indicator of what the future will be. but The litTlE is not t query evaluation algorithm rather a dynamic method for choosing good relation fragments in Therefore, a Distributed Relational Database System. the cited passages of the Chaturvedi reference are irrelevant to the present invention. With regard to the comment on Page 3, heading 3, sentence 1, nowhere on Page 197, column 1 or Page 199, column 2 of Chaturvedi is there any mention of a local hash table or any hashing operation. With regard to the comment on Page 3, heading 3, sentence 2, no object identifiers are mentioned on page 198 of Chaturvedi. Indeed, since the relational model explicitly rejects object identity, it would be amazing if it did mention object identifiers. The Illustrative Example on page 198 simply discusses how to find relational algebra expressions for defining time invariant relational fragments. With regard to the comment on Page 3, beading 3, sentence 3, no hashing operation is mentioned anywhere in the Abstract. With regard to the comment on Page 3, heading 3, sentence 4, floutsma does mot teach use of hashing. Indeed, on page 130, column 2, par. 3, Houtsma refers to a number of papers that use different 11 afl OAONF$QI k IAy5 FAX M' 131-lEI) 14 - JAR0002834 Serial No.: 08/328,252 Filed: October 5, 1994 Group Art tnit: noi nethods to solve the transitive closure problem, including hashbased methods. Eoutsma teaches a disconnection set approach that does not use hashing. Further, the graph shown in Routana is an auxiliary structure used in the algorithm. The graph defines a This is unrelated notion of adjacency between relation fragments. to the graphs (semantic networks) used in the present invention. As discussed above, the fragments of the present invention are guite different from the fragments of the relational model Since the fragments of the present invention are parts of the semantic network, there is no concept of fragment adjacency in the present invention. In Boutema, the graph has the relation fragments as the vertices, with unlabeled edges defined by relation fragment adjacency, while in the present invention the fragments may be regarded as fragments of a graph having labeled edges (semantic relationships) another. that connect concept instantiations with one With regard to the comment on Page 3, heading 3, sentence 5, no hashing operation is mentioned here or anywhere The fragment U is the high speed fragment. in the The term referente "high speed was probably chosen because of their motivating example: the railway network of many European countries. It could equally well have been called the "special fragment" or the "vide- connection fragment." 15 ownmN a '1*7e mr.") T1 IL') JA RO O 02835 08/318,252 Filed; October 5, 1994 Group Art Unit: 2307 Serial No. t The Examiner has also rejected claims 2, 7 and 14 based on the Chaturvedi and Houtsma references. However, iloutema does not use hashing and Chaturvedi does not salve the iuforr.ttion retrisval problem of the present invention. The Chaturvedi network architecture is very different from the architecture of the present invention. In Chaturvedi, except for the central server node, it is presumed that the servers are located where the queries will be presented by users. By contrast, the architecture of the present invention is a search engine that is entirely remote from any user nodes. The "home node" in Chaturvedi is the user node itself, i.e., the node where the query is presented to the distributed system. The "home node" in the present invention is one of the nodes in the search engine, and it can be randonly chosen by one of the front end processors. query. Further, Chaturvedi never fragments a tn addition te the architectural differences, there are no concepts of measure of relevance or degree of relevance (claims 3, 9) in the relational model, and no such concepts are mentioned or employed in Chaturvedi. In particular, the use of the word tirelevancell in Chaturvedi is unrelated to the "fuzzy" notion of relevance in the present invention. Li)ce all research on relational systems, Chaturvedi employs no notion of weighted relevance, When it is stated, for example, that ".. .it (join-value set] is transmitted to the relevant nodes participating in the join WMNflATfll, SOIURGM. 16 - nl 6Th sc-re VAX k O 014319 JA R 0 0 0283 6 Serial No.: 08/318,252 Piled; October 5, 1994 Group Art unit: 2307 operation," Chaturvedi simply means that the join-value set is sent to those nodes participating in the join whih may contribute any tuples to the result of the join. There is no relevance weighting involved in this operation. It it can be determined that a node participating in the join will not contribute any tuples to the result, then it is not sent the join-value set, otherwise the joinvalue set is sent to the node. The decision is completely "sharp" and does not involve any "fuzziness.' This is hardly surprising since Chaturvedi describes a re'ational model which is unrelated to information retrieval using fuzzy queries. With regard to fragment storage, the storage of relation fragments in a Distributed Relational Database System is -specified in the allocation schema. In Chaturvedi, Example 4, there are T1A is the relation three relation fragments: flA, 'f13, and T2. fragment defined by the relational algebra expression: SLECP * FROM T). WHERE e 'A' and T1B is the relation fragment defined by the relational algebra expression: SELECT * PROM Pl WHERE e 'B' The allocation schema simply specifies which nodes contain a copy of each relation fragment. Bere, for example, is the allocation schema used by Chaturvedi in this example; T1A: node A TiE: node B WelQalt4 OAN}nN .urnrs 75. (OU) $0. PM (OU) 'SI-OU 17 - flGfl, JAR0002837 08/318,252 Serial No.: Filed: October 5, 1994 Group Art Unit: 2307 T2: node A It is merely coincidence that the value of the attribute e coincides with the mame of the node. With regard to the comments on Page 4, the steps in Chatunedi, page 199, column L are concerned with choosing time invariant relation queries. These steps are not concerned with query processng per se. In the present invention a query request Roughly can specify one cf several levels of service (claim 16) . speaking, the lower levels of service are faster but are less accurate, accurate. the higher levels of service are slower but more This notion of level of service is meaningless for the relational model. In the reltional model, all queries have exactly ana correct answer. There is no concept in the relational model of answers that are better or worse. In sum, queries" model. the field of "information retrieval using fuzzy la guite different from the relational a (a term of art) In the relational model a query is of complete and in unambiguous specification the result. Relevance the relational model is either TRUE or FALSE. In information retrieval results are returned which may or nay not satisfy the intentions behind the query, and which may even be unrelated to the intentions behind the query. The claims have been amended to particularly point out this difference and remove the confusion which has la GAGNEM4 t hAYO 7fl Jc-rc FAX 6hZ 431.013 JAR0002633 Serial No.: 08/318,252 Filed: October 5, 1994 Group Art Unit: 2307 apparently been brought about by the use of tern which are similar to those of the cited references. For the reasons given above, reconsideration and allowance is respectfully requested. The Examiner is encouraged to telephone the undersigned attorney ta discuss any matters in furtherance of the prosecution of this application. Respectfully submitted, Xenneth P. Baclawski Stanley K. Schurg Registration No. 20,979 Attorney for Applicant(s) WEINGARTEN SCHURGIN, GAGNEBIN & RAYES Pen Post Off ice Square Boston, Massachusetts 02109 Telephone: Telecopier: Date: (617) 542-2290 (611) 451-0313 SRS/jet 84277 19 wnoAam4. OAOtuM & taGr4. TU. (ata Seri.. FM ,6J lSrO.13 JAR000 2839 4 t .o Ro 13 196 DIG I IN THE 'j.' DT PAT NT AND t' .32 ' OFF n re appltcation Application No. Filed For Examiner Attorney's Docket Kenneth P. Baclawski ca/na, 252 October 5, 1994 DISTRIBUTED COMPUTER BATAnASE SYSTEM AND METHOD C. Lewis NU-360X1 Group Art Unit: 2307 * t tt** * t tt ** k * t*t* ** ** * t* * ** *t t t * I hereby certify that titis correspondence is being deposited with the United States Postal Service as first class mail in an envelope Assi tan Commissioner for addressed co: BOX NON-flE AMENDMENT, Patents, Washington, D.C. 202fl on Curgin Registration No. 20,979 Attorney for Applicant R Lt RECEIVED AMENDMENT JAN 021997 GROUP 2300 BOX NON-FEE AMENDMENT Assistant Commissioner for Patents 20231 Washington, D.C. Sir: In response to the Office Action dated September 11, 1996, please amend the above-identified patent application as follows: -1w&Notnm,. (ORmolU. GAGUEEN SWiG QE niEl?) 512.0)0 6)2,43)031) JAR0002848 Application No.: 08/31,252 Piled: October 5, 1994 Group Art luit: 2307 In the Claims Please amend claims 1, 6, 7, 8, 12, 13 and 17 as follows: 1 1. (Twice Amended) A method for information retrieval using fuzzy 2 3 4 queries in a onrelatioItal.. distributed database system having a plurality of home nodes and a plurality of query nodes connected by a network, said method comprising the steps of; s 6 7 B randonily selecting a first one of said plurality of home nodes; fragmenting, by said selected home node, a query from a user into a plurality of query fragments; hashing, by said selected home node, each said query fragment 9 10 of said plurality of query fragments, said hashed query fragment having a first portion and a second portion; 11 )12 transmitting, by said selected home node, each said hashed query fragment of said plurality of query fragments to a respective 13 14 15 16 17 18 one of said plurality of query nodes indicated by said first portion of each said hashed query fragment; using, by said query node, said second pertion of said respective hashed query fragment to access data according to a local hash table located on said query node; and returning, by each said query node accessing data 19 20 21 according to said respective hashed query fragment, an object identifier corresponding to said accessed data to said selected home node. WEnGMThH. 5RM5sl. I GAONeS s*ve u, ThL fl 3e7210 FAX (SII) lARGO 02849 Application No.: 09/318,252 Filed: October 5, 1994 2307 Group Art Unit, (Twice Amended) A method of storing [data] objects in a manner 1 2 3 4 6. which is conducive to infornation retrieval using fuzzy queries in a np jartj, distributed database system having a plurality of home nodes and a plurality of query nodes connected by a network, said method comprising the steps of: s 6 7 randomly selecting a first one of said plurality of home nodes; $ 9 to fragmenting, by said selected home node, [data) pjtg from a user into a plurality of [datai object fragments; hashing, by said selected home node, each said Idatai object fragment of said plurality of [datai object fragments, said hashed [datai il fragment having a first portion and a second portion; 13 14 15 transmitting, by said [data) selected home node, each said hashed phj.sat. fragment of said plurality of data fragments to a respective one of said plurality of query nodes indicated by said first portion of each said using, 1G 17 hashed [data) object fragment; and by said query node, said second portion of said 18 19 respective hashed [datai biect fragment to store data according to a local hash table located on said query node. 1 2 3 7. (Amended) The method of claim 6 further comprising the step of receiving, at said home node, said [datai objects from said user, prior to the step of fragmenting said [datai object. f WSNGAaThN. SCHURGN, 3- OAON)$L') & (AlPS (LP Th_ aP) Pax (JI) 45)I) JA RO 0 0 28 5 0 Application No.: 08/318,252 October 5, 1994 Filed: Group rt Unit: 2307 1 8. (Twice Amended) A -relational, distributed database system 2 3 having an information retrieval tool for handling queries from a user, comprising: 4 5 G a plurality of home nodes; and a plurality of query nodes; said plurality of home nodes and said plurality df query nodes 7 8 9 connected by a network, wherein each said home node upon receiving a query from a user, fragments said query into a plurality 0f query fragments, hashes each 10 said query fragment of said plurality of query 11 12 13 fragments into a hashed query fragment having a first portion and a second portion, and transmits each said hashed query fragment to a respective one of said plurality of query nodes indicated by said 14 15 16 first portion of said hashed query fragment, and further wherein each said query node uses said second portion cf said hashed query fragment to access data according to a local 17 18 hash table located on said query node and returns an object identifier corresponding to said accessed data to said home node. 1 12. (Twice flmended) A non-relational distributed database system for storage and retrieval of information objects, comprising: 3 4 a plurality of hone nodes; and a plurality of query nodes; -4 GAmmaDI HMPS UI PAX [617) 4iIM313 JAR0002USI Application No.: 08/318,252 B'iled: October 5, 1994 Group Art Unit: 2307 s 6 said plurality of home nodes and said plurality of query nodes connected by a network, 7 B 9 wherein each said home node, upon receiving [datai n_pjsS. from a user, fragments said [datai object into a plurality of (datai object fragments, hashes each said (datai s2j-jqX. fragment of 10 said plurality of (datai pjest fragments into a hashed [data] Qj.sz fragment having a first portion and a second portion, and transmits each said hashed [data) Q2jQt fragment to a respective Il 12 13 14 nne of said plurality of query nodes indicated by said first portion of said hashed [datai sjsst. fragment, and wherein each said query node uses said second portion of said hashed [datai ohjecr fragment to store [datai objects according to 15 )l6 47 1 a local hash table located on said query node. 13. (Twice Amended) non-relational distributed database system 2 3 having an information retrieval tool for handling queries from a user, comprising: 4 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, S 6 7 each said home node, upon receiving a command from e user, 8 enqueueing a predetermined task in response to said command, 9 a query task enqueued being resultant in, in response to a 10 query command from said user, fragmenting a query contained in said -5W6a]krn:N. ICI) 0501M. OAC.16E004 & lAYS] tip Wi 611) SIl-ns 6.M 611) 431-MIll JARDO 028 52 Application No.: 08/318,252 Piled: October 5. l994 Group flt Unit: 2307 il 12 13 query command into a plurality of query fragments, hashing each said query fragment of said plurality of query fragments into a hashed query fragment having a first portion and a second portion, 14 15 16 17 and transmitting a query message containing each said hashed query fragment to a respective one of said plurality of query nodes indicated by said first portion of said hashed query fragment, said query node, upon receipt of said query message, using said second portion of said hashed query fragment to access data Y9 20 21 according to a local hash table located on said query node and transmitting a message returning an object identifier corresponding to said accessed data to said home node. 1 2 3 4 5 17. (Twice Amended) A non-relational, distributed database system for storage and retrieval of information, comprising: a plurality of hone node nodes; and a plurality of query nodes, said plurality of home nodes and said plurality of query nodes connected by a network, 6 7 8 each said home node, upon receiving a command from a user, enqueueing a predetermined task in response to said command, an insert task enqueued, in response to an insert cormand from said user, fragmenting data contained in said insert command into lo 11 12 a plurality of data fragments, hashing each said data fragment of said plurality of data fragments into a hashed data fragment having a first portion and a second portion, and transmitting an insert -6w,midjair., ,om,,m. OAONSUJ)l k HAYa iL? lao',, 5C2O LAX (II?) 4M3I3 JAR0002BS3 Application No.: 08/318,252 Filed October 5, 1994 Group Art Unit: 2307 13 14 message containing each said hashed data fragment to a respective one of said plurality of query nodes indicated by said first portion of said hashed data fragment, 415 said query node, upon receipt of said insert message, using said second portion of said hashed data fragment to store data 18 according to a local hash table located on said query node. REKS Claims l-17 are pending in this application. Claims 1, 6, 8, 12, 13 and 17 have been amended. The Examiner has rejected claims l-17 under 35 U.S.C. 102W) as being anticipated by Neches, U.S. Patent No. 5,006,978 Neches teaches breaking up arid distributing a relational database with a hash function for facilitation of data storage. Claims l-S, 8-11 and 13-17 of the present application do not relate to storage of data, and are therefore not suggested by Meches. Claims 6, 7 and However, 12 of the present application relate to storage of data. claims 6, 7 and 12 are distinguished from Neches since these claims (as amended) recite method and apparatus for fragmenting, hashing and distributing objects. Operating upon objects is significantly different from operating upon relations because of size, content and structural differences. For example, a relation will typically be touch larger than an object, and will not include methods. -7- JAR 000 285 4 Application No.: 08/318,252 Filed: October 5, 1994 Group Art Unit: 2307 Relational database systems consist of relations, sometimes referred to as tables or files, where each auch relations is a set of records, sometimes referred to as rows or tuples Bach record in such a relation has a set of attributes, also known as fields or columns, Significantly, each record in a relation has exactly che For same number of fields, and the fields have the same types. example, a customer relation could consist of a forty character name field, a sixty character address field and six digit customer identifier. Further, records in relational database systems do not have object identity. More particularly, each record is uniquely determined by the values of its fields, The present invention expresses queries of and records differently than the relational databases previously cited references. Neches and the The query language used by the present invention is used to erpress information objects that ate indexed by the search engine. tn contrast, relational database queries are expressed in a relational algebra and recorda are expressed in other ways. The present invention therefore provides 'languages' Further., an advantage since separate are not required for the result of a query expressing queries and records. provided to the search engine of the present invention is a set of object identifiers with weights attached thereto. Such results do not necessarily contain each term in the query or provide relevant information, and are therefore known as "fuzzy" queries. In -8GA&a saaoN, GAGNTh4 t BRIm us ,a (li?, sc-mo WX (6Th 4514313 JAR0002855 Application No.: 08/318,252 Filed: october 5, 1994 Group Art Unit: 2307 contrast, relational algebra expressions return a precise and unaitiguous set of records, each of which is relevant since it satisfies each terni in the relational algebra, and hence there is no "fuzziness" in the relational database model- The claims therefore recite these distinguishing features. For the reasons stated above it is suggested that claims l-17 are allowable, and reconsideration and allowance are respectfully requested. The Examiner is invited to telephone the undersigned attorney to discuss any matters which would expedite allowance Of present application. Respectfully submitted, KBNNTU p. BACLAWSICI By anley M. hurgin Registration No. 20,979 Attorney for Applicant WEINGARTEN, SCRURGIN, GAGNEBIN & HAYES fIL? Ten Post Office Square Boston, Massachusetts 02109 Telephone: Telecopier: Date: StIS/j et (617) 542-2290 (617) 451-0313 {1_f'c( (c 93805 -9 WmNOAM5. ScflUtGOl, CA0N)N * SAVIO 12 171 (617) 303-036 P1 (6)7) 47)-031) JA R 0 002856 RECEWED JU1 -2 91 application Application No. Filed For Examiner Attorney's Docket PATENT : : Kenneth P. Baclawski 06/318,252 October 5, 1994 DISTRIBUTED COMPUTER DATABASE SYSTEM AND METhOD C. Lewis NU-3GOXX * ** *** * * *** **** * ** . * I hereby certify that this correspondence is being deposited with the United States Postal Service as first class nail in an envelope addressed to: BOX NON-FEE AMENDMENT, A ssta t Commissioner for Patents, Washington. D.C. 20231 on S4'y /'- By 4tgin Registration No. 20,979 Attorney for Applicant t ** * t * **t*t*** *** t t***t* tt ** t * * tt AIENDMENT BOX NON- FEE AMENDMENT Assistant Coriraissioner for Patents Washington, D.C. 20231 Sir: In response to the Office Action dated March 21, 1991, reconsideration is respectfully requested in view of the following remarks: JAR0002866 Application ko.: 08/318,252 Filed: October 1994 Group Art Unit: 2307 , Rs Claims l-17 are pending in this application. Applicant is pleased to acknowledge allowance of claims 3-5, 9-fl and 14-16. Claims 1, Kuechler. 2, 6-8, 12, 13 and li have been rejected in view of However, the present invention as claimed is patentably - distinct from kcueehler. As described at various points throughout columns 1-20, Kuechler employs a single node system for storing and manipulating information At column 20, lines 60-68 and column 21, lines l-30 Kuechler discusses a distributed version cf the disclosed method. However, even in this distributed version lcuechler only describes employing the same node as the home node. Hence, Icuechler makes no distinction between a home node and a query node as recited in each of the independent claims of the present invention. In addition to failing to distinguish home nodes from query nodes, Kuechler broadcasts the same query to every processing node (column 21, lines 9-10). Hence, the query is not fragmented as Further, the recited in the claims of the present invention. information elements (i.e., records) are distributed by storing whole records on the processing nodes, elements are also not fragmented. and these information The location of an information element is determined by its record number, not by any information contained in the record. By contrast, the present invention -2WnIOAt,m. auRGD 5A031L0334 a RAYm Ja. 5fl (617) scesO BOX (607) 4)00303 JAR0002867 Application No.: 08/318,252 Filed: October 5, 1994 Group Art Unit: 2307 describes a fundamentally distributed technique, and both queries and objects are fragmented. Zn the present invention query fragments are processed only on the node for which the query fragment is relevant, query fragments are not broadcast to all the nodes, objects are fragmented, and the information content of an object fragment is used to determine on which node it is to be stored. Further, objects are flot stored on a single node Because objects are fragmented and because these fragments are stored independently, objects are distributed over many nodes distinguishing These features are recited in the claims and hence distinguish the present invention from Xuechler. The xuechier concept of a query relational model. is ttte one used by the Such a query is unanibiguous in the sense that every record either satisfies the query or it does not. There is no "fuzziness." The Kuechler query processing technique does introduce additional records that may or may not satisfy the query, but this is done for the sake of improving performance, not because there is any fuzziness in the query. A final filtering step (FigA item 32) removes the spurious records. By contrast, the present "fuzzy" invention employs an intrinsically notion of query. Higher Objects satisfy the query to a greater or lessor degree. levels of service in the present invention are designed to improve the estimates of the degrees by which objects satisfy the query -3 WLNGfljTh. fljUkGIN GAGNESN & '1AY np 75. (on n PM 67 43L0313 JAR00028SO Application No.: 08/318,252 Filed: October 5, 1994 Group Art Unit: 2307 rather than to eliminate spurious objects. Such higher levels of service are optional, whereas the final filtering step of Kuechier is mandatory. Furthermore, the distribution of processing effort for the higher levels of service in the present invention are very different from the distribution of processing effort for the final filtering step in Kuechier. codes (Abstract, Kuechler assigns compact synth'ols or line 7 and column 8, lines 5-7) to ranges of They are attribute values. These codes are assigned unigue codes. very different from hash values, which are computed, not assigned, and which are not unique hashing techniques. Finally, Kuechler does not use any The topological maps of Ruechlar are stored using Some forte of bit map (coluirn 17, lines 51-61) rather than using a hash table. wrloAtm.. smuloot 0AoNWa IoAv54 LI) lfl (60) 542-mo PA)C (307) 00.420 JAR0002869 Application No.; 08/328,252 Piled: October 5, 1994 Group Art Unit: 2307 For the reasons stated above it is submitted that claims 1. 2, 6-8, 12, 13 and 17 are allowable, and reconsideration and allowance are respectfully requested. The Examiner is invited to telephone the undersigned attorney to discuss any matters which would expedite allowance of present application. Respectfully submitted, KENNETH P. BACTJAWSKI 'RSistrat.ioSNo. n yM n i 20,979 eg Attorney for Applicant WEINGZRTEM SCHUROIN, GAGNIEBIN & HAYES LLP Ten Post office Square Boston, Massachusetts 02109 Telephone: Telecopier: Date; (617) 542-2290 (617) 451-0313 SMS/rec 1 015 S 5 5 W51O.*1N, SCMUkOD1. OAONFSIN & llAVES [L? TVt{5') Sfl ?0(Vl1) 451-0313 JAR0002870

Disclaimer: Justia Dockets & Filings provides public litigation records from the federal appellate and district courts. These filings and docket sheets should not be considered findings of fact or liability, nor do they necessarily reflect the view of Justia.


Why Is My Information Online?