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. 4

EXHIBIT 3

Dockets.Justia.com

111111

11111111

III

11111

11111

11111

11111

1111111111

11111

11111

liii

III

11111

liii

USD05

121495A

United States Patent
Nemes METHODS AND APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL UTILIZING HASHING
TECHNIQUES
Inventor Assignee Richard

Patent

Number
of

5121495
Jun
1992

Date

Patent

Computer Science 1973 506549

and

Information

Processing

pp
Pas

Data cal N.Y Inc

Structures

with

Abstract

Data

Types

and

Stubbs

and

Webre
Section

Brooks/Cole

Nemes

Publishing

Brooklyn Research

mentations

Company 1985 pp 310336
and

7.4 Hashed

Imple Kruse

BeH

Communications

Data

Structures

Program Design
1984 Section 3.7

Livingston

N.J

AppI
Filed

No

430901 Oct 31
1989

PrenticeHal 112126

Inc

Hashing

pp

Primary ExaminerGareth
Assistant

Shaw
Kulik

ExaminerPaul
Agent
or

Related
Continuation of

U.S
5cr

Application

Data

Attorney

FinnJames ABSTRACT

Fak

No

151639

Feb

1988

aban method and
in uses

doned

apparatus information hashing of the

for

performing system
In

storage
is

and

mt
U.S

CL5 Cl 364/222.82

GO6F

15/411 395/600

GO6F

12/00

retrieval

an
the

storage

disclosed

which

364/222.81 364/252.3
expiring File

technique

order to

prevent used

contamination 364/281.1 364/282.1

storage

medium
collection

by automatically technique
is

364/DIG
Field of

records removes
all

garbage
expired data

Search

..

364/200

MS
Cited

File 900

MS

which of

records in the
storge

neighborhood

probe each
is

into

the

system
retrieval the

More

particu of of re

References

larly

probe an

for insertion to

or deletion chain

U.S
4121286
4.215402 10/

PATENT
1978 7/1980 5/1984 2/1985

DOCUMENTS
et et et al

record cords
364/900 364/200 364/200

occasion
for

search

entire

found and

expired the

records chain
expired

and

then

removing
collection in

Venton
Mitchell Bolton

them

closing

This

garbage

4447875 4502118 4716524 4775932

automatically the vicinity

removes of the
the

record contamination

Hagenmaier
Oxley Oxley
et et

Jr

et

al

364/200 364/200 364/200

probe

thereby automatically space up
in

decon
long term
it is

12/1987 10/1988

taminating

storage

Because
the present are

no

contamination
useful for large require

can

build bases

system used

data the
fast

which

OTHER PUBLICATIONS The
Art of Searching

heavily

and

which
Sorting Series

access

provided

by hashing

Computer Programming Knuth AddisonWesley

and
in

aaims

Drawing

Sheets

DEF00004032

U.S

Patent

June

1992

Sheet

of

5121495

FIG.1

FIG.2

20

22

DEF00004033

U.S

Patent

June

1992

Sheet

of

5121495

FIG
30

31

NO

.37

SAVE
OF IN CAN

LOCATION CELL RECORD

EMPTY WHICH
BE

INSERTED

36

RETURN SUCCESS

DEF00004034

U.S

Patent

June

1992

Sheet

of

5121495

FIG
51

55

YES

58

BASE

CELL

POSITION
IN

BECOMES WHICH CAN

POSITION
NEW

RECORD

DEF00004035

U.S

Patent

June

1992

Sheet

of

5121495

QTART

FIG

r71
SEARCH-TABLE SEARCH RECORD AND TARGET
IN

FOR TABLE

CLEAN CHAIN

r72
YES

RECORDFOUND

NO

573
PUT
IN BY

RECORD SAVED NO TABLE LOAD THRESHOLD

76

CELL

SEARCH-TABLE

YES

r74
RETURN RETURN FULL

77

-78
PUT IN

RECORD SAVED

CELL

BY

SEARCHTABLE

ADJUST LOAD ONE

TABLE

TO REFLECT ADOITIONAL RECORD

F80
RETURN FiLL

DEF00004036

U.S

Patent

June

1992

Sheet

of

5121495

FIG

DEF00004037

U.S

Patent

June

1992

Sheet

of

5121495

FIG
100

101

YES

NO

103

DEF00004038

5121495
searched
to locate desired

records

With

the

passage
the

of

METHODS
INFORMATION
UTILIZING
This application

AND APPARATUS FOR STORAGE AND RETRIEVAL
HASHING
is

time

such

storage retrieval

contamination
operations

can below

reduce

perfor
levels

mance of
Problems
detail in

acceptable
in

TECHNIQUES
of application Ser

of Data

this

type

are

discussed

considerable

Structures

and

Program

Design

by 1984

continuation

Kruse

Prentice-Hall

Englewood
Structures with

Cliffs

N.J

No

pp

07/151639

filed

Feb

1988

now

abandoned

TECHNICAL FIELD
This
retrieval invention relates to

and Data 112126 and PASCAL by Brooks/Cole and

Abstract

Data

Types

Stubbs

and Calif

Webre
1985

Publishing

Monterey

pp

information
particularly

storage to the use

10

310336
In the prior

systems techniques

and
in

more
such

of

art by

such

storage

space

contamination
that eliminated

hashing

systems

was

avoided

deletion replacing the

procedures
the

BACKGROUND
Information
storage particular

OF THE INVENTION
in

deleted

records by record and
thus in

deleted

record
chain leaving

with of re any
in the

another
15

collision-resolution the

or data stored can be

computer-controlled by searching
for

cords
deleted

close

chain

without
is

mechanism key in the matching

retrieved

records

One such
text

procedure
at

shown 527

stored the

records search
require

The
is

stored

record

aforementioned nately
necessity 20 take so

by

Knuth

page

Unfortu
due
to the

with Such

key

key

then

retrieved
accesses

such
for

non-contaminating
successive that

procedures
into the

searching
into In the

techniques
storage

repeated
to

or

probes they can hence

storage

space
the

probes

mechanism and

perform key systems search

com
such

much time
is

be used

only when
for

parisons searching
rithms sive

large
if

storage

retrieval

data ing

base

off

line

and

not available

access

even
as

augmented search

by

efficient

algo

such

binary

often

requires

an exces

The problem then
of hashing techniques
25

is

to

provide
large

the speed
heavily data

of access infor
at the

amount

of time well-known
retrieving

for

and

used

Another
storing involves

and

much

faster

method

for store

mation same

storage

systems having
the large-scale

expiring

and

and

information
so-called also

from computer

time

prevent

contamination

which
large

the

use

of
are

hashing
called In

techniques
scatter-stor

normally results
heavily

from expired

records in such

and

These

techniques

sometimes techniques upon

used

systems

age or key-transformation hashing tion
to the

system using hashing
storage
is

key

is

operated
storage

by
in the

func-

30 In

SUMMARY OF THE
accordance
these

INVENTION
embodiment
are

produce
the

address

space with or
in 35

with the and

illustrative

of the

called
to

hash
the

table
desired accesses

This storage
storage

address

then used

invention using

other problems procedure
the storage

access

location

directly sequential described

garbage

collection to

on
data

overcome by the fly while
are taking or insertion

fewer
binary the

storage

or

probes techniques

than
are

other types of access place
retrieval In particular

space

searches
text

Hashing by

during
the data

normal store the

classic

Knuth Volume

entitled Sorting

The

Art of

Com

probes into

expired obsolete neighborhood records in record to be
retrieval

puter Programming

and

Searching 1973
the

records are identified of the
the 40

and removed in the
expired

