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

Filing 284

Response to CLAIM CONSTRUCTION BRIEF filed by AOL Inc, 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. 6 EXHIBIT 5 PART 1 OF 6 BTEX0000I 74 120 fu2h- Foreign priority claimed 35 USC 119 COndWons ysy met CI no AS FILED OR COUNTRY STATE SHEETS TOTAL CLAIMS ORWGS .- INOEP CLAIMS FILING RECEIVEO FEE Verified and Acknowledged ATTORNEYS OOCKET NO Exantnegntuais cflt.jr jnn1r RSSUE FEE IN FILE I- u.a OEPt OPcOMMJPAT TMPTO-436L Racl2-94 PARTS FILED NOTICE OF APPLICATION SEPARATELY ions Eiier OF ALLOWANCE ILEO HOAitJ -1- /CLAIM$ ALLOWED I.unt Claim ALkM q1 ISSUE FEE Amount Due Date /9 Sheets toipltaims Assistant Examiner DRAWING PaeL mOWS B1JkCI Drwg Age Drwg Fi9 ISSUE Primary Examiner BATCH NUMBER Label Area WARNING PREPARED The by FOR ISSUE may be 35 Unaut 18 Information the United disclosed States herein title restricted ed 368 disclosure PossessIon may be prohibited the Code Office Sections to 122 outside only U-S Patent Trademsil Is restricted authorlz employees end contractors Fomi PTO-436A 5/52 Rev CA flC\ BTEX0000I 75 BAR CODE LABEL HhIll 1100 III 111 IlIIDIllIhI IW PATENT APPLICATION SERIAL NUMBER FILING DATE CLASS GROUP ART UNIT 08/775864 01/02/97 395 2307 RICHARD NEMES BROOKLYN NY CONTINUING VERI FlED DATA FOPEIGN/PCT VERIFIED APPLICATIONS FOREIGN FILING LICENSE GRANTED 03/01/97 SMALL ENTITY RICHARD 1432 Lu MICHAEL 35TH NY NEMES STREET EAST BROOKLYN 11234-2604 METHODS HASHING EXPIRED AND DATA APARATUS WITH FOR INFORMATION STORAGE AND AND RETRIEVAL USING OF TECHNIQUE EXTERNAL CHAINING ON-THE-FLY REMOVAL This Patent is to certify that annexed Office hereto of the is true and of the Trademark application of the United copy from the rcords which is identified above States By authority COMMISSIONER OF PATENTS AND TRADEMARKS Date Certifying Officer BTEX0000I 76 SEpjA 140 AA 02/28/97 08775864 201 42SOc ON flO-1556 5/87 BTEX0000I 77 Plea. 1e pin Sgnj Reduction Act of 11 1995 no penons 1w Apprewed ittademaft QeIre is Uvough WJWPa vetS U.S DOfrRTKCHT CF dionieva 049 lb Paoe.wat as isouSd to tnpcnd toe ooltecllnlwvneUon usia casicRc toInu floe AUomey DS Number 775 22 /Alia4 .7L 64 NEW tie UTILITY PLICATION PATENT TRANSMITTAL Wit First Named Inventor ____________ Total ________________ -I tiwn.wappe Pages in this tiisat sJ1rfeJS Dninc.s APPLICATION haidct Checkilsf ELEMENTS ACCOMPANYING APPLICATION Swis mwiedned Eemenn Appilcabon action smjcte new usMy patent Please Wee to applicant MPEP Sections 506 601 37CFR 1.71 1.53 35 usc 111 112 Ar beta/led Of an onpinal paIwi exptansflriugatntng il.nsss app/catton PARTS Fee Tiznsmlttal Specification Fomi prescribed tiling fees Assignment Paped Certified Title Copy of Priority is Documents of the Invention foreign pnonty claimed Cross References to Rated Applications Computer Program in Microfiche applicable Statement Regarding Federalty.sponsored English Research/Development applicable Translation Document applicable Reference to Microfiche Appendix 10 Information Disclosure ri L......J Copies citations of CS applicable StatemenuPTO-i9 Background of the Invention 11 Petition Checklist and Accompanying Petlion Brief Summary of the Invention Preliminary Amenoment Brief Description filed of the Drawings 13 Proprietary Information drawings CfI Detailed Description 14 Return Receipt Postcard Claim or ClaIms 15 Small Entity Statement Abstract of the Disclosure 16 as prescribed E1 Additional Enclosures please identify b.lotq IJ Genetic Drawings 35 USC 113 when necessary by LISP REPERi5 Executed Dlantion Sequence ii Submission SIGNATURE Firm OF APPLICANT A1TORNEY OR AGENT if applicable must be indudeo9 or lndividuaj Paper Copy RICHAR name NEMES Computer statement Readable Copy Slgia/ure Identical Verifying Paper and Date Computer Readable Copy DECEMBER 20 1995 FOR OFFICIAL USE ONLY Application Number class Independent Claims Date of Receipt Application TYej GAU Total claims Filing Date Foreign Filing LicerSe Drawing Sheets Small Entity Foreign Address Special Handling Suroen Inc Hour Statement ol time This loan are required estimated to to tale this 0.2 hours to complete sent to the Time will vary depending Officer upon the needs and amount ol the individual Office 4t you complete loan THIS case ahould be Any remments Chief Information FEES OR COMPLETED Patent for FORMS TO ADDRESS Trademark Washington SEND To Washington Assistant DC 202 Commissioner Patenis DC 20231 BTEX0000I 78 FEE CALCULATION The Conimlseloner SaSated fees end Is continued hereby tlhothad to dwgs to ndll any as ADOm0NAI Cods 106 124 130 205 60 FEES bssaipdon SwSwpe-Ssflhingf.sroMh Swdierge las pr5Asiotal p......nla Accounif Number Account Nina Vi uo i3 147 25 titan9 In or os Fe R.qus4 tIC and ens Mde.nI User 37 ie 11 td 1.1$ ST ii Unis Fat act at Ta State sat ti 129 130 Non.Engiih.p.citaticn For l%ng r.qunl for AWs 37 1412.460 L460 900 fnaminauon 1.311b 112 900 112 Enclosed crtaac ReqtnsllngpublatoncWSlRpnoto .edcn Dottier tees effectIve 113 17W 110 390 930 1.470 300 300 260 113 1.7W Requnteig publiention action SIR Slot amrna FEE CALCULATION FILING FEE large Pee EntIty 1010196 115 116 111 215 216 217 216 219 220 221 56 195 465 736 150 150 130 btenSenSrsspons.vsithinSstmonth En.nsicntora.pont..wWhinncondmw Eidsntionterresponsewdhlnf$dmosh EnteSon Sr rapone althln Small Entity Ft 770 320 530 170 150 Pa Cods 201 206 201 203 214 Fee Pee Osawlpton Pa 116 Paid 119 loutS moit Code 101 NSic.dA.S 345 160 255 355 15 UtllttyIThngfn 120 121 136 flngaSkisupponoansppni aqu.atrosbeavtng PMMSatiatAlaeapublictas.pqoonet5 P.dIfon to 106 107 ios 114 Deelgnl%llngtee PIenIfIllngfn RelseusIllIngle 1470 110 1331470 240 65 140 PrctIslonslflhlngfee rwwn unavoidably sb.ndonS 141 SUBTOTAL 1290 241 646 PMiSai to ran uninl.nhionalty 385- .bendsn.d 142 ppMion or r.rasu CLAIMS Toticlaims Indepenosnt Extra Pm 1.20 242 243 244 645 220 325 tiflufy Satan Fee Paid 143440 144650 Daign Satiate Plait _3 .ZOs ___ .3 Claims sa In to the Multiple Dependent ____X tfb 122130 122130 Petitions Csnmsaioaar to 12350 126230 12350 126 230 Petitions mated of pnMsion.l applications Sutonission Woonalon latent fltfltat Disclosure Stied large Entity Small Pee Entity $n Code 103 102 104 109 Fe Pee Pa 531 Dsactptton 40 531 40 Code 22 60 260 50 203 202 204 209 11 nde PIUyIW Sass R..ennIl flIng sssignmsd per PM be ejection to Clalsnslqessoeeaof2o 146 170 246 365 sdsniseion oiler final 40 130 40 lnda.aisl.ritdSnakeaancf3 PAillIplsdep....d.lclalm 31 CFR 149 770 249 335 For adaed 1.1 .thMl....J knentlon be R.iseu independent Sims Other Other fee 31 01R 1.129b as 11 110 22 210 Rnasssm.ans20 atS over petal scsdfl spe SUBTOTAL by Basic fling SUBTOTAL fs 4o Raduosd Fe PSS 5UBMrrrfD Typedor Pflnted BY Name RICHARD _j NEIvtES Signature $1 This of oat nanted sit DEC QUiZ to the 20 II901 the Button comments flout Statement the loon is to take to 0.2 hours thIs to osmose elmuld Time be sent vat deoending on amount tim needs it odisus Patent asS required oompls form Washington DC 20231 DO NOT SEND PUS OR COWLETED FORMS TO ThIS 0151 Soonatlor ADDRESS SEND TO an My OfIloer Assistant Tiadenarit Dittos Commiss5e for Patents BTEX0000I 79 zo Patent Application of jq 864 Richard Nemes 1432 East 35th Street Brooklyn Citizen New York 112342604 of America U.S.A of the United States SPECIFICATION to TITLE OF INVENTION METHODS AND APPARATUS FOR INFORMATION STORAGE AND R1kIEVAL USING HASRING TECHMQIJB WITH EXTERNAL CHAJNThTQ AND ON-THE-FLY REMOYAL OF EXPIRED DATA 15 CROSS-REFERENCE TO RELATED APPLICATIONS Not Applicable STATEMENT DEVELOPMENT 20 REGARDING FEDERALLY SPONSORED RESEARCH OR Not Applicable REFERENCE TO MICROFICHE APPENDIX Not Applicable 25 BACKGROUND OF THE INVENTION This invention relates to information storage and retrieval systems and more particularly to the use of hashing techniques stored in in such systems storage mechanism can be retrieved Information or data computer-controlled stored by searching 30 for particular key is value in the records The stored record with key matching to the search key value then retrieved Such searching techniques require repeated and access records into the storage systems such searching mechanism even if to perform key comparisons In large storage such retrieval augmented by efficient search procedures as the BTEX0000I 80 Richard Nemes binary search comparisons often requires an excessive amount of time due to the large number of key required and Another well-known computer technique is much faster way of storing and retrieving information from storage also called albeit at the expense of additional storage is the so-called hashing scatter-storage or key-transformation method to In such system the key called operated on by which hashing fUnction is produce storage address in the storage space array the hash table large one-dimensional record of record locations This storage in the address is then accessed directly for the desired Hashing techniques are described classic text by Knuth entitled The Art of Computer Massachusetts Programming 1973 Volume Sorting and Searching Addison-Wesley flmctions Reading pp 506-549 of keys into Hashing distributed are designed to translate the universe addresses unifonnly truncation folding will throughout and the hash table Typical hashing functions include transposition modulo arithmetic in the disadvantage of hashing is that more than one key inevitably translate same storage address causing collisions be provided forward in storage Some form called of 15 collision resolution must therefore For example the simple strategy from the initial linear probing which consists of searching storage address to the first empty storage location is often used for resolving collisions is Mother each hash table method location called external chaining of records In this technique all is pointer to the head of linked list of whose keys list is itself 20 translate under the hashing function to that very hash table address The linked searched sequentially when retrieving inserting or deleting record is Insertion and deletion are done by in the adjusting pointers in the linked list External chaining in discussed in considerable detail aforementioned text by Knutli Data Structures and Program Design Englewood of flashing Cliffs Second 1987 Data Edition 25 by 6.5 Kruse Prentice-Hall and Section Incorporated New Jersey in Section Hashing with Abstract 6.6 Analysis and Pascal pp Stubbs 198-2 15 and Structures Data Types by and Webre 7.4 Brooks/Cole Publishing Company Monterey California 1985 Section Hashed Implementations pp 310-336 Some 30 forms of information are such and that individual data items is after limited period of time become obsolete theft presence in the storage system no longer needed or desired BTEX0000I 81 Richard Nemes Scheduling activities for example involve data data that become it obsolete once the scheduled occupies event has occurred An automatically-expiring item once put to expires needlessly an unexpired for computer memory storage that could be otherwise be use storing the item Thus expired data insertions items must eventually addition linked the removed to reclaim storage subsequent long In the presence of many expired items results in needlessly will be search times since lists associated with external chaining longer than they otherwise and maintain fast would be The to goal is to remove these expired items to reclaim the storage access the data for large The heavily problem then is to provide the speed of access of bashing techniques at used information storage systems having expiring data and the same time prevent the records 10 performance degradation technique for resulting from the accumulation data of many and expired Although Patent hashing dealing with expiring is known is disclosed in U.S Number 5121495 entirely inapplicable issued June 1992 that technique confined to linear probing and is to external chaining The procedure shown in the there traverses in reverse order continually consecutive sequence fill of records residing hash table array relocating 15 unexpired records to gaps linked left by the removal leave of expired ones items Unlike furthermore arrays is lists no gaps when singly from list it are removed and it not possible to to efficiently traverse linked in reverse order There it are significant advantages external chaining over linear probing that sometimes make texts chaining are the method of choice 20 as discussed in considerable detail in the aforementioned and so bashing prove wholly techniques inadequate for dealing with expiring data that For do not if use external for certain applications example the data records large considerable memory can be saved using need to external chaining instead of linear probing with expiring be used Accordingly there is develop hashing techniques are for external chaining data The with linked methods lists of the to above-mentioned patent limited to arrays and cannot due the 25 significant difference in the organization of the computers memory BRIEF SUMMARY In accordance OF THE INVENTION with the illustrative embodiment collection of the invention these and other problems are overcome by using garbage are procedure on-the-fly while other types during normal data insertion or so of access to the storage space taking place In particular 4/ BTEX0000I 82 Richard Nemes storage system in accordance with the present invention flow chart for and FIG hashed shows general record deletion operation that might be used in storage system in accordance facilitate with the present identical invention numerals used to designate To elements reader understanding to the figures reference are common DETAILED FIG comprising to DESCRIPTION of the drawings Central OF THE 1NVENTION shows general block 10 and 11 diagram of computer hardware system Processing Unit stored in the CPU RAM stored Random accessed Access Memoiy 10 and RAM unit 11 one Computer instruction programs at are by of CPU executed operated time by instructions CPU 10 Data by in other portions RAM 11 are on by the program accessed CPU 10 from RAM 11 all in accordance with well-known data processing techniques Unit data Central Processing 15 CPU stored 10 also controls and accesses disk controller such unit 12 that in turn unit accesses digital on one or more disk storage units as disk storage 13 until required by CPU 10 and At this time such programs 11 for rapid and data are retrieved from disk storage unit 13 in blocks stored in RAM also access Central Processing Unit to CPU 10 controls an InputlOutput as I/O controller 14 that terminal in turn provides access plurality of input devices such CRT cathode 15 ray tube 20 15 for as well as plurality of output devices such as printer and 16 Terminal into provides mechanism computer user to introduce instructions commands the computer system of tape readers 16 FIG and may be supplemented with other input and other devices such as magnetic remotely located terminals optical readers types of input devices Similarly printer provides for the mechanism 25 for displaying theresults of the operation of the computer system of by and and FIG computer displays user Printer 16 may similarly be supplemented line printers cathode ray tube devices phototypesetters laser printers graphical plotters other types of output their cooperative The well-known to large constituents of the computer system of are typical FIG operation are in the art and of all computer systems from small personal and operation computers and mainframe systems The architecture be further described here of such systems are well-known 30 will not BTEX0000I 83 Richard Nemes FIG system such shows as that graphical representation of typical software architecture for computer mechanism shown personal in FIG The software of FIG may to consist comprises user access 20 that In for simple computers service of nothing more than turning the system on and larger systems be providing many users login password user access procedures would 20 has typically implemented the in user access mechanism 20 Once is mechanism completed login procedure the user placed of in the operating system environment 21 the Operating system 21 coordinates the and activities all of the hardware components of computer to the system shown user in FIG provides number of example and utility programs 22 of general use basic file computer Utilities 22 might for comprise access and 10 manipulation programs system maintenance facilities programming language also compilers The such as computer software system of FIG software typically includes application programs for application 23 24 25 Application formatting software 23 through 25 might program example database comprise text editor document software spreadsheet management The present system is game program and with so forth is invention concerned information storage and retrieval It can be application software packages 23-25 or used by other software parts of the system such as user access software 20 or operating provided by the present system 21 invention The information storage and disclosed as flowcharts in retrieval technique and are herein FIGS through shown 20 as PASCAL-like pseudocode in the APPENDIX to this specification Before proceeding to useffil description of one embodiment of the present invention for it is first to discuss hashing techniques in in general Many fast techniques storing and retrieving data are known the prior art In situations where storage space is is considered cheap each compared record in with the retrieval time technique called hashing often used In classic hashing in value information storage is system includes distinguished field unique to each record 25 called the key which used as the basis for storing is and retrieving the associated record Taken as whole hash table large one-dimensional units array of logically is contiguous stored in consecutively 11 numbered where fixed-size storage Such table of records typically RAM of FIG bashing into each record is an identifiable and addressable location in physical memory as an index be fi.tnction translates the key into hash table array subscript which is used the 30 array where searches for the data record begin The hashing fbnction can any operation on BTEX0000I 84 rnchd Netnes the key that results in subscripts mostly uniformly distributed across the table Known hashing of fUnctions include truncation folding transposition modulo generally arithmetic and combinations these operations in Unfortunately in hashing functions keys do not produce producing hashing unique locations the hash table that many distinct map to the same location in all what are called collisions Some form of collision the alternate of collision an resolution is required for systems In every is occurrence finding alternate location collided record necessary for Moreover location must be readily reachable during future searches the displaced record common 10 is collision resolution strategy with which the present invention each hash table is concerned all called external chaining at Under location external chaining entry stores but instead of the pointer the records that to the head collided that by storing not the records themselves lists of linked list of those same records allocated Such linked are formed by each storing records individually to the location in dynamically storage and maintaining records with record pointer is of the next record in the chain of collided used to When search key If the hashed is to hash table entry the pointer the key found there is locate the first record search key this does not match the found is there the pointer traversed there is used to locate the second record record In way end chain of records is sequentially until the desired is found or until the of the chain reached Deletion of records involves merely adjusting the pointers to bypass storage pool maintained the deleted record and returning the storage it occupied to the available 20 by the system flashing techniques have been used classically for very fast access to static short term data such as the need compiler symbol table Typically in such storage systems deletions are infrequent and for the storage system disappears quickly system is In some common can types of data storage obsolete merely by systems however 25 the storage long lived and of some records become expired the passage of time or by the occurrence event If such lapsed or obsolete records are not removed from the system they will in time seriously of the records retrieval degrade the performance system Degradation search times since shows up they cause in two ways First the presence chains to be longer of expired than they lengthens the external otherwise would be could be returned Second to the expired records occupy pool dynamically allocated allocation memory storage that the system 30 system memory for useful Thus when BTEX0000I85 Richard Nemes memory memory pool is depleted by an new data item can be inserted into the storage system only if the occupied expired one is reclaimed Referring then to the hash table FIG there is shown flowchart of search table procedure for searching preparatory to inserting retrieving or deleting record records in accordance with the present linked list invention in and involving the dynamic removal of expired of FIG in targeted Starting box 30 of the search table procedure the search key of the of an array element is record being searched the hash table for is hashed in box 31 to provide the subscript generated In box 32 to array location indicated by the subscript Decision in box 31 accessed provide the pointer to the target linked list box 33 examines reached If the the pointer value to has io determine whether is the end of the linked list has been end been reached box 39 box decision box 34 be entered to determine if key match was previously found is in decision as will described below If so the search successful and If returns success is in 35 followed by the procedures termination and of the the in terminal box 37 not box 36 entered where failure is returned procedure again terminates in box reached 37 box is lithe end list has not been as determined by decision 33 decision box 38 is entered to determine if the record pointed to has expired external This is determined by comparing in the some portion for of the contents of the record to some the condition timestamp maintained record example could be compared with Alternatively the record In the current time-of-day value be compared with by all computers 20 occurrence if of an event can field identiijring that event in any case the record has not expired If decision box 39 is entered to determine saved if the key in this record matches entered the search key record it does not the address of the record is in box 40 and box 41 is If the does match the search key the procedure forward to bypasses box 40 and proceeds in directly to box 41 In box procedure under 41 the procedure to box advances the next record the linked list and the returns 33 box 42 list is 25 If decision box 38 determines the on-the-fly occupies to that the record question has expired entered to perform removal of the expired record from the linked described and the return of the storage it the system storage pool as will be in connection with FIG In general the remove list procedure of box 42 predecessors FIG to operates to remove bypass that an element from the linked by adjusting is its pointer element However if 30 the element to be removed the first element of the list then there is no predecessor and the /7 BTEX0000I 86 Richard Nemes hash table array entry is adjusted instead returns On to completion of procedure remove invoked\ from box 42 the search It table procedure box 33 of can be seen that the search tab/c of records of which procedure record FIG part operates to and examine the expired is entire linked list the searched-for is to remove records and of returning storage to the storage pool records remain despite with each removal If the storage pool depleted many new expired such 77 automatic of garbage until collection deletion is then the insertion records is inhibited boxes 76 and FIG made by the delete procedure FIG its or until the search table procedure has had chance to replenish the storage pool through 10 on-the-fly garbage collection Though as the search table procedure as shown and described above in FIG implemented in connection in the APPENDIX PASCAL-like and pseudocode appears with an information its storage removal retrieval system using the hashing technique linked list with external chaining linked on-the-fly technique data while traversing appears even can be used anywhere person linked list of records art will with expiring is in contexts unrelated to hashing manipulate skilled in the appreciate used that this technique can be readily applied to lists not necessarily with hashing The search and table procedure shown in FIG entire implemented linked list as pseudocode all in the APPENDIX as it described above traverses the removing expired records but not searches for key match The procedure can be readily list adapted to remove time and some 20 all of the expired records thereby shortening the linked traversal speeding up the the search at the expense of perhaps to leaving some expired records in the list For example procedure for this can be modified version tenninate when appears key match occurs PASCAL-like pseudocode in alternate of search table the APPENDIX dynamically expired The at implementor even has the prerogative of choosing among these strategies removing the time search table is 2$ invoked by but the caller thus sometimes all records at other times removing some not all of them and yet at other times choosing to remove none of them Such example how much memory the number and dynamic is runtime decision might be based on factors such as for available in the system storage pool general system load in time of day of records to currently residing the information system and itself other factors both internal external the 30 information storage and retrieval system person skilled in the art will appreciate that the -.9 /0 BTEX0000I 87 ID Richard Nemes technique include of removing all expired not records while searching the linked all list can be expan4ed and that to techniques whereby if necessarily expired can records be are removed the decision regarding In and how many shown records to of delete dynamic one that FIG there is flowchart remove procedure through the delete removes record from noted in the retrieval in system either an unexpired record procedure table as will be connection with FIG.7 or an expired record this is through the search procedure as noted connection with HG In general accomplished by the invoking procedure being passing to either the delete procedure to FIG linked or the search table procedure FIG to that the remove procedure 10 pointer list element to remove the subscript pointer elements predecessor location element in the same linked to the list and of the hash table array containing the pointer head of the linked list from which the element element of the linked is to be removed In the case that the element to be removed is the first list the predecessor pointer passed to the remove procedure by the invoking to the procedure has the NIL sometimes to called NULL or EMPTY 15 value in indicating remove procedure procedure that that the element be removed has no predecessor to the list The invoking expects the remove to the procedure on completion element so that final have advanced the passed pointer originally pointed now-removed removed it points to the successor element in that linked list or NIL in if the element was the element The search table procedure of FIG particular makes use is of the remove that procedures 20 advancing is this passed pointer in the described way it made use of in was box 33 in of FIG entered directly following completion of box 42 as described above connection with FIG procedure causes actual so that it The remove predecessor predecessor pointer removal of the designated the element to element by adjusting In the case that the the bypasses value be removed pointer has the NIL the hash table array entry indicated the by the passed in its 25 subscript plays Following the role of the predecessor adjustments the pointer and is adjusted same way is stead the pointer storage occupied by the removed element returned to system storage pool for future Beginning is allocation then at starting box 50 of FIG to its the pointer to the list element to remove decision advanced in box 51 so that it points successor in the linked list Next box 52 testing 30 determines if the element to remove is the first element in the containing linked list by lo ll BTEX0000I 88 Richard Nemes the predecessor pointer for the NIL value as described above bypass If so box 54 first is entered to adjust the linked list head pointer in the hash table array to the element after which the pointer is procedure adjusted to continues on to box 55 If not box 53 is entered where the predecessor the procedure bypass the element to remove 55 the storage after which proceeds once again is to box 55 Finally in box storage pool and occupied by the bypassed element returned to the system the procedure detailed terminates in terminal box 56 suitable for Fig shows and flowchart of an insert procedure use in the information storage begins 10 at retrieval system of the present invention In box be The insert procedure of FIG starting box 71 from which box 71 is entered 71 the search table procedure in connection of FIG with is invoked with the search key table of the record to inserted As noted FIG the search procedure the search finds the linked list element whose key value of the expired records whether record contained therein matches key and at the same time removes is on-the-fly from that linked list Decision box 72 then entered where key value it is determined the search table procedure found record with matching list If so box 73 is entered is where the record to be inserted value is put into the linked the insert element in the position that of the old record has been with matching key In box 74 procedure reports the old record replaced by the new rebord and to decision the procedure terminates in terminal record box 75 decision Returning entered box 72 sufficient if matching is not found box 76 is to determine if there is storage in the system storage pool entered to report the that the storage to accommodate and the 20 new linked list element be If not box 77 is system is full record cannot inserted Following that that procedure terminates in terminal box be allocated 75 If decision box 76 determines sufficient storage can is from the system storage allocation pool is for new linked list element record to then box 78 be inserted entered where the actual memory in made In box 79 the is copied into the storage allocated 25 box 78 and into it box 80 is is entered In box 80 the the linked linked list element containing the record copied in box 79 inserted into list to which the contained into the record hashed and The procedure then reports and that the record was inserted information storage retrieval system in box 81 the procedure terminates in box 75 procedure in FIG so shows detailed flowchart of retrieve used to retrieve record from of the information storage and retrieval system Starting box 90 the search table procedure 11 BTEX0000I 89 Richard Names FIG decision is invoked in box 91 using if the key of the record with to be retrieved as the search key In box 92 If it is determined 93 record matching failure key of the was found retrieve by the search procedure is table procedure not box in is entered to report and the procedure terminates terminal box 96 record If matching record was found box 94 calling entered to copy the matching entered to return record intO store for processing by the program box 95 is an indication of successful retrieval and the procedure terminates in terminal box 96 FIG.7 shows records of detailed flowchart of delete procedure useful for actively removing from the information storage and invokes the search table retrieval system in Starting at box 100 the procedure FIG procedure In decision of FIG box box 101 using the key of the record it to be deleted as the search key find 102 key is determined if the search table procedure failure was able to record with and matching If not box 103 is entered to report of the deletion procedure the procedure terminates in terminal box 106 If matching is record was found as determined in by decision box 102 the remove procedure procedure of FIG causes then 15 invoked box 104 As noted linked list in connection with FIG the remove linked removal entered of to designated element from its containing list Box 105 is report successful deletion to the calling program and the procedure terminates in terminal box 106 The attached APPENDIX contains PASCAL-like pseudocode listings for all of the 20 programmed operating have components necessary to implement invention an information storage and retrieval system art will in accordance with the present Any person of ordinary skill in the no difficulty implementing all the disclosed system and and procedures shown in the APPENDiX on the basis including programs for common hardware system software arrangements of this description 25 It including flowcharts and information shown in the art that in the APPENDIX of the present of the used should also be be clear to those skilled other embodiments invention may made by those It is skilled in the art without departing art that from the teachings be present diverse invention also clear to those skilled in the the invention can use in computer applications to and that it is not limited to the of hash tables but is applicable other techniques requiring linked lists with expiring records 30 12-- BTEX0000I 90 Richard Names Appendix Functions Provided The following functions are made available to the application program insert record record type io Returns replaced if record associated with record key was found and subsequently replaced Returns passed 15 inserted record if record associated with record key was not found and the was subsequently inserted Returnsfiill if record associated with record key was not found is and the passed record could not be inserted because no memory available 20 retrieve record record_type Returns success if record associated with record key was found and assigned to record 25 Returns failure if search was unsuccessthl delete record_key record key type 30 Returns quently success deleted if record associated with record_key was found and subse Returns failure if not found 35 Definitions The following formal definitions are required all for specifing the insertion retrieval and deletion procedures 40 They are global to procedures and functions shown below 13 BTEX0000I 91 fl Richard Nemes const table_size ft Size of hash table type list_element_pointer list_element Pointer to elements of linked list type list_element Each element of linked list record record_contents next 10 record type Singly-linked list list_element_pointer end var table array table_size of list_element_pointer /t ft Hash table of list Each array entry is pointer to head is Initial state of table table nil table size Initially empty Insert 20 Procedure function insert record record_type replaced insertedfu/l var position list_element_pointer ft Pointer into ft list of found if record tf tf or new element not found 25 dummy_pointer list_element_pointer ft Dont need positions predecessor tf index 0. table_size Table index mapped to by hash function tf begin 30 if search_table record key position dummy_pointer index It Record already exist then begin ft Yes update it with passed record tf 35 position .record_conents record return replaced end 40 else ft No insert new record at head of list tf 14 ._/ BTEX0000I 92 Th Richard Nemcs if no memory available then return full if memory available to do so else begin /4 Memory is available for node 4/ newposition Dynamically allocate new node position .record contents record /4 Hook it in position 10 .next table position table return inserted is end /4 else begin 4/ end insert 20 Retrieve Procedure function retrieve var record record type successfailure 25 var position list_element jointer Pointer into list of found record 4/ dummyflointer list elementjointer /4 Dont need positions predecessbr 4/ dummy_index 30 table size /4 Dont need table index mapped to by hash tbnction begin if search table record key position dummyflointer dummy_index /4 Record exist 35 then begin /4 Yes return it to caller 4/ record position .record_contents return 40 success end l5 BTEX0000I 93 fl. Richard Names else return failure /5 No report failure end /5 retrieve Delete Procedure function 10 delete record_key record_key_type success failure var position list_element_pointer /5 Pointer into list of found record previous_position list_element_pointer /5 Points to positions predecessor is index table_size Table index mapped to by hash thnction begin if search_table record_key position previous_position index Record exist 5/ 20 then begin rn Yes remove it remove position previous_position index 25 return success end else 30 return failure No report failure end delete 5/ 35 Search Table Procedure function search_table record_key var position record_key_type list_element_pointer list_element_pointer var previous_position 40 var index 0. table_size boolean 16 /7 BTEX0000I 94 Richard Nenwa /4 Search point to table for record_key and delete expired to records its in target list if found is position is made to located record and previous _position is predecessor that is and TRUE returned otherwise in either FALSE case returned Index is set to table subscript mapped to by hash function var list _element_pointer Used for traversing chain previous_p list_element_pointer /4 Points to ps predecessor io begin index hash record_key hash returns value in the range 0. table_size table 15 Initialization before loop previous_p nil /4 Ditto position nil /4 Ditto 20 previous_position nil Ditto while nil H_______F __________TOIJE _ EART O _ TI-IF TECHN ___ Traverse jjj list deleting 4/ expired records as we search begin 25 ifpl .recordcontents is expired then remove previous_p mdcx rn 01-THE-FLY REMOVAL OF EXPIRED RECORD 30 else begin if position nil then ifpl .record_contentsicey record key /4 If this is record wanted 4/ then 35 begin position previous_position previous_p end save its position to 4/ previous_p /4 Mvance pI 40 next next record 4/ end else begIn 4/ end 17-- /7 BTEX0000I 95 Richard MNcmes return position nil /t Return TRUB if record located otherwise FALSE end /t search_table Alternate Version of Search Table Procedure function io search table record cey record_key_type list_element_pointer list_element_pointer size var position var previous_position var index 0. table boolean ft is SAME AS VERSION SHOWN ABOVE EXCEPT THAT THE SEARCH TERMINAThS RECORD ISIOUND INSTEAD OF ALWAYS TRAVERSING THE ENTIRE CHAIN tf element _pointer IF varp list ft Used for traversing chain previous_p 20 list_element_pointer ft Points tops predecessor tf begin index hash rebordjcey ft hash returns value in the range 0. table_size 25 table previous_p nil /t Initialization before loop t/ /4 Ditto 4f position 30 nil /4 Ditto 4/ previous_position nil /4 Ditto 4f while nil /4 HEART OF THE TECI-INIOUB ft Traverse list deleting 4/ t/ expired records as we search 35 begin ifpl record contents is expired then 40 remove previous_p index ON-THE-FLY REMOVAL OF EXPIRED RECORD else begin 18 BTEX0000I 96 Richard Nemea ifpi .record contents.key record_key If this is record wanted/ then begin save its position position previous _position previous_p return 10 true We found the record so terminate search end previous_p Advance to 15 Inextrecord end else begin end 20 return false Record not found end searchable 25 Remove Procedure procedure remove var elem_to_del 30 list_element_pointer previous_elem list_element_pointer index 0. table_size Delete elem_to_delI from list advancing nil if elein_to_del is to next 1it element previous_elein in list.t/ points to elem_to_dels 35 predecessor or elem_to_delI element var list_element_pointer Save pointer to elein_lo_del for disposal begin 40 elem to_del ft Save so we can dispose when finished adjusting pointers 19 BTEX0000I 97 -Th Richard Names e/emtodel elemtodel .next if previousplem nil ft Deleting element requires changing Sf then kthle elem elern ode elem_todel ft bead pointer as opposed to else previous next /5 predecessors next pointer 5/ dispose 10 Dynamically de-allocate node Sf end remove 20 BTEX0000I 98 Richard Nemes CLAIMS claim An information storage and to store retrieval system access to the system comprising linked list and provide records stored in memory of the system at least some of the records automatically search means utilizing search means including ones expiring search key to access the linked and list record the record of the expired means for identifying removing list is at least some and of the records from the linked the list when the linked accessed at the means 10 utilizing record search means for accessing the linked the list and same time removing The at least some of expired retrieval ones of the records in the linked list to claim the record further infonnation storage and system according for including means remove for dynamically accessed determining linked list maximum number search means to in the of records is method provide for storing and retrieving information records using linked list to store and access to the records at least some of the records automatically expiring the method comprising the steps of list accessing the linked at least of records the identifying some of automatically expired expired ones of the records and 20 removing the linked at least some of the automatically records from the linked list when list is accessed claim the step of dynamically to The method according to fUrther including determining linked list is maximum number accessed of expired ones of the records remove when the 25 An information storage and retrieval system the system comprising stored in hashing means to provide access an external the records technique to store to records memory of the system and hash address at least using chaining the records with same some of automatically expiring 30 record search means utiliEing search key to access linked list of records having the 21 BTEX0000I 99 Richard Nemes same hash address the record search means including means list for identing and removing linked at least sOme expired and ones of the records from the linked of records when the list is accessed means utilizing the record search means for inserting at least retrieving and deleting records from the system and in the accessed linked at the same time removing some expired ones of the records list of records The information storage and retrieval system according for to claim further including means io for dynamically determining linked list maximum number of records the record search means to remove in the accessed method access for storing and retrieving information records using to hashing technique store to provide with to the records and using an external chaining technique the records same the hash address at least some of the records automatically expiring the method comprising is steps of accessing identiFying linked list of records the having same hash address ones at least some of automatically expired expired of the records from the linked list removing the linked list at least some of and the automatically records when is accessed 20 inserting retrieving or deleting one of the records from the system following the step of removing The method according to claim further including the step of dynamically to determining linked list is maximum number accessed of expired ones of the records remove when the 22 BTEX0000200 JAN Richard Nemea ABSTRACT OF TIlE DISCLOSURE for performing method and apparatus system collision is storage and with retrieval in an information storage for disclosed that uses the hashing technique performance collection the external chaining to method presence all resolution In order to prevent garbage deterioration due the of automatically expiring data items technique is used that removes into expired storage to records stored in the system in the each external chain targeted by probe of the data an system More search an an expired it particularly insertion retrieval or deletion items and record is occasion entire linked-list chain of records for expired then remove is them Because probed data item will not remain in the system long term are if the system frequently 10 is useful for large information storage systems that and cannot be taken off-line heavily used require the fast access provided by hashing for removal of expired data 23 BTEX00002OI IN THE UNITED STATES PATENT AND TRADEMARK OFFICE Declaration As the below named inventor hereby declare that My name residence post office address and citizenship are as stated below next to my believe am the original patent is first and sole inventor of the subject matter which is claimed and for which sought on the invention entitled METHODS AND APPARATUS FOR INFORMATION STORAGE AND RETRIEVAL USING HASHING TECHNIQUE WITH EXTERNAL CHAINING AND ON-THE-FLY REMOVAL OF EXPIRED DATA the specification of which attached hereto is hereby identified state that have reviewed and understand and any the contents of the above specification including the claims amendments flIed therewith acknowledge of this application the duty to disclose with information which 37 is material to the examination Regulations 1.56 in accordance Title Code of Federal hereby claim foreign priority benefits under for Title 35 United States Code 119 or other a-d 365 or 365 of any foreign applications patent or inventors at least certificate of any PCT international application listed which designated also one country than the United States application for filing of America below and have identified below any foreign application patent or inventors that certificate or of any PCT international is having date before of the application on which priority claimed None hereby claim the benefit States United claims under Title 35 United States Code 120 of any United designating the applications States or 365 listed is of any PCT international as the application subject of America below and insofar matter of each of the of this application in the not disclosed in the prior first United States or application manner provided the duty to by the paragraph of Title is 35United States Code .as 112 defined acknowledge in Title disclose information which material to patentability available 37 Cede of Federal Regulations 1.56 which became between BTEX00002O2 the filing date of the prior application and the national or PCT injernational filing date of this application None Direct all correspondence to icliard 1432 Michael Nemes East 35th Street klynNeiXorkil23t25QA USA Telephone 718 3775438 hereby declare that all that all statements made herein of my own to knowledge be true and are true further and that like statements made on information and with the belief are believed that willful these statements were made so made are punishable knowledge false statements and the by fine or imprisonment or both under Section 1001 of Title the 18 of the United States Code of the application and that such willThl false statements mayjeopardize validity or any patent issued thereon 00 Full name of sole inventor Richard Michael Nemes Inventors signamre Date Residence Brooklyn Kings County New York 1j Citizenship United States of America Post Office Address 1432 East 3S New Street Brooklyn York 112342604 U.SA BTEX00002O3 4CRo 1991 BTEX00002O4 S% kc\ flits Pswnt of lfl vadt t-T Pain and TILd Ofl rrt Us notdi 10151/fl Ot OF 1046 Oe5IC1 rifle DEPARTMR4T thr eul 5I4ERCE RIFlED STATEMENT 1.91 CLAIMING SMALL ENTITY STATUS Docket Number Optional CFR 1.27bINDEPENDENT iNVENTOR Applicant RICHARD NEBES orPatentee_________________________________ or Application Patent No.________________________________ Filed or Issued METHODS uu As AND APPARATUS PO INPORMATIo WITH STORAGE AND RETRIEVAl CHAINING as defined In HASHING TECHNIQU fees to the Patent EXTERNAL AND in ON.TH bel3ne for Rre of aL4fy title as en independent Inventor 37 CFR 1.9c purpses paying reduced and Trademark Office described the speitication tiled herewith with as listed above the application identified above the patent identified above granted conveyed or licensed and am under no obligation under contract or lawto assign to any person who would not qualify convey or license any rights in the invention as an independent inventor had made the invention orto any concern which would not under 37 CFR 1.9c If that person small as qualify business concern under 37 CFR 1.9d ore nonprofit organization under 31 CFR 1.9e have not assigned grant Each person concern under or organization to which grant have assigned granted convey exists or license conveyed rights in or licensed is or am listed under an below obligation contract or law to assign any the invention No such Each person concern or organization such person concern or organization is listed below Separate invention verified statements are required from each named person concern 1.27 or organization having rights to the averring to their status as small entIties 37 CFR or patent acknowledge entitlement to the duty to file small entity fee due after in this application prior to notification of any change in status resulting in loss of status the date paying status or at the time of paying as small entity is the earliest maintenance of the Issue fee or any on which no longer appropriate 37 CFP 1.28b statements hereby declare that all statements made herein of my own knowledge are true and that all made on information willful of false and belief are believedto betnie andfurtherthatthese statementswere made statements and the States like Title 18 of the United so made are punishable Cods and that such willful or with the knowledgethat by fine or imprisonment or both false under sectIon 1001 the validity of statements may jeopardize is the application any patent issuing thereon any patent to which this verified statement directed RICHARD NAMEOF INVENTOR NEIVIES _________________ NM$EOFINVENTOR _______________ NAME OF INVENTOR Signature of inventor snare ot Š.scr DEC Date 2O jgg _________________ Dare _______________ Date Suraen comments Hour on Statemarn the This of torn hrre aflunt you Washington Wasningion DC 20231 DC 20231 DC NOT .swtSd to Ins 0.3 tcurs to lrvlsts Tate vsy depending upofl the reds of the raviduat 05.4 en mound to ntete Via tomi ahou be aunt to the Dial Inloorsuon Officu Pewisi end Tresas SEND FEES OR COMPLETED FORMS It ThiS AOORESS SEND.TO Msi5afltConrusion.r for Patents is Are Office BTEX00002O5 PRINT iF DKAWI2WS FILED AS ORIGINALLY 08/775864 Shccl of6 Richard Namea FIG FIG BTEX00002O6 PRINT OF DRAWINGS FILED AS ORiGINALLY 08/775864 Sht of Richard Ncmc BTEX00002O7 PRINT OF DRAWINGS ORIGINALLY FILED 08/775864 Shect3of6 Richard Nema FIGyl Cl -f 5-3 5-5- BTEX00002O8 PRThtT AS ORIGENALLY OF DRAWINGS FUID 77 of RicIwd Ncm BTEX00002O9 PRINT OF DRAWINGS AS ORIGINALLY FILED 08/775 864 Sheet of6 Richatd Netne FIG BTEX00002I PRINT OF DRAWINGS 08/775864 Sheet of Richard Names FIG YES 103 BTEX00002I fl Please type plus sign inside rper PTOiSB08A 695j Patent ths..4 U.S Depatlment Patent and of and Appro4a usethrough 9/30198 Trademark d1.U.S DEPARTMENT Complete If 0MB 065 10031 OF COMMERCE Commerce Ott Ice Known Trademark Application Number OF PRIOR ART CITED BY APPLICANT use as many sheets iIIng First Date Named Art Unit Inventor .Rirhpr║l Nemns Group as necessary Examiner Attorney Name Docket Number lou ______________ U.S Examine Initials U.S PATENT Name of of DOCUMENTS ate of Publication of Patent Oocumenj Patentee or Appltcant No Number Clad Document et 5rL21435 t12f aichar.d...s.Ne.mes.....o.oaGgai 92_2QZ/L--_._ FOREIGN PATENT Foreign Patent Examiner Initials DOCUMEN Patentee Date or of PublicatIon Document Name tcrnd Cit ot of No Office Number Cod dAnon Applicant fled Document Cited Document Pege Columsi Lines Wtae Pe4ver Pssaaqss Finwis eq MM-DDWfl rr nas Anna TI .j Fj 1111 .. 1T7.IIIIITIIITIIIIIIITIT iii IDate Examiner Signature j//3J4K .1 Considered reference copy of ExAMINER considered tnltlai considered loan with whether or not cItation to lain conlomtance wib UPEP 609 Draw line through citation if not in conformance and not Include this next communIcation attached patent Kinds of applicant Enter of Office reign the that of Unique code number posatfe Burden uttotint the citation designation W1PO of the Standard patent 51.3 nuner See For Japanese Kind check of U.S Patent Documenta the Indication of issued the document rnuat by the the twtetler aerial it documents by the the year as Indicated is the on the Emperef under precede Standard document is document mark eppropilate symbois Translation document WIPO $1.1 Appltcant tope This form hem to take Engttah tanguage .2 attached Hour Of Statement is esilmated hours be to cocqMete to the TEn Chief to wit vesy.depen4tg Informal Ion Officer ton Patent the needs and ft of the individual case Any comments on the tIme you are reqtilmd Act of to cotyplete this form -should sent Tradifliatit cisplays -Off Ice Washington Paperwork Reduction 1995 no persons are requ Wed to reepond Acosedton of kilorrnatlon for unless Patents valid SEND FEES OR COMPLETED FORMS TO THIS ADORESS SEND To Aseletant Commissioner Washington 0MB control DC 20231 DC 20231 Under number DO NOT BTEX00002I i9ZEf PTO/SB/08B Please 6-95 twe plus sign Inside thk4...t U.S Department Patent and of Patent and Trademark Approv iso through 0MB 0651-0031 U.S DEPARTMENT OFCQMlERcE 07/31/96 -t If 14496/FTC Rev toios Commerce 0111cc Trademark Complete Application_Number iCnown OF PRIOR ART CITED BY JAN shoots Filing First Dat Inventor Named Art Unit Tiirhrrr1 NI Group 199l PPLICAN of as necossa Examiner Attorney flame Docket Number J/Vf OTHER Include Ut \J PRIOR ART the NON PATENT LETTERS tile LITERATURE of the article DOCUMENTS appropriate volume-issue title -i name of author in CAPITAL when of the Examiner Initials Cite item No book magazine ournal serial publlstrer syntoslum catalog etc date pages nunters oountrywhere published source DE KNUTH Sorting chetts The Art Of Computer Programming Volume and Searching Reading Massa Addison-Wesley F97 pp 506549 R.L KRUSE Edition Data Structures and Program Design Second Prentice-Hall Englewood Cliffs New Jersey i.9.ft7 S.ctIan $Q.tjpn Analysis of Hashing pp 198215 D.F 3113 STUEBS and N.W Abstract Company Data Types Montea CaLLfnni18SctiaLJ.5_ Pp 310-336 and WEBRE Data Structures with Pascal Brooks/Cole Publishing Hashed Implementations 3J EXAMINER considered InItial reference copy considered form with whether or riot citation to Is In conformance wIth MPEP 609 Draw line through citation not In conformance and not Include of this next communication applicant Unique Burden amount citation designation nurrber ApplIcant Is to piece hours check mart hers Time If English language Translation Is attached the Hour of Stalerneni ThIs form estimated to take .2 to conlefe wit vary dependIng Officer tgon the needs of Individual case Any comments on the this tomi strould sent to the Chief Information an required to corriete NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS SEND TO AsaSant lime you Patent and for Trademark Office Washington DC 20231 DO Commissioner Patents Washington DC 20231 BTEX00002I Sorting and Searching THE ART OF COMPUTER PROGRAMMING Reading \Ienlu Massachusetts Park California London Arnsteidam Don Mills Ontario Sydney BTEX00002I This book is in the This SERIES IN book forms because natu it ADDISON.WESLEY COMPUTER Chapter PROCESSING SCIENCE AND INFORMATION basic structural ideas those book tion Editors VA1tOA is only for of general-purpose in Consulting olettAitus But 2diit1Ci1AEL hARRISON fact the area of discussing wid are can can can variet How How How How En good given the algoi alg efficie person same application what does can large senses the can thee How How with external data lR that Indeed somewhere This is believe in the cont volume with compi sort concerned divided been also 1973 1973 chiefly mi are supplenxentar\ Copyright by AddisooWtY of this Putilish ig Company Inc Philippilies ropyri tations Section deals is 5.1 with 1w II Addison-WeSley ri Publishing Cthnpany fur may reprodtuvd st gus nserved ted in No part put tieation 001 vt nova1 system Chapter files of this or transmit or otherwise of .\ hrt.ronn any form or by any menos the Iut prior si nwrbauiid the pul At photocopying Prin ted iii rerorIitmg tin ni subdivided without writ.teiI 15rIoiSSIOIl iu of hsher ted States monica tithed nuitaneousiy Cans in rtuy of Congress Catalog Card by digital problcm of secondttry keys or No BPS \7-.26020 O-25135S3-X OEFGIIJ-MA-7957 BTEX00002I 506 sEAItdULNi 6.4 6.4 6.4 MASHING will have the same month au docn So ir function which maps into this 23 we to ave cot isidered in is searci ni eth ods its based digits to corn pant govern ig tI cc give cc argm no two keys map they the resul meict third the keys the table to or using all branching process arith of Skeptics large who doubt work possibility ovoid this rummaging function around which by doing is some parties attend of metical ii calculation issoci cited oci computing in is the location unpublished Essays Day Sec also tic ci at the table ider 1939 New and 45 lot subjected ci ex cm to 11 let cot agcu cc the set in ccl .31 Ec igl ish words nh ch we 6.3 into Ii Ove Mecmuasi Theory 1939 145163 19 various search which strategies transforms If Section of 6.22 and keys to Table unique show5 number for York Wiley hand Turski can the short MIX program 10 each the 31 On niewski the other ap fot lilu between the other trie of acid 30 have we compare this method the MIX optimal programs tree YAC be methods digital acid we considered e.g find binary it is search superior uses search suitable function to memory space the tree search except we that that from the standpoint less amusing Of solve this in puzzle both speed time binary search slightly space of In course kccown it method advance to hi at fact with average for of successful search using the program only 41 Table must be making the frequency to dit store it Fig 12 is cxciv about 7.Su acid table ben There necessary start if tims are needed Unfortunately are the 31 very keys easy to more versatile method discover such functions set into we gi isnt keys to yield the same value been lea cI 41 only each 41 10 40 possible functions 11 41 from 31element 1041 of 41element distinct set values ambiguity These known chop after has and for /l0 one them will give considerations argument thus only about of evei10i1tihii1iiiiLtions will be as Iiaslimy or scatter or to sl suitable Functions fairly something up aspects of mals as which table people avoid duplicate values are surprisingly rare even asserts with that of off sonic the key .t large For example are pri\secct the famous in birthday paradox that searching We compute begins has 23 or more room Table chances are good two them where the search birthday The K1 INTO paradox hash In tel which the so TilANSFOIUIINU SET OF KEYS UNIQUE ADDRTSSES 14 Ct C-C LOAN L02 1501 JAR INCA LEE 221 3c01 Jie INCA LOS Jsz DCCX JIN INCA LDA 0504 255 811 X22 162 2-22-I II Ii -c ii II s5 52 s s2 211 .1 li-S .5 .5 ci ii II II III AJ 15 ii II III cci IV 17 Is 18 Is .29 ii 13 15 Is iS 13 Is 15 25 25 25 211 833 OF ii III Iii Ii in is ii is ii 282 or i2 77-22 20 --7 20 29 22 -.IS.H -3 25 35 12 112 12 20 544 9F 35 IS 17 52 or 10 19 25 --7 25 -1 TABLE1 FAILURE i-i II Ii 521 IS III 14 i

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?