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

EXHIBIT 5
PART 6 OF 6

Dockets.Justia.com

5287499
17
recursive delete delete

18

mod

table

size

end

knuth

List

Insert Algorithm

procedure
/5 var begin

list

nsen
list

iarp

lust

ementype new
in it and

ecord record
link to
list

ype
to

Allocate

element put new_record

pointed

byp

llist_elemenctflx

new

allocate

list

element record

5/

qecord_conents
qt.next

new

end
Table

Insert

Algorithm

procedure
/5

table

insen record
in table

table_size-I at or ahead

new

ecord record_type

Store new

of position

begin while

eable
table
is

table

occupied

do

mod

table

size

new_record

occupied

end

What

claimed

is storage portion storage

when
and of each
address retrieval said
in

said to

collision

count

in

said

storage

means

is

An
data generating

information

system
record

for for said

equai

or greater

than said
storage

preselected retrieval

threshold system

records using hashed

data

The
means

information

and

ac
said
is

said

system

cording to claim
for

further

comprising of said data
said

system comprising
storage set

storing

one
address

records at
collision

means of said

for storing data records

collision

count
identical

for

each

50

hashed below

storage said

when
and

count

having

bashed

preselected

threshold
retrieval

storage
first

addresses
responsive to said storage

The
means
for

information

storage further

system

ac

means

cally said

resolving collision

coUisions

by open

addressing

lo when

cording to claim means
at for storing said at said

comprising
to

pointer

one of said data address

records said

count in said storage threshold
responsive

means

is

below

hashed
is

storage to

when
said

preselected

and
to said storage external

collision

count

equal

or greater

than

pre

second
locally

means

means

for

selected

threshold

resolving

collisions

by

chaining

60

65

BTEX0000438

f_y\

UNITED STAThD
Patent

DEPARTMENT
Office

OF COMMERCE

and

Trademark

NOTICE

OF ALLOWANCE

AND ISSUE FEE DUE

RI CHARD MI CHAEL NEMES 1432 EAST 33TH STREET

BROOM

VU

NV

1234-2604

APPLICATION

NO

HUNG DATE

TOTAL

CLAIMS

EXAMINER

AND GROUP

ART

UNIT

DATE MAILED

@3/775.864
Nemed
OF
ITION

01102197

@08

ALAN
RICHARD

2771

09/29/9

NEMES
METHODS HASHING EXPIRED

AND APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL USING AND ON-THE-FLY REMOVAL OF TECHNIQUE WITH EXTERNAL CHAINING DATA

A1TYS

DOCKET

NO

CLASS-SUBCLASS

BATCH

NO

APPLN

TYPE

SMAlL ENTITYJ

FEE DUE

DATE DUE

77-26..O@0

J78

UTILITY

YES

366000

12/29/9

APPLICATION
-SECUTION

IDENTIFIED

ON THE

MERITS

ABOVE HAS BEEN EXAMINED IS CLOSED
WITHIN

AND

IS

ALLOWED FOR ISSUANCE AS

PATENT

ISSUE FEE MUST BE PAID
LICATION

SHALL BE REGARDED THIS
as

THREE MONTHS FROM THE MAILING DATE OF THIS NOTICE OR THIS AS ABANDONED THIS STATUTORY PERIOD CANNOT BE EXTENDED

TO RESPOND TO
view the

NOTICE
above
verify

SMALL

ENTITY
is

status shown

SMALL
ent

ENTITY ENTITY
is

shown
status

YES

your

If

the

SMALL

ENTITY

is

shown

as

NO

SMALL

If

the status

FEE DUE shown Traemark
f4he status
Office
is

changed above

pay twice the amount of the and notify the Patent and
in

Pay FEE DUE

shown

above

or

of the change

status

or

the

same

pay the FEE

DUE

shown
File verified

Æ5ove

statement
1/2

of

Small

Entity

Status before

or

with

payment
ifB-Issue Fee Transmittal
if

of

the

FEE DUE shown
Office

above

should

be completed
already

and returned been

to

the Patent
to

and Trademark

PTO

with your

SUE FEE oId be

Even

the ISSUE

FEE has
if

paid by charge

deposit account

Part

Issue Fee Transmittal

completed

and retumed
should

Issue Fee Transmittal
II

the ISSUE FEE to your deposit account section you are charging be completed and an extra copy of the form should be submitted application
prior to

Mb

of Part

communications
all

regarding communications

this

must give
to

application

number and

batch

number
to

lease direct

issuance

Box ISSUE

FEE
filed

unless advised

the contrary

RTANT

REMINDER

Utility

patents

Issuing

on applicatIons patentees

on or after

Dec 12

1980

may require

payment

of

maintenance
fees

fees

It/s

responsibility

to ensure timely

payment

of maintenance

when due
PATENT AND TRADEMARK
OFFICE

copy

REv

10-96

Appmved

for

use

Iivough

06/30/9t

0651-0033

BTEX0000439

PTO/SBt2l Please
typo ptus sign inside this

6-98

box

El
Patent

and

Approved Trademark
to

for

use

through 0913012000

Office
to

U.S DEPARTMENT
of information

0MB 0651-0031 OF COMMERCE
unless
it

Under
vatid

the

Paperwork
control

Reduction

Act

of

1995

0MB

no persons

are

required

respond

collection

displays

number

-S
Application

Number

08/7 75864 01/02/97

TRANSMITTAL

Filing

Date

FORM
to be used
for at

First

Named
Art Unit

Inventor

Richard
2771

Michael

Nemes

correspondence

after/nit/a

liEn

Group

Examiner

Name
Number

Hosain

Alan

jotai

Number

of

Pages

in

This

Submissionf

Attorney Docket

ENCLOSURES
Transmittal

check

all

that

apply
After to

Form

fl

Assignment Papers for an Appicatlon Drawings

Allowance

Communication

Group Communication
to

Fee Attached

fl
Papers

Appeal
of

Board

Appeals and

Interferences

Amendment

Response

Appeal
Licensing-related

Communication

to

Group

AppealNoke

At

Rep

8rS7

After

Petition Final

Routing

Slip

PTOISB/69
Petition

and Accompanying
AffIdavits/declarations

LIII

Proprietary

Information

LI LI LI

Petition

to

Convert

to

Status Provisional Application

Letter

Power

Extension

of

Time

Request

Change Address
Terminal

of Attorney Revocation of Correspondence

fl

Additional

Enclosures
Identify

please

below

Disclaimer

Express

Abandonment

Request

LI
Information Disclosure

Small

Entity

Statement

RECEIV
Publishing

Statemen

LI
Certified

isbn

Request

for

Refund

Copy

of

Priority

Documents
Response
Incomplete
to

Remarks
Missing

utu

Parts

Application

six
Response
Parts under or 1.53
to

sheets Hail

of

formal

drawings
431 173 533

Missing

37 CFR

152

Certified OF APPUCANT

Article

NumberZ

SIGNATURE
Firm or Individual

ATTORNEY

OR AGENT

name

Richard

Michael

Nemes

Signature

WtiJ
December CER11FICATE
1998

Date

OF MAIUNG
with the United States Postal Service
this

hereby envelope

certify

that

this

correspondence

Is

being

deposited
for

as

first

class

mail

In

an

addressed

to Assistant

Commissioner

Patents

Washington

D.C 20231

on

date

IDecember

10

19

ci

Typed

or printed

name

Richard

Michael

Nemes
Date

Signature Burden Hour Statement en
the

JLjJvxij l4pu.eThis amount form
of
is

December
upon Chief the needs
Information of the

1998
Individual

estimated

to take required

02 hours
to

Any comments
Trademark Commissioner

time

we

are

complate Time vQiU this foam should cornplse

to

vary

be

deoending send to the

case
and

Officer

Patent

Office
for

Washington Patents

DC 20231 DC 20231 Washington

DO NOT SEND

FEES

OR COMPLETED

FORMS TO

ThIS

ADDRESS

SEND TO

Assistant

BTEX000044O

5893120

15

FIG

Jr

USER ACCESS SOFTWARE
20
_________________

OPERATING

GENERAL
UTILITY

SYSTEM SOFTWARE

SOFTWARE

22

21
_______
APPLICATIONI APPLICATIONI

___
Tj

r25

APPLICATION

___

SOFTWARE

SOFTWARE
____________
24