pp 506549
Hashing
verse

Addison-Wesley
functions are

Reading
to

Mass

probe
are

Specifically

or obsolete
the

designed

translate

uni

collision-resolution

chain
as

including

of

keys
the

into

addresses table

uniformly hashing

distributed operations

accessed procedure This
the

removed

part

of the

normal

throughout
include

hash

Typical

truncation

folding

transposition

and

modulo
is

incremental

garbage of by
the

collection automatically

technique

has

arithmetic

disadvantage

of hashing
into

techniques
the

that

decided

advantage caused
that

eliminating

more than one key can
address causing operations sometimes vided forward empty
latter
is

translate in

same or

storage retrieval strategy 45

contamination without such
for

obsolete data

or expired

records

collisions

storage

requiring

base be taken off-line for
is

Some form of
called the
initial

collision-resolution

garbage
data bases to

collection requiring the user

This
rapid

particularly access

important continuous

rehashing

must

therefore

be

pro
first

and

For

example
the

simple strategy
storage will resolve

of
to

searching
the

availability

population

from
storage

address
the

location
is

collision If the

This 50

BRIEF DESCRIPTION
complete understanding by

OF THE DRAWING
of the
the present invention detailed

technique
to

called

linear so to

probing
that

hash table beyond
the

considered of the
the

be circular

addresses

may be
description

gained
in in

considering

following
the

end then i.e

table

map back
probing
is

the

beginning

of the

table

conjunction

with

accompanying of
the

linear the

done
table

with
as

open

addressing space
in the 55

drawing

which
general

with
that

entire collision

hash

overflow

FIG
storage

shows

block
in

diagram which
the

computer information
invention

event

occurs

system hardware and

arrangement system

Some forms of data records have limited lifetime which activi they become obsolete Scheduling ties for example involves records which become obso
after lete after

retrieval

of

present

might be implemented

FIG
60

shows

general

block
in

diagram which
the

of
the

computer information
invention

the scheduled
locations

activity

has occurred

Such
since

system
storage

software arrangement and
retrieval

record storage
this location

cannot
link in

be simply emptied chain of locations

system

of

present

may be
during
solution

previ

might fmd use

ously

created

collision-resolution to this

procedure
to

FIG
operation
65

shows
which
in

general flow chart might be used
in

for table

searching
storage

The
cord
the

classic as

problem
as

is

mark
and

the to

re

hashed

deleted

rather In

than

empty
the excessive

leave

system

accordance shows

with the
general

present chart

invention
for

record in place

time

however
by an
locations

storage

space be

FIG
collecting table

flow

garbage
part

can

become
or

contaminated
obsolete

number of
must

remove procedure
operation of

which

forms

of the

deleted

storage

that

searching

FIG

DEF00004039

5121495
FIG
tion

shows

general

flow

chart in

for

record

inser

number of
computer assemblers

utility

programs

22

of

general

use

to

the

operations

which

might be used with the

hashed

storage

user Utilities and

22 might for example mathematical

comprise
basic

system in accordance

present chart

invention
for storage

compilers and

routines

FIG
trieval

shows
operation

general for use the in

flow

record system

re
in

file

handling routines computer

system maintenance
also

facilities

hashed

Many

software systems 23 which base
disk 13

include access to

data
the for as

accordance

with

present

invention
chart for

and record dele hashed stor

FIG
tion

shows

general

flow

base manager program records in data data example
disk 10 reside

controls

24

Data
unit

base

24

may
such

operation which
in

might be used with
the

in the present

on

storage

or units
application use

age system

accordance

invention refer

storage

unit

of

FIG
program 23 to access
deleting

User

prothe data

To
ence
to the

facilitate

reader understanding
are

identical

grams

such

as application

25 then
data

numerals
figures

used

to

designate

elements

common

base manager data base 24 records
It is

program
for the

base records in modifying
data

adding
efficient

and of

data

DETAILED DESCRIPTION
Referring ings there
puter

realization

base

man
to

of the drawmore particularly to FIG is shown of com general block diagram system comprising Access
stored

15

base manager program ager such as data which the present invention is directed Before ment proceeding
to description
it is first

23 in

FIG

of one
useful

embodi
to discuss

hardware

Central Processing

Unit
unit

10 and Random 11 Computer programs by

CPU
by

Memory
in the

RAM

RAM
11 are at 20

of the present techniques

invention
in

hashing been

general Hashing very
fast

techniques
to static

have
short in the

used classically
as tables storage

for

access

accessed time

CPU

10 and

executed
stored

one
in the

instruction portions

term data such such need
In storage for the

compiler symbol
deletions table are

table Typically
infrequent

CPU
are

10

Data

other

of

and

RAM
tions

11
with

operated by

accessed

CPU

by upon 10 from
data

program

instruc
in

disappears

quickly

RAM
10

11
also

all

accor
and
25

dance

well-known Processing
disk

processing

techniques
controls in disk

Central accesses cesses units

Unit

CPU
unit

controller stored storage are

12

digital

data disk data

on
unit stored

one

which or more
In disk

turn

ac

some common types of data storage systems data records become obsolete merely by the passage of time or by the occurrence of some event If such expired or obsolete records are not removed from the lapsed
storage

storage

table

they will in time
the

seriously

degrade

or

such

as

13
on
this disk

normal

operation
unit 13 30

contaminate Contamination need
tions to search

performance
arises

of the of
the

retrieval

system

programs
until

and

storage

because

ever-increasing

required data are

by

CPU 10 At
from
11 in

time

such

programs
unit 13 in

longer and longer chains which
are

of record loca reach
desired

and

retrieved

storage

many

of

expired

to

blocks

and

stored

RAM
Unit

for rapid

access
controls in

location

Central

Processing

Input-Output
vides access ray to

10
tube
such
for

CPU
14
input

10 also

an
pro

More
logically 35

particularly

hash
circular

table
list

can

be described

as

controller of

which
devices
as

turn
as

contiguous
fixed-sized

of consecutively nuin
called cells

plurality terminal as

such

CRT
of

bered
ble

storage

units

cathode

15

as well

plurality 15

of storing

single

item called
field

record
called the

each capa Each record
is

output devices mechanism
structions

printer

16 Terminal
operator to
the

provides

contains

distinguishing the basis for

key which
the table

computer
into

introduce system
other

in
of
40

used
ated base

as

storing

and

retrieving the

associ data

and and such

commands may
be card and
readers printer

computer with

record
are

The keys throughout
and unique
for associate

hash record

FIG
devices terminals vices

supplemented
tape

input

distinct

each with

Hashing
addresses

as

readers remotely located other types of input

functions are tinct usually

which
not into

keys

storage

optical

and
16

de
for

one-to-one
the

in that

they map

many

dis

Similarly
the

provides

mechanism

keys
store

same

location
cell

displaying

results

of the

operation of the

computer

To

new record
the

number
on
the

is

generated
for the the

by

system

of

FIG

for the

computer

user Printer

similarly

be supplemented

by line printers
graphical

16 may 45 cathode ray and

invoking record record
collision

hashing
cell

function
is cell

key

If
is

this

location

not occupied
location
is

new new
be

tube

displays

phototypesetters

plotters

stored

there If this and

occupied must

other types

of output devices of the computer system of

has occurred elsewhere
in

the

new
area

record
using

The
and
art

constituents

FIG
in the 50

stored priate

an overflow

an appro
colli
is

their

cooperative
typical

operation are
all

well-known systems frame

collision-resolution

technique which under
will

common
be described addressing
area
is

and

are

of

computer main of such

from small

sion-resolution

strategy probing
that

here

personal architecture

computers and
since not

to

