Size-dependent hashing for credit card verification and other applications

• US 20030172085A1
• Filed: 03/08/2002
• Published: 09/11/2003
• Est. Priority Date: 03/08/2002
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Arcot Systems, Inc. (Broadcom, Inc.)
• Inventors: Rajasekaran, Sanguthevar, Reno, James
• Granted Patent: US 7,020,782 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

Searching is an important problem that arises in a variety of applications, particularly for computerized databases. Further, many such applications involve searching set of (possible very large) integers (e.g., credit card numbers, employee identifiers, customer identifiers, dates, parts numbers, etc.). We present techniques for integer searching in a computer database based on a improved form of hashing which we shall refer to as “size-dependent hashing.” This technique can be used to strike a balance between the available memory in the computer system and the required search time.

Claims

1. A method of constructing a computer-searchable hash table, comprising:

(a) accessing a plurality of elements, including values representable in integer form in a base b;

(b) selecting a hash index parameter, q, by taking into account computer memory and search time constraints;

(c) constructing a hash table from said plurality of elements by;

(i) initializing a plurality of at least L lists, where L=b^q;

(ii) populating each of said lists with a subset of said plurality of elements (if any) that share at least q digits in common; and

(d) storing said hash table including said populated lists in a computer memory, thereby allowing future searching thereof, for a target value, by using a q-digit portion of said target value as an index to said hash table.

2. The method of claim 1 further comprising:

(e) receiving said target value, comprising said value in (d), and representable in integer form in said base b;

(f) determining, in said hash table, a corresponding list configured to store elements sharing at least q digits in common with said target value;

(g) determining if any of said elements of said corresponding list includes said target value;

(h) if the result of (g) is positive, reporting a successful search result.

3. The method of claim 1 where said taking into account memory and search time constraints includes substantially minimizing said search time by using substantially all computer memory available to said search.

4. The method of claim 1 where said taking into account memory and search time constraints includes balancing said search time against utilization of said computer memory.

5. The method of claim 1 where said selecting said q in (b) includes:

(i) for each of a plurality of possible values of q, computing the corresponding computer memory required to store the corresponding L lists; and

(ii) selecting one of said potential values of q such that the corresponding required memory is available.

6. The method of claim 1 where said searching in (d) includes determining a location for an insert or delete operation.

7. The method of claim 1 further comprising maintaining a separate, searchable data structure for tracking insert/delete operations that have occurred since construction of said hash table.

8. The method of claim 1 where said plurality of elements include ranges of values to be checked for the presence of said target value.

9. The method of claim 8:

(1) configured for use in a credit card searching environment;

(2) where said elements include valid credit card ranges; and

(3) where said target value includes a credit card number.

10. The method of claim 9:

(1) implemented at a directory server accessible over a network by a party checking for validity of said credit card number;

(2) where said elements include at least one reference to an access control server containing information about participation in a payment authentication program.

11. The method of claim 1 further comprising representing one of said populated lists using another hash table in a manner analogous to the method of claim 1.

12. The method of claim 11 in which said q-digit portion of said target value represents the q most significant digits thereof, and said another hash table utilizes one or more of the next most significant digits (after q) of said target value values as a search index.

13. The method of claim 1 where:

(1) each of said elements includes data pertaining to a numeric interval; and

(2) facilitating the handling of an out-of-range interval by allowing a searcher to access a nearest non-empty list.

14. The method of claim 13 where (2) includes adding a reference, within each empty list, to a non-empty list nearest thereto.

15. The method of claim 1 further comprising padding shorter values within said plurality of elements to be the same length as longer values therein.

19. The method of claim 16:

(1) where at least some of said included values are associated with data pertaining to a numeric interval;

(2) further comprising modifying each empty list to include a reference to the next-nearest non-empty list; and

(3) where said (d) includes handling an out-of-range interval by checking its nearest non-empty list.

25. The system of claim 20:

(1) configured for use in a credit card searching environment;

(2) where said elements include valid credit card ranges; and