SOFTWARE

FIG

BTEX000044I

4/.p

A1b

BTEX0000442

APiQVED

jSsJsuRCLA.1

36

FIG

BTEX0000443

Attti

op/

iJ1

og

g4

BTEX0000444

AROVED
in

tcssGHG C
SUBCAssj

ADVANCE PTR TO ELEMENT
FOLLOWING

ONE TO REMOVE

DE-ALLOCATE

ELEMENT TO BE REMOVED
LIST

FIG

BTEX0000445

At t7lOW

j1.tig

BTEX0000446

OG
EY

flG

TABLE

SEARCH FOR RECORD AND CLEAN TARGET

LLJ

RETURN

FIG

BTEX0000447

Auptc

loAf

kr
tt

oqc

BTEX0000448

____

.4

RI

SEAR
RECORD AND CLEAN TARGET

FIG

It

BTEX0000449

ci4io

TA

BTEX000045O

OVED

OG HG

100

H-TABLE

SEARCH FOR RECORD AND CLEAN TARGET

06

FIG

BTEX000045I

75

BTEX0000452

PAnT
icompiete

BISSUE

FEE TRANSMITTAL

and mail

this

form together

with

app

ale

tees

to

Box ISSUE PEE
Assistant Comynlsaione
for

Patents

cP
t17
papers Each drawing must have Certificate
additional
Its

Washington

D.C

20231

IAiæi
jough4
p.eceipt

INS

TFf

ficTioNs
advance

This

form should

be

used

for

transmitting

the

ISSUE
including

FEE
the

Blocks
Issue

should be completed
the

where.appmpitate
orders indicated andnottfucatron

Alt further of

correspondence
fees directed
will

Fee
for

Paten new
fee

maintenance below
or

be mailed
in

to the

current

any

other

accompanying
or formal

paper

such

as an

Srreapondence gpcifying iaintenance

address as

unless

corrected

otherwise

Block

by
for

malgnment

own

curtificate

of maIling

correspondence
notifications

address

and/or

indicating

separate

FEE ADDRESS
aodc

of Mailing
Tmnsmittai
Is

iFNT

CORRESPONDENCE

ADDRESS

Note

Legaly

mart-up

with

eny

serredlara

or

use

hereby the United
In

certify

that

this

Issue

Fee

being

deposited

with

States envelope

Postal

Service

wIth to the

sufficient

nEar
0ub
1ShIng

an

addressed

Box

Issue

VEo

fo first class postage Fee address above on

DEc

01993

RICIIARD

MICHAEL

NEMES

tees

ease

s8
APPLICATION

SS
December
EXAMINER

10

1998
ART UNIT DATE MAILED

NO

FlUNG DATE

TAt

CLAIMS

AND GROUP

Li

THC
5LEOF
iliVENT1ON

PApERNEflco pc
7P

rr

f7

CC

iccLMt

Cr

EXPIPEL
ATIYS DOCKET

DiT
Ct-ASS-SUBCLASS

NO

BATCH

NO

APPLN

TYPE

SMALL

ENtiTY

FEE DUE \TEE

DATE DUE

IT
ChÆnge of
Use
of

.tir.i

correspondence

address

or indication

of

Fee Address
but

37
not

CIII

1.363

For the attomeys

printing

on
of

the

patent to

front

page

list

PTO foess and Customer

Number

are

recommended

regoired

names
or of

up

registered alternatively firm

patent

i____________________

agents

OR

ChangeoiconaspondenceeddressorChangeofConespondenoeAddressfom1 PTOISBI1fl
IX attached

the

name

single

having
or

as agent
patent

member and
the

regIstered

attorney to

names
or

of

up
If

registered
Is

Fee Address

Indication

or

Fee Address

Indication

fona

PTO/SB/47

attached

attorneys

agents

no name

listed

no

namewillbeprinted

ASSIGNEE NAME AND RESIDENCEDATA TO BE PRINTED PLEASE NOTE Unless an assignee identified below no
is

ON ThE
assignee data

PATENT
wf

print

or

type
patent 10

4a The
of

following

fees

are

enclosed

make rtedc

payable

to

CommIssioner

appear
prevIously
Is

on

the

Patenta

and Trademarks es OrderIt

Inclusion the flln

of or

assignee
Is

data submitted

isonly

approplate separate

when cover

an assIgnment
Completion

has been
of
this

submitted subeltifue

PTO

being

under

form

NOT

ssue
for

an assignment

Advance

of

Copies

NAME OF ASSIGNE
4ts

The

following

fees

or deficiency

In

these

fees

should

Ire

charged

to

RESIDENCE

CITY

STATE OR COUNTRY
below be on

DEPOSIT

ACCOUNT AN EXTRA
Fee

NUMBER COPY OF THIS FORM

ENCLOSE
Please check DlndMctuai
the appropriate aSsignee category Indicated wilt not prInted the patent

Ogovemment OF PATENTS AND TRADEMARKS
IS requested to apply the Issue

AdvanceOrder-ofCopies Fee
to the application Identified

The

COMMISSIONER

above

10
NOTE1 The
iaate

199

Fee
aSsignee

will

not or

be

accepted party in

from
Intet

anyone

other

than the

the

applicant of the

registered Patent

attorney

er ae

or the

other

alas shown

by

records

end

1_/18/199
01 FL

IBRAHjN

00008

08754
605.00 jp

TraderparkOffice

Burden depending
to

WourstarementmisfomiiaeafimatedtotakeO2houmtocomplefe
Sn
the

Timewilivary
of

needs

of the

Individual

case
the

Any domments
InformatiOn

on

the

amount

time

required

complete

thiØfSrtn

shixild

be

sent

to

Chief

Officer

Patent end

Trademark THIS
for Rt-fund

Office

WaaiingtSn

ADDRESS
Patents

SEND

DO NOT SEND FEES OR COMPETED FEES ANDTHIS FORM TO Box Issud Fee Assistant
D.C 20231
20231

FORMS TO
CommIssioner

Ref

WaahlngtonDC

WBPAHIM

0000117t46u

iS
$55.00

UnderthePaperworkReductionActoflgg5nopersonaarerequiredtoreapondtOacollection
of Information

unless

It

displays

valid

0MB

control

number

CHECK

Refund

Tub

TRANSMIT
PTOtastt REV.10-95 Approved
for

This FORM

WITh

FEE
Patent end
Trederearic

use

through

06/30/99.0MB

Q551

-0033

office

US

DEPARTMENT

OF COMMERI

BTEX0000453

Please type

PTO/SB/122
plus sion -tinside this

11-96

Appr
Patent

.4.1

ior

use

through

6/30/99

aid

Trademark

Office unless

U.S DEPARTMENT
displays valid

OF

0MB 0651-0035 COMMERCE
contiol

Under

the

Paperwork

Reduction

Act

of

1995 no pemons

are

required

to

respond

to

coHeion

of information

0MB

number

CHANGE OF CORRESPONDENCE ADDRESS
Appilcatlon
Address to

Application

Number

08/7

75864

Filing Date

1/02/97
inventor

First

Named

Richard
2771

Michael

Nemes

GroupArtUnit
Examiner

AssistantCommisslonertorPatents

Name
Docket

Hosain
Number

Alam
-F

Washington %-

D.C

20231
Attorney

Please Change to

the Correspondence

Address

for

the above-identified

application

Place

Customer Bar

fl
OR

Customer Number
Type

Number CustomerNurnoer
here Label

Code

hem

flFirm
Address

or

IndividualName

Richard
2821

Michael

Nemes Apartment
1M

Kings

Highway

Address
City

Brooklyn

State

New

York

JZlPJll22gl835

Country Telephone

U.S.A

718 6771748
cannot

212
the

346_.l782IFaxI

212
with

3461863

This

form

be used

to

change

data

associated

Customer Number
for

To

change

the data associated

with an existing

Customer Number use Request

Customer

Number Data Change PTO/SB/1

24

am the
Applicant

RECEIVED
Publishing
Division

EEl

Assignee
Certificate

of

record

of the

entire

interest
is

under 37

CFR 3.73b

enclosed

DEC

10

1998

LI

Attorney

or agent

of

record

16

Typed
Printed

or

Name

Richard

Michael

Nemes

SignatUre

Date

December
Hour on Statement
the

1998
to take to 0.2

Buiten comments

This
of

form

