User segment population techniques

• US 7,966,333 B1
• Filed: 09/04/2008
• Issued: 06/21/2011
• Est. Priority Date: 06/17/2003
• Status: Active Grant

• Current Assignee: AudienceScience, Inc.
• Original Assignee: AudienceScience, Inc.
• Inventors: Chan, Stella, Uppala, Krishna, Jayachandaran, Umachandar, Basko, Roman, Choudary, Piali
• Primary Examiner(s): Radtke; Mark Andrew X
• Application Number:
  US12/204,709
• Time in Patent Office: 1,020 Days
• Field of Search: 707/747
• US Class Current: 707/747
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

A facility for populating a segment from a population of individuals is described. The facility accesses two or more fact tables, each containing data about attributes of a number of users who are members of a number of arbitrary user groups. The facility generates a number of column chunks from each fact table. Each column chunk contains data about a single attribute of users that are members of a single arbitrary user group. The facility applies a segment membership test that tests particular user attributes to each arbitrary user groups in turn. In doing so, the facility collects the generated column chunks that contain data about attributes of users that are members of the current arbitrary user group tested by the segment membership test. The facility applies the segment membership test to the collected column chunks to identify individuals within the arbitrary user group that satisfy the segment membership test.

Claims

1. A method in a computing system for populating a segment from a population of individuals, comprising:

from one or more fact tables each comprised of rows, each row divided into columns including an individual identifier column and at least one fact column, the individual identifier column containing an individual identifier value uniquely identifying an individual, each fact column containing a fact relating to the individual identified by the individual identifier value, extracting the individual identifier column and the fact columns;

creating a hash column, wherein, in each entry of the hash column, the hash column stores a hash value computed by applying a hash function to the value contained in the corresponding entry of the extracted individual identifier column, wherein the hash function creates one or more groups based on the values contained in the corresponding entries that hash to the same value, and wherein a substantially equal number of individual identifiers is attributed to each of the one or more groups;

for each distinct hash value occurring in the hash column;

storing in a distinct, contiguous portion of a filesystem file the individual identifier values of the entries of the extracted individual identifier column corresponding to the entries of the hash column containing the distinct hash value, in the order in which the individual identifier values occur in the extracted individual identifier column;

for each of the extracted fact columns;

storing in a distinct, contiguous portion of a filesystem file the fact values of the entries of the extracted fact column corresponding to the entries of the hash column containing the distinct hash value, in the order in which the fact values occur in the extracted fact column;

receiving a request to populate a segment, the segment being defined by a segment definition containing a reference to a specialized routine for evaluating individuals for segment membership, the referenced specialized routine depending on a subset of the fact columns;

for each distinct hash value occurring in the hash column;

of the filesystem file portions stored for the distinct hash value, loading for simultaneous co-residency in memory those stored for the individual identifier column and the subset of fact columns depended on by the referenced specialized routine; and

executing the specialized routine against the loaded data to identify individuals among the population that are members of the segment.

2. The method of claim 1 wherein the subset of fact columns referenced by the referenced specialized routine is a proper subset of the extracted fact columns.

3. The method of claim 1 wherein the subset of fact columns referenced by the referenced specialized routine contains all of the extracted fact columns.

4. The method of claim 1 wherein the segment definition contains two distinct clauses each comprising a reference to a specialized routine for evaluating individuals for satisfaction of the clause, each of the two specialized routines depending on a subset of the fact columns,

and wherein, for each of the two referenced specialized routines, the loading and executing is performed for each distinct hash value occurring in the hash column to produce a clause result,

the method further comprising combining the two produced clause results to identify individuals among the population that are members of the segment.

5. A method in a computing system for populating a segment from a population of individuals, comprising:

reading a fact table comprised of rows, each row divided into columns including an individual identifier column and at least one fact column, the individual identifier column containing an individual identifier value uniquely identifying an individual, each fact column containing a fact relating to the individual identified by the individual identifier value;

