- Patent Number:
12197,415
- Appl. No:
17/898963
- Application Filed:
August 30, 2022
- نبذة مختصرة :
A method and apparatus for performing storage and retrieval in an information storage system cache is disclosed that uses the hashing technique with the open-addressing method for collision resolution. Insertion, retrieval, and deletion operations are limited to a predetermined number of probes, after which it may be assumed that the table does not contain the desired data. Moreover, when using linear probing, the technique facilitates maximum concurrent, multi-thread access to the table, thereby improving system throughput, since only a relatively small section is locked and made unavailable while a thread modifies that section, allowing other threads complete access to the remainder of the table.
- Inventors:
Nemes, Richard Michael (Woodmere, NY, US); Lotvin, Mikhail (Sunnyvale, CA, US); Garrod, David (Pittsburgh, PA, US)
- Claim:
1. An information storage and retrieval system, the system comprising: a hash table comprised of slots residing in a physical memory of a computer with multi-threading capability, means for providing access to data records stored in the hash table using a hashing function that maps search key data values to slots and using open addressing to store the records with a same hash address, means for identifying an initial slot using the hashing function applied to a search key data value, means for determining whether there is a collision, which occurs when the initial slot contains a data record that lacks a key field value matching the search key value, means for probing additional slots in the case of the collision to find a data record whose key field value matches the search key value, or an empty slot, whichever comes first, where the number of such additional slots is at least one, and fewer than a predetermined limited number of slots, where the predetermined limited number of slots is more than one and fewer than a number of slots comprising the hash table, wherein the predetermined limited number of slots is dynamically decreased, thereby relinquishing access to those records that cannot be reached within the decreased predetermined limited number of additional slots, and wherein limiting the number of additional slots enables at least one executing thread among concurrent threads accessing the hash table to execute without conflict from threads that alter slots of the hash table.
- Claim:
2. The information storage and retrieval system according to claim 1 where the predetermined limited number of slots is dynamically decreased by one.
- Claim:
3. The information storage and retrieval system according to claim 1 where the predetermined limited number of slots is dynamically decreased by more than one and not more than ten.
- Claim:
4. The information storage and retrieval system according to claim 1 where the predetermined limited number of slots is dynamically decreased by more than ten.
- Claim:
5. The information storage and retrieval system according to claim 1 wherein the value of the dynamically decreased predetermined limited number of slots is at least one after the decrease.
- Claim:
6. The information storage and retrieval system according to claim 1 further including added means for probing additional slots in the case of the collision to find a slot into which a data record can be inserted, where the number of such additional slots is at least one, and fewer than the predetermined limited number of slots, and forgoing insertion if the slot is not found.
- Claim:
7. The information storage and retrieval system according to claim 1 wherein a slot into which a record is inserted is a slot where no data record is stored or that contains a data record whose score is not superior to a score of the data record to be inserted in its place.
- Claim:
8. The information storage and retrieval system according to claim 1 wherein dynamically decreasing the predetermined limited number of slots enables at least two records with a matching key field value to be in the table simultaneously.
- Claim:
9. The information storage and retrieval system according to claim 1 wherein collisions are resolved using linear probing.
- Claim:
10. The information storage and retrieval system according to claim 1 wherein the information storage and retrieval system is a caching system.
- Claim:
11. The information storage and retrieval system according to claim 1 wherein the computer is a portable electronic device.
- Claim:
12. The information storage and retrieval system according to claim 1 wherein the computer is a server.
- Claim:
13. A method for managing data in an array located in a physical memory of a computer with multi-threading capability using hashing with open addressing, the method comprising the steps of: identifying an initial array slot by the computer executing a hashing function applied to a search key value, determining whether there is a collision, which occurs when the initial array slot contains data and that data lacks a key field value that matches the search key value, probing additional slots in the case of the collision to find a data item whose key field value matches the search key value, or an empty slot, whichever comes first, where the number of additional slots is at least one, and fewer than a predetermined limited number of slots, where the predetermined limited number of slots is more than one and fewer than a number of slots comprising array, wherein the predetermined limited number of slots is dynamically decreased, thereby relinquishing access to those data items that cannot be reached within the decreased predetermined limited number of additional slots, and wherein limiting the number of additional slots enables at least one executing thread among concurrent threads accessing the array to execute without conflict from threads that alter slots of the array.
- Claim:
14. The method according to claim 13 wherein dynamically decreasing the predetermined limited number of slots enables at least two data items with a matching key field value to be in the array simultaneously.
- Claim:
15. The method according to claim 13 wherein a data item in the array is replaced by inserting into its slot another data item with a matching key field value.
- Claim:
16. The method according to claim 13 wherein collisions are resolved using linear probing.
- Claim:
17. A method for managing data in an array located in a physical memory of a computer with multi-threading capability using hashing with open addressing, the method comprising the steps of: identifying an initial array slot by the computer executing a hashing function applied to a search key value, determining whether there is a collision, which occurs when the initial array slot contains data and that data lacks a key field value that matches the search key value, probing additional slots in the case of the collision to find a data item whose key field value matches the search key value, or an empty slot, whichever comes first, where the number of additional slots is at least one, and fewer than a predetermined limited number of slots, where the predetermined limited number of slots is more than one and fewer than a number of slots comprising array, wherein the predetermined limited number of slots is dynamically decreased, thereby enabling at least two data items with a matching key field value to be in the array simultaneously, and wherein limiting the number of additional slots enables at least one executing thread among concurrent threads accessing the array to execute without conflict from threads that alter slots of the array.
- Claim:
18. The method according to claim 17 wherein a data item in the array is replaced by inserting into its slot another data item whose key field value matches the key field value of the replaced data item.
- Claim:
19. The method according to claim 17 wherein collisions are resolved using linear probing.
- Claim:
20. The method according to claim 17 further including the added step of probing additional slots in the case of the collision to find slot into which a first data item can be inserted, where the number of such additional slots is at least one, and fewer than the predetermined limited number of slots, where a second data item whose key field value matches the key field value of the first data item is removed if encountered during the probing.
- Patent References Cited:
5226092 July 1993 Chen
5490258 February 1996 Fenner
5991847 November 1999 Ballard et al.
6625612 September 2003 Tai et al.
6658652 December 2003 Alexander, III
7031985 April 2006 Pecheny
7788240 August 2010 Rossmann
7809701 October 2010 Blake
9081672 July 2015 Nemes
2005/0091443 April 2005 Hershkovich et al.
2006/0143168 June 2006 Rossmann
2007/0073733 March 2007 Matthews et al.
2007/0083531 April 2007 Hussain
2007/0294506 December 2007 Ross
2010/0023727 January 2010 Lim
2010/0070509 March 2010 Li
2011/0252216 October 2011 Ylonen
2012/0195208 August 2012 Abel
2012/0222005 August 2012 Harris et al.
- Other References:
Cormen et al., “Introduction To Algorithms—Third Edition,” 2009, The MIT Press, 1313 pages printed (Year: 2009). cited by applicant
Gao et al., “Non-Blocking Dynamic Hash Tables With Open Addressing,” Jul. 2004, 48 pages printed (Year: 2004). cited by applicant
Gao et al., “Lock-Free Dynamic Hash Tables With Open Addressing,” Nov. 2004, 22 pages printed (Year: 2004). cited by applicant
Kolosovskiy, Maxim, “Simple Implementation Of Deletion From Open Address Hash Table,” Sep. 2009 (from PDF metadata), 6 pages printed (Year: 2009). cited by applicant
Luo et al., “Comparison Of Different Open Addressing Hashing Algorithms,” Feb. 2003 (PDF metadata), 4 pages printed (Year: 2003). cited by applicant
Unknown, “Fundamental Data Structures,” Nov. 17, 2011, pp. 104-125, 366 pages printed (Year: 2011). cited by applicant
- Assistant Examiner:
Le, Michael
- Primary Examiner:
Mahmoudi, Tony
- الرقم المعرف:
edspgr.12197415
Processing Request
No Comments.