is

estimated
are

hours

to

complete form should

Time be
sent

wilt

vary to the

depending
Chief

upon

the

needs

of

the

individual

case

Any
Office

amount

time you

required

complete

this

Information

Officer Assistant

Patent

and

Trademark
for

Washington Washington

DC 20231 DC 20231

DO NOT SEND

FEES

OR COMPLETED

FORMS TO

THIS

ADDRESS

SEND

TO

Commissioner

Patents

BTEX0000454

ij

PTO UT1UTY
Paper Number

GRANT

/c

The Commissioner of Patents and Thutemarks
1/as received

an
usejid

application

for The
are

patent for
title

new and
scription

invention
invention

and de
The

of

the

enclosed

law have been complied with requirements of and it has been determined that patent on
the

invention

shall

be

granted

under

the

tans

Theref ire

thit

United States Patent
Grant-s to the the

persons
to exclnde

baring
others

title

to

this

patent

right

from

mah
the

c.Anlckiea

inp

using

off ering

for

sale

or

selling

in
of
the

vention America United
belous

throughout or importing
States sukject

the the

United
invention the

States into

of America
to the

for

term

set forth

payment

of maintenance

fees

asprovided

by

lam
was
filed

If

this

application the resin

prior
it

to

June of
this

1995
seventeen

of

this

patent

the

longer

years

from
years

the

date of
the

rant of

patent
ive

or twenty
filing

from of
the

earliest

effect

U.S
to

date

application

sub

ject If

any

statutory

extension an
is

this

application the

was

filed

or

after

June
years

1995
from
tory the

tenn of this patent
filing

twenty
to

U.S

date
the

subject

an

statu

extension
reference

If

contains application earlier

specific tion

to

an nader
the

filed

appllca

or

applications the

35 U.S.C
patent
the
is

120 121
years

or35c
from
tion siotL the

term of

twenty

date on

which
to

earliest statutory

applica

was filed

subject

any

aten

tgJn
Conmissioner of Patents

am1

Trsdenunt

Few

P10-1554

Rev

2/97

FPILOM

OIflUT

IPlCIflC

BTEX0000455

fill

1111

0111111101111111

III

US005893

20A

United States Patent
Nemes

Fill

Patent

Number
of Patent

5893120
Apr
1999

Date

1541

METHODS ANt APPARATUS

FOR INFORMATION STORAGE AND RETRIEVAL USING HASHING WiTH TECHNIQUE CHAINING AND ON-TIlE-FLY EXTERNAL REMOVAL OF EXPIRED DATA
inventor

R1

Kruse

Data

Structures

and

Program
Cliffs

Design

Second 1987

Edition Section

PrenticeflaIl

Englcwood and Section

New

Jersey of

6.5

Hashing
and and

6.6 Analysis

hash

ing Data

pp

1982 15

Stubhs Types

N.W
Pasca4

Webre
1985

Data

Structure Publishing

wish

Abstract

Brooks/Cole
Section

Richard

Michael

Neines

1432

35th

Monterey tations

California

7.4 Hased

Company Implemen

Si
AppI
Piled

Brooklyn

N.Y

11234-2604

pp 310-336
Ci

No

Primary EraminerThomas

Black

775$64 Jan
1997

Assistant

Exa.rniner

Alam

ABSTRACT
GO6F
707/206 707/1 707/101
17/30
in

1511

tnt CL6

method
an

and apparatus
storage with In

for

performing storage
is

and
that

retrieval

U.S

Cl

707/100

information technique

system
the

disclosed chaining

uses

the for

707202

hashing collision rioration

external
to

method

Field

of

Search

707/1 707/2

200206
100103

resoltition

order

prevent

performance
expiring that

dete
data

due to the presence gathage collection
records stored into
in

of

automatically
is in

items References
Cited
all

technique the the

used
the

removes
chain

expired

system
data

external

targeted

by

probe

storage

system
of

More
record

U.S PATENT
5121495 5212981 5287499
611992 4/1993 2/1994 Ncrncs

DOCUMENTS
701/3 707/1 707/206

particularly
is

each insertion
to search items will

retrieval

or deletion

an

occasion

an entire linked-list chain remove
in
it

of records an expired
if

Shackdford

for expired data item
is

and then
not

thea Because
system
long useful for large require

Ncmes

remain probed
are

the
is

term

the

system

frequently
that

information
fast

OThER
D.E
Sorting chusetts

PUBLICATIONS
Programming Reading vol

storage provided

systems

heavily

used

the

access for

by
of

hashing data

and

cannot

be

taken

off-line

Knuth and

The

Art

of Computer

removal

expired

Searching

1973

AddisonWesley pp 506549

Massa Claims
Drawing Sheets

BTEX0000456

U.S Patent

Apr

1999

Sheet

of

5893120

FIG

APPLICATION

SOFTWARE

FIG

BTEX0000457

U.S

Patent

Apr

1999

Sheet

of

5893120

36

FIG

BTEX0000458

U.S

Patent

Apr

1999

Sheet

of

5893120

ADVANCE

PTA

TO ELEMENT FOLLOWING ONE TO REMOVE

ADJJST PREDECESSORS PTR TO
BYPASS ELEMI

DE-ALLOCATE

ELEMENT TO BE REMOVED
LIST

FIG

BTEX0000459

U.S

Patent

Apr

1999

Sheet

of

5893120

4i
SEARCH-TABLE

SEARCH FOR

RECORD AND
CLEAN TARGET
LIST

INTRECORD
RETURNED BY AVAILABLE

78

RETURN
FULL

NEW

LIST

ELEMEN

4j9
tco
LIST

RECORD

INTONEW

ELEMfl

INSERT
LIST INTO

NEW

ELEMENT TARGET
LIST

RETURN
INSERTED

FIG

BTEX000046O

U.S

Patent

Apr

1999

Sheet

of

5893120

-TABLE

SEARCH FOR RECORD AND CLEAN TARGET
LIST

FIG

BTEX000046I

U.S

Patent

Apr

1999

Sheet

of

5893120

SEARCH FOR RECORD AND CLEAN TARGET

06

FIG

BTEX0000462

5.893120

METHODS AND APPARATUS FOR INFORMATiON STORAGE AND RETRIEVAL WITH FlASHING USING TECHNIQUE CHAINING AND ON-TUE-FLY EXTERNAL REMOVAL OF EXPIRED DATA
CROSS-REFERENCE TO RELATED APPLICATIONS
Not
Applicable
10

Ilall

Incorporated and by

Englewood

Cliffs

NJ.
of Abstract

1987

Section

6i Hashing
198215
and Pasca4

and Section Data

6.6 Analysis
with

Hashing
Data

in

pp

Structures

Types

Stuhbs and Monterey

Webre Brooks/Cole
Calif 1985
Section

Publishing

Company

7.4

Hashed

Implementations
information period storage activities the

pp 310336
are of such
that

Some forms of
items
after

individual obsolete

data

limited in the

time

become
is

and
or
that

their presence desired

system
for

no longer
involve has expires

needed
data

Scheduling
obsolete

example
event
it

STATEMENI REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not
Applicable

become

once

scheduled

occurred

An
he
items for

automatically-expiring occupies put
to

data

item once
storage

needlessly otherwise

computer
use storing

memory
an

that could

unexpired removed
to

item Thus
reclaisn

expired the storage of times

REFERENCE
Not
Applicable

TO

MICROFICHE APPENDIX

must

eventually

be

subsequent data insertions
expired the items results
in

In addition needlessly with

the presence long search

many
since he

linked than expired to

lists

associated otherwise

external

BACKGROUND OF
This invention systems
techniques Information age

HE INVENTION
longer storage the use

chaining goal
is

will to

they

would
the

be The
storage

remove
fast

relates to information

and retrieval
of

20

these access

items

to reclaim

and maintain

and
in

more
such

particularly

to

hashing

the

data then
is to

systems
stored
in

The
computer-controlled stor particular
25

problem
techniques

provide heavily data

the used

speed

of

access

of stor

or data can

hashing age

for large expiring

information
at

mechanism

be retrieved records

by searching The
stored
is

for

systems the

having

and

the

same

time
the

key value matching
searching the storage

in the stored the search

record

with

key Such
into

prevent

performance
of

degradation

resulting

from

key
require
to

value

then access

retrieved
to

