Data indexing using bit vectors
The present invention provides for indexing of occurrences of a value in at least one data record using a bit vector wherein a bit vector is associated with the value and a bit of the bit vector representation is associated with the at least one data record, a determination is made whether the value exists in the at least one data record, a bit value is assigned to the bit in the bit vector representation based on the outcome of the determination. Further, operations may be performed on multiple bit vectors indexing data records and values used in the data records to determine the existence of combinations and associations between the corresponding values and the indexed data records.
1. A method of indexing occurrences of a value in at least one data record using a bit vector comprising:
associating a first bit vector with a first value to be held in a first field;
associating a second bit vector with a second value to be held in said first field;
associating a third bit vector with a third value to be held in a second field;
performing a first logical “AND” operation on said first bit vector with said third bit vector to yield a first result Boolean value wherein said first logical “AND” operation terminates upon achieving a first successful match on a bit by bit basis;
performing a second logical “AND” operation on said second bit vector with said third bit vector to yield a second result Boolean value wherein said second logical “AND” operation terminates upon achieving a second successful match on a bit by bit basis;
storing said first result Boolean value and said second result Boolean value as a value limit correlation wherein said value limit correlation comprises a first index having a first dimension sized to a first number of distinct values held in said first field and a second index having a second dimension sized to a second number of distinct values held in said second field irregardless of a total data record count; and
determining if at least one record in a database exists wherein said at least one record comprises both said first value in said first field and said third value in said second field by accessing said value limit correlation and without accessing said database and without accessing said first, said second or said third bit vectors.
2. A method of indexing occurrences of a value in at least one data record using a bit vector comprising:
associating a first bit vector with a first value to be held in a first field;
associating a second bit vector with a second value to be held in said first field;
associating a third bit vector with a third value to be held in a second field;
performing a first logical “AND” operation on said first bit vector with said third bit vector to yield a first result Boolean value wherein said first logical “AND” operation terminates upon achieving a first successful match on a bit by bit basis;
performing a second logical “AND” operation on said second bit vector with said third bit vector to yield a second result Boolean value wherein said second logical “AND” operation terminates upon achieving a second successful match on a bit by bit basis;
storing said first result Boolean value and said second result Boolean value as a value limit correlation wherein said value limit correlation comprises a first index having a first dimension sized to a first number of distinct values held in said first field and a second index having a second dimension sized to a second number of distinct values held in said third field irregardless of a total data record count;
determining if at least one record in a database exists wherein said at least one record comprises both said first value in said first field and said third value in said second field by accessing said value limit correlation and without accessing said database and without accessing said first, said second or said third bit vectors;
changing said first value in said first field in a first data record to said second value;
inverting a first bit in said first bit vector to represent a false value at a first bit vector position corresponding to said first data record;
inverting a second bit in said second bit vector to represent a true value at said first bit vector position corresponding to said first data record;
setting a Boolean true value in said value limit correlation at said first index corresponding to said second value and at said second index corresponding to said third value;
performing a third logical “AND” operation on said first bit vector with said third bit vector to yield a third result Boolean value wherein said third logical “AND” operation terminates upon achieving a third successful match; and,
setting a Boolean false value in said value limit correlation at said first index corresponding to said first value and at said second index corresponding to said third value if said performing said third logical “AND” operation yields a false third result Boolean value.