large

systems
are present

The
well-

known
hash
55

as

linear

open

Open
entire

operation

systems of the here

addressing
table

means
itself

the

overflow probing with the

the

known
vention
In

and
will

they form no be
is

part

in
of

Linear beginning

indicates

sequential recalling collision

further

described
graphical for

scanning
that
is

of cells
storage

next cell

FIG
as that

there

shown
architecture in

representation

the

table

is

viewed

circularly

The
first

typical

software

computer

system

resolved by storing

the

record in the

unoccupied

such

shown
access

FiG

The software of
20

FIG
60

cell

found
retrieve

comprises
personal ing to the

an

mechanism

computers system

may comprise
In larger

which for simple no more than turnproviding password
in access service

To
cell

record
If the

the

key
is

is

hashed

to

generate for

location

record

not there following

the keys do not
the

on

systems
login

match
the the 65 In

searching
as

continues

same

larger

number of users
typically access

and

proce

ward path
retrieval

record storage procedure

An

dures would nism
login

be implemented mechanism
is

mecha
the

which

empty cell terminates has then failed to find

20 Once
procedure

20 has completed placed
in the

record to be

retrieved
is

the user

operating 21 coordi of

FIG

there for

shown
the

flowchart hash
table

of

search

table to

system
nates the the

environment
activities

21
of
all

Operating

system

procedure
inserting

searching

preparatory

of the hardware
in

components and provides

retrieving

or deleting comprise
the

record
data

The hash
of

table

computer

system

shown

FIG

may

for

example

base 24

FIG

DEF00004O4O

5121495
and
the search table data

procedure

of

portion in

of the 30

base manager
table

23 of

FIG FIG
of
for In

comprise
Starting

record to be
for

removed

in

forward
at

direction

searching
cell

record whose

key hashes

or
is

behind the
it

to

be

box

of the

search

procedure searched of
cell

FIG
is

the in the

removed
the
is

When
as

such

search

key of the
to

record being
the the address

hashed

cell

of the record to
taken the

is found copied to be removed The copied record

record

box 31 empty empty
pied cell

provide
past

box

32

then
is

record
the

to

be

removed of the

and search
is

the

pro
is

cell just cells
is is

end of the i.e
the
first

search chain succeeding

of non-

cess

continued
In prior

until

end

chain marked

located
In

unoccu
one
the to 10

reached empty

box
to

54

the

final the

copied

record

cell

found

box 33
current

the

procedure

moves

teminating might

procedure

The
portion

remove of the

backward of the

from the

cell position

now
the If

at

procedure data base
Starting

of

FIG

comprise of

end

chain
whether

Decision
the cell

box 34
is

examines or not
decision

cell the

manager

determine
tested

empty match

cell

23 program at starting box 50 of
location

FIG
the

FIG
box 51
adjusted

procedure

is

in decision to

box

34
if

is

empty

box

35

is

entered
is

with the
the

of

cell to

be removed which
is

entered found

determine

key

was previously

called load

base cell
in the

Initially table
is

entered to

where
the

in decision

box 41 as will be described
successful in terminal

below
in
is

If
15

the

count

reflect
is

so
and

the

search

is

and returns box 39 of the
In If

success

box 36

removal

of one record
cells

terminates

not box 37
is is

en
for

ber of occupied
this

The load of course As previously noted
to disable

the

num
of

the

value of

tered

where

the

location insertion cell

possible since

record an empty

cell empty box 38 failure

saved

load can

be
the

used
load

the insertion low enough
the

new
value

returned with

records until
to 20

has reached
In

was

found

before

cell

matching

key
cell

The procedure
tested
is

permit efficient

searching
to the next

box

52

procedure beyond
to see

again

terminates

in

box

39
If the in decision to
is

of
the

FIG
base
is

advances
cell In If
it

cell

in the

chain
is

decision
is

box 53 this cell
the

tested

box

34

is if

not empty record in

if it

decision that
cell

box 40
has

entered This

determine determined of
the in the the

the

empty
and

empty
is is

end of the chain
to

has been
cell as
if

reached by comparing record record
to

box

54

entered then
search

mark

the to

base

expired of
the

some
external

portion

contents

some
for

25

empty
matched

Decision

box 55

entered
table
if

determine

condition

timestamp with of an
that

ex

record was found
the

by

the

procedure
the

which
is

ample could
natively with event
entered the the field
if

be compared occurrence
identifying

time-of-day can be

Alter
not In

search

key

terminated in terminal

and box 56
is

so

procedure

If

event

compared any 41
is

matching
to

record was
if

event

in the

record

found
is

decision

box 57 of the
is

entered
location

determine

the

the to

record

has not expired
if

decision

box

base cell
30 If

ahead

hash

of the

search key
If the the

determine

the

key
the

in this cell

record
is

matches saved
If the
in

not

the

procedure hash ahead

terminated in box 56 search record

base base
the

search

key
the

If

it

does

location to

cell

does

of the

then
In

box cord

42 and

procedure not match
to

returns the

box

33
the

rš
35

cell

can be used

for storing cell
is

new record
therefore

box 58
as

key does
directly

search key

location

procedure
ble

of this empty
site to

saved

possi

returns If

box 33 40 determines
to that the

insertion

decision

box
is

record

has 59

Returning
is

box 53
to

if

the

next
if

cell

is

not

empty box
in
is

expired
ing in

box 43

entered

perform
as

non-contaminat
will

entered

determine base cell
cell
in

the

record

this

cell

deletion

of the with

expired record

be

described of
40

hashes ahead
to

of the
the

If the

so box 52
chain

re-entered cell

connection 43

FIG
operates

In to

general the

procedure

advance
at to

to

next

If this next

box

FIG
the

move
into the

record
position

further

hashes entered
cell tents

or behind copy
the

the

base

cell

however
cell the
if

box
to the
cell

60

is

toward record
pired

end

of the

chain

of
the

the

contents

of this next

base

which record

has

expired
at the

thereby time

removing
closing the

ex

thereby

obliterating
is

removing
to
test

base

con
table
is

and

same

search

Box 61
to

then

entered

the

search

chain
It

procedure can be seen that
to the search the table

found

matching
to the

record
next

If

not box 52
If

procedure chain part and

of

FIG
of

45

re-entered

advance

cell
is

matching
to If test
if

operates

examine

entire
is

of records
to

record
the

was found
to the

decision
is

box base
to the

62
cell

entered

which

the

searched-for

record

delete

matching
is

record

the

record
cell

not box

expired records by chain-filling such
the

rather

than

by marking of
50

52
ing

re-entered
is

advance

next

If the
is

match
to

records
storage

as

deleted by

In

this

way

contamination
is

record
the

base cell of the

however

box 63
cell

entered

space each

expired table

records search such of

removed

in the

store

location

former base

as
is

the

position to

vicinity

of

new
even
the

If

contamination garbage can be has had
re55

of the advance
It

matching
to the

record and
next cell the

then box 52 search of

re-entered

becomes collection
inhibited

too large then
until to

with

automatic records

in the

chain

insertion search table

new

can

be

seen that
the entire

procedure

FIG

operates

the

procedure

to

examine

search chain
in the

and to move vacated

records
in

chance cords
to

remove

sufficient

number of expired

from
the

later positions

chain
is

to

positions

render the operation of the

system sufficiently

chain
the

such

that

the

chain
is

entirely

closed at the
cells are
left

end
to

efficient

of
search
is

procedure break

That up

no empty

The

table

procedure
in the

illustrated

generally as

in

erroneously nection
60

search chain expired records of

As noted
are will

in

con
to in

FIG
like

implemented Source on

