Patent application EP16305620A (EP), filed 2016-05-27
Publication number: EP3249553A1
Title: WORM HASHING
Abstract: An entries array having a pre-selected number of initially empty buckets and structured as a circular array is maintained. Each of the pre-selected number of entries in the entries array has a corresponding index value. A chaining array having the pre-selected number of buckets and structured as a circular array is also maintained. Each of the pre-selected number of entries in the chaining array has the same corresponding index value as the corresponding bucket in the entries array. A hash operation is performed on data to be stored to determine a hash value corresponding to the data. The data is stored in a bucket in the entries array corresponding to the hash value as an unmovable head-of-chain entry, and moving previous data, if any, stored in the entries array corresponding to the hash value if the previous data has a different hash value. The data is stored in another bucket in the entries array if the bucket in the entries array corresponding to the hash value is occupied by a head-of-chain entry. The bucket storing the data is linked to the head-of-chain entry with the chaining array.
IPC codes: G06F  17/    30            A I
G06F  16/   901            A I
Claims: number: 1
text: A method comprising:
number: 2
text: The method of claim 1 wherein a sign bit in the corresponding chaining array entry indicates whether the corresponding entries array bucket contains a head-of-chain entry or a tail-of-chain entry.
number: 3
text: The method of claim 1 or 2 further comprising displacing, with one or more processors, a movable tail-of-chain entry from the bucket in the entries array corresponding to the hash value to a free bucket within a maximum chaining range in the entries array.
number: 4
text: The method of one of claims 1 to 3 further comprising recursively displacing one or more tail-of-chain entries in the entries array to free a bucket to add new data in the entries array when there is no free bucket available within the maximum chaining range.
number: 5
text: The method of claim 4 further comprising enlarging both the entries array and the chaining array if no free bucket can be found within a maximum chaining range through recursive displacement.
number: 6
text: The method of one of claims 1 to 5 further comprising enlarging both the entries array and the chaining array if no free bucket can be found within a maximum chaining range.
number: 7
text: The method of claims 5 or 6 further comprising re-hashing and resorting data stored in buckets of the entries array in response to enlargement of the entries array and the chaining array.
number: 8
text: An apparatus comprising:
number: 9
text: The apparatus of claim 8 wherein a sign bit in the corresponding chaining array entry indicates whether the corresponding entries array bucket contains a head-of-chain entry or a tail-of-chain entry.
number: 10
text: The apparatus of claim 8 or 9 further comprising means for recursively displacing one or more tail-of-chain entries in the entries array to free a bucket to add new data in the entries array when there is no free bucket available within the maximum chaining range.
number: 11
text: The apparatus of claim 10 further comprising means for enlarging both the entries array and the chaining array if no free bucket can be found within a maximum chaining range through recursive displacement.
number: 12
text: The method of one of claims 8 to 11 further comprising means for enlarging both the entries array and the chaining array if no free bucket can be found within a maximum chaining range.
number: 13
text: The apparatus of one of claims 11 or 12 further comprising means for re-hashing and resorting data stored in buckets of the entries array in response to enlargement of the entries array and the chaining array.
Office action: search_report, dated 2017-11-29
Prior art cited: ref_id: US7730478B2
ref_type: patent
severity: background
ref_id: US81716104A
ref_type: patent
severity: background
ref_id: US7827182B1
ref_type: patent
severity: background
ref_id: US2006265370A1
ref_type: patent
severity: background
ref_id: US5287499A
ref_type: patent
severity: background
ref_id: - "Local and Metropolitan Area Networks, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Higher-Speed Physical Layer Extension in the 2.4 GHz Band", IEEE 802.11 B CORRESPONDS TO IEEE STD. 802.1 LB-1999, 16 September 1999 (1999-09-16)
ref_type: npl
severity: background
ref_id: - "Local and Metropolitan Area Networks, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Amendment 4: Further Higher Rate Extension in the 2.4 GHz Band", IEEE 802.1 IG CORRESPONDS TO IEEE STD. 802.1 LG-2003, 27 June 2003 (2003-06-27)
ref_type: npl
severity: background
ref_id: - "Specification of the Bluetooth System: Core, Version 1.1", 22 February 2001, BLUETOOTH SPECIAL INTEREST GROUP, INC
ref_type: npl
severity: background
ref_id: WO2011073680A1
ref_type: patent
severity: background
ref_id: US2014214855A1
ref_type: patent
severity: background
ref_id: - PETER NIMBE ET AL: "An Efficient Strategy for Collision Resolution in Hash Tables", INTERNATIONAL JOURNAL OF COMPUTER APPLICATIONS, vol. 99, no. 10, 1 August 2014 (2014-08-01), pages 35 - 41, XP055315670, DOI: 10.5120/17411-7990
ref_type: npl
severity: background
ref_id: - MUNRO J I ET AL: "Techniques for Collision Resolution in Hash Tables with Open Addressing", PROCEEDINGS OF THE FALL JOINT COMPUTER CONFERENCE. DALLAS, NOV. 2 - 6, 1986; [PROCEEDINGS OF THE FALL JOINT COMPUTER CONFERENCE], WASHINGTON, IEEE COMP. SOC. PRESS, US, 2 November 1986 (1986-11-02), pages 601 - 610, XP002468465
ref_type: npl
severity: background
ref_id: WO2011073680
ref_type: patent
severity: background
ref_id: US2014214855
ref_type: patent
severity: background
ref_id: - PETER NIMBE ET AL, "An Efficient Strategy for Collision Resolution in Hash Tables", INTERNATIONAL JOURNAL OF COMPUTER APPLICATIONS, (20140801), vol. 99, no. 10, doi:10.5120/17411-7990, pages 35 - 41, XP055315670 [A] 1-13 * section 2.1, 2.2 *
ref_type: npl
severity: background
ref_id: - MUNRO J I ET AL, "Techniques for Collision Resolution in Hash Tables with Open Addressing", PROCEEDINGS OF THE FALL JOINT COMPUTER CONFERENCE. DALLAS, NOV. 2 - 6, 1986; [PROCEEDINGS OF THE FALL JOINT COMPUTER CONFERENCE], WASHINGTON, IEEE COMP. SOC. PRESS, US, (19861102), pages 601 - 610, XP002468465 [A] 1-13 * the whole document *
ref_type: npl
severity: background
Final disposition: pending (2017-11-29)