accumulation
technique disclosed that 30 inapplicable there records ing traverses for
in

many
Pat

expired with

records Although
expiring data issued
is

techniques

repeated

records

dealing

hashing known and 1992
entirely

mechanism
retrieval
efficient

perform key comparisons
such searching

In large
if

U.S
is

No

5121495
to linear

Jun
is

storage

and by
often

systems
search an

even
as the

aug

technique to

confined external

probing and

mented search
large

procedures

such

binary

chaining order
table gaps

The

procedure

shown
of

requires of

excessive

amount
required

of time

due to the

in reverse in the records

consecutive array
left

sequence removal

number

key comparisons

residing

hash
to

continually

relocat of

Another
retrieving

well-known
information

and much faster way of storing and from computer
storage
is

unexpired

fill

by

the

storage so-called

albeit

at

the

expired

ones
linked
lists

expense technique

of

additional also called

the

hashing
it

Unlike arrays
are

leave

no gaps
it

when

items to

from
effi

scatter-storage

or key-transformation
is

removed and
traverse

furthermore linked
list

is

not

possible

method
hashing space

In

such to the

system produce hash
of record directly

the

key

operated

on

by

ciently

singly

in

reverse

order There are over linear prob

function called

storage

address
is

in the large

storage

significant ing that

advantages

to external

chaining

table

which

one
address

sometimes

make

it

the
in

method
the

of

choice

as

dis

dimensional array
is

locations for the

This

storage

cussed in considerable and so hashing do
not use techniques

detail

aforementioned
with expiring

texts that for are

then

accessed are

desired text

record by

Hashing Knuth

for dealing

data

techniques entitled Sorting

described

in the

classic

external

chaining

prove can be

wholly
if

inadequate records

The and

An

of

Computer

Programming

Volume Mass.

certain

applications considerable instead of

For

example

the

data

Searching

Addison-Wesley

Reading

large
chaining

memory
linear

saved

using

external there
is

1973

pp 506549
functions addresses are designed to translate the universe the uniformly hashing distributed throughout truncation

probing
techniques

Accordingly
for of the be external

Hashing
of

need with
patent
lists

to

develop

bashing

chaining

keys into
table

expiring are

data
to

The

methods

above-mentioned used
with linked of

hash

Ipieal

functions

include

limited

arrays

and cannot
difference

folding transposition
tage

and modulo more
than

arithmetic

disadvan
inevitably in

due to the computers

50 the

significant

in the

organization

of hashing
in the

is

that

one

key

will

memory

translate storage

same

storage of

address

causing

collisions

Some form

BRIEF
In ss

collision the of

resolution

must therefore
called

be

SUMMARY OF THE INVENTION
with and
the
illustrative

provided

For example which
consists

simple

strategy

linear from
the
is

accordance
these

embodiment
are

of

the

probing
initial

searching
first

forward

invention garbage
types of

other

problems

overcome

by using
other In

storage

address

to the

empty storage

location

collection to the

procedure
storage data

on-the-fly
space are or

while

often

used method
In the for resolving
this

access during data

taking

place

Another
nal

collisions

is

called

exter
is

particular into fled the

normal
the

insertion

retrieval are linked

probes identi
list list

chaining
to

technique
of the linked hashing
list is

each
list

hash table records
to

location of

store

expired obsolete
the external records are

records chain in the

pointer

head

of

all

whose hash

and

removed
expired the record

from
or to

keys translate
table

under

function
itself

that very

Specifically including the

obsolete

linked as part

address
retrieving are

The
done

linked

searched

sequentially

be accessed

removed

of

when

inserting

or deleting pointers

record insertion
in the linked detail Structures

and
list

normal

search

procedure garbage
collection technique

deletion External

by adjusting
is

This
65

incremental

has the unneeded

chaining

discussed

in considerable

in the

decided
records

advantage
without taken

of automatically
that the

eliminating information

aforementioned Program Design

text

by

Knuth
Edition by

in

Data

and

requiring off-line for

storage

sys
55

Second

Knise

Prentice-

tem

be

such

garbage

collection

This

BTEX0000463

5.893.120

particularly requiring

important access

for

information

storage
to

systenss the user

Central

Processing controller input as

Unit 14

CPtJ
that such
in

10

also

controls

an access ray

lnputl
to

rapid

and continuous

availability

Output

110
of

turn

provides

population More
information access cally
list

plurality

devices as

as

CR1
of

cathode
devices

tube
as

specifically records records
is

method
using
at least

for

storing to

and

terminal retrieving printer puter

15

well

plurality provides instructions

output

such

linked

list

store

and provide automati
the linked

16 Terminal 15
user to introduce

mechanism and coisunands

for

com
into the with

to the expiring

some lhe
at It

of

the record-s accesses

disclosed
identifies

method
least

computer
other input

system of
devices

HG
such
as

and may be magnetic
tape

supplemented

of

records ones of

and the

some

automatically
at least

readers remotely
types

expired

records unes
is

also

removes

some
list to

located

terminals Similarly the of be

optical printer of the

readers 16 the

and

other

of input
for

automatically

expired linked
list

of the records

from the linked
the

devices
displaying

provides operation user of

mechanism
the

when

the

accessed

Furthermore

method
of

results for

provides expired
list is

for dynamically ones of

determining
to

maximum when

number

system

HG
of

computer

computer

Printer cathode graphical ray

may
tube plotters

the records

be

removed

the linked

similarly displays
15

supplemented

by line printers
laser printers

accessed

phototypesetters types output of the

and

other

devices computer
are

BRIEF

DESCRIPTION VIEWS

OF THE SEVERAL OF TI-lB DRAWING
of the present following invention

The

constituents

system

of

HG
art

and

their cooperative

operation

well-known from small The

in the

and are

complete understanding
gained

may be
in

typical puters 20 operation further

of to

all

computer

systems

personal architecture

com
and

by considering
with the

the

detailed

large of such

mainframe systems here
graphical for

systems
are

description in of the

conjunction

accompanying
block
in

drawing diagram which
present

which computer

well-known

and will not he

described

FIG
system
storage be

shows hardware and retheval

general

FIG
software

shows
architecture in

arrangement system
of

information

representation

of such

typical as
that

the

invention

might
25

shown
access

implensented

HG
nothing providing

computer
of

The
that

software

HG
the

system

comprises computers
In

user

mechanism
of

FIG

shows

for simple than

personal

may
larger

general arrangement

block
in

diagram
the

of

computer
stor

consist

more

turning to

system on
login

system software
age

which

information

systems word
access 30

service

and

retrieval

system of the present

invention

might find

many users
be
access the

and
in

pass
user

procedures

would

typically user

implemented mechanism
is

use

mechanism
the

20

Once

20 has
in the

FIG
operation

shows
that

general

flow in

chart

for

table storage

searching

completed
in

login

procedure

user

placed

might be used
the present flow

hashed

system

operating coordinates

system
the

environment
of
all

21
of the in

Operating

system

21

accordance

with

invention chart for of linked-list element the table searching

activities

HG
remove
operation

shows
procedure of

general that

of

the

computer
of
utility

system

shown
for

HG

hardware components and provides
use to the

forms past

number user

programs might

22 of general example

computer
basic
file

HG
general flow
in

Utilities

22

comprise system

HG
operation accordance

shows
that

chart

for

record storage

insertion

access

and

manipulation

programs language system of
such as

maintenance

might be used
the present general
in

haslsed

system in

facilities

and programming
software

compilers

with

invention flow chart for record
in

The
retrieval includes

computer
application

HG

typically

also

HG
operation with the

shows
for use present

programs

application

software 25

hashed

storage

system

accordance

23
for

24 example

25

Application

software text editor

23 through document
database

might

invention general

and
flow chart for record storage deletion

comprise
spreadsheet

formatting

HG
operation

shows
that

software hashed system in system The
identical reference to the storage

program
so

management

might be used in
the present

gasne present

program and
invention
It is

forth with information

accordance with

invention

concerned

To

and retrieval
or

facilitate

reader used to

understanding
designate

can be application
pasts operating of the

software

packages
as user

numerals
figures

are

elements

common

2325
access

used

by 20

other or

system

such

software

system 21
technique

software The provided
in

information

storage

and retrieval

by the

DETAILED

DESCRWFION
INVENTION

OF THE

so

present

invention

are herein as

disclosed