(3) where said target value includes a credit card number.

26. The system of claim 25:

(1) implemented at a directory server accessible over a network by a party checking for validity of said credit card number; and

(2) where said elements include at least one reference to an access control server containing information about participation in a payment authentication program.

27. The system of claim 20:

(1) further comprising means for representing one of said populated lists using another hash table in a manner analogous to that of claim 20;

(2) where said q-digit portion of said target value represents the q most significant digits thereof; and

(3) where said another hash table utilizes one or more of the next most significant digits (after q) of said target value values as a search index.

31. The system of claim 28:

(1) where at least some of said included values are associated with data pertaining to a numeric interval;

(2) further comprising means for modifying each empty list to include a reference to the next-nearest non-empty list; and

(3) where said (d) includes means for handling an out-of-range interval by checking its nearest non-empty list.

37. The computer-readable medium of claim 32:

(1) configured for use in a credit card searching environment;

(2) where said elements include valid credit card ranges; and

(3) where said target value includes a credit card number.

38. The computer-readable medium of claim 37:

(1) implemented at a directory server accessible over a network by a party checking for validity of said credit card number; and

(2) where said elements include at least one reference to an access control server containing information about participation in a payment authentication program.

39. The computer-readable medium of claim 32:

(1) further comprising logic instructions that if executed represent one of said populated lists using another hash table in a manner analogous to that of claim 32;

(2) where said q-digit portion of said target value represents the q most significant digits thereof; and

(3) where said another hash table utilizes one or more of the next most significant digits (after q) of said target value values as a search index.

43. The computer-readable medium of claim 40:

(1) where at least some of said included values are associated with data pertaining to a numeric interval;

(2) further comprising logic instruction that if executed modify each empty list to include a reference to the next-nearest non-empty list; and

(3) where said (d) includes handling an out-of-range interval by checking its nearest non-empty list.

16. A method of conducting a computerized search of an integer database, comprising:

(a) accessing from a computer-readable memory a hash table;

(i) including a plurality of at least L lists;

(ii) at least one of said lists being non-empty;

(iii) each said non-empty list including at least one value to be searched;

(iv) each included value in said non-empty list sharing at least q common digits, where L=b^q for some integer base b;

(b) receiving a target value, representable in integer form in a base b, to be searched among said plurality of lists; and

(c) determining, in said hash table, a corresponding list configured to store values having at least q digits in common with said target value;

(d) determining if any of said values of said corresponding list includes said target value;

(e) if the result of (d) is positive, reporting a successful search result.

17. The method of claim 16 where (d) includes searching said corresponding list using another hash table in a manner analogous to the search method of claim 16.

18. The method of claim 17 in which:

(i) said q represents the q most significant digits shared in common among said target value and said values in said list; and

(ii) said another hash table utilizes one or more of the next most significant digits (after q) of said target value as a search index.

20. A system for constructing a computer-searchable hash table, comprising:

(a) means for accessing a plurality of elements, including values representable in integer form in a base b;

(b) means for selecting a hash index parameter, q, by taking into account computer memory and search time constraints;

(c) means for constructing a hash table from said plurality of elements by;

(i) initializing a plurality of at least L lists, where L=b^q;

(ii) populating each of said lists with a subset of said plurality of elements (if any) that share at least q digits in common; and

(d) a computer memory for storing said hash table including said populated lists, thereby allowing future searching thereof, for a target value, by using a q-digit portion of said target value as an index to said hash table.

21. The system of claim 20 further comprising:

(e) means for receiving said target value, comprising said value in (d), and representable in integer form in said base b;

(f) means for determining, in said hash table, a corresponding list configured to store elements sharing at least q digits in common with said target value;

(g) means for determining if any of said elements of said corresponding list includes said target value;

(h) means for reporting a successful search result, if the result of (g) is positive.

22. The system of claim 20 where said taking into account memory and search time constraints includes substantially minimizing said search time by using substantially all computer memory available to said search.

