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)

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

Oøe

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 anirgoçnatjqn
2
3

er es

-

01e

.

Ser

comprising:

a plurality of hom nodes [node); and

wv»,onnoç scnua.
OACNThDI .Hrnt

FM Cfl

4617 fltÇO

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 * .tçyu

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 whióh 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

processìng 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 relâtional 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:

[phone] [phone]

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-jqçX. 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,
GAGNThÏ4 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

[phone] [phone]

{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

AÎIENDMENT

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 6Ì7 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;

[phone] [phone]

SMS/rec
1 015 S 5

5
W51O.*1N, SCMUkOD1. OAONFSIN & llAVES [L?

TVt{5') Sfl
?0(Vl1) 451-0313

JAR0002870