Table look-up method with adaptive hashing

• US 7,539,661 B2
• Filed: 06/02/2005
• Issued: 05/26/2009
• 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.
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Uddin; Mohammed R
• Application Number:
  US11/143,054
• Publication Number:
  US 20060277178A1
• Time in Patent Office: 1,454 Days
• Field of Search: 707/4, 707/5, 707/6, 707/7, 707/8, 707/101, 707/102, 707/103, 707/104
• 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 controlling a system using control data stored in a data table within a controller memory unit indexed as a function of a measurable parameter of the system, the method comprising the steps of:

establishing a hash table in said memory unit having hash index values;

linking various values of said measurable parameter to said hash index values with a hash function;

forming key elements for each of the linked values of said measurable parameter, each key element including a hash index value, an index value for said data table and a weight value;

selecting for inclusion in the hash table only key elements for which said weight value exceeds a specified weight, and chaining the selected key elements to a respective hash index value in said hash table;

obtaining a sample of said measurable parameter;

determining a hash index value corresponding to said sample, probing the key elements chained to the determined hash index to locate a key element for said sample, and locating control data stored for said sample using a data table index value of the located key element;

probing said data table to locate the control data for said sample if a key element for said sample is not located in said hash table; and

controlling said system using the located control data.

2. The method of claim 1, including the steps of:

periodically updating said weight values based on at least one of access frequency and time since last access; and

repeating the steps of selecting for inclusion in the hash table only key elements for which said weight value exceeds a specified weight, and chaining the selected key elements to a respective hash index value in said hash table.

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

ordering the key elements chained to a respective hash index value based on said weight values so that such key elements are probed in order of weight value.

4. The method of claim 3, including the steps of:

periodically updating said weight values; and

re-ordering said key elements based on the updated weight values.

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

periodically updating said weight values; and

repeating the steps of selecting for inclusion in the hash table only key elements for which said weight value exceeds a specified weight, and chaining the selected key elements to a respective hash index value in said hash table.