23. The system of claim 20 where said taking into account memory and search time constraints includes balancing said search time against utilization of said computer memory.

24. The system of claim 20 where said selecting said q in (b) includes:

(i) computing the corresponding computer memory required to store the corresponding L lists, for each of a plurality of possible values of q; and

(ii) selecting one of said potential values of q such that the corresponding required memory is available.

28. A system for conducting a computerized search of an integer database, comprising:

(a) means for accessing from a computer-readable memory a hash table;

(i) including a plurality of at least L lists;

(ii) at least one of said lists being non-empty;

(iii) each said non-empty list including at least one value to be searched;

(iv) each included value in said non-empty list sharing at least q common digits, where L=b^q for some integer base b;

(b) means for receiving a target value, representable in integer form in a base b, to be searched among said plurality of lists;

(c) means for determining, in said hash table, a corresponding list configured to store values having at least q digits in common with said target value;

(d) means for determining if any of said values of said corresponding list includes said target value; and

(e) means for reporting a successful search result, if the result of (d) is positive.

29. The system of claim 28 where (d) includes means for searching said corresponding list using another hash table in a manner analogous to that of claim 28.

30. The system of claim 29 in which:

(i) said q represents the q most significant digits shared in common among said target value and said values in said list; and

(ii) said another hash table utilizes one or more of the next most significant digits (after q) of said target value as a search index.

32. A computer-readable medium containing logic instructions for constructing a computer-searchable hash table, said instructions if executed:

(a) accessing a plurality of elements, including values representable in integer form in a base b;

(b) selecting a hash index parameter, q, by taking into account computer memory and search time constraints;

(c) constructing a hash table from said plurality of elements by;

(i) initializing a plurality of at least L lists, where L=b^q;

(ii) populating each of said lists with a subset of said plurality of elements (if any) that share at least q digits in common; and

(d) storing said hash table including said populated lists in a computer memory, thereby allowing future searching thereof, for a target value, by using a q-digit portion of said target value as an index to said hash table.

33. The computer-readable medium of claim 32 further comprising logic instructions that if executed:

(e) receive said target value, comprising said value in (d), and representable in integer form in said base b;

(f) determine, in said hash table, a corresponding list configured to store elements sharing at least q digits in common with said target value;

(g) determine if any of said elements of said corresponding list includes said target value; and

(h) if the result of (g) is positive, report a successful search result.

34. The computer-readable medium of claim 32 where said taking into account memory and search time constraints includes substantially minimizing said search time by using substantially all computer memory available to said search.

35. The computer-readable medium of claim 32 where said taking into account memory and search time constraints includes balancing said search time against utilization of said computer memory.

36. The computer-readable medium of claim 32 where said selecting said q in (b) includes:

(i) for each of a plurality of possible values of q, computing the corresponding computer memory required to store the corresponding L lists; and

(ii) selecting one of said potential values of q such that the corresponding required memory is available.

40. A computer-readable medium containing logic instructions for conducting a computerized search of an integer database, said instructions if executed:

(a) accessing from a computer-readable memory a hash table;

(i) including a plurality of at least L lists;

(ii) at least one of said lists being non-empty;

(iii) each said non-empty list including at least one value to be searched;

(iv) each included value in said non-empty list sharing at least q common digits, where L=b^q for some integer base b;

(b) receiving a target value, representable in integer form in a base b, to be searched among said plurality of lists;

(c) determining, in said hash table, a corresponding list configured to store values having at least q digits in common with said target value;

(d) determining if any of said values of said corresponding list includes said target value;

(e) if the result of (d) is positive, reporting a successful search result.

41. The computer-readable medium of claim 40 where (d) includes searching said corresponding list using another hash table in a manner analogous to the search computer-readable medium of claim 40.

42. The computer-readable medium of claim 41 in which:

(i) said q represents the q most significant digits shared in common among said target value and said values in said list; and

(ii) said another hash table utilizes one or more of the next most significant digits (after q) of said target value as a search index.