Appendix
suitable

PASCALcompilation software from by
this

with

FIG
FIG

subjected

pseudocode execution

code

for

the remove connection
data

procedure with
are also

FIG
to the

As

be

noted

and

any standard can
readily

hardware be

and

records to be deleted remove

from the of

computing pseudocode person
In

system and
the

devised

base

subjected

procedure

flowcharts
in the

of the

figures

any

FIG
The remove
procedure
in the illustrated generally as for in

of ordinary

skill is

art flowchart of
the

FIG
and

FIG

there

shown

remove database
In

65

is

implemented

Appendix
suitable

PASCAL-like
compilation

procedure
either

which

removes

records from or expired by traversing

pseudocode execution puting on

Source

code

records to be deleted
is

records
the

gen

any standard can
readily

hardware be devised

and software from
this

com

eral this

accomplished

chain

of the

system

pseudo-

DEF00004O41

5121495
code and
the
skill

flowchart
in the there
is

of

FIG
detailed in the

by

any

person

of

with
failure

matching of the

key

If

not box procedure
If

103

is

entered
the

to

report
is

ordinary
In insert

art

deletion

and

procedure

FIG

shown
for use

flowchart information invention
starting

of an stor

terminated in box
as

106

matching remove

record was found procedure
in

procedure
retrieval

suitable

determined
is

by box 102 the
in

of

FIG
with

age and
insert

system of
is

of the

present as

The
70
table

invoked
this at the

box

104

As noted
the the

connection

procedure

FIG
entered
is

begins
In

box

FIG
and
is

procedure same
to

removes
closes

record to be deleted chain
to

from which procedure
the

box 71 of

box 71 the with the
in

search

time

search

Box 105
the

FIG

invoked

search

key

of

then

entered

report

successful
is

deletion

call

record to
the

be inserted
table

As noted
procedure
search

connection
the target

with
cell 10

ing

program
delete

and the

procedure

terminated in box 106
in

FIG
location pired

search
if

locates

The code
tion

procedure
in the

illustrated generally as for

FIG

is

and
cells

part that

of

chain

removes

all

ex
is

implemented Source

Appendix
suitable

PASCAL-like
compilation and

pseudo-

from

search
is

chain

Decision whether

box

72

code

execu
and
skill

then entered
search table If

where

it

determined

or not the matching
to

on any standard
readily

hardware

and software computing from this pseudocode of ordinary

procedure
is

found entered
storage

record with where
table the

system can
15

be devised

key
the

so box 73
in

record

be of

the

flowchart art

of

FIG
Appendix

by any person

inserted old

put into

the

in the In

position

in the

record with
reports

matching
the old

key

box 74 the

insert

The attached
for
all

contains functions

pseudocode necessary These
further to

listings

procedure by the
terminal

that

record has been
is

replaced
in 20

of the
data

programmed
base manager
the

imple

new record and box 75
to decision decision
is

the

procedure

terminated

ment

23

FIG
invention 3-7 and

operating in

ac

cordance follow and
skill

with

present

listings explain

Returning not found
table load

box
is

72

if

matching
to

record
if

is

the

flowcharts of
the art

FIGS
no

box 76

entered

determine

the

elucidate in the

flowcharts
will

Any

person

of ordinary

below of the

preselected table the

threshold If table entered the
is

typically load
full is

have

difficulty

implementing language
to

about below
access the the

75%
the

capacity
storage

not be
25

these

functions

in

any desired

program those

run

threshold and

too
to

to

on

any desired
It

efficiently table
is full

box
the

77

is

report

that

should

computer also be clear

hardware
to

configuration
skilled in the art that

and

record cannot
in terminal

be inserted box 75 where
cell

further

embodiments
those skilled

of the
in the present

present art

invention

may

be

The procedure
load
is

then terminates
the

If the the 30

made by
the

without

departing from

below

threshold
is

box 78
in the

is

entered

teachings

of the

invention

record to be inserted found
is

placed

empty
In

position the

by the search
to reflect

table the

procedure
addition reports

box 79

load
the Junctions Provided

kPprsDix

adjusted

of one
that

record to
the

storage inserted

table the procedure
in

record was
in

box SO and

the

procedure

terminated

box
35 The following functions are

75 The code
tion insert

sad

available

to

the

procedure
in the

illustrated generally as for

in

FIG

is

application

prograa
record

implemented Source on

Appendix
suitable

PASCAL-like
compilation and

pseudo-

code

execu
40

ins.rt

record

tvoe rcord.kev

and software computing any standard hardware and system can readily be devised from this pseudocode
the
skill

Returns was found

replaced in the

if table

record and

associated subsequently

with

flowcharts of the
in the

FIG
show
is

by any person

of ordinary
Returns inserted found in if the record table

replaced
with record.kev was

art
there
is

associated and

In

FIG

detailed

flowchart
retrieve in

of

was

not

th

passed

record

retrieve

procedure

which

used

to

record box 90
using the the In 45

subsequently

inserted

from the
search

data base 24 of procedure record to be determined
the search

FIG
invoked
retrieved

Starting in as

table

is

box
the

91

Returpa not found

full in

if the

record table load

associated and passed has

with record reached

record.kev could sax not load

was be factor

key

of the
it

search key matching
If

box 92

is

if

record with procedure
retrieve

inserted

because

factor

key
retrieve 50 Returns found success in the if record and

was found by
is

table

not box 93
and matching
the

entered

to

report
is

failure

of the
in

record

record

type

procedure
If

the

procedure record

terminated box 94
buffer
is

box

96
to

associated to

with

record.lcev

was

record was found
ing into

entered
for

copy

match
by
the

table

assigned

store
is

processing
to return

calling tion

program
successful in

box

95

entered and

an

indica
termi55 Returns delete failure if Icey search record was key unsuccessful

of

retrieval

the

procedure of

nated

box 96
for the retrieve

The pseudo-code
is

procedure

FIG
for
all

record

type

included

in the

Appendix
and system by
those

Executable

code

Returns found 60 Returns in

success

if

record and

associated

with deleted

record

kay

common
can
the In delete

hardware

software arrangements
skilled in the art

was

th

table

subsequently

readily

be devised and
there the
is

from

flowchart

pseudo-code

failure

it

none-found

FIG

shown
for

detailed actively

flowchart

of

procedure

useful

removing
at

records the
65

fiitioas
The following the forsal definitions

from the data base procedure dare of be deleted
if

24 of
first

FIG
invokes

Starting the the

box 100
table

of

FIG
in

search

proce-

ar

required

fur

FIG

box 101 using

key

of the record to
it is

specifying

insertion

retrieval

md

deletion

as the table

search key In box 102 procedure

determined record

algoritbsa cout
table size size of bash table

the

search

was

able

to locate

DEF00004042

5121495
10
rout
sax load factor sax load factor dummy

variable
/A last not two

table

sizei
to rezove are hera

arguments

var

table

azrsyO
/5

table hash

sizei
5/

of

record

type

relevant

table

Tar

load

table

sizei
number hash of occupied array entries of

bsgin

tab

initially

if

search

table

record

key

position

them .lgnritbms 10

begin

remove Algorithms given for the functions described above are

position
dummy

dummy

variable

variable

below
insert record

function

type
full
15

return

success

replaced

inserted

var

position

table position insert

sizei
in table to by update search or else
5/

return

failure

returned

table

end 20

/delete/

if

search

table

ecord

position

function

search Tar

table

record key
table

record

key

tvoe

position

sizei
and delete

biolean

then

begin 25 search expired index of table for record in key expired
in

tableposition
return

record

records found

target or

chain

position empty

set

to

replaced

