Table look-up method with adaptive hashing

• US 20060277178A1
• Filed: 06/02/2005
• Published: 12/07/2006
• Est. Priority Date: 06/02/2005
• Status: Active Grant

• Current Assignee: Aptiv Technologies AG (Aptiv PLC)
• Original Assignee: Delphi Technologies, Inc. (BorgWarner Incorporated)
• Inventors: Wang, Ting Z.
• Granted Patent: US 7,539,661 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Accessed memory locations of a data table are assigned weights based on usage history, and a hash table chains the highest-weight key values to an abbreviated hash index. The hash table includes keys having at least a predetermined weight so that highly accessed keys are identified by hashing. Additionally, the keys chained to a given hash index are ordered based on their weight in order to optimize the overall data retrieval time. The weights assigned to accessed keys are updated over time so that the content of the hash table is adaptively updated to suit the current table look-up requirements.

Claims

1. A method of accessing data stored in an indexed data table for various values of a key, the method comprising the step of:

establishing a hash table having hash index values and a hash function that links the values of said key to said hash index values;

assigning weights to the values of said key that are used to access said data;

establishing key elements corresponding to the values of said key that are used to access said data, said key elements including a corresponding index value for said data table;

selecting key elements for values of said key that are linked to a given hash index value and that have a selected weight, and chaining the selected key elements to the given hash index value in said hash table; and

responding to a data access request for a supplied value of said key by probing the chained key elements of said hash table to locate a key element for the supplied key, along with the data table index value of such key element, and accessing data stored in the data table using the located data table index value.

2. The method of claim 1, where the weights assigned to the values of said key that are used to access said data are based on at least one of access frequency and time since last access.

3. The method of claim 1, including the step of:

selecting key elements for values of said key that are linked to a given hash index value and that have a weight in excess of a specified minimum weight, and chaining the selected key elements to the given hash index value in said hash table.

4. The method of claim 1, including the step of:

ordering the key elements chained to the given hash index value in said hash table based on the assigned weight so that such key elements are probed in order of assigned weight in response to said data access request.

5. The method of claim 1, including the step of:

updating the weights assigned to the values of said key that are used to access said data; and

changing an order of the key elements chained to the hash index values of said hash table based on the updated weights.

6. The method of claim 1, including the step of:

updating the weights assigned to the values of said key that are used to access said data; and

repeating the step of selecting and chaining said key elements based on the updated weights.