as flowcharts

HOS
in the

through

and shown
to

PASCAL-like

pseudocode

APPENDIX
general block

HG
ing unit Unit

this specification to
it

of the

drawings

shows

diagram of Process
the 55

Before proceeding
present

description
is first fast

of

one embodiment
M.-discuss

of

computer

hardware system comprising
10

Central

CPU
by

and

Random Access
stored in

Memory
the

RAM
11 are
at

invention
in data

useful

hashing and

techniques retrieving storage

11

Computer

programs

RAM RAM
by

general Many
are
is

techniques

for storing situations with

known
called in

in the prior art In

where

accessed

CPU
Data

10

and executed
in other

one instruction
portions of

time

by

CPU 10

space

considered

cheap
hashing the

compared
is

retrieval In classic

stored

ii

are

time hashing
60 includes called

technique

often

used

operated

on by the program instructions 11
all

accessed

CPU

10

each

record

information in value basis as array

from

RAM

storage to for

system

in

accordance

with

well-known

data

distinguished the

field unique
is

each record
storing

processing Central accesses digital disk auth data

techniques Processing disk Unit

key which
the associated

used

as

the

and hash

CPU
unit

10

also in

controls accesses

and

retheving table
is

record

Taken

whole
of

controller

12 that
disk

turn

large

one-dimensional

logically storage

stored unit

on one or more
13
until

storage

units

such

as 65

contiguous
units

consecutively table of records record

numbered
is is

fixed-size stored in

storage

required

by

CPU 10
from disk
for rapid

At

this

time
unit

Such

typically

RAM

11

programs

and data are retrieved
in

storage

of FIG
sable

where
in

each

an identifiable

and addres
funetion

13 in blocks

and stored

RAM

11

access

location

physical

memory

hashing

BTEX0000464

5893
translates used record the uted as an the

120

key into
into

hash table
the array

array

subscript

which
for the

is

successful

and

returns

success
in is

in

box 35 box 37 and
the

followed
if

by the
is

index

where

searches

data

procedures
entered terminates
-5

termination failure

terminal

not box 36

begin

The

hashing

function

can be any operation mostly uniformly
functions

on

where
in

returned

procedure

again

key that results
across the

in subscripts

distrib include

box 37
list

table

Known
operations not

hashing

If

the

end of the box

has

not

been

reached
is

truncation consbinations functions hash table

folding of

transposition these

tssodulo

arithmetic

and by decision
if

as deternsined
to

33

decision to has of

box 38
expired the

entered
is

determine

Unfortunately unique
keys locations to

hashing in the

the

record

generally
in

do

produce
distinct

pointed

lhis

determined
the record

by
to for

that

many
what
is

map
hashing
an

the

same
of
10

comparing some

some

portion

contents
in

of

location collision every for

jroducing
resolution of record

are called
in

collisions
all

Some form
systems
location

external could

condition be compared by
all

tinsestainp with the

the

record
time-of-day the

example
value rence

current

required

In

maintained
of event an
in

occurrence collided

collision
is

finding

alternate the

computers be compared
In
is

Alternatively
witls if field

occur

event the

can

necessary reachable

Moreover
during future

identifying has the not

alternate that

record box 39
the in

location the

must be readily record
collision
is

searches

for

any

case
to

the

record
if

expired decision
US in this

entered

determine
if it

key

displaced

record record

matclses
is

search

common
present

key

does
is

the

address
if

resolution
is

strategy called table

with which
external entry

the

of

the

saved
not

box 40 and box 41
the search directly to

entered the

the

invention external that

concerned

chaining stores
alt

record of

does

match

key
to the to next

procedure
In

Under
the

chaining each
collided but at
that

hash

bypasses box 40 and proceeds
the

box 41

box 41
in the

records

location pointer

by storing
to the

not

the

procedure
list

advances
the

forward

record

records linked

themselves
list

instead

head
lists

of are

20

Linked
if

and

of

those the

same

records

Such

procedure 38

returns

box 33
the to record

linked in

decision has

box

determines

that entered

under
the
list

formed
allocated to the

by storing
storage

records

individually with in

dynamically
question pointer collided entry
If 25

and maintaining
of the next record
is

each
the
to

record of

expired
of

box
tise

42

is

perform

location

chain

on-the-fly

removal

expired
it

record

from the linked
to the

records

When
found
docs
to

search there not

key
is

hashed

hash
first

table

and the return of the storage
the

occupies

system storage

the pointer search there
is

used to locate
the

the

reeort

pool

as

will

be

described

in connection of

with

HG

In

key

match
the

key

found record

there the pointer
In
this

general the remove
to

procedure

box 42

FIG

operates
its if

used

locate
is

second

remove

an element
pointer to

from the linked
to bypass
is that first

list

way

the

by adjusting

chain
record Deletion bypass pied
is

of records

traversed the

sequentially

until the chain the
is

desired 30

predecessors
the

element

However

found

or

until involves record

end

of

the

readied
to

element
is

be rensoved

the

element of the list then
table array entry
is

there

no

of records the deleted

merely adjusting and returning
pool the

predecessor

and

the

hash of table

pointers
it

storage

occu

adjusted

instead from box

On

completion the search

procedure procedure

remove
returns to

to the available techniques to static

storage

maintained used

invoked box 33
It

by the systeni
for very

42
that

Hashing
fast

have
short in

been

classically

access table

term data
such for the types
is

such

as

compiler
deletions the

can

be
to

seen

the

search

table

procedure
of records to

of of

HG
which
expired each

symbol

Typically

storage storage of data

systems

operates

examine

the

entire
is to

linked past the
is

list

are infrequent quickly In

and the need some

searched-for returning
if

record

and

remove
pool

system disappears records
storage

common

systems can removal
records then the

storage pool such

storage

with

however become
occurrence
lete

the

storage

system

long

lived

and

records

the

storage despite of

depleted

and

many
boxes

expired

obsolete of

merely by the passage event removed
the If

of time or by the
or

remain

automatic
is

garbage

collection

some
not

such

expired lapsed system
of they the

obso
in

insertion
until

new
search

records
is

inhibited

76

and

records

are

from the

will

77 of

HG

deletion

time

seriously

degrade

performance up
in

retrieval First the since they

FIG
collection

or until the the

made by the delete procedure chance table procedure has had
through
its

system
presence they

Degradation
of expired the

shows
records

two

ways
search longer records that useful

to replenish

storage

pool

on-the-fly

garbage

lengthens to

trues than

cause

external

chains

be

Though

the

search in

table

procedure

as as

shown

in

FIG

otherwise

would

be

Second memory

expired storage pool pool for
is

occupy could be

implemented
pseudocode with an hashing removal anywhere

the

APPENDIX
above

PASCAL-like
in connection the

dynamically
returned to

allocated the the

and

described storage

appears

system memory system memory
into the

allocation

information technique technique linked

and retrieval

system using
its list

Thus when
item

depleted system

new
only
if

data the

with

external

chaining
linked

on-the-fly can

can

be

inserted

storage

while traversing
list

be used appears

memory
search ratory

occupied
then

by an expired
to

one
is

is

reclaimed
flowchart of

of records to

with

expiring

data

Referring table

FIG
for

there

shown
the

even
art

in contexts

unrelated that
this

hashing

procedure

searching

hash

table in

prepa accor

will appreciate

technique

person can be readily used with

killed in the applied

to inserting with the

retrieving

or deleting

record
the
list

to

manipulate

linked table in entire for

lists

not

necessarily

hashing

dance

present

invention and involving
in targeted linked of

dynamic
Starting search to oo as

The
traverses as
it

search

procedure
the

shown

in

FIG

implemented above
records be readily

removal
in

of expired

records table

pseudocode
the

APPENDIX
list

and
all

described expired can

box 30 of the search
being of

procedure
for
is

FIG
in In

the

linked

removing

key of the record
provide table the array
is

searched

hashed

box 31

searches

key match The procedure some
the but not
list all

subscript location

an array

element

box 32 the hash
generated target linked to in

adapted to remove
thereby shortening
at

of

the

expired

records

indicated to provide

by the
the

subscript to the

linked

traversal

time and speeding
expired

box 31
list

accessed

pointer the

up the search
records in

the

Decision

box 33
the

examines

pointer
list

value

deter
If

the

some leaving expense of perhaps list For the procedure example

can