record

appropriate

cell

Tar /5 misc if

table used both for

sizei
scanning

chain
backwards

g4/table

size

sax

load

factor

3Q

forwards

then

begin

posppy
index of

table leftzost of

sizel
empty 5/ cell

loadl
tableposition
35 return

to

right

position

inserted

rec

found

boolean
whether search is successful
5/

indicates

ala

returO

full
40

begin

posi __ n ____tio_ is function retrieve rec found

hash

r___o_d___ey ec _ r _ k false

var

record

record

type
if 45

success position

failure

table
begin

in not

empty

then

var

table position resides in

sizei

i2

where by

ecord table

returned

earch

position
repeat 50

/5

loop acan

initialization forward to end of chain

begin

containing

positiOfl

if

search

table

reeord

position

11
until

sod

table

size

then

begin

tablei
empty

is

empty

record return

tahlepositien3 sucoess

55 poe

iltable
while else ruturu

size

sod

table

size

tablei
/ecan
deleting

is

not in

empty revarse
entrie

do

failure

chain

expired

and

retrieve begin

function

delete

record

key

record

key

type
if 65

success position
/5

failure

tableI

is

expired remove is rec

them

found

var

table position resides in

sizei
where by record search

position

posecty recordf

returned

tabi

lse

if

tablei

DEF 00

04 04

5121495
11
then begin

12
hashing cords
is

techniques

to

provide

rapid

access

to

the

re

of said system
to store

and utilizing
the

linear

probing tech addreSs
at

rec

found

nique
least

records with
said

same

hash

potitio

some of

records automatically

expiring

said

system

comprising means
utilizing the

record search

search key to access same hash address
for identi

jltable
end
while

size

tod

table

size said

chain

of records having

record search means and
said

including

means

fying 10

removing chain and
said

all

expired ones

of said records chain
is

from

of records each

time said

if

not

is

rec

found

then

position

pen

epotv

accessed

end
return

then

means
ing tern

utilizing retrieving

record
deleting

search means records from removing accessed

for

insert

and
the

said

sys

is

rae

found

and

at

same

time

all

expired

ones
end procedure table sax pos of /5 search to rae table 5/

of said

records in the

chains

of re

cords

m9e
search

call
is

dcl found eapty boclean
table

The information sizei
20

sizei

storage

and

retrieval

system

ac

rec

02

cording means

to

claim

further

comprising record from
later

for

recursively in said

moving

/5

Delete

table
size-i

to

del

tj

position

chain

of records into the

position

of

one
vex table

of said

expired records
storage

The information
cording
to

and

retrieval

system

ac
said

claim

further the

including

begin load

25

means

for

counting

number of records means

in

loadi

system

means responsive
do forever ing the insertion

to said

counting

for inhibit said

of new

records into
in said

system

when
call to

the

number of records
value
storage

system exceeds

del
save position ci .sptied slot 5/

30

preselected

The information
cording to claim
also

and

retrieval

system

ac
for said

further

repeat

scan

forward to

looking

for in chain

including to said

record

fill hole

means
35

responsive the the

counting

means

re-enabling cell to del

insertion

of new

records into
in said

cell

to

dell

Sod

table

size

system when
falls

number of records
preselected

system

below

said for

value
retrieving to

if

tablecell

10

dcl

is espty

method
records using
cess to said to

storing

and

information
rapid

hashing

techniques
utilizing the

provide

ac
techat said

then

begin

records and

linear

probing

tablei
if not is

espty

40

nique
least

store

records with

same

hash

address

rec

found

then

some of said records automatically method comprising the steps of
accessing

expiring

if or or

poe poe
then

of pos

search espty pos

rec pos of of

pen search rec

zv
rec
45

chain

or

records

having

the

same

hash

address
identifying the automatically

spty
pot

expired

ones

of

said

search

records removing chain
all

eapty automatically expired

records from said chain
is

of records each

time said

return

accessed

end
50

and
inserting retrieving

or deleting following
to

one
said

of said

records

hae
until or or Cell

aiscel1
cell to del to

to

del.fy

from said

system

step

of removing compris

The method according
dcl ing the step of record from
the

claim

further

cell

to

del
tablecell
to

moving

later position

in said

chain
expired

of

records into

position

of

one

of

said

dcl
to plug bole in chain

records

use

f.tfcell found
rec search

to

del

The method according
ing the steps of
the the

to

claim

further

compris

if

is
of

rec

and cell rae to

counting dcl
inhibiting

number of records
insertion the

in said

system
said

and sys

ucs
then

search of

of new

records into
in said

poe

tem
rises

when
above

number of records
value
to

system

preselected

The method according
ing 65 re-enabling the step

claim

further

compris

of
the insertion the said of new records into number of records in said system

What

system when
is

claimed

is
falls

below

said

An

preselected

value

information

storage

and

retrieval

system

using

DEF00004044

/OF
..I

III

IIIIII

Ill

11111

11111

11111

11111

11111

11111

11111

11111

111111

III

11111

II

USOO5 121495A

United States
Nemes METHODS

Patent

Patent

Number
of Patent

5121495
Jun
1992

Date

AND APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL UTILIZING HASHING
TECHNIQUES
Inventor Assignee Richard
Bell

Computer

Science 1973

and

Information

Processing

pp
Pa.s

506549

Data cal

Structures

with

Abstract

Data

Types

and

Stubbs

and 1985

Webre
Section

Brooks/Cole

Nemes

Brooklyn Research

N.Y
Inc

Publishing

Company
pp
and Inc

7.4 Hashed

Imple Kruse

mentations Communications

310336
Program 1984

Data
112126

Structures

Design
3.7

Livingston

N.J

Prentice-Hall

Section

Hashing

pp

AppI
Filed

No

430901

Oct

31

1989

P-imary ExaminerGareth
Assistant

Shaw
Kulik Faik

EraminerPaul
Agen4
or

Related

U.S
of

Application

Data

Attorney aban method

FirmJames ABSlRACT

Continuation

Ser

No

151639

Feb

1988

doned

and
in

apparatus

for

performing system
In

storage
is

and

mt CL
U.S
CI 364/222.82 Search

GO6F
364/281.1

15/411 395/600 364/282.1

006F

retrieval

12/00 which
uses

an
the

information hashing of the

storage

disclosed

364/222.81 364/252.3
expiring

technique

order

to

prevent used

contamination

storage

medium
collection

by automatically technique
the
is

S7O

364/DIG
Field of
..

records removes
all

garbage
expired data

364/200

MS
Cited

File 900

MS

which
File

records storge

in

neighborhood

of References
larly

probe each
is

into

the

system
retrieval the

More

particu of of re

probe an

for insertion to

or deletion chain

U.S
4121286 4215402 4447875 4502118 4716524 4775932

PATENT
7/1980 5/1984 2/1985

DOCUMENTS
et et ci al ii al

record cords
364/900 364/200 364/200

occasion
for

search
records

entire

found and

expired the

and

then

removing
collection in

10/1978

Venton
Mitchell Bolton

them

closing

chain
expired

This

garbage

automatically the vicinity

removes of the
the

record contamination

Hagenmaier Oxley Oxley
et Ct al al

Jr

Ct

al

364/200 364/200 364/200

probe

thereby automatically space up Because
present are heavily

decon
long term
it is

12/1987 10/1988

taminating

storage

no

contamination
useful for large require

can

build bases

in the

system used

data the
fast

which

and

OTHER PUBLICATIONS The
Art of Searching

which
Sorting Series

access

provided

by

hashing

Computer Programming Knuth Addison-Wesley

and
in

Claims

Drawing

Sheets

