Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Filing 284

Response to CLAIM CONSTRUCTION BRIEF filed by AOL Inc, Amazon.com Inc., Google Inc., Match.Com LLC, MySpace Inc., Softlayer Technologies, Inc., Yahoo! Inc.. (Attachments: #1 Affidavit, #2 Exhibit 1, #3 Exhibit 2, #4 Exhibit 3, #5 Exhibit 4, #6 Exhibit 5-1, #7 Exhibit 5-2, #8 Exhibit 5-3, #9 Exhibit 5-4, #10 Exhibit 5-5, #11 Exhibit 5-6, #12 Exhibit 6)(Chaikovsky, Yar)

Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Doc. 284 Att. 6

EXHIBIT 5
PART 1 OF 6

Dockets.Justia.com

BTEX0000I 74

120

fu2h-

Foreign

priority

claimed

35

USC

119

COndWons

ysy
met
CI

no

AS
FILED

OR COUNTRY
STATE

SHEETS

TOTAL CLAIMS

ORWGS
.-

INOEP CLAIMS

FILING RECEIVEO

FEE

Verified

and Acknowledged

ATTORNEYS OOCKET NO

Exantnegntuais

cflt.jr

jnn1r
RSSUE FEE IN FILE

I-

u.a

OEPt

OPcOMMJPAT

TMPTO-436L

Racl2-94

PARTS FILED NOTICE

OF APPLICATION
SEPARATELY
ions

Eiier

OF ALLOWANCE

ILEO
HOAitJ
-1-

/CLAIM$

ALLOWED
I.unt Claim

ALkM

q1
ISSUE FEE Amount Due
Date

/9
Sheets

toipltaims

Assistant

Examiner

DRAWING

PaeL

mOWS

B1JkCI

Drwg

Age Drwg

Fi9

ISSUE

Primary

Examiner

BATCH NUMBER

Label Area WARNING

PREPARED
The
by

FOR ISSUE
may be 35 Unaut
18

Information the United

disclosed States

herein
title

restricted

ed 368

disclosure PossessIon

may

be

prohibited the

Code
Office

Sections
to

122

outside only

U-S

Patent

Trademsil

Is

restricted

authorlz

employees

end

contractors

Fomi

PTO-436A
5/52

Rev

CA

flC\

BTEX0000I 75

BAR

CODE

LABEL

HhIll

1100

III

111

IlIIDIllIhI

IW

PATENT APPLICATION

SERIAL

NUMBER

FILING

DATE

CLASS

GROUP

ART

UNIT

08/775864

01/02/97

395

2307

RICHARD

NEMES

BROOKLYN

NY

CONTINUING
VERI FlED

DATA

FOPEIGN/PCT
VERIFIED

APPLICATIONS

FOREIGN

FILING

LICENSE

GRANTED

03/01/97

SMALL

ENTITY

RICHARD
1432
Lu

MICHAEL
35TH NY

NEMES STREET

EAST

BROOKLYN

11234-2604

METHODS HASHING EXPIRED

AND DATA

APARATUS
WITH

FOR

INFORMATION

STORAGE AND

AND

RETRIEVAL

USING
OF

TECHNIQUE

EXTERNAL

CHAINING

ON-THE-FLY

REMOVAL

This Patent

is

to

certify

that

annexed
Office

hereto of the

is

true

and
of the

Trademark

application

of the United copy from the rcords which is identified above

States

By authority COMMISSIONER

OF PATENTS

AND TRADEMARKS

Date

Certifying

Officer

BTEX0000I

76

SEpjA

140

AA

02/28/97

08775864

201

42SOc

ON

flO-1556

5/87

BTEX0000I 77

Plea.

1e

pin

Sgnj
Reduction Act
of

11
1995 no penons

1w Apprewed ittademaft QeIre

is

Uvough

WJWPa
vetS

U.S DOfrRTKCHT CF
dionieva

049

lb Paoe.wat

as isouSd

to

tnpcnd toe ooltecllnlwvneUon

usia

casicRc toInu floe

AUomey

DS

Number

775
22 /Alia4
.7L

64

NEW
tie

UTILITY

PLICATION

PATENT TRANSMITTAL
Wit

First

Named

Inventor

____________
Total

________________
-I

tiwn.wappe

Pages

in

this

tiisat

sJ1rfeJS

Dninc.s

APPLICATION
haidct
Checkilsf

ELEMENTS ACCOMPANYING
APPLICATION

Swis mwiedned Eemenn Appilcabon action smjcte new usMy patent Please Wee to applicant MPEP Sections 506 601 37CFR 1.71 1.53 35 usc 111 112 Ar beta/led Of an onpinal paIwi exptansflriugatntng il.nsss
app/catton

PARTS

Fee Tiznsmlttal
Specification

Fomi prescribed

tiling

fees

Assignment

Paped

Certified Title

Copy

of

Priority is

Documents

of the

Invention

foreign pnonty

claimed

Cross

References

to

Rated

Applications

Computer Program

in

Microfiche

applicable Statement Regarding Federalty.sponsored English Research/Development applicable Translation

Document

applicable

Reference

to

Microfiche

Appendix 10

Information

Disclosure

ri
L......J

Copies
citations

of

CS

applicable

StatemenuPTO-i9

Background

of the

Invention

11

Petition

Checklist

and Accompanying

Petlion

Brief

Summary

of

the

Invention Preliminary

Amenoment

Brief

Description
filed

of the

Drawings

13

Proprietary

Information

drawings

CfI

Detailed

Description

14

Return

Receipt

Postcard

Claim

or

ClaIms

15

Small

Entity

Statement

Abstract

of

the

Disclosure

16
as prescribed

E1

Additional

Enclosures

please

identify

b.lotq

IJ
Genetic

Drawings 35 USC 113

when

necessary

by

LISP

REPERi5

Executed

Dlantion

Sequence
ii

Submission

SIGNATURE
Firm

OF APPLICANT

A1TORNEY

OR AGENT

if applicable

must be indudeo9
or
lndividuaj

Paper

Copy

RICHAR
name

NEMES

Computer
statement

Readable

Copy
Slgia/ure
Identical

Verifying

Paper

and
Date

Computer

Readable

Copy

DECEMBER

20

1995

FOR OFFICIAL USE ONLY
Application

Number
class Independent Claims

Date

of Receipt

Application

TYej

GAU

Total

claims

Filing

Date Foreign
Filing

LicerSe

Drawing

Sheets

Small

Entity

Foreign

Address

Special

Handling

Suroen
Inc

Hour

Statement
ol time

This loan
are required

estimated to

to

tale this

0.2

hours

to

complete
sent to the

Time

will

vary

depending
Officer

upon

the

needs and

amount

ol

the

individual Office

4t

you

complete

loan THIS

case

ahould be

Any remments

Chief

Information

FEES

OR COMPLETED

Patent for

FORMS TO

ADDRESS

Trademark Washington

SEND

To

Washington

Assistant

DC 202

Commissioner

Patenis

DC 20231

BTEX0000I 78

FEE CALCULATION
The Conimlseloner
SaSated fees end
Is

continued

hereby

tlhothad

to

dwgs
to

ndll any

as

ADOm0NAI
Cods 106 124
130 205 60

FEES
bssaipdon
SwSwpe-Ssflhingf.sroMh Swdierge
las pr5Asiotal

p......nla

Accounif Number
Account

Nina

Vi uo
i3
147

25

titan9

In

or

os
Fe R.qus4
tIC
and

ens
Mde.nI
User 37

ie

11

td

1.1$

ST ii Unis Fat act at Ta State sat
ti

129

130

Non.Engiih.p.citaticn For l%ng r.qunl
for

AWs

37

1412.460

L460 900

fnaminauon

1.311b 112 900 112

Enclosed
crtaac

ReqtnsllngpublatoncWSlRpnoto
.edcn

Dottier
tees
effectIve

113

17W
110 390 930 1.470 300 300 260

113

1.7W

Requnteig

publiention action

SIR

Slot

amrna FEE CALCULATION
FILING FEE
large Pee
EntIty

1010196

115 116 111

215 216 217 216 219 220 221

56 195 465 736 150 150 130

btenSenSrsspons.vsithinSstmonth En.nsicntora.pont..wWhinncondmw Eidsntionterresponsewdhlnf$dmosh EnteSon Sr rapone
althln

Small

Entity

Ft
770 320 530 170 150

Pa
Cods
201 206 201 203 214

Fee

Pee

Osawlpton

Pa

116 Paid 119

loutS

moit

Code
101

NSic.dA.S

345 160 255 355 15

UtllttyIThngfn

120 121 136

flngaSkisupponoansppni
aqu.atrosbeavtng PMMSatiatAlaeapublictas.pqoonet5
P.dIfon
to

106 107 ios 114

Deelgnl%llngtee PIenIfIllngfn RelseusIllIngle

1470
110

1331470
240 65

140
PrctIslonslflhlngfee

rwwn

unavoidably

sb.ndonS

141

SUBTOTAL

1290

241

646

PMiSai

to

ran

uninl.nhionalty

385-

.bendsn.d 142

ppMion
or r.rasu

CLAIMS
Toticlaims Indepenosnt

Extra

Pm

1.20

242 243 244

645 220 325

tiflufy

Satan

Fee

Paid

143440 144650

Daign Satiate
Plait

_3

.ZOs

___ .3
Claims

sa In
to the

Multiple

Dependent

____X

tfb

122130

122130

Petitions

Csnmsaioaar
to

12350
126230

12350
126 230

Petitions

mated
of

pnMsion.l

applications

Sutonission

Woonalon
latent fltfltat

Disclosure

Stied

large

Entity

Small Pee

Entity

$n
Code
103 102 104 109

Fe

Pee

Pa

531 Dsactptton

40

531

40

Code
22 60 260 50 203 202 204 209
11

nde PIUyIW Sass
R..ennIl flIng

sssignmsd per

PM be
ejection to

Clalsnslqessoeeaof2o

146

170

246

365

sdsniseion

oiler

final

40 130 40

lnda.aisl.ritdSnakeaancf3
PAillIplsdep....d.lclalm

31 CFR
149 770 249 335 For adaed

1.1
.thMl....J

knentlon

be

R.iseu independent

Sims
Other Other
fee

31 01R

1.129b

as
11

110

22

210

Rnasssm.ans20
atS over petal

scsdfl

spe
SUBTOTAL
by Basic fling

SUBTOTAL

fs

4o
Raduosd

Fe

PSS

5UBMrrrfD
Typedor
Pflnted

BY

Name

RICHARD
_j

NEIvtES

Signature

$1
This
of

oat nanted
sit

DEC
QUiZ
to the

20
II901 the

Button comments

flout

Statement
the

loon

is

to

take to

0.2

hours
thIs

to

osmose
elmuld

Time
be
sent

vat

deoending

on

amount

tim

needs

it odisus
Patent asS

required

oompls

form

Washington

DC 20231

DO NOT SEND PUS OR COWLETED

FORMS TO

ThIS

0151 Soonatlor ADDRESS SEND TO

an

My

OfIloer Assistant

Tiadenarit

Dittos

Commiss5e

for Patents

BTEX0000I

79

zo
Patent Application of

jq

864

Richard

Nemes

1432 East

35th

Street Brooklyn
Citizen

New

York 112342604
of America

U.S.A

of the United

States

SPECIFICATION

to

TITLE OF INVENTION

METHODS

AND

APPARATUS

FOR

INFORMATION

STORAGE

AND

R1kIEVAL USING

HASRING TECHMQIJB

WITH EXTERNAL CHAJNThTQ

AND

ON-THE-FLY

REMOYAL OF EXPIRED

DATA

15

CROSS-REFERENCE TO RELATED APPLICATIONS
Not
Applicable

STATEMENT DEVELOPMENT
20

REGARDING

FEDERALLY

SPONSORED

RESEARCH

OR

Not Applicable

REFERENCE

TO

MICROFICHE

APPENDIX

Not Applicable

25

BACKGROUND OF THE INVENTION
This invention
relates to

information

storage

and

retrieval

systems

and

more

particularly

to

the use of hashing techniques
stored in

in such

systems storage mechanism can be
retrieved

Information or data

computer-controlled
stored

by searching
30

for

particular

key
is

value in the

records

The

stored

record

with

key

matching
to

the search key

value

then retrieved

Such

searching techniques

require repeated and

access

records into the storage systems such searching

mechanism
even
if

to

perform

key

comparisons In

large

storage such

retrieval

augmented by

efficient

search procedures

as the

BTEX0000I 80

Richard

Nemes

binary search comparisons

often

requires

an

excessive

amount

of time due

to

the

large

number

of key

required and

Another well-known computer
technique
is

much

faster

way

of storing

and

retrieving

information

from

storage
also called

albeit

at

the

expense

of additional

storage

is

the

so-called

hashing

scatter-storage

or key-transformation method
to

In such

system the key
called

operated

on by
which

hashing fUnction
is

produce

storage address in the storage space
array

the

hash table

large

one-dimensional record

of record

locations

This

storage
in the

address

is

then accessed

directly

for the

desired

Hashing

techniques

are

described

classic

text

by

Knuth

entitled

The

Art of Computer Massachusetts

Programming 1973

Volume

Sorting

and

Searching

Addison-Wesley
flmctions

Reading

pp 506-549
of keys
into

Hashing
distributed

are designed

to translate the universe

addresses unifonnly truncation folding
will

throughout and

the

hash

table

Typical

hashing

functions

include

transposition

modulo arithmetic
in the

disadvantage

of hashing

is

that

more than one key

inevitably

translate

same storage address causing collisions
be provided forward

in storage

Some form
called

of

15

collision

resolution

must

therefore

For example the simple strategy from
the initial

linear

probing

which

consists

of searching

storage address to the

first

empty

storage location

is

often

used
for resolving collisions
is

Mother
each hash
table

method
location

called

external

chaining
of records

In this technique
all

is

pointer

to

the

head

of

linked

list

of whose keys
list is itself

20

translate

under

the

hashing function to

that

very hash

table

address

The

linked

searched

sequentially

when

retrieving

inserting

or deleting

record
is

Insertion

and

deletion

are

done by
in the

adjusting

pointers

in the linked

list

External chaining
in

discussed in considerable

detail

aforementioned

text

by

Knutli

Data Structures and Program Design Englewood
of flashing
Cliffs

Second 1987 Data

Edition
25

by 6.5

Kruse

Prentice-Hall and Section

Incorporated

New

Jersey
in

Section

Hashing
with Abstract

6.6 Analysis and Pascal

pp
Stubbs

198-2

15 and

Structures

Data

Types

by

and

Webre
7.4

Brooks/Cole

Publishing

Company

Monterey

California

1985

Section

Hashed

Implementations pp 310-336

Some
30

forms of information are such and

that

individual

data items
is

after

limited

period

of

time become

obsolete

theft presence

in the

storage

system

no longer needed or desired

BTEX0000I

81

Richard

Nemes

Scheduling

activities

for

example involve data
data

that

become
it

obsolete

once the scheduled
occupies

event

has occurred

An

automatically-expiring

item once put to

expires needlessly an unexpired
for

computer

memory

storage

that

could be

otherwise

be

use storing
the

item Thus expired
data
insertions

items must eventually addition
linked the

removed

to

reclaim

storage

subsequent long

In the

presence

of many

expired

items results in needlessly
will be

search times since

lists

associated

with external

chaining

longer than they otherwise and maintain
fast

would be The
to

goal

is

to

remove

these

expired

items

to reclaim

the storage

access

the data
for large

The
heavily

problem then

is

to

provide

the

speed

of access

of bashing techniques
at

used information

storage

systems having expiring

data

and

the same

time prevent the
records

10

performance

degradation technique
for

resulting

from the accumulation data

of many
and

expired

Although
Patent

hashing

dealing

with

expiring

is

known
is

disclosed

in

U.S

Number 5121495
entirely inapplicable

issued

June

1992

that

technique

confined

to

linear

probing

and

is

to external

chaining

The procedure shown
in the

there

traverses in reverse order continually

consecutive

sequence
fill

of records

residing

hash

table

array

relocating

15

unexpired

records to

gaps
linked

left

by the removal
leave

of expired

ones
items

Unlike furthermore

arrays
is

lists

no gaps

when
singly

from
list

it

are

removed

and

it

not possible
to

to

efficiently traverse

linked

in reverse

order There
it

are

significant

advantages

external

chaining

over linear probing

that

sometimes make
texts chaining
are

the

method of choice
20

as discussed

in considerable

detail

in the aforementioned

and so bashing
prove wholly

techniques inadequate

for

dealing

with

expiring

data that For

do not
if

use

external

for

certain

applications

example

the

data records

large

considerable

memory can be saved using
need
to

external

chaining

instead

of linear probing with expiring be used

Accordingly

there

is

develop

hashing techniques
are

for external

chaining

data The
with linked

methods
lists

of the
to

above-mentioned

patent

limited

to

arrays

and

cannot

due

the

25

significant

difference

in the

organization of the computers

memory

BRIEF

SUMMARY
In accordance

OF THE INVENTION
with the
illustrative

embodiment
collection

of the invention

these

and

other

problems are overcome

by using

garbage
are

procedure

on-the-fly while other types
during normal data insertion or

so

of access

to

the

storage space

taking

place

In

particular

4/
BTEX0000I
82

Richard

Nemes

storage system in accordance

with the present invention flow chart
for

and

FIG
hashed

shows

general

record

deletion

operation

that

might

be used

in

storage system in accordance
facilitate

with the present
identical

invention numerals used to designate

To
elements

reader understanding
to the figures

reference

are

common

DETAILED
FIG
comprising
to

DESCRIPTION
of the drawings
Central

OF THE 1NVENTION
shows
general block 10 and 11 diagram of

computer hardware system

Processing Unit
stored in the

CPU
RAM
stored

Random
accessed

Access

Memoiy
10 and

RAM

unit

11
one

Computer
instruction

programs
at

are

by of

CPU

executed
operated

time by
instructions

CPU

10 Data
by

in other portions

RAM

11

are

on by

the program

accessed

CPU

10 from

RAM

11

all

in accordance

with well-known

data processing

techniques Unit
data

Central Processing
15

CPU
stored

10 also

controls

and

accesses

disk controller such

unit

12

that in turn
unit

accesses

digital

on one or more

disk

storage

units

as

disk storage

13

until

required

by

CPU 10
and

At

this

time such programs
11
for rapid

and

data are retrieved

from

disk

storage unit

13

in blocks

stored

in

RAM
also

access

Central

Processing Unit
to

CPU 10

controls

an InputlOutput
as

I/O

controller

14 that terminal

in turn

provides access

plurality

of input

devices such

CRT

cathode
15

ray tube

20

15
for

as well

as

plurality of output

devices

such as printer and

16 Terminal
into

provides

mechanism

computer

user to introduce

instructions

commands

the computer system of tape readers 16

FIG

and

may

be supplemented

with other input and
other

devices such

as magnetic

remotely

located

terminals

optical readers

types

of input

devices

Similarly printer

provides
for the

mechanism
25

for displaying

theresults

of the operation

of the computer system of by and and

FIG

computer
displays

user

Printer

16

may

similarly be

supplemented

line printers cathode

ray tube devices

phototypesetters

laser printers

graphical

plotters

other types of output
their cooperative

The well-known
to large

constituents

of the computer system of
are typical

FIG

operation

are

in the

art and

of all computer systems from small personal
and
operation

computers and

mainframe systems The architecture be further described here

of such

systems are well-known

30

will not

BTEX0000I 83

Richard

Nemes

FIG
system such

shows
as that

graphical

representation

of

typical

software architecture

for

computer mechanism

shown
personal

in

FIG

The software of FIG may
to consist

comprises

user access

20 that
In

for simple

computers
service

of nothing

more than turning the system on
and

larger

systems be

providing

many

users

login

password
user access

procedures

would 20 has

typically

implemented the

in user

access

mechanism 20 Once
is

mechanism

completed

login

procedure

the

user

placed of

in

the

operating

system

environment

21
the

Operating

system

21

coordinates

the and

activities

all

of the

hardware

components

of

computer to the

system

shown
user

in

FIG

provides

number of example
and

utility

programs 22 of general use
basic
file

computer

Utilities

22

might

for

comprise

access

and

10

manipulation

programs system maintenance

facilities

programming language
also

compilers

The
such
as

computer software system of FIG
software

typically

includes

application

programs
for

application

23

24

25

Application formatting

software

23 through

25 might program

example
database

comprise

text

editor document

software

spreadsheet

management The
present

system
is

game

program and
with

so forth

is

invention

concerned

information

storage

and

retrieval

It

can

be

application

software packages

23-25 or used by other
software

parts

of the system

such

as user

access

software 20 or operating provided by the present

system 21
invention

The information storage and
disclosed as flowcharts in

retrieval

technique and

are

herein

FIGS

through

shown
20

as

PASCAL-like

pseudocode

in the

APPENDIX

to

this specification

Before proceeding to
useffil

description

of one

embodiment

of the present invention
for

it

is

first

to

discuss

hashing techniques
in

in general

Many

fast techniques

storing

and

retrieving

data

are

known

the prior art In

situations

where storage space
is

is

considered

cheap each

compared
record
in

with the

retrieval

time

technique

called

hashing

often

used

In

classic

hashing
in value

information

storage
is

system includes

distinguished

field unique

to each

record

25

called

the

key which

used as the basis for storing
is

and

retrieving

the associated

record

Taken

as

whole

hash table

large one-dimensional
units

array

of logically
is

contiguous stored
in

consecutively 11

numbered
where

fixed-size

storage

Such

table

of records

typically

RAM

of FIG
bashing
into

each

record

is

an

identifiable

and

addressable location

in physical

memory
as an index be

fi.tnction

translates

the

key

into

hash table

array

subscript which

is

used

the

30

array

where searches

for the

data record

begin

The hashing fbnction can

any operation

on

BTEX0000I 84

rnchd

Netnes

the key that

results

in subscripts

mostly uniformly

distributed

across the table

Known

hashing of

fUnctions

include

truncation

folding

transposition

modulo
generally

arithmetic

and

combinations

these operations
in

Unfortunately
in

hashing functions keys

do not produce
producing hashing

unique

locations

the hash table

that

many

distinct

map

to

the

same location
in
all

what

are

called

collisions

Some form
of collision
the alternate

of collision an

resolution

is

required
for

systems In every
is

occurrence

finding

alternate

location

collided

record

necessary
for

Moreover

location

must be

readily

reachable

during

future

searches

the

displaced record

common
10 is

collision resolution

strategy

with which the present invention each hash
table

is

concerned
all

called

external

chaining
at

Under
location

external

chaining

entry stores but instead

of the
pointer the

records that to the head

collided

that

by storing not the records

themselves
lists

of

linked

list

of those same records
allocated

Such

linked

are

formed by
each

storing

records individually
to the location

in

dynamically

storage and

maintaining records

with

record

pointer
is

of the next record

in the

chain of collided used to

When

search key
If the

hashed

is

to

hash table entry the pointer
the key

found

there

is

locate

the first record

search key
this

does not match
the

found
is

there the pointer
traversed

there

is

used

to

locate

the second record

record In

way
end

chain

of records
is

sequentially

until the desired

is

found or

until the

of the chain

reached

Deletion of records

involves

merely

adjusting

the pointers to bypass storage pool maintained

the deleted

record and

returning

the storage

it

occupied

to the available

20

by the system
flashing

techniques

have

been

used

classically

for very fast

access

to

static

short

term

data

such as
the need

compiler

symbol table

Typically

in such

storage

systems

deletions

are infrequent

and

for the storage

system disappears quickly system
is

In

some common
can

types of data storage obsolete merely by

systems however
25

the

storage

long lived and of some

records

become
expired

the passage

of time or by the occurrence

event

If such

lapsed

or obsolete

records are not removed from the system they will in time seriously of the records
retrieval

degrade

the performance

system Degradation
search times since

shows up
they cause

in

two

ways

First the presence chains to be longer

of expired
than they

lengthens

the

external

otherwise would be could be returned

Second
to the

expired

records

occupy pool

dynamically allocated allocation

memory

storage that the system

30

system

memory

for useful

Thus when

BTEX0000I85

Richard

Nemes

memory memory

pool

is

depleted by an

new

data item can

be

inserted

into

the storage

system

only if the

occupied

expired

one

is

reclaimed

Referring then to
the hash table

FIG

there

is

shown

flowchart of

search

table

procedure

for

searching

preparatory

to

inserting

retrieving

or deleting

record
records

in accordance

with the present linked
list

invention
in

and

involving

the dynamic

removal

of expired of FIG

in

targeted

Starting

box 30 of

the

search table

procedure

the search key of the of an array element
is

record

being searched
the hash table

for is hashed

in

box 31

to

provide

the subscript generated

In

box 32
to

array

location

indicated

by the subscript Decision

in

box 31

accessed

provide

the pointer

to

the target

linked

list

box 33 examines
reached
If the

the pointer value to has

io

determine

whether
is

the

end

of the linked

list

has been

end

been reached box 39 box

decision

box 34
be

entered

to determine

if

key

match was previously found
is

in decision

as

will

described

below

If

so

the

search

successful

and
If

returns

success
is

in

35

followed

by the procedures termination
and of the
the

in terminal

box

37

not box 36

entered

where

failure is returned

procedure

again terminates in box reached

37
box

is

lithe

end

list

has not been

as determined by decision

33

decision

box

38

is

entered

to

determine

if

the record

pointed

to

has expired
external

This

is

determined

by comparing
in the

some

portion
for

of the contents of

the

record

to some
the

condition

timestamp maintained

record

example could be compared with
Alternatively
the record In the

current

time-of-day value be compared with

by

all

computers
20

occurrence
if

of an event

can

field identiijring

that

event

in

any case

the record

has not expired
If

decision

box 39

is

entered

to

determine saved

if

the

key in this record

matches entered

the

search key record

it

does
not

the address of the record

is

in

box 40 and

box 41

is

If the

does

match the search key the

procedure forward
to

bypasses

box 40 and proceeds
in

directly

to

box 41 In box
procedure under

41

the procedure to box

advances

the next record

the

linked

list

and

the

returns

33
box 42
list is

25

If decision

box 38 determines
the on-the-fly occupies
to

that

the record

question

has expired

entered

to

perform

removal

of the expired

record

from the linked
described

and the

return

of the storage

it

the

system storage pool as will be

in connection

with

FIG

In

general the remove
list

procedure of box 42 predecessors

FIG
to

operates to remove bypass
that

an

element

from the linked

by adjusting
is

its

pointer

element

However

if

30

the element to be

removed

the

first

element of the

list

then there

is

no predecessor

and the

/7 BTEX0000I 86

Richard

Nemes

hash

table

array

entry

is

adjusted instead
returns

On
to

completion

of procedure

remove invoked\

from

box 42 the search
It

table

procedure

box 33
of

can be seen that the search tab/c of records of which

procedure record

FIG
part

operates to and

examine the
expired
is

entire

linked

list

the

searched-for

is

to remove

records and of

returning

storage to the storage pool records remain despite

with each

removal

If the

storage

pool

depleted

many new

expired

such 77

automatic of

garbage
until

collection
deletion
is

then the insertion

records

is

inhibited

boxes 76 and

FIG

made by

the delete

procedure

FIG
its

or

until

the search table

procedure has had

chance

to

replenish

the storage

pool through
10

on-the-fly

garbage

collection

Though
as

the search table

procedure as shown and described above

in

FIG

implemented
in connection

in the

APPENDIX

PASCAL-like
and

pseudocode

appears

with

an information
its

storage removal

retrieval

system using the

hashing technique
linked
list

with external

chaining linked

on-the-fly

technique
data

while traversing appears even

can

be

used

anywhere
person
linked

list

of records
art will

with expiring
is

in contexts

unrelated

to

hashing manipulate

skilled

in the

appreciate used

that

this technique

can

be readily

applied

to

lists

not necessarily

with hashing

The

search and

table

procedure

shown

in

FIG
entire

implemented
linked
list

as

pseudocode
all

in

the

APPENDIX
as
it

described above traverses

the

removing

expired

records but not

searches

for

key

match

The procedure

can

be readily
list

adapted

to remove time and

some

20

all

of the expired

records

thereby shortening

the linked

traversal

speeding

up the
the

search at the

expense

of perhaps
to

leaving

some

expired

records

in the

list

For example

procedure
for this

can be modified
version

tenninate

when
appears

key match occurs PASCAL-like pseudocode
in

alternate

of search table

the

APPENDIX
dynamically expired

The
at

implementor

even

has

the

prerogative

of choosing

among

these strategies removing

the time search

table

is

2$

invoked

by
but

the

caller

thus sometimes

all

records

at

other times removing

some

not

all

of

them

and

yet

at

other times choosing

to

remove none of them Such example how much memory
the number and

dynamic
is

runtime

decision

might be

based

on

factors

such

as

for

available

in

the

system storage pool general system load
in

time of day

of records
to

currently

residing

the information

system and
itself

other factors

both internal

external

the

30

information

storage

and

retrieval

system

person skilled

in the

art will appreciate

that

the

-.9

/0
BTEX0000I 87

ID
Richard

Nemes

technique include

of removing

all

expired not

records while searching the linked
all

list

can

be expan4ed
and
that

to

techniques

whereby
if

necessarily

expired can

records be

are

removed

the

decision regarding
In

and

how many
shown

records to of

delete

dynamic one
that

FIG

there

is

flowchart

remove procedure
through
the delete

removes

record

from
noted
in

the retrieval
in

system

either

an unexpired

record

procedure
table

as will be

connection

with FIG.7

or an

expired record
this is

through

the search

procedure

as

noted

connection with

HG

In general

accomplished

by the invoking

procedure being
passing to

either

the

delete

procedure
to

FIG
linked

or the search table

procedure

FIG
to that

the remove

procedure
10

pointer

list

element to remove
the subscript

pointer

elements predecessor
location

element in the same linked
to the

list

and

of the hash table

array

containing

the

pointer

head

of the

linked

list

from which the element element of the linked

is

to

be

removed

In the case that

the element to be

removed

is

the

first

list

the predecessor

pointer passed

to

the remove procedure

by the invoking to the

procedure

has the

NIL sometimes
to

called

NULL

or

EMPTY
15

value
in

indicating

remove procedure
procedure
that

that

the element

be

removed

has no

predecessor
to

the list

The

invoking

expects the remove
to the

procedure on completion
element so that
final

have

advanced

the passed

pointer

originally pointed

now-removed removed

it

points

to

the successor

element

in

that

linked

list

or

NIL
in

if

the

element was the

element

The

search

table

procedure

of

FIG

particular

makes use
is

of the remove
that

procedures
20

advancing
is

this

passed

pointer

in the

described

way

it

made use of in was

box 33
in

of

FIG

entered

directly

following

completion

of box

42

as

described

above

connection

with

FIG
procedure causes actual so
that
it

The remove
predecessor predecessor
pointer

removal of the designated the element
to

element by adjusting In the case
that

the the

bypasses value

be

removed

pointer has

the

NIL

the

hash

table

array

entry indicated
the

by the passed
in its

25

subscript plays Following

the role of the predecessor adjustments
the

pointer

and

is

adjusted

same way
is

stead the

pointer

storage occupied

by

the

removed element

returned

to

system storage pool for future Beginning
is

allocation

then

at starting

box 50 of FIG
to
its

the pointer

to

the

list

element to remove decision

advanced

in

box 51

so that

it

points

successor in the linked

list

Next

box 52
testing

30

determines

if

the

element to remove

is

the

first

element in the containing

linked

list

by

lo
ll

BTEX0000I 88

Richard

Nemes

the predecessor

pointer

for the

NIL

value

as described

above
bypass

If

so box 54
first

is

entered

to adjust

the linked

list

head

pointer

in the

hash table

array

to

the

element

after

which the
pointer
is

procedure adjusted
to

continues

on

to

box 55

If

not box 53

is

entered where the predecessor the procedure

bypass

the

element to remove 55
the storage

after which

proceeds once again
is

to

box

55

Finally in box storage pool and

occupied

by the bypassed

element

returned

to the

system

the procedure
detailed

terminates in terminal

box 56
suitable for

Fig

shows
and

flowchart

of

an

insert

procedure

use

in

the

information storage begins
10 at

retrieval

system of the present

invention In box be

The

insert

procedure

of

FIG

starting

box 71 from which

box 71

is

entered

71

the search

table procedure
in connection

of FIG
with

is

invoked

with the search key
table

of the record

to

inserted

As

noted

FIG

the

search

procedure
the search

finds the

linked

list

element whose

key value of the
expired records whether

record contained therein

matches

key and at the same time removes
is

on-the-fly

from that linked

list

Decision

box 72

then entered where key value

it

is

determined

the search

table

procedure

found

record

with matching
list

If

so box 73

is

entered

is

where

the

record to be inserted value

is

put into the linked
the insert

element in the position
that

of the old record
has been

with matching

key

In

box 74

procedure

reports

the old record

replaced

by the new rebord and
to decision

the procedure

terminates in terminal record

box

75
decision

Returning
entered

box 72
sufficient

if

matching

is

not found

box 76

is

to determine

if

there

is

storage in the system storage pool entered to report
the that the storage

to accommodate and the

20

new

linked

list

element be

If

not box 77

is

system

is full

record

cannot

inserted Following

that
that

procedure

terminates in terminal box be allocated

75

If decision

box 76 determines

sufficient

storage can
is

from the system

storage
allocation

pool
is

for

new

linked

list

element record to

then box 78 be inserted

entered where

the actual

memory
in

made

In box

79

the

is

copied into

the storage

allocated

25

box 78 and
into
it

box 80
is

is

entered

In

box 80 the
the linked

linked

list

element containing

the record

copied

in

box 79

inserted

into

list

to

which the contained
into the

record

hashed
and

The

procedure

then reports and

that

the

record was

inserted

information storage

retrieval

system in box 81

the

procedure

terminates

in

box 75
procedure
in

FIG
so

shows

detailed

flowchart

of

retrieve

used

to

retrieve

record

from of

the information storage

and

retrieval

system

Starting

box 90

the search

table

procedure

11

BTEX0000I 89

Richard

Names

FIG
decision

is

invoked

in

box 91 using
if

the

key

of the record with

to

be

retrieved

as the search key

In

box 92
If

it

is

determined 93

record

matching
failure

key of the

was found
retrieve

by the search procedure
is

table

procedure

not box
in

is

entered

to

report

and

the

procedure terminates

terminal

box 96
record

If

matching

record

was found box 94
calling

entered to

copy the matching
entered to return

record

intO

store

for processing

by the

program

box 95

is

an indication

of successful

retrieval

and

the procedure

terminates in terminal

box 96 FIG.7 shows
records of
detailed

flowchart of

delete

procedure

useful

for

actively

removing

from the information storage and
invokes the search table

retrieval

system
in

Starting

at

box 100 the procedure

FIG

procedure
In decision

of FIG box

box 101 using the key of the record
it

to be deleted

as

the

search key
find

102
key

is

determined

if

the

search

table

procedure
failure

was

able

to

record

with and

matching

If

not box

103

is

entered

to

report

of the

deletion

procedure

the

procedure

terminates in terminal

box

106

If

matching
is

record was found as determined
in

by decision

box 102

the

remove procedure
procedure

of FIG
causes then

15

invoked

box 104 As noted
linked
list

in connection

with

FIG

the remove
linked

removal entered

of
to

designated

element

from

its

containing

list

Box 105

is

report successful

deletion

to

the

calling

program and

the procedure

terminates in

terminal

box 106 The
attached

APPENDIX

contains

PASCAL-like

pseudocode

listings for

all

of the

20

programmed
operating have

components

necessary to

implement invention

an information

storage and

retrieval

system
art will

in accordance

with the present

Any

person

of ordinary

skill

in the

no

difficulty

implementing
all

the disclosed

system and and

procedures

shown

in the

APPENDiX
on the
basis

including programs for

common

hardware

system software

arrangements

of this description
25 It

including

flowcharts and

information shown
in the art that

in the

APPENDIX
of the present
of the used

should also be

be

clear

to

those skilled

other embodiments

invention

may

made by those
It is

skilled

in the

art without

departing
art that

from

the

teachings be

present diverse

invention

also

clear

to

those skilled

in the

the invention can use

in

computer applications
to

and

that

it

is

not

limited

to

the

of hash

tables

but

is

applicable

other techniques

requiring

linked

lists

with expiring

records

30

12--

BTEX0000I

90

Richard

Names

Appendix

Functions

Provided

The

following

functions are made

available

to

the

application

program

insert

record

record

type

io

Returns

replaced

if

record

associated

with

record key

was

found

and

subsequently

replaced

Returns passed
15

inserted record

if

record

associated

with record key was

not

found

and

the

was subsequently inserted

Returnsfiill

if

record

associated

with record

key was not found
is

and

the passed

record

could not be inserted

because

no memory

available

20

retrieve

record

record_type

Returns success

if

record associated

with record

key was

found

and assigned

to

record

25

Returns failure

if

search was

unsuccessthl

delete

record_key

record

key

type

30

Returns quently

success deleted

if

record

associated

with

record_key

was

found

and subse

Returns failure

if

not found

35

Definitions

The

following

formal definitions

are required
all

for specifing

the insertion

retrieval

and

deletion

procedures
40

They

are

global

to

procedures

and

functions

shown below

13

BTEX0000I

91

fl

Richard

Nemes

const

table_size

ft

Size of hash

table

type

list_element_pointer

list_element

Pointer

to

elements

of linked

list

type

list_element

Each element

of linked

list

record record_contents next
10

record

type
Singly-linked list

list_element_pointer

end

var table array

table_size

of list_element_pointer
/t

ft

Hash table
of list

Each

array

entry

is

pointer to head

is

Initial

state

of table

table

nil

table

size

Initially

empty

Insert
20

Procedure

function

insert

record record_type

replaced

insertedfu/l

var position

list_element_pointer

ft

Pointer into
ft

list

of found
if

record

tf tf

or new

element

not found

25

dummy_pointer

list_element_pointer

ft

Dont

need positions

predecessor

tf

index 0.

table_size

Table

index mapped

to

by hash

function

tf

begin
30

if

search_table

record key position

dummy_pointer

index

It

Record

already exist

then

begin

ft

Yes

update

it

with passed

record

tf

35

position

.record_conents

record

return

replaced

end
40

else

ft

No

insert

new record

at

head

of list tf

14
._/

BTEX0000I

92

Th

Richard

Nemcs

if

no memory

available

then

return

full

if

memory

available

to

do

so

else

begin

/4

Memory

is

available

for

node

4/

newposition

Dynamically

allocate

new node

position

.record contents

record

/4

Hook

it

in

position
10

.next

table
position

table
return

inserted

is

end

/4

else

begin

4/

end

insert

20

Retrieve Procedure

function

retrieve

var record

record

type

successfailure

25

var position

list_element

jointer

Pointer

into

list

of found

record

4/

dummyflointer

list

elementjointer

/4

Dont

need positions

predecessbr

4/

dummy_index
30

table

size

/4

Dont

need

table

index mapped

to

by hash

tbnction

begin

if

search

table

record key position

dummyflointer dummy_index

/4

Record exist

35

then begin

/4

Yes

return

it

to

caller

4/

record

position

.record_contents

return
40

success

end

l5

BTEX0000I

93

fl.

Richard

Names

else

return

failure

/5

No

report

failure

end

/5

retrieve

Delete Procedure

function
10

delete

record_key

record_key_type

success failure

var position

list_element_pointer

/5

Pointer

into

list

of found

record

previous_position

list_element_pointer

/5

Points to positions

predecessor

is

index

table_size

Table

index mapped

to

by hash

thnction

begin

if

search_table

record_key

position

previous_position

index

Record

exist

5/

20

then

begin

rn

Yes remove

it

remove position

previous_position

index

25

return

success

end

else
30

return

failure

No

report

failure

end

delete

5/

35

Search

Table

Procedure

function

search_table

record_key var position

record_key_type list_element_pointer list_element_pointer

var previous_position
40

var index 0.

table_size

boolean

16

/7
BTEX0000I
94

Richard

Nenwa

/4

Search point
to

table for record_key

and

delete expired
to

records
its

in

target list

if

found
is

position

is

made

to

located record and previous _position
is

predecessor
that is

and

TRUE

returned

otherwise
in either

FALSE
case

returned

Index

is

set

to

table

subscript

mapped

to by hash function

var

list

_element_pointer

Used

for traversing

chain

previous_p

list_element_pointer

/4

Points

to

ps

predecessor

io

begin

index

hash record_key

hash

returns

value

in the

range

0.

table_size

table
15

Initialization

before loop

previous_p

nil

/4

Ditto

position

nil

/4

Ditto

20

previous_position

nil

Ditto

while

nil

H_______F __________TOIJE _ EART O _ TI-IF TECHN ___

Traverse

jjj

list deleting

4/

expired records as

we

search

begin
25

ifpl .recordcontents

is

expired

then

remove

previous_p

mdcx

rn

01-THE-FLY

REMOVAL

OF EXPIRED

RECORD

30

else

begin

if position

nil

then

ifpl .record_contentsicey

record

key
/4 If this
is

record wanted 4/

then
35

begin

position

previous_position

previous_p

end
save
its

position
to

4/

previous_p

/4

Mvance

pI
40

next

next record

4/

end

else

begIn

4/

end
17--

/7
BTEX0000I 95

Richard

MNcmes

return

position

nil

/t

Return

TRUB

if

record located

otherwise

FALSE

end

/t

search_table

Alternate

Version of Search

Table

Procedure

function
io

search

table

record

cey

record_key_type list_element_pointer list_element_pointer
size

var position

var previous_position var index

0.

table

boolean

ft

is

SAME AS VERSION SHOWN ABOVE EXCEPT THAT THE SEARCH TERMINAThS RECORD ISIOUND INSTEAD OF ALWAYS TRAVERSING THE ENTIRE CHAIN tf
element _pointer

IF

varp

list

ft

Used

for traversing

chain

previous_p
20

list_element_pointer

ft

Points

tops

predecessor

tf

begin

index

hash rebordjcey

ft

hash

returns

value

in the

range

0.

table_size

25

table
previous_p nil

/t

Initialization

before loop

t/

/4

Ditto

4f

position
30

nil

/4

Ditto

4/

previous_position

nil

/4

Ditto

4f

while

nil

/4

HEART

OF THE TECI-INIOUB
ft

Traverse

list deleting

4/ t/

expired records as

we

search

35

begin

ifpl

record

contents

is

expired

then
40

remove

previous_p

index

ON-THE-FLY

REMOVAL

OF EXPIRED

RECORD

else

begin

18

BTEX0000I

96

Richard

Nemea

ifpi .record contents.key

record_key

If this

is

record wanted/

then

begin

save

its

position

position

previous _position

previous_p

return
10

true

We

found

the

record

so terminate search

end

previous_p

Advance

to

15

pT.next

Inextrecord

end

else

begin

end
20

return

false

Record not found

end

searchable

25

Remove

Procedure

procedure remove var elem_to_del
30

list_element_pointer

previous_elem list_element_pointer
index

0.

table_size

Delete

elem_to_delI

from

list

advancing
nil if

elein_to_del
is

to next
1it

element previous_elein
in list.t/

points

to

elem_to_dels
35

predecessor

or

elem_to_delI

element

var

list_element_pointer

Save

pointer

to

elein_lo_del

for

disposal

begin

40

elem

to_del

ft

Save

so we

can

dispose

when

finished

adjusting

pointers

19

BTEX0000I

97

-Th

Richard

Names

e/emtodel

elemtodel

.next

if

previousplem

nil

ft

Deleting

element

requires

changing

Sf

then

kthle
elem

elern

ode
elem_todel

ft

bead

pointer

as

opposed

to

else previous

next

/5

predecessors

next pointer

5/

dispose
10

Dynamically

de-allocate

node

Sf

end

remove

20

BTEX0000I

98

Richard

Nemes

CLAIMS
claim

An

information

storage and
to store

retrieval

system access
to

the

system comprising

linked

list

and

provide

records stored in

memory of

the system at

least

some

of the records automatically search means utilizing search means including ones

expiring search key to access the linked and
list

record

the record of the expired

means

for identifying

removing
list is

at

least

some
and

of the records from the linked
the

list

when the

linked

accessed
at the

means
10

utilizing

record

search means for accessing the linked
the

list

and

same

time removing The

at least

some of

expired
retrieval

ones of the records in the linked list to claim the record
further

infonnation

storage

and

system according
for

including

means remove

for

dynamically accessed

determining
linked
list

maximum number

search means to

in the

of records

is

method
provide

for

storing

and

retrieving

information records

using

linked

list

to

store

and

access

to the records

at least

some of

the records

automatically expiring

the method

comprising

the

steps

of
list

accessing the linked
at least

of records
the

identifying

some of

automatically

expired expired

ones

of the records

and

20

removing
the linked

at least

some of

the

automatically

records

from the linked

list

when

list is

accessed claim the step of dynamically
to

The method according

to

fUrther

including

determining
linked
list is

maximum number
accessed

of expired

ones

of the records

remove

when

the

25

An

information storage and

retrieval

system

the

system comprising
stored
in

hashing means to provide access an external the records technique to store

to records

memory of the system and
hash address
at least

using

chaining

the

records with same

some

of

automatically expiring

30

record search

means

utiliEing

search key to access

linked

list

of records

having

the

21

BTEX0000I

99

Richard

Nemes

same hash address
the record search means including

means
list

for

identing

and

removing
linked

at

least

sOme

expired and

ones of the records from the linked

of records when

the

list

is

accessed

means

utilizing

the record

search means for inserting
at least

retrieving

and

deleting

records

from the system and
in the accessed linked

at

the

same time removing

some

expired

ones

of the records

list

of records

The

information

storage and

retrieval

system according
for

to

claim

further

including

means
io

for

dynamically

determining
linked
list

maximum number
of records

the record

search means to

remove

in the accessed

method
access

for storing and

retrieving

information

records

using
to

hashing technique
store

to provide with

to the records

and

using

an external

chaining

technique

the records

same
the

hash address at

least

some of

the records

automatically expiring

the method

comprising

is

steps

of
accessing
identiFying linked
list

of records
the

having

same hash address
ones

at

least

some of

automatically expired expired

of the records from
the linked
list

removing the linked
list

at least

some of
and

the

automatically

records

when

is

accessed

20

inserting

retrieving

or deleting

one

of the records

from the system following

the step of

removing The method according
to

claim

further

including

the step of dynamically
to

determining
linked
list is

maximum number
accessed

of expired

ones

of the

records

remove

when

the

22

BTEX0000200

JAN
Richard

Nemea

ABSTRACT OF

TIlE

DISCLOSURE
for performing

method and apparatus
system
collision
is

storage

and with

retrieval

in an

information

storage
for

disclosed

that

uses

the

hashing

technique performance
collection

the

external

chaining
to

method
presence
all

resolution

In

order to

prevent garbage

deterioration

due

the

of

automatically

expiring

data

items

technique

is

used that

removes
into

expired storage
to

records

stored

in the

system in the each

external

chain targeted

by

probe of

the data an

system More
search an an expired
it

particularly

insertion

retrieval

or deletion items and

record

is

occasion

entire

linked-list chain

of records for expired

then remove
is

them Because
probed

data

item

will

not remain in the system long term
are

if

the

system

frequently

10

is

useful

for

large

information storage systems that and cannot be taken
off-line

heavily

used

require the fast access

provided

by hashing

for removal

of expired

data

23

BTEX00002OI

IN THE UNITED STATES PATENT AND TRADEMARK OFFICE

Declaration

As

the

below named

inventor

hereby declare

that

My
name

residence

post office

address and

citizenship

are

as

stated

below next to

my

believe

am

the original patent
is

first

and

sole

inventor

of the

subject

matter

which

is

claimed

and

for

which

sought

on the invention

entitled

METHODS AND

APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL USING HASHING TECHNIQUE WITH EXTERNAL CHAINING AND ON-THE-FLY REMOVAL OF EXPIRED DATA the specification of which attached hereto
is

hereby
identified

state

that

have

reviewed

and understand
and any

the

contents

of the

above

specification

including the claims

amendments

flIed therewith

acknowledge of this application

the

duty to disclose with

information which 37

is

material to the examination Regulations 1.56

in accordance

Title

Code

of Federal

hereby claim foreign priority

benefits

under
for

Title

35

United

States

Code

119 or other

a-d
365

or

365

of any foreign applications

patent

or inventors
at least

certificate

of any

PCT

international

application listed

which designated
also

one country

than the United States
application for
filing

of America

below and have

identified

below any foreign
application

patent

or inventors
that

certificate

or of any

PCT

international
is

having

date before

of the application

on which

priority

claimed

None

hereby claim the benefit States United claims

under

Title

35

United

States

Code

120 of any United
designating the

applications
States

or

365
listed
is

of any

PCT

international as the

application
subject

of America

below and

insofar

matter

of each

of the

of

this application in the

not disclosed

in the prior
first

United

States or PCT.international

application

manner provided
the duty to

by the

paragraph

of Title
is

35United

States

Code
.as

112
defined

acknowledge
in Title

disclose

information

which

material to patentability
available

37 Cede

of Federal

Regulations

1.56 which became

between

BTEX00002O2

the

filing

date

of the prior application

and

the

national

or

PCT

injernational

filing

date of

this application

None

Direct

all

correspondence

to

icliard 1432

Michael

Nemes

East 35th

Street

klynNeiXorkil23t25QA

USA
Telephone

718

3775438

hereby declare
that
all

that

all

statements made

herein

of

my own
to

knowledge
be true and

are true further

and
that like

statements made

on information and with the

belief

are believed that willful

these statements were made so made
are punishable

knowledge

false statements

and

the

by

fine or imprisonment

or both

under

Section

1001

of Title
the

18

of the United States Code of the application

and that

such

willThl

false statements

mayjeopardize

validity

or any patent

issued

thereon

00
Full

name of

sole

inventor

Richard Michael

Nemes

Inventors

signamre

Date

Residence

Brooklyn

Kings

County

New

York

1j

Citizenship United

States

of America

Post Office

Address

1432

East

3S
New

Street

Brooklyn

York

112342604

U.SA

BTEX00002O3

4CRo
1991

BTEX00002O4

S%
kc\

flits

Pswnt

of

lfl

vadt

t-T

Pain

and

TILd Ofl

rrt
Us

notdi

10151/fl

Ot
OF

1046 Oe5IC1
rifle

DEPARTMR4T

thr

eul

5I4ERCE

RIFlED

STATEMENT
1.91

CLAIMING SMALL ENTITY

STATUS

Docket

Number Optional

CFR

1.27bINDEPENDENT iNVENTOR

Applicant

RICHARD NEBES orPatentee_________________________________
or

Application

Patent

No.________________________________

Filed

or

Issued

METHODS

uu
As

AND

APPARATUS

PO

INPORMATIo
WITH

STORAGE AND RETRIEVAl
CHAINING
as defined In

HASHING

TECHNIQU
fees to the Patent

EXTERNAL

AND
in

ON.TH

bel3ne
for

Rre
of

aL4fy
title

as en independent

Inventor

37 CFR

1.9c

purpses

paying

reduced

and Trademark

Office described

the speitication

tiled

herewith with

as listed above

the application

identified

above

the patent identified

above

granted conveyed or licensed and am under no obligation under contract or lawto assign to any person who would not qualify convey or license any rights in the invention as an independent inventor had made the invention orto any concern which would not under 37 CFR 1.9c If that person small as qualify business concern under 37 CFR 1.9d ore nonprofit organization under 31 CFR 1.9e

have not assigned

grant

Each

person concern
under

or

organization

to

which grant

have assigned granted convey
exists or license

conveyed
rights
in

or licensed
is

or am
listed

under an below

obligation

contract or law to assign

any

the invention

No such Each

person concern

or organization

such

person concern

or organization

is

listed

below

Separate invention

verified

statements

are required from each

named person concern
1.27

or organization

having

rights

to

the

averring to their status as small entIties

37 CFR
or patent

acknowledge
entitlement
to

the duty to file small entity fee due
after

in

this application prior to

notification

of

any change

in

status resulting

in loss

of

status the date

paying
status

or at the time of paying as small
entity
is

the earliest

maintenance

of the Issue fee or any

on which

no longer appropriate

37 CFP 1.28b
statements

hereby

declare that

all

statements

made

herein of

my own knowledge

are true and

that

all

made on

information
willful of false

and

belief

are believedto betnie

andfurtherthatthese

statementswere

made

statements

and the
States

like

Title

18 of the United

so made are punishable Cods and that such willful
or

with the knowledgethat

by fine or imprisonment or both
false

under sectIon 1001
the validity
of

statements

may

jeopardize
is

the

application

any patent issuing

thereon

any patent to which

this verified

statement

directed

RICHARD
NAMEOF
INVENTOR

NEIVIES

_________________
NM$EOFINVENTOR

_______________
NAME OF INVENTOR

Signature

of inventor

snare

ot

æ.scr

DEC
Date

2O jgg

_________________
Dare

_______________
Date

Suraen comments

Hour on

Statemarn
the

This of

torn
hrre

aflunt

you

Washington Wasningion

DC 20231 DC 20231

DC NOT

.swtSd to Ins 0.3 tcurs to lrvlsts Tate vsy depending upofl the reds of the raviduat 05.4 en mound to ntete Via tomi ahou be aunt to the Dial Inloorsuon Officu Pewisi end Tresas SEND FEES OR COMPLETED FORMS It ThiS AOORESS SEND.TO Msi5afltConrusion.r for Patents
is

Are
Office

BTEX00002O5

PRINT

iF DKAWI2WS
FILED

AS ORIGINALLY

08/775864
Shccl of6

Richard

Namea

FIG

FIG

BTEX00002O6

PRINT OF DRAWINGS FILED AS ORiGINALLY

08/775864
Sht
of

Richard

Ncmc

BTEX00002O7

PRINT

OF DRAWINGS ORIGINALLY FILED

08/775864
Shect3of6

Richard

Nema

FIGyl

Cl

-f

5-3

5-5-

BTEX00002O8

PRThtT

AS ORIGENALLY

OF DRAWINGS FUID

77
of

RicIwd

Ncm

BTEX00002O9

PRINT OF DRAWINGS AS ORIGINALLY FILED

08/775 864
Sheet of6

Richatd

Netne

FIG

BTEX00002I

PRINT

OF DRAWINGS

08/775864
Sheet of

Richard

Names

FIG

YES

103

BTEX00002I

fl
Please
type plus sign inside

rper
PTOiSB08A
695j
Patent

ths..4
U.S Depatlment
Patent and
of

and

Appro4a usethrough 9/30198 Trademark d1.U.S DEPARTMENT
Complete
If

0MB

065 10031

OF COMMERCE

Commerce
Ott Ice

Known

Trademark

Application

Number

OF PRIOR ART CITED BY
APPLICANT
use as many
sheets

iIIng
First

Date

Named
Art Unit

Inventor

.Rirhprºl

Nemns

Group as necessary

Examiner
Attorney

Name
Docket Number

lou

______________
U.S
Examine
Initials

U.S PATENT
Name
of of

DOCUMENTS
ate
of Publication of

Patent Oocumenj Patentee
or Appltcant

No

Number

Clad Document

et
Penar.ocRei.v.ni

5rL21435

t12f

aichar.d...s.Ne.mes.....o.oaGgai

92_2QZ/L--_._

FOREIGN PATENT
Foreign Patent Examiner
Initials

DOCUMEN
Patentee Date
or of PublicatIon

Document Name
tcrnd

Cit

ot of

No

Office

Number

Cod dAnon

Applicant

fled Document

Cited

Document

Pege Columsi Lines Wtae Pe4ver
Pssaaqss Finwis
eq

MM-DDWfl

rr

nas

Anna

TI

.j

Fj

1111
..

1T7.IIIIITIIITIIIIIIITIT

iii
IDate

Examiner Signature

j//3J4K
.1

Considered
reference copy
of

ExAMINER
considered

tnltlai

considered loan
with

whether

or

not

cItation to

lain

conlomtance

wib UPEP

609

Draw

line

through

citation

if

not

in

conformance

and

not

Include

this

next communIcation attached patent Kinds
of

applicant Enter
of Office reign the that of

Unique
code number posatfe Burden
uttotint the

citation

designation

W1PO
of the

Standard patent

51.3

nuner See For Japanese
Kind
check
of

U.S Patent Documenta
the Indication of

issued

the

document
rnuat

by

the the

twtetler
aerial
it

documents
by
the

the year as
Indicated
is

the on

the Emperef under

precede Standard

document
is

document mark

eppropilate

symbois
Translation

document

WIPO

$1.1

Appltcant

tope
This form

hem
to take

Engttah tanguage
.2

attached

Hour
Of

Statement

is

esilmated

hours be

to

cocqMete
to the

TEn
Chief
to

wit vesy.depen4tg
Informal Ion Officer

ton
Patent

the needs and
ft

of

the

individual

case

Any

comments

on

the

tIme you

are reqtilmd Act
of

to cotyplete

this

form

-should

sent

Tradifliatit cisplays

-Off

Ice Washington

Paperwork

Reduction

1995 no persons are requ Wed

to

reepond

Acosedton

of kilorrnatlon for

unless Patents

valid

SEND

FEES

OR COMPLETED

FORMS TO THIS ADORESS

SEND To

Aseletant

Commissioner

Washington

0MB control DC 20231

DC 20231 Under number DO NOT

BTEX00002I

i9ZEf
PTO/SB/08B
Please

6-95

twe

plus

sign

Inside

thk4...t
U.S Department
Patent and
of

Patent

and

Trademark

Approv

iso through

0MB 0651-0031 U.S DEPARTMENT OFCQMlERcE
07/31/96
-t If

14496/FTC Rev
toios

Commerce
0111cc

Trademark

Complete
Application_Number

iCnown

OF PRIOR ART CITED BY
JAN
shoots

Filing First

Dat
Inventor

Named
Art Unit

Tiirhrrr1

NI

Group

199l

PPLICAN
of

as necossa

Examiner
Attorney

flame Docket Number

J/Vf
OTHER
Include

Ut
\J

PRIOR ART
the

NON PATENT
LETTERS
tile

LITERATURE
of the article

DOCUMENTS
appropriate volume-issue
title

-i

name

of

author in

CAPITAL

when

of the

Examiner
Initials

Cite

item

No

book

magazine ournal

serial publlstrer

syntoslum

catalog

etc

date

pages

nunters

oountrywhere

published

source

DE

KNUTH

Sorting

chetts

The Art Of Computer Programming Volume and Searching Reading Massa Addison-Wesley F97 pp 506549

R.L KRUSE
Edition

Data Structures and Program Design Second Prentice-Hall Englewood Cliffs New Jersey i.9.ft7 S.ctIan isJti.ag.2 $Q.tjpn Analysis of Hashing pp 198215

D.F
3113

STUEBS

and

N.W

Abstract Company

Data

Types

Montea

CaLLfnni18SctiaLJ.5_
Pp 310-336

and

WEBRE Data Structures with Pascal Brooks/Cole Publishing

Hashed

Implementations

3J
EXAMINER
considered
InItial

reference copy

considered form
with

whether

or

riot

citation to

Is

In

conformance

wIth

MPEP 609

Draw

line

through

citation

not

In

conformance

and

not

Include

of this

next communication

applicant

Unique Burden amount

citation

designation

nurrber

ApplIcant

Is to

piece hours

check

mart hers
Time

If

English

language

Translation

Is

attached the

Hour
of

Stalerneni

ThIs form

estimated

to

take

.2

to

conlefe

wit vary dependIng
Officer

tgon

the

needs

of

Individual

case

Any

comments

on

the

this tomi strould sent to the Chief Information an required to corriete NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS SEND TO AsaSant

lime you

Patent and
for

Trademark

Office

Washington

DC 20231

DO

Commissioner

Patents

Washington

DC 20231

BTEX00002I

Sorting and Searching

THE ART OF

COMPUTER PROGRAMMING

Reading
\Ienlu

Massachusetts

Park

California

London

Arnsteidam

Don

Mills

Ontario

Sydney

BTEX00002I

This book

is

in

the

This SERIES
IN

book

forms
because

natu
it

ADDISON.WESLEY COMPUTER

Chapter PROCESSING

SCIENCE

AND

INFORMATION

basic structural

ideas those

book
tion Editors VA1tOA

is

only

for

of general-purpose
in

Consulting olettAitus

But
2diit1Ci1AEL hARRISON

fact

the

area

of

discussing

wid
are can can can

variet

How How How How
En

good
given the

algoi

alg

efficie

person

same application what
does can large senses the can thee

How How
with

external data

lR
that

Indeed somewhere
This
is

believe
in

the cont

volume
with

compi
sort

concerned divided

been
also 1973 1973

chiefly

mi

are supplenxentar\

Copyright

by

AddisooWtY
of this

Putilish

ig

Company

Inc

Philippilies

ropyri

tations

Section
deals
is

5.1
with

1w
II

Addison-WeSley
ri

Publishing

Cthnpany

fur may reprodtuvd
st

gus nserved ted
in

No

part

put tieation

001

vt

nova1

system

Chapter
files of this

or transmit or otherwise
of
.\

hrt.ronn any form or by any menos
the Iut prior
si

nwrbauiid
the pul
At

photocopying
Prin ted
iii

rerorIitmg
tin ni

subdivided

without

writ.teiI

15rIoiSSIOIl iu

of

hsher

ted

States

monica

tithed

nuitaneousiy

Cans in

rtuy of Congress

Catalog

Card

by digital problcm of secondttry

keys

or

No
BPS

\7-.26020
O-25135S3-X OEFGIIJ-MA-7957

BTEX00002I

506

sEAItdULNi

6.4

6.4

6.4

MASHING

will

have

the same

month

au

docn So
ir

function

which

maps
into this

23

we
to

ave

cot isidered in
is

searci

ni

eth ods
its

based
digits to

corn pant govern

ig

tI

cc

give

cc

argm

no

two

keys

map
they

the
resul

meict
third

the keys

the table
to

or using
all

branching

process arith
of

Skeptics large

who doubt
work

possibility

ovoid

this

rummaging
function

around which

by doing
is

some

parties

attend
of

metical
ii

calculation
issoci cited

oci

computing
in
is

the location

unpublished Essays

Day
Sec
also

tic

ci

at

the table
ider

1939 New
and

45

lot subjected
ci

ex cm
to

11

let

cot

agcu

cc

the set
in

ccl

.31

Ec

igl

ish

words nh ch we
6.3 into

Ii

Ove

Mecmuasi
Theory

1939

145163
19

various

search which

strategies transforms
If

Section
of

6.22 and
keys
to

Table
unique

show5 number
for

York Wiley hand
Turski
can the

short

MIX

program
10

each

the 31

On
niewski

the other

ap
fot
lilu

between
the other
trie of

acid

30
have

we

compare

this

method

the MIX optimal

programs
tree

YAC
be

methods
digital acid

we

considered

e.g
find

binary
it is

search superior uses

search

suitable

function
to

memory
space the

tree

search
except

we
that

that

from the standpoint
less

amusing
Of

solve
this in

puzzle

both

speed
time

binary

search

slightly

space
of

In

course kccown
it

method advance
to

hi at

fact with

average

for of

successful

search

using

the

program
only 41

Table

must be making

the frequency
to

dit
store
it

Fig

12

is

cxciv

about

7.Su

acid

table

ben
There

necessary

start
if

tims are needed
Unfortunately
are

the 31 very

keys
easy
to

more versatile method
discover such functions
set into

we

gi

isnt

keys

to

yield

the

same

value been
lea
cI

41
only each 41

10
40

possible

functions
11 41

from

31element
1041
of

41element
distinct

set values

ambiguity These known chop

after

has

and
for

/l0
one

them

will

give

considerations

argument

thus

only

about

of

evei10i1tihii1iiiiLtions

will

be

as Iiaslimy

or scatter or
to

sl

suitable Functions
fairly

something up
aspects of

mals as

which table people

avoid

duplicate

values

are surprisingly

rare

even
asserts

with that of

off

sonic

the key
.t

large

For example
are pri\secct

the famous
in

birthday

paradox
that

searching

We

compute begins

has

23

or

more

room
Table

chances

are good

two

them

where

the search birthday

The K1 INTO

paradox
hash
In

tel

which

the so

TilANSFOIUIINU

SET

OF KEYS

UNIQUE

ADDRTSSES
14

Ct
C-C

LOAN L02 1501 JAR INCA LEE 221 3c01 Jie INCA LOS Jsz DCCX JIN INCA LDA 0504 255

811 X22
162

2-22-I

II
Ii

-c

ii

II

s5 52 s
s2
211
.1

li-S

.5

.5

ci

ii
II II
III

AJ

15

ii
II
III

cci

IV 17
Is 18 Is .29

ii

13

15 Is iS 13 Is 15
25 25 25
211

833
OF

ii

III

Iii

Ii

in is

ii

is

ii

282
or

i2
77-22
20
--7

20 29

22

-.IS.H

-3
25
35

12

112

12

20

544
9F

35
IS 17

52
or 10
19

25 --7 25

-1 TABLE1
FAILURE

i-i

II
Ii

521
IS

III

14
i