Encoded-data database for fast queries

• US 6,804,664 B1
• Filed: 10/10/2000
• Issued: 10/12/2004
• Est. Priority Date: 10/10/2000
• Status: Active Grant

• Current Assignee: NetZero Incorporated (B. Riley Financial, Inc.)
• Original Assignee: NetZero Incorporated (B. Riley Financial, Inc.)
• Inventors: Hartman, Brian, Jones, Jr., Michael R., Anusauskas, Laimonas, Achenbach, James
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): WOO, ISAAC M
• Application Number:
  US09/685,479
• Time in Patent Office: 1,463 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/8, 707/9, 707/10, 707/100, 707/101, 707/102, 707/200, 707/201, 707/202
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A new and efficient way of structuring databases enabling efficient query processing, reduced database storage requirements, and more flexible content targeting is described. A database is defined having bit mapped data. The data to be stored in the database is characterized as a number of binary questions. Each record comprises one or more groups of bit maps corresponding to the answers to the questions. For some types of data, there may be two or more possible values. In such cases, each possible value is itself a binary question. In some cases, there may be data which does not lend itself to characterization as binary questions. In such cases, the database includes numeric and string values. Queries of the database may be obtained through simple bit wise Boolean operations directly of the records in the database.

Claims

1. A method of querying a database, the method comprising the steps of:

providing binary attributes having respectively associated therewith predefined lists of allowable values and corresponding bitmasks

providing the database, the database comprising plural records, at least some of the records comprising profiles, the profiles comprising at least one target comprising one binary attribute having a bitmask, at least some of the records comprising profiles comprising a range attribute having a numeric value

forming a query comprising a query profile, the query profile including

a first target comprising a first bitmask corresponding to a first binary attribute and a first value

a second target comprising a range attribute and a range of numeric values performing bitwise logical operations of the first bitmask with the record profiles to thereby identify records in the database having the first target (“

first records”

)

after the step of performing bitwise logical operations, testing the range attributes of each of the first records to thereby identify second records in the database having the range attribute within the range of numeric values of the third target (“

second records”

).

2. The method of querying a database as set forth in claim 1

the query profile further including a third target comprising a second bitmask corresponding to a second desired attribute and a second value

the first bitmask and the second bitmask being joined into a single bitmask to thereby form a chunk

the step of performing bitwise logical operations comprising performing bitwise logical operations of the chunk with the record profiles to thereby identify records in the database having the first target and the third target.

3. The method of querying a database as set forth in claim 1

the query profile further including a third target comprising a second bitmask corresponding to a second desired attribute and a second value

the first bitmask comprising a first chunk and the second bitmask comprising a second chunk

the step of performing bitwise logical operations comprising

performing bitwise logical operations of the first chunk with the record profiles to thereby identify records in the database having the first target (“

second records”

) and then

performing bitwise logical operations of the second chunk with the profiles of each of the second records to thereby identify first records having the second target.

4. The method of querying a database as set forth in claim 1

at least some of the records comprising profiles comprising a string attribute having a non-numeric value

the forming step further comprising forming the query from a fourth target comprising a string attribute and a non-numeric value

after the step of performing bitwise logical operations, testing the string attributes of each of the second records to thereby identify third records in the database having the string attribute corresponding to the non-numeric value of the fourth target.

5. A method of querying a database using binary attributes, the binary attributes having respectively associated therewith predefined lists of allowable values and corresponding bitmasks, the database comprising plural records, at least some of the records comprising profiles, the profiles comprising a first target comprising one binary attribute having a bitmask and a second target comprising a range attribute and a range of numeric values, the method comprising the steps of

forming a query comprising a query profile, the query profile including

a first target comprising a first bitmask corresponding to a first binary attribute and a first value

a second target comprising a range attribute and a range of numeric values performing bitwise logical operations of the first bitmask with the record profiles to thereby identify records in the database having the first target

after the step of performing bitwise logical operations, testing the range attributes of each of the second records to thereby identify second records in the database having the range attribute within the range of numeric values of the third target.

6. A method of storing data in a database, the method comprising the steps of:

providing a correlation table for plural binary attributes, the binary attributes having respectively associated therewith predefined lists of allowable values and corresponding bitmasks,

receiving a first field of raw data

receiving a second field of raw data

looking up the first field in the correlation table and retrieving the bitmask for the binary attribute corresponding to the first field

looking up the second field in the correlation table and retrieving the bitmask for the binary attribute corresponding to the second field

storing a profile in the database, the profile comprising

a first target, the first target comprising the retrieved bitmask for the binary attribute corresponding to the first field having the corresponding bit set corresponding to the raw data for the first field as provided in the correlation table