be

mine whether
the

end of the linked reached match
decision

has

been 34
is

reached
entered
in

modified to terminate
65 like

when

key match

occurs
of

PASCALsearch table the

end

has been
if

box

to

pseudocode
in

for

this alternate

version

determine

key
will

was

previously

found
if

decision search
is

appears

the of

APPEN1IX
choosing

The

implementor
strategies

even has

box 39

as

be

described

below

so

the

prerogative

among

these

dynansically

BTEX0000465

5.893.120

at

the

time

search

table
all

is

invoked

by

the
at at

caller other other

thus times times

begins

at

staring

box 70
table the

from which
of

box 71

is

entered

In

sometimes removing choosing
decision

removing some
to but

expired of thent

records and yet

box 71
the

the search key with of

procedure record the
to

FIG
inserted

is

invoked As

with
in

not

all

search

be

noted
finds

remove

none
based
is

of

them Such
factors

dynamic as
for

runtime

connection linked therein retnoves Decision
list

FIG
whose
the

search

table

procedure
record the that
it

the

might be

on

such

example pool

element

key value key

of the

contained

how much memory
general currently factors

available of

in the

system storage number system
information
in

matches
expired

search

and
where

at

same
linked

time
list

system

load time
in the

thy

the

of

records other

records
is

on-the-fly entered

from

residing internal

information to the

and

box
the

72

then table
If

is

determined
record with

both

and external
itself

whether
storage
art

search

procedure
is

found

and retrieval
appreciate while

system

person of
list

skilled
all

the

will

matching
to be

key value
is

so box 73
into the

entered
list

where

the record
in

inserted of
insert

that the technique the linked not the can
is

put

linked

element

the

removing
can be
all

expired to

records position the old record with

matching
that the

key value
old record

In has

box been
in

searching

expanded
expired
if

include are

74

the

procedure

reports

techniques

whereby
that

necessarily

records

removed and
records In dure an

decision be

regarding

and how

replaced

by the new box 75

record

and the procedure

terminates

many
tS

terminal

to delete there

dynamic

one
of

Returning

to decision

box
is

72

if

matching
to

record
if

is

not
is

FIG
that

shown
record through with table

flowchart

remove system
as

proce
either will

found

decision storage
list

box 76
in

entered

determine

there

removes
record

from the retrieval
the delete or as

sufficient

unexpired
in

noted through with

connection the search

HG
is

procedure an
noted

be

new
that 20 inserted nal
if

linked

system storage pool to accommodate element If not box 77 is entered to report system
is full

the

expired

record

the

storage

and

the

record

cannot
in

lse

procedure

in connection

Following that

the

procedure

ternsinates

termi

FIG
table

In general being

this

accomplished
procedure paasing
list

by the invoking

box 75
decision

procedure
search

either the

delete

FIG
to the
to

or the

box 76 determines

that

sufficient

procedure pointer to

FIG
linked

storage

can

remove

be allocated
list 25

from the system storage
then
is

pool for
the to

new

linked

procedure
pointer linked to
list

element element
table the In

remove
same
location
list that

element

box 78
In

is

entered the

where
record

actual

memory
is is

that

elements

predecessor of the the hash

in the

allocation copied

made
the

box 79
allocated linked

he inserted and box 80

and the subscript
the pointer
is

array

into In copied the that

storage the in

in list

box 78 element
into

containing

to to
is

head removed
first to

of

linked the of case

from
the
list

entered
record to 30

box 80
into
it

containing the linked

the
list

which element
the the

the to

element

be
the

box 79
record

is

inserted

be removed
pointer procedure

element
the

the linked procedure

which

contained the record

hashed
inserted in

The procedure
into the

then

predecessor

passed has

remove

by

reports storage terminates

was

information

invoking
or

the

NIL
to has

sometimes
the

called

and
in

retrieval

NULL
dure the

system

box

81

and

the

procedure

EMPTY
element

value
to

indicating

remove

proce
in

box 75
detailed record Starting
is

that list

the

be rensoved procedure
to

no predecessor
the the

FIG
used
to retrieval dure record
it

shows
retrieve

flowchart

of

retrieve

The on

invoking

expects

remove
passed

from the
in

information the search the

procedure
pointer so or that that
it

completion

have
to the

advanced now-removed
in final

storage table

procedure and proce
of the

system

box 90

originally pointed
to

element
linked
list

of

FIG
to be

invoked
as

in

box 91

using In

key was

points the

the

successor

element was
in

that

retrieved
if

the

search with If

NIL

if

removed

element
of

the

element makes

The
use of in the
is

key

decision

box 92 found
to

is

determined
search failure

record

search the

table

procedure

FIG

matching not box and

key 93
is

particular

by the
report

table of the

remove

procedure
retrieve

entered

described entered described

procedures advancing passed pointer is made use of in that box 33 of FIG way
it

this

procedure

the

procedure
record

terminates

in terminal
is

directly

following
in

completion with

of

box

42

box
to

96
copy

If

matching matehing

was
into

as

was

found
record

box 94
store

entered

the

record

above

connection

FIG
actual

for processing

by the
of

calling

The remove
designated
that it

program

box 95 and

procedure

causes the

removal

of

the so that table role 45

is

entered

to return an

indication

successful

retrieval

element the

by adjusting element
has to the

predecessor

pointer

the

procedure shows

terminates detailed

in terminal flowchart records Starting search

box 96
of delete the

bypasses

be removed In the ease

FIG.7
useful storage

procedure
information the

the

predecessor entry

pointer

NIL value
subscript adjusted
is

the

hash
the

for actively

removing system
the

from
at

array of
its

indicated

by the passed
pointer

plays

and

retrieval

box

100

pro
as the

the

predecessor

and

the the

same
storage

stead Following pointer by
the

adjustments
is

way in occu
system

cedure of FIG
in

invokes the

table

procedure
to

of FIG

box 101 key

using

key of the record box 102
to find
it

be deleted
if

pied

removed

element
allocation starting

returned

to

the

search table

In decision

is

determined
with

the

search

storage

pool for future then
at

procedure

was
is

able entered

record

matching
of the

key

Beginning
to the
it

box 50 of FIG
is

the

pointer so that

if

not box

103

to report

failure

deletion

list

element
its

to

remove

advanced
list

in

box 51

procedure

points

to

successor
if

in the linked to

Next
is

decision
first

box

106
in

If

52 determines
in the

the

element
list

remove by

the the

element

decision

and the procedure terminates in terminal box record was found as determined matching by box 102 the remove is invoked procedure of

HG

containing for the to

linked

testing

predecessor
If

box 104

As noted

in connection of
list

with

FIG
linked
is

the
list

remove element
to the

pointer
is

NIL value
the the

as described
list

above
pointer

so box 54
in the

entered array

adjust to

linked

head

hash
the

removal procedure causes from its containing linked
report successful deletion

designated

Box
the

105

then

entered

table

bypass

first

element

after

which

to

caking box

program

and

on to box 55 if not box 53 is entered procedure continues where the predecessor is to bypass the pointer adjusted element to remove after which the procedure proceeds once again to box 55 Finally in box 55 the storage occupied by
the

procedure

terminates

in terminal

106 PASCAL-like
components and retrieval invention no difficulty shown
in

The

attached
listings

APPENDIX
for
all

contains programmed

pseudocode
necessary to

of

the

implement
in

an information

storage

bypassed element

is

returned

to the

and the procedure

tenninates detailed
in

in terminal flowchart of

system storage box 56

pool

system operating

accordance
skill

with the present
art

Any
65 the

person

of ordinary the

in the

wifi

have

FIG
suitable

shows
for use

an insert procedure and
retrieval of

implementing ware

disclosed including

system and procedures programs
for
all

the

information

storage

APPENDIX

common

hard
of
this

system of the present

invention

The insert procedure

FIG

and system software

arrangements

on the basis

BTEX0000466

5893120
14
description the
It

including

flowcharts

and information

shown

in

present that the

invention
invention

It

is

also

clear

to those
in

skilled

in the

art

APPENDIX
should also he clear
to

can
that
it

he
is

used

diverse
to

computer
use of hash linked

those

skilled

in

the be

art

that

other

applications tables
lists

and
is

not

limited

the

embodiments
skilled
in

of the present
art

invention

may

made by those
of the

but with

applicable

to other

techniques

requiring