for each row of the fact table, applying a hashing function to the individual identifier value contained by the fact table to obtain a hash value, wherein the hash function creates one or more groups based on the values contained in the corresponding entries that hash to the same value, and wherein a substantially equal number of individual'"'"'identifiers is attributed to each of the one or more groups;

for each distinct hash value obtained;

storing in a distinct, contiguous portion of a file the individual identifier values of the rows of the fact table for which the distinct hash value is obtained, in the order in which the individual identifier values occur in the individual identifier column;

for at least a portion of the fact columns;

storing in a distinct, contiguous portion of a file the fact values of the entries of the rows of the fact table for which the distinct hash value is obtained, in the order in which the fact values occur in the fact column;

receiving a request to populate a segment, the segment being defined by a segment definition containing a reference to a segment membership test for evaluating individuals for segment membership, the referenced specialized routine depending on a subset of the fact columns;

for each distinct hash value obtained;

of the file portions stored for the distinct hash value, loading for simultaneous co-residency in memory those stored for the individual identifier column and the subset of fact columns depended on by the referenced specialized routine; and

applying a segment membership test against the loaded data to identify individuals among the population that are members of the segment.

6. The method of claim 5 wherein the subset of fact columns referenced by the referenced specialized routine is a proper subset of the fact columns.

7. The method of claim 5 wherein the subset of fact columns referenced by the referenced specialized routine contains all of the fact columns.

8. The method of claim 5 wherein the segment definition contains two distinct clauses each comprising a reference to a clause satisfaction test for evaluating individuals for satisfaction of the clause, each of the two clause satisfaction tests depending on a subset of the fact columns,

and wherein, for each of the two referenced clause satisfaction tests, the loading and applying is performed for each distinct hash value obtained to produce a clause result, the method further comprising combining the two produced clause results to identify individuals among the population that are members of the segment.

9. The method of claim 8 wherein each clause result is a clause satisfaction bit array having a bit corresponding to each individual in which only the bits corresponding to individuals satisfying the clause satisfaction test from which the clause result is produced,

and wherein combining the two produced clause results comprises performing a bitwise boolean operation on the two clause satisfaction bit arrays to produce a segment membership bit array.

10. One or more computer memories collectively containing an individual attribute data structure generated from a database table, comprising:

an individual identifier column extracted from the database table, the individual identifier column comprising an ordered series of entries each containing an individual identifier value;

a plurality of fact columns, each fact column extracted from the database table and comprising an ordered series of entries each containing a fact value; and

a hash column comprising an ordered series of entries each containing a hash value obtained by applying a hash function to the individual identifier value contained in the corresponding entry of the individual identifier column, wherein the hash function creates one or more groups based on the values contained in the corresponding entries that hash to the same value, and wherein a substantially equal number of individual identifiers is attributed to each of the one or more groups;

such that, to determine whether an individual belongs in a population segment, the contents of the data structure is compared to segment membership criteria;

such that, it is possible to compare the contents of the data structure to segment membership criteria by;

for each distinct hash value occurring in the hash column;

storing in a distinct, contiguous portion of a filesystem file the individual identifier values of the entries of the individual identifier column corresponding to the entries of the hash column containing the distinct hash value, in the order in which the individual identifier values occur in the individual identifier column;

for each of the fact columns;

storing in a distinct, contiguous portion of a filesystem file the fact values of the entries of the fact column corresponding to the entries of the hash column containing the distinct hash value, in the order in which the fact values occur in the fact column;

receiving a request to populate a segment, the segment being defined by a segment definition containing a reference to a specialized routine for evaluating individuals for segment membership, the referenced specialized routine depending on a subset of the fact columns;

for each distinct hash value occurring in the hash column;

of the filesystem file portions stored for the distinct hash value, loading for simultaneous co-residency in memory those stored for the individual identifier column and the subset of fact columns depended on by the referenced specialized routine; and

executing the specialized routine against the loaded data to identify individuals among the population that are members of the segment.

11. The computer memories of claim 10 wherein the individual identifier column, each fact column, and the hash column are each stored an array.

12. The computer memories of claim 10 wherein the individual identifier column, each fact column, and the hash column are assembled in an in-memory table.