DEF00004045

5121495
searched
to locate desired

records

With

the

METHODS
11FORMATION UTIUZING
This application

AND APPARATUS FOR STORAGE AND RETRIEVAL
HASHING
is

passage
the

of

time such

storage retrieval

contamination
operations

can below

reduce

perfor
levels

mance
detail

of

acceptable in

TECHNIQUES
of application Ser

Problems
in

of Data

this

type are and

discussed

considerable

Structures

Program

Design

by 1984

continuation

No

07/151639

filed

Feb

1988

now

abandoned

Kruse Prentice-Hall Englewood and Data Structures wirh 112126
and

Cliffs

N.J

pp

Abstract

Data

Types

TECHNICAL FIELD
This
retrieval invention relates to

PASCAL

by Publishing art such by
deletion replacing

Stubbs

and Calif

Webre
1985

Brooks/Cole
storage to the

Monterey

pp

information
particularly

and
use

10

310336
In the prior storage

systems
techniques

and
in

more
such

of

space

contamination
that eliminated

hashing

systems

was

avoided

procedures
the

BACKGROUND
Information
or data

OF THE INVENTION
stored in

deleted

records by record and
thus

deleted

record
chain leaving

with of re any
in the

another
15

in the close

collision-resolution the

computer-controlled by searching
for

cords
deleted

chain

without
is

5/

s23

storage particular

mechanism key
in the

can

be retrieved records
search require

records

One such
text

procedure
at

shown 527
due

stored the

The
is

stored

record

aforementioned nately
necessity 20 take data

by

K.nuth

page

Unfortu
to the

with Such

key

matching

key

then

retrieved
accesses or

such
for

non-contaminating
successive

procedures
into the

searching into In the

techniques
storage

repeated
to

probes they can hence

storage

space
the

probes

mechanism and

perform key systems
search

com
such algo

so much base
is

time that
line

be
not

used only when
available for

parisons searching
rithms sive

large
if

storage

retrieval

off

and

access

even
as

augmented

by efficient
often

ing

such

binary search

requires

an exces

The problem
of hashing
25

then

is

to

provide the and

speed

of access used infor
at the

amount

of time well-known
retrieving use

techniques

for large

heavily data

Another
storing involves

and

much

faster

method

for

mation same

storage

systems having
the

expiring

and

and

information socalled
also

from computer

store

time

prevent

large-scale

contamination
in

which
large

the

of
are

hashing
called In

techniques
scatter-stor

normally results
heavily

from expired

records

such

and

These

techniques

sometimes techniques upon

used

systems

age or key-transformation hashing tion
to the

system using hashing
storage
is

key

is

operated
storage

by
in the

func-

30 In

SUMMARY
accordance
these

OF THE INVENTION
illustrative

produce
the

address

space with or
in 35

with the and

embodiment
are

of the by while
taking

called
to

hash
the

table
desired accesses

This storage
storage

address

then used

invention
using

other problems procedure
the storage

overcome
the

3Co

access

location

directly sequential described

fewer binary
the

storage

or

probes

than
are

other place

garbage collection of access to types
In particular

on
data

fly
are

ii

space

searches
text

Hashing by

techniques
entitled Sorting

during

normal

insertion

or

classic

Knuth

The

Art of

Com

retrieval

probes into the data

store the expired obsolete
in the

puter Programming

Volume
are

and

Searching 1973 the uni
40

records are identified of the probe
the

and removed
expired

neighborhood records in record to be
retrieval

pp 506549
Hashing
verse

Addison-Wesley
functions

Reading
to

Mass

Specifically

or obsolete
the

designed

translate

collision-resolution are

chain including
as part

of

keys
the

into

addresses

uniformly hashing

distributed operations

accessed procedure This
the

removed

of the

normal

throughout
include

hash

table folding

Typical

truncation

transposition

and

modulo
is

incremental

garbage of by
the

collection automatically

technique

has

arithmetic

disadvantage

of hashing
into

techniques
the

that

decided

advantage caused
that

eliminating

more than one key can
address causing operations sometimes vided forward empty
latter
is

translate in

same or

storage retrieval strategy 45

contamination without such
for

obsolete data base
is

or expired

records

collisions

storage

requiring

be taken off-line for important continuous

Some form of
called the
initial

collision-resolution

garbage
data bases to

collection requiring the user

This
rapid

particularly access

rehashing
storage will

must therefore

be

pro
first

and

For

example
the

simple strategy address
the

of searching
to the

availability

population

from

storage

location
is

resolve

collision If the

This 50

BRIEF DESCRIPTION
complete understanding by
considering

OF THE DRAWING
of the
the present invention detailed

technique
to

called

linear so

probing
that

hash table beyond
the table

considered of the

be circular

addresses

may be gained
description in in

following
the

end

table

map back
probing
is

to the

beginning

of the

conjunction

with

accompanying

then the i.e

linear

done
table

with
as

open

addressing space
in the 55

drawing

which
general

with the
that

entire collision

hash

overflow

FIG
storage

shows

block
in

diagram which

of
the

computer information
invention

event

occurs

system hardware and

arrangement system

lifetime Some forms of data records have limited which activi they become obsolete Scheduling involves records which become obso ties for example after lete after the

retrieval

of the

present

might

be implemented shows
general

FIG
60 storage

block
in

diagram which
the

of
the

computer information
invention

scheduled
locations

activity

has occurred

Such
since

system software arrangement and
retrieval

record storage
this location

cannot be simply emptied
in

system

of

present

may be slink

chain

of locations

previ

might find

use
general

collision-resolution owly created during procedure The classic solution to this problem is to mark the re cord as deleted rather than as empty and to leave the

FIG
operation 65

shows which

flow chart be used
in

for table

searching
storage

might

hashed

system in accordance

with the
general

present chart

invention
for

record in place

In

time however by an

the

storage

space be

FIG
collecting table

shows remove

flow

garbage of the

can

become
or

contaminated
obsolete

excessive

number of
must

procedure of

which

forms part

deleted

storage

locations

that

searching

operation

FIG

DEF00004046

5121495
FIG
tion

shows

general

flow

chart
in

for

record

mser

number of
computer
assemblers

operations
in

which

might be used with
the

hashed

storage

22 of general the utility use to programs user Utilities 22 might for example comprise and compilers and mathematical
routines basic

8cc
gL2q

system

accordance shows

present chart

invention
for storage

FIG
trieval

general for the use
in

flow

record system

re
in

file

handling routines computer

system maintenance systems
also

facilities data to the for as

operation

hashed

Many
base
data

software

include access

accordance

with shows

present

invention

and record dele hashed stor

FIG
tion

general

flow chart used

for
in

manager program records in data
reside unit as

23 which
base disk

controls

24
storage

Data
unit

base or

24
units

may
such

operation

which
in

might be

the

example
disk 10

on 13

age

system

accordance
reader are

with the

present

invention refer

storage

of

FIG
23 to access
deleting

User

application the

pro.-

To
encc
to the

facilitate

understanding
to designate

identical

grams such
base data

application

program

25 then use
data

data

numerals
figures

used

elements

common

manager base 24
It is

program
for the

base records in modifying
data data

adding
efficient

and of

DETAILED DESCRIPTION
Referring ings
puter there
is

records ager such of the of

realization

base

man
to

as

data base

manager
is

program directed

23 in

FIG

more particularly shown general
10 and

to

FIG
Central

block

diagram

draw com

15

which

the

present

invention to

Before ment

proceeding
present

description
it

of one
useful

embodi
to discuss

hardware

system comprising

Processing

of the

invention
in

is

first

Unit
unit

CPU
by by

Random

