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)

Download PDF
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

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


Why Is My Information Online?