the

without

departing

from the teachings

expiring

records

Appendix

Functions

Provided

lit

tollowing insert

functions

we

made

available

to

the

application

program

record

record_type
if

Returns

replaced

record

associated

with

recordicey

was

found

and

subsequently Returns passed Returns record retrieve Returns record Returns delete

replaced
if

inserted record
full if

record subsequently

associated inserted with

with

record.key

was

not

found

and

the

was

record be

associated because

recordkey
is

was

not

found

and

rIte

passed

could

not

inserted

no memory

available

tecord
success

record_type
if

record

associated

with

record.key

was

Iburad

and

assigned

to

failure

if

seareb

was

unsuccessful

record_key
success deleted failure
if if

record_key_type
record associated with

Reotrns quently Returns

record_key

was

found

and

subse

not

found
Definitions

The

following

fonnal

definitions global
to all

are

required

for

speciing
functions

the

insertion

retrieval

and

deletion

procedures court type type

They
table_size

are

procedures

and

shown

below
/s Size

of of of

bash linked linked

table
list

list_element_pointer list_element

list_element

/5

Pointer /5

to

elements element

Each

list

4/

record record_contents

record_type
Singly-linked
list

next end
var table

list_elenrent._pointer

array

0.
table

table_size

lJ

of

list_element_pointer /5

Hash Each
array entry
is

table of
list

pointer

to

head

Initial

state

of

tableiJ

nil

table_size
fittest

Initially

empty

5/

Procedure

function var

insert

record

record_type

replaced

inserted

full
Pointer or into
list

positiotr

list_elentent_pointer

of

turns
if

record

5/

new

element positions to

not

found

s/

dmamy_pokeer index
begin
if

list_element__pointer table_size /5

t5 Table

Dont
index

need

predecessor function

a/

0.

mapped

by bash

search_table

recotdkey

position

dunsntypointer

index

/4

Record

already

exist

5/

thenbegin
position1 return .tecord_contermta

/Yeaupdateitwithpassedrecord
record

replaced

end
else
if

/Noinaennewrecordatbeadoflist/
available then return

no memory
else begin

full
/5 /5

if

memory
is

available available allocate /5

to for

do

so

Memory
Dynamically

nate node
it 5/

newposition
positicint position1 tablelindexi return

new Hook

iecotdcontents
next tablelindexi position

record

in

5/

inserted ./
else begin

end end
Retrieve

insert5
Procedure

function var

retrieve

var

record

record__type

success

failure
/5 Pointer nerd into
list

poaitiosr

list_element_pointer liat_gletnemd_pointen table_size

of found

record

duny_pointrt
durnmy_irxlex
begin
if

Dont

positions to

predecessor function

Dont

need

table

Sex

mapped

by bash

search_table then begin

recomeLkey

position

duntrny_pointer

dununy_iralex Yes

Record
return
it

exist

to caller

record

positiont

record_couteuts

rehen end
else

success

return

failure
retrieve

No

report

failure

5/

end

BTEX0000467

5.893.120
11
-cotsfitsued

12

Appendix

Delete

Procedure

function var

delete

record_key

record__key_type

successfailure
Pointer /C /5 Points into to
list

position

list_element_pointer list_element_pointer table_size

of

found

record

Cl

previous_position

positions
to

predecessor hash finartion

index
begin
if

index

mapped

by

search that

table begin

record_key

position

previous_position

index

/5

Record Yes

exist
it

5/

retnove

remove
return

position

previotts_position

index

success

end
else return failure /5 Search Table delete

No
Procedure

report

failure

end

function

search_table var var var

record_key
position

record_Jcey_type

list_element_pointer list_element_pointer table_size and delete expired

previous__position index

boolean
records to subscript
its in

Search point
to

table

for record_key record and
is

target

list

if

found
is

position returned
in

is

made
otberwise

to

located
is

previous_position
set to

predecessor
is

and
to

TRUE
hash

FALSE
case
var

returned

index

table

that

mapped

by

function

either

hsL_elemeuL_potnter
previous_..p
list

/e

Used
Points

for traversing to

chain

elensent_pomter

ps

predecessor

begin index hash tabletindexi previous_flp posit nit nil nil /5

record_key

Ia

hashretutasvalue

intbetange0
/s

table_size_laI
before

Initialization

loop Dino
Ditto Ditto

sI

on

is

Cf

previous_position while
nil

HEART

OF THE

TFCl-INIQUE
/a

Traverse expired

entire records

list

deleting search

af

as

we

a/

begin
if

pt
then else
if

record_contents

is

expired

remove
begin position

previous_p

index

/5

ON-THE-FLY

REMOVAL OF EXPIRED

RECOIWt

nil

then

if

pI

xecotd_rontents.key

record_key
/e
If this is

record

wajated/

tlaen

begin

position

previous__position

previous_p

end
pa save
its

pssition
to

previous_p

Advance
.next next record begin

pT end

else

return

position

nil

Jr

Return /5

TRUE

if

record

located

otherwise

FALSE

5/

search_table Table Procedure

Alternate

Version

of

Search

function

search_table var var var

record_key
position

record_key_type

list_element_pointer list_elensesit_pointer boolean

previotus_positiorr index

table_size

SAME

AS VERSION
IS

SHOWN

ABOVE EXCEPT
OF ALWAYS

THAT

THE

SEARCH THE

TERMINAVES CHAIN
Used
Polets
5/

IF

RECORD
var

FOUND INSTEAD

TRAVERSING

ENTIRE

list_element_pointer

for traversing

chain

aJ

previous_p
begin index hash

lisLslensenLpoiuter

tops

predecessor

5/

record_key
Initialization nil before

tabletindexi

loop
Ditto /a Ditto Ditto
el

previous_p
position nil

5/
5/

previous_position while
nil

nil

/5

HEART

OF THE

TECHMQUE
expited

Traverse tecoids

list

deleting search

as

we

begin

lipt
then

reconi_ccxstents

is

expired

remove
begin

ptevious_p

index

/5

ON-THE-FLY

REMOVAL OF EXPIRED
If
this is

RECORDt
wanted/
pnsttion
5/

else
if

pI
than

.recottl._contents.key begin

record__key

record
its

save

position previous_position return previorss_p

true

We

found

the

record

so

terminate

search

end previous_p
is

Advance
next

to

pI next

record

BTEX0000468

5893120
13
-continued
II

Appendix cal eat
return

else

begin

false
/5

Itecard seasch_ table

not

banal

end Remove

Proceduns

procedure

remove

var

etetn_to_det

tist_eknseiit_pointer list_elcment_jiointer

previous_elem
isxlex Delete

table_size

stein_to_dell

from

list

advancing
nit it

clem_to_del
is 55t

to

next

clement previous_elem
in lists
to

points

to

elem_to_jIels
war begin

predecessor

or

dent_to_dell

clement

list_elcmeriLpointer

Save

pointer

elan_to_del

hr

disposal

dens_to_del elem_to_4el
if

Save

so

we

can

dispose

when

finished

adjusting

pointen

elem._to_dell
nit elens_to._del next

next
fs Deleting jC element head requises as changing

previotss_elem then else

table
previous_elemt

pointer

opposed

to

elem_to_det

js

p_Assofl

next

pointer

dispose
/5

Dynamicauy remove/

dc-allocate

node

claim

technique storage

to

store

the

records

with

same

hash

address

An

inform_ation

and retrieval

system the system
25

at

least

some

of the records means
records utilizing

automatically search the

expiring to access

comprising
linked in
list

record linked the record

search
list

key

to store of the

and provide system
at

access least

to records of the

stored records

of

having

same means
ones

hash address
for identifying of the records
list is

memory
search list

some

search
at

means
least list

including

automatically record linked the record

expiring

means

and removing
utilizing search

some
of

expired

key to access

the 30

from the accessed

linked

records

when

the

linked

and
the record search

search

means
at least

including

means
of the

for identifying ones linked of
list

and removing
records

some

expired the

the
is

meals

utilizing

means

for inserting
at

from and

the

linked

list

when

retrieving the

and deleting time removing
in the

records
at least

from the system and some
list

accessed

same

expired of

ones

of

means
the

utilizing
list

the

record
at

search

means
records

for accessing
at

the

records

accessed

linked

records

linked of

and

the ones

same
of

time removing
in

least to

The
claim

information further