Access
stored

Memory
in the

11 Computer programs

RAM

RAM
11 are at 20

hashing been

techniques
classically

general Hashing very
fast

techniques
to static

have
short in the

used

for

access table

accessed time

CPU 10 and CPU 10 Data
are

executed
stored

one
in the

instruction portions

term data such need
In

such

ass compiler symbol
tables deletions table are

Typically and

other

of

RAM
tions

storage for the

infrequent

II

operated by

upon

by

program

instruc
in

storage

disappears

quickly

accessed

CPU

10 from
data

RAM
10

11

all

accor

dance

with well-known Processing
disk digital

processing

techniques
also controls in

some common types of data storage.systems data records become obsolete merely by the passage of time
25

Central accesses cesses units

Unit

CPU
unit

and

or by
lapsed storage

the

occurrence

of some event

If

such

expired from
the or

controller stored storage are

12

which
In

turn

ac

or obsolete
table

records are

not removed
seriously

data disk

on
unit stored

one

or more disk normal

storage

they will in time
the

degrade

such

as

13
on
this disk for

operation
unit

contaminate Contamination
30

performance
arises

of the of
the

retrieval

system

1362-

programs
until

and

data

disk

storage

13

because

ever-increasing

required data are

by

CPU
in

10 At
from
11

time

such

programs
unit

need
tions

to

search longer and of which
are

longer chains expired
to

of record loca reach
desired

and

retrieved

storage rapid

13

in

many

blocks

and

stored

RAM
Unit

access
also
in

location an

33
372-

Central

Processing

Input-Output
vides access ray to

10
tube
such
for

CPU
14

10

controls

More
logically 35

particularly

hash
circular

table
list

can

be described

as

controller

which
devices
well as

turn
as

pro

contiguous
fixed-sized

of consecutively
called cells

num
capa
record
is

plurality terminal as

of input

such

CRT
of

bered
ble

storage

units

each

cathode

15

as

plurality 15

of storing

single

item called
field

record
called the

Each
the

output devices mechanism
structions

printer

16 Terminal
operator to
the

provides in of
40

contains

distinguishing the basis

key which
table

5-D

373

computer
into

introduce system
other

used
ated

as

for storing

and

retrieving the

associ
data

and and such

commands may
be card and
readers printer

computer with

record
are

The keys throughout
and unique
for associate

hash record

FIG
devices terminals

supplemented
tape

input

base

distinct

each with

Hashing
addresses

as

readers remotely located other types of input

functions are usually

which
not

keys

storage

optical

and

de
for

one-to-one
the

in that

they map

many dis
by

3s-

vices

Similarly
the

16 provides
operation

mechanism of the

tinct

keys into
store the If
is

same

location
cell

displaying

results

of the

computer 16 may
ray 45

To

new record
hashing
cell this location

number
on
the not

is

generated
for the the

system of
similarly

FIG
be

for the

computer

user Printer

invoking record record
collision

function
is

key

supplemented

by line printers
graphical

cathode
plotters

occupied
is

new new
be

tube
other

displays
types

phototypesetters

and

stored

there If this and

cell

location

occupied must

of output devices of the computer system of

has occurred elsewhere
in

the

new
area

record
using

The
and
art

constituents

FIG
in the small 50

stored priate

an overflow

an appro
colli

their

cooperative
typical

operation are
all

well-known systems frame from

collision-resolution

technique which under
will

common
be described addressing
area
is

and

are

of

computer main of such no

sion-resolution

strategy probing
that

here

is

personal architecture

computers and
since

to

large

systems
are present

The
well-

known
hash
55

as

linear

open

Open
entire

operation they form

systems of the here

addressing
table

means
itself

the

overflow probing

the

known
vention
In

and
will

part

in

Linear beginning

indicates next cell

sequential recalling collision

not be further
is

described graphical for

scanning
that
is

of cells
storage

with the

FIG
as that

there

shown
in

representation

of

the

table

is

viewed

circularly
first

The

typical

software architecture

such

shown
access

FIG

The
20

system computer software of FIG

resolved by storing

the

record in the

unoccupied

cell

found
retrieve

comprises
personal ing to the

an

mechanism

computers system

may comprise
In larger

which for simple no more thin turnproviding
service

To
60 cell

record
If the

the

key
is

is

hashed

to

generate

location

record
continues

not there following

the keys do not
the cell

on

systems

match
ward
the the 65

searching
as

same

for

number of users login and password proce dures would typically be implemented in access mecha
larger

path
retrieval

record storage procedure

An

empty
has

terminates to find

which

then

failed

nism 20
login

Once

access the

mechanism
user
is

20 has completed placed
in the

the

record to
In

be retrieved
is

procedure environment
activities

operating 21 coordi of

FIG

there for

shown
the

flowchart hash
table

of

search

table to

system
nates the

21
of
all

Operating of the

system

procedure
inserting

searching

preparatory

the

hardware
in

components and provides

retrieving

or deleting

record
data base

The hash
24 of

table

computer

system

shown

FIG

may

for

example

comprise

the

FIG

DEF00004047

5121495
and
the search table

procedure manager
table

of

portion in

of the data 30 of the key of the

base

23 of

FIG FIG
of
for In

comprise
Starting

record to be
for

removed

in

forward

direction

searching
cell

record whose key hashes at or behind the

to

be
to

box

search

procedure

FIG
is

the
in

removed
the
is cell

When
as

such

record

is

found

it

is

copied

search

record being searched address end of
cell search

hashed

of the record to be removed The copied
taken the

record
the

box

31 to

provide the
past the

box

32

the

then
is

record to be removed
the

and
search
is

pro
is

empty
empty
pied
cell

cell just cells
is is

of the
first

chain

of non

cess

continued
In prior

until

end

of

the

chain marked

located
In

i.e the box

succeeding

cell

found

33

the

procedure

unoccu moves one
at the cell to 10 the

reached empty

box
to

54

the

final

copied

record

teminating

the

procedure

The remove
portion

backward of the

from the

current

cell position

now

procedure data
base

of

FIG
starting

might comprise program 23 of

of the

end

chain
whether

Decision
the cell
is

box 34 examines
is

manager
at

determine
tested

empty

or

not

If the

cell

Starting entered
is

box 50 of of

FiG FIG the
to

procedure

is

in decision to

box 34
if

empty

decision

box

35

is

with the location
the base cell in the

cell

be removed
51
is

which where
the

entered found

determine

key

match

was

previously

called load

Initially table
is

box

entered to

in decision search
is

box 41 as will be described
successful in terminal

below
in
is

If
15

the

count of one

adjusted

reflect
is

so
and

the

and returns box 39 of the
In If

success

box 36

removal

record
cells

terminates

not

box 37
is is

en
for

ber of occupied
this load

The load of course As previously noted
to disable the

the

num
of

the

value of

tered

where

the

location insertion cell

empty

cell

saved

can

be

used

insertion

new

possible since

record an empty

box 38

failure

returned

records until the
to

load has

reached
In

was

found

before

cell

with
in

matching

key The procedure
cell tested
is

permit efficient

searching
to the next

box

low enough value 52 the procedure
chain
is

again

terminates

box

20

of
the

39
If the in decision to
is

FIG
base
is
it

advances
cell In If
it

cell

in the

beyond
to see

decision
is

box 53 this cell
the

tested has

box

34
if

is

not

empty

if

decision that cell

box 40

entered

determine determined of the
in the the

the

record in comparing
to

empty

empty
is is

end of the
to

chain the base

been
as
if

has expired
of the

This

reached by record record

and box

54

entered

mark

cell

some
external

portion

contents

some
for