a second target, the second target comprising the retrieved bitmask for the binary attribute corresponding to the second field having the corresponding bit set corresponding to the raw data for the second field as provided in the correlation table

wherein the first target and the second target are formed and stored in a chunk of plural bits, the first target and the second target each having predefined positions in the chunk, the chunk having a length, wherein the length renders the chunk at least one of easily stored in memory, retrievable from memory or manipulated by a processor.

7. The method of storing data in a database as set forth in claim 6, wherein the assigned bit is set as “

1”

.

8. The method of storing data in a database as set forth in claim 6, wherein the assigned bit is set as “

0”

.

9. The method of storing data in a database as set forth in claim 6, the bitmasks each have a length equal to the number of allowable values for the corresponding binary attribute.

10. The method of storing data in a database as set forth in claim 6, the binary profile comprising plural chunks of plural targets.

11. The method of storing data in a database as set forth in claim 6

further comprising receiving a second field of raw data, the second field comprising a numeric value

storing a range attribute in the database, the range attribute comprising the numeric value.

12. The method of storing data in a database as set forth in claim 6

further comprising receiving a second field of raw data, the second field comprising a non-numeric value

storing a string attribute in the database, the string attribute comprising the non-numeric value.

13. A database system comprising

a correlation table of binary attributes having respectively associated therewith predefined lists of allowable values and corresponding bitmasks

a user database comprising plural records, at least some of the records comprising profiles, the profiles comprising

a first target comprising one binary attribute having a bitmask

a second target comprising a range attribute and a range of numeric values

a content database comprising plural records, at least some of the records comprising profiles, the profiles comprising

a first target comprising one binary attribute having a bitmask

a second target comprising a range attribute and a range of numeric values

computer software code for matching records of the content database with a selected record of the user database, the selected record having a first target, the computer software code including code for

performing bitwise logical operations of the bitmask of the selected record of the user database with the profiles of the records of the content database to thereby identify records of the content database having the first target (“

first records”

)

after performing bitwise logical operations, testing the range attributes of each of the first records to thereby identify second records in the database having the range attribute within the range of numeric values of the second target.

14. A method of querying a database, the method comprising the steps of:

providing binary attributes having respectively associated therewith predefined lists of allowable values and corresponding bitmasks

providing the database, the database comprising plural records, at least some of the records comprising profiles, the profiles comprising a first target comprising one binary attribute having a first bitmask and a second target comprising one binary attribute having a second bitmask, the records including at least one chunk comprising binary attributes of a single bitmap, the chunk having a length, wherein the length readers the chunk at least one of easily stored in memory, retrieved from memory or manipulated by a processor

forming a query comprising a query profile, the query profile including a chunk formed from

a third target comprising a third bitmask corresponding to a first binary attribute and a first value

a fourth target comprising a fourth bitmask corresponding to a second binary attribute and a second value

performing bitwise logical operations of the query chunk with the chunks of the record profiles to thereby identify records in the database having the third target and the fourth target.

15. The method of querying a database as set forth in claim 14

at least some of the records comprising profiles comprising a range attribute having a numeric value

the forming step further comprising forming the query from a third target comprising a range attribute and a range of numeric values

after the step of performing bitwise logical operations, testing the range attributes of each of the second records to thereby identify second records in the database having the range attribute within the range of numeric values of the third target.

16. The method of querying a database as set for in claim 15

at least some of the records comprising profiles comprising a string attribute having a non-numeric value

the forming step further comprising forming the query from a fourth target comprising a string attribute and a non-numeric value

after the step of performing bitwise logical operations, testing the string attributes of each of the third records to thereby identify third records in the database having the string attribute corresponding to the non-numeric value of the fourth target.

17. A database system comprising

a correlation table of binary attributes having respectively associated therewith predefined lists of allowable values and corresponding bitmasks

a user database comprising plural records, at least some of the records comprising profiles, the profiles comprising a first chunk including

a first target comprising one binary attribute having a first bitmask

a second target comprising one binary attribute having a second bitmask

a content database comprising plural records, at least some of the records comprising profiles, the profiles comprising a second chunk including

a third target comprising one binary attribute having a third bitmask

a fourth target comprising one binary attribute having a fourth bitmask

computer software code for matching records of the content database with a selected record of the user database, the selected record having a fifth target, the computer software code including code for

performing bitwise logical operations of the bitmask of the selected record of the user database with the profiles of the records of the content database to thereby identify records of the content database having the fifth target

wherein the first chunk and the second chunk comprises plural bits having a respective length, wherein the length renders the chunk at least one of easily stored in memory, retrieved from memory, or manipulated by a processor.