Size-dependent hashing for credit card verification and other applications
AssigneeArcot Systems, Inc.
InventorsSanguthevar Rajasekaran, James Reno
Life of this patent
Estimating the term…
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.
Claims43
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=bq;
- (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.
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=bq 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.
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=bq;
- (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.
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=bq 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.
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=bq;
- (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.
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=bq 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.
Dependencies are inferred from the claim text.