25

empty Decision
record was matched found
the
in

box 55

then entered
search table
if

to

determine

condition

timestamp with of an
that

ex

by

the

procedure
the

which
is

ample could

be compared occurrence
identifying

time-of-day can
the

Alter

search
terminal

key

599

natively with event
entered the

the

event
in

be compared record
In

terminated not found
base
is

and box 56
is

so

procedure

If

matching
to

record was
if

field
if

event

decision

box 57 of the
is

entered location

determine

the

any
cell
is

the to

record

has not
if

expired key
the

decision

box 41

ahead

hash

of the search
If the

30 If

key
base base the

determine

the

in this cell

record matches
is

not
can

the

procedure hash ahead

terminated in box 56 record

search

key
the

If

it

does

location to

saved
If the

cell in

does

of the search

then the
In

box 42 cord

and

procedure
not to

returns the

box 33
the

re

cell

be used

for storing cell
is

new record
therefore

box 58
as

key

does

match

search key

procedure

location ble

of this empty
site to

saved

p0551-

returns If

directly

box 33 40 determines
to that the

insertion

decision

box
is

record

has 59

Returning
is

box 53
to

if

the

next
if

cell

is

not

empty
in is

box
cell

expired
ing in

box 43

entered

perform
as

non-contaminat
will

entered

determine
base cell
in

the

record

this

deletion

of the with

expired record

be described procedure of

hashes ahead
to

of the
to the

If the

so box 52
chain

re-entered
cell

connection 43

FIG
operates the

In to

general the

advance
at to

next

cell

If this next

box

FIG
the

move
into the

record
position

further

hashes
entered cell tents

or behind copy
the

the

base

cell

however
cell

box
to the cell

60

is

toward .2.

end

of

chain

of
the

the cx-

contents

of this next
the
if

base

2..X

record
plied

which

has expired
at the

thereby time

removing
closing the

thereby obliterating

removing
to
test

base

con
table
is

record and

same

search

Box 61

is

then

entered

the

search

chain
It

procedure can be seen that
to the search the table

found
to

matching
to the

record
next

If

not box 52
If

procedure of and

of

FIG
delete

45

re-entered

advance

cell
is

matching
to If test
if

operates

examine

entire
is

chain part

records of
to

record
the

was

found

decision
is

box 62 base
to the cell

entered

which
expired

the

searched-for

record

matching
is

record
to the

the

record
cell

not

box

records by chain-filling records as deleted
In
this

rather

than

by marking of
tj

52
ing

re-entered
is

advance
cell

next

If the
is

match
to

such
the

way

contamination
is

record
the

base

however box 63
box 52
is

entered

storage

space each

by expired records

removed

in the

store

location

of the former base record and then
next that entire
cell

cell as the

position to

vicinity

of

new
even
the

table

search such of

If

contamination garbage can had
ress

of the advance
It

matching
to the

re-entered

becomes
collection inhibited

too large then
until to

with

automatic records

in the

search of

chain

insertion search

new

be
to

can

be seen
the

the

procedure chain
to

FIG

operates

the

table

procedure

has
expired

examine

search in the

and to move vacated
closed cells

records
in

chance cords
to

remove

sufficient operation

number of
of the

from
the

later positions that

chain
is

positions at the are
left

render the

system sufficiently

chain such

the

chain is

entirely

end
to

efficient

of the
search
is

procedure

That up

no

empty
chain

The

table

procedure
in the

illustrated

generally as

in

erroneously break
nection 60 the

search expired

As noted
will

in

con
to in

FIG
like

implemented Source on

Appendix
suitable

PASCALcompilation software from
this

with

FIG FiG

records are

subjected

pseudocode execution

code

for

remove

procedure with
also

of

FIG
to the

As

be

noted

and

any standard can
readily

hardware be

and

connection
data

records to be deleted remove

from the of

computing pseudocode person
In

system and
the

devised

base are

subjected

procedure

flowcharts
in the

of the

figures

by any remove database
In

FIG
The remove
procedure
in the illustrated generally as for in

of ordinary
there

skill is

art flowchart of
the 65
is

FIG
and

FIG

shown

implemented

Appendix
suitable

PASCAL-like
compilation

goc

procedure
either

which

removes

records from or expired by traversing

pseudocode execution

Source

code

records to be deleted
this
is

records
the

gen

on any standard
readily

hardware be devised

and software

com

era

accomplished

chain

of the

puting system can

from this pseudo-

DEF00004048

Ic
5121495
11
then begin

12
hashing
found techniques to

provide

rapid

access

to

the

re

cords of said system
is

and utilizing
the

linear

probing tech address
at

tee

position

mque
least

to

store

records with
records

same

hash

some

of said

automatically

expiring

said

and

system comprising record search means
utilizing the search

key to access hash address
for identi records chain
is

iltabls
end
/5

size

sod

table

size said

chain

of records having means
all

same

record search and

including expired

means ones

ehil
10

fying

removing chain and
said

of said
said

from said accessed

of records

each

time

if

sot

is

ran

found

tbsp

position

poe

empty

sad
ratnrs

then

5/

means
ing tern
15

utilizing retrieving

record search
deleting

means

for insert said

and
the

records from removing accessed
all

sys

is

yen

found
table

and

at

same
in

time
the

expired

ones
Cd

of said

records

chains

of re

esareb resove

cords

proc.dnre table mar poe

cell r.c

to

del found .epty boolean
table

The information sizei
20

sizei
search

storage

and

retrieval

system

ac

is tee pee

cording to means
for

claim

further

of

comprising record from
the later

recursively in said

moving
records
storage

/C

Delet

tIblecell

to

del

position

chain of records into

position

of

one
Tar table

of said

expired

size-i

The
cording to
25

information claim

and

retrieval

system

ac
said

further the

including

means

for

counting

number

of

records

in

system

means
do gorav.r ing

responsive the insertion

to said

counting

means

for inhibit said

of new

records into
in said

system

when
ca.l to /5

the

number of records
value
storage

system exceeds

del
save position of .apti.d slot

30

preselected

The
cording

information
to

and

retrieval

system

ac
for said

claim

further

including to said

rupsat

scan rscord

forward to

locking

for in chain

fill

bel
end

means
35

also

responsive
the the

counting

means

re-enabling cell to del

insertion

of new

records into
in said

c.ll

to

d.11

table

ci

system
falls

when

number of records
preselected

system

below method

said for

value
retrieving to information rapid

if

c.l1
tbsa begin

to

del

is .spty

storing

and

records using
cess to said to

hashing

techniques
utilizing the

provide

ac
techat said

records and

linear

probing

eepty
if set is found then

40

mque
least

store

records with
said

same

hash

address

some of

records automatically
steps

expiring

ran

method

comprising the chain

of
the

if Or or

pee poe
thea

of poe

search eeptv poe

tee poe of of

poe s.arcl ran

sv
ran
45

accessing

or records having

same

hash

address
identifying the automatically expired

ones

vf

said

.ectwc poe

search

records removing chain
all

eapty

automatically

expired

records from said chain
is

of records each

time said

accessed

returp

sad
50 buii

and
inserting retrieving

or deleting following
to

one
said

of said
of

records

c.ll
call
to to 4.1

to

dsi.5
ing

from said

system

step

removing compris chain
expired

The method nU.1
or or cell

according

claim

further

del

the

step

of record from
into the later position in said

cell

to

d.l

moving
55

of

records records

position

of

one

of said

sea

c.li
fuwd
.sarch of

atcll
to

to deli

del
to plug hole in chain ing

The method
the steps

according

to

claim

further

.coinpris

of
the the

if

is
of pee