storage including

and retrieval means
for the
list

system according dynamically deter
search

some
list

the

expired

the

the

linked

for record

mining maximum
information further storage including

number

means

to

The
to claim

and retrieval means
for the
list

system according
dynamically search

remove

in the

accessed

linked

of records
information access to the the records records records auto-

for record

deter means
to using

method

for storing technique

and retrieving
to provide technique

mining maximum remove
in the

number

hashing

accessed

linked

of records
information access to the records

and using
with

an external hash

chaining
at

to store of the

method
using at
least

for storing
list

and retrieving and provide

same

address
the

least

some

records steps

linked

to

store

records
matically the accessing

expiring

method
list

comprising the
records

of hash

some

of

the

records

automatically

expiring

method

comprising the steps
the linked
list

of
records

linked

of

having

same

address
identifying
at

accessing identifying of the

of

least

some

of the automatically

expired

ones

at least

some of the automatically and some
linked of the
list

expired

ones
of 50 the

records
at

records
at

removing
records

least the

removing
automatically expired records linked
list is

least the

some
linked

of

the
list

automatically

expired
list is

from

when

from and

the

when

the

linked

accessed

accessed
according to

The method
step of

claim

further

including

the of
list

inserting 55 the

retrieving

or deleting the step

one
of

of

the

records

from

dynamically ones

determining
to

maximum when
the

number
linked

system method

following according

removing
further including the of
list

expired
is

of the records

remove

The
step

to claim

accessed

of

dynamically ones

determining to

maximum when
the

number
linked

An

information

storage

and retrieval

system

the

system

expired
is

of the records

remove

comprising hashing means
to provide access using to records an external stored in

accessed

memory

of the

system and

chaining

BTEX0000469

Application

or

Docket

Number

PATENT APPLICATION FEE DETERMINATION
Effective

RECORD

October

1996

57
SMALL
ENTITY

-7

7C6/
OR
OTHER THAN SMALL ENTITY

CLAIMS

AS FILED
Column

PART
Column

FOR

NUMBER

FILED

NUMBER EXTRA

RATEJ
OR

FEE

BASIC

FEE CLAIMS CLAIMS PRESENT

TOTAL

minus 20

OR
INDEPENDENT
minus

OR
MULTIPLE

DEPENDENT

CLAIM

OR
It

the

dillerence

in

column

is

less

than zero

enter

in

column

OR
CLAIMS

AS AMENDED

PART

II

SMALL

ENTITY

OR

OTHER THAN SMALL ENTITY

ADDI RATE
TIONAL FEE RATE

AUDI-

TIONAL FEE

x$11 x40
FIRST

OR OR OR OR

x$22 xOO

PRESENTATION

OF MULTIPLE

DEPENDENT

CLAIM

130
TOTAL ADUlT FEE

26O
TOTAL ADUlT FEE

cc

ADDI
RATE TIONAL RATE

ADDI
TIONAL FEE

FEE

x$11 x40
FIRST

OR OR OR OR

x$22 x80

PRESENTATION

OF MULTIPLE

DEPENDENT

CLAIM

130
TOTAL ADUlT FEE

260
TOTAL AUDIT FEE

ADDI
RATE TIONAL RATE

AUDI-

TIONAL FEE

FEE

x$11
Ui

OR OR OR OR
in

x$22 xBO

x40
FIRST
lithe

PRESENTATION
in

OF MULTIPLE
than the Paid Paid entry
in

DEPENDENT
write in
is

CLAIM
column

130
enter

260
TOTAL AUDIT FEE

entry

column

is

less

column

tt

the Highest Highest

Number Number Number

Previously Previously Previously

For IN THIS

SPACE

tess less
is

than than

20

20
lound

lithe

The Highest FORM PTO-875

For IN THIS SPACE Paid For Tcital or Independent Governmt
Oeice
rese

is

enter

TOTAL AUDIT FEE
in the

_________
box

the highest

number

appropriate

colurnni
u.s

-u.s

Rev

Printing

413-2sW4sts1

Patent and

Trademark

Ottice

DEPARTMENT

OF

COMMERCE

10/96

BTEX000047O

FomPTO
REV
ZiOn

1120

U.S

DEPARTMENT
Patent arid

OF COMMERCE
Trademark
Office

PACE

DATA ENTRY

ST EXAMINER 2ND EXAMINER

CODING
TYPE APPL

SHEET
FILING DATE MONTH

__4

C_

DATE DATE

2-

_97

APPLICATiON

NUMBER

a8/77536
TOTAL
CLAIMS

ci
SMALL ENTITY

1k-i
FEE CONTINUITY

DAY

YEAR

SPECIAL HANDLING

GROUP
ART
UNIT

jJJ54j7
ATTORNEY

a9j

CLASS

SHEETS OF DRAWING

INDEPENDENT CLAIMS

FILING

FOREIGN LICENSE

rRir
CONT STATUS

DOCKET NUMBER

r-JF_191

El

LL4_Lsj
DATA
PARENT PATENT PARENT FILING DATE MONTH DAY YEAR

PARENT APPLiCATION SERIAL NUMBER

CCT17 T/ CT
Lii

CT/ft
APPLICATION_SERIAL

NUMBER

NUMBER

CT

PCTIFOREIGN

APPLICATION

DATA
FOREIGN DATE
DAY YEAR

FOREIGN
PRIORITY

CLAIMED

COUNTRY CODE

FILING

PCT/FOREIGN

APPLICATION

SERIAL

NUMBER

MOTN

u.sa

1995-401-429

BTEX000047I

TITLE

OF INVENTION

______________

______________

ATTORNEY

REGISTRATION

_________

________
CORRESPONDENCE

J1IIrrErJIlIr
NUMBERS ______________

NAME AND ADDRESS

AUTHORITY FAMILYNAME GIVEN NAME
CITY

CODE

APPLICANT/iNVENTOR

DATA

NAMESUEFIX STATE/CTRYCODE

AUTHORITY
FAMiLY

CODE
NAME
SUFFPX

NAME

GIVEN NAME
CITY

STATE/Cm

CODE

MORE

BTEX0000472

Search Options Search for both singular and plurals Search for spelling variants Display intermediate result sets

YES YES NO

Num

Search

Hits
W/2

collision
AND

chain hash AND chain
Clinked

resol
W/2

OR

avoid

415

OR pointer

list

51

AND AND AND AND

chain hash
W/2

collision

resolution OR resolv

48

hash

OR linked OR

chain
pointer

10

collision

AND

linked OR pointer

IEEE/lEE

Publications

Ondisc Jan

1990

Nov

1996

Page

BTEX0000473

INSPEC
Doc

4358851

Type Title
Authors Affiliation Conf Title

C9304-6120-017 Conference Paper Hash table in massively

Yen I.-L Bastani Dept of Comput Sci
660-4

parallel

systems USA Processing

Houston Univ TX Sixth International Parallel Proceedings Symposium Cat No.92TH0419-2

Editors Publisher

Prasanna V.K Canter L.H IEEE Comput Soc Press Los Alamitos CA USA Date 1992 xviii693 pp USA Country of Publication

ISBN CCC
Language
English

8186 2672 8186 2672 0/92$03.00

Conf Date 23-26 March 1992 Conf Loc Beverly Hills CA USA Conf Sponsor IEEE ACM
Treatment Abstract
look at the performance and new collision resolution strategies for hash tables in massively parallel systems The results show that using hash table with linear probing yields accesses OlogN time performance for handling by processors when the load factor of the table is 50% where is the size of the hash table This is better than the performance of using sorted arrays Two phase hashing gives an average time complexity OlogN for simultaneous accesses to hash table of size even when the table has 100% load Simulation results also show that hypercube hashing significantly outperforms linear probing and double hashing
The

Practical authors

Refs

Classification .C6l20 File organisation C5440 Multiprocessing and algorithm theory C5470 systems C4240 Programming Performance evaluation and testing Thesaurus Computational complexity File organisation Parallel Performance evaluation processing Simulation results Massively parallel systems Free Terms Hash table Collision resolution Linear probing Time complexity Performance Hypercube hashing Double hashing Item Availability Image

Copyright

Instn

Electrical

Engineers

All

rights reserved

BTEX0000474

dhis
FILE
Li

USPAT
DEL

ENTERED
HIS

AT

082439

ON

14

APR

1998