Systems and methods of using a bitmap index to determine bicliques

1. A method comprising:

receiving, at a computing device comprising a processor, a request to determine bicliques in a graph, wherein the graph includes a first set of nodes, a second set of nodes, and a set of edges, each edge in the set of edges connecting a node in the first set of nodes to a node in the second set of nodes; and

determining at least one biclique based on querying a bitmap index representing the graph, wherein the bitmap index includes a plurality of bit strings corresponding to the first set of nodes, and wherein a value stored in a particular location in each bit string indicates whether an edge connects a first node corresponding to the bit string to a second node corresponding to the particular location.

2. The method of claim 1 , wherein the bitmap index represents data stored in a data store.

3. The method of claim 2 , wherein the data stored in the data store is determined based on event signals received from devices associated with users that accessed a website.

4. The method of claim 3 , wherein the graph includes nodes corresponding to less than all of the users.

5. The method of claim 3 , wherein the graph includes nodes corresponding to a custom segment of the users.

6. The method of claim 3 , wherein the graph corresponds to top N signals associated with the website, wherein N is an integer greater than or equal to one.

7. The method of claim 3 , wherein the event signals include at least one registration event signal.

8. The method of claim 1 , wherein one or more of the plurality of bit strings corresponds to a demographic attribute, a behavior, a brand affinity, or a combination thereof.

9. The method of claim 1 , wherein the bitmap index is distributed across a plurality of storage nodes.

10. The method of claim 9 , wherein each of the plurality of bit strings is stored as one or more distributed slices, and wherein at least a first slice of a particular bit string of the plurality of bit strings is stored in a different storage node than a second slice of the particular bit string.

11. The method of claim 1 , wherein determining the at least one biclique includes:

determining a third set of nodes;

determining a fourth set of nodes; and

outputting an indication that a combination of the third set of nodes and the fourth set of nodes corresponds to a maximal biclique of the graph.

12. The method of claim 1 , wherein querying the bitmap index includes generating a query execution plan for a query.

13. The method of claim 12 , wherein the query execution plan identifies:

one or more set operations;

that one or more first storage nodes are to send stored portions of one or more bit strings to a second storage node;

that the second storage node is to perform the one or more set operations with respect to:

the portions of the one or more bit strings received from the one or more first storage nodes; and

portions of one or more bit strings stored at the second storage node; and

that the second storage node is to concatenate results of performing the one or more set operations to generate a result bit string that indicates a result of the query.

14. An apparatus comprising:

a processor; and

a memory storing instructions executable by the processor to perform operations comprising:

receiving a request to determine bicliques in a graph, wherein the graph includes a first set of nodes, a second set of nodes, and a set of edges, each edge in the set of edges connecting a node in the first set of nodes to a node in the second set of nodes; and

determining at least one biclique based on querying a bitmap index representing the graph, wherein the bitmap index includes a plurality of bit strings corresponding to the first set of nodes, and wherein a value stored in a particular location in each bit string indicates whether an edge connects a first node corresponding to the bit string to a second node corresponding to the particular location.

15. The apparatus of claim 14 , wherein the bitmap index represents data stored in a data store.

16. The apparatus of claim 15 , wherein the data stored in the data store represents users that accessed a website, wherein the biclique corresponds to a target segment, the target segment corresponding to fewer than all of the users that accessed the website.

17. The apparatus of claim 14 , wherein the bitmap index is distributed across a plurality of storage nodes.

18. The apparatus of claim 17 , wherein each of the plurality of bit strings is stored as one or more distributed slices, and wherein at least a first slice of a particular bit string is stored in a different storage node than a second slice of the particular bit string.

19. A computer readable storage device storing instructions that, when executed, cause a computer to perform operations comprising:

receiving, at a first storage node, a request to determine bicliques in a graph, wherein the graph includes a first set of nodes, a second set of nodes, and a set of edges, each edge in the set of edges connecting a node in the first set of nodes to a node in the second set of nodes; and

determining at least one biclique based on querying a bitmap index representing the graph, wherein the bitmap index includes a plurality of bit strings corresponding to the first set of nodes, and wherein a value stored in a particular location in each bit string indicates whether an edge connects a first node corresponding to the bit string to a second node corresponding to the particular location.

20. The computer readable storage device of claim 19 , wherein the bitmap index is generated by a measurement system, and wherein the graph corresponds to at least one of:

less than all users tracked by the measurement system,

a custom segment of the users tracked by the measurement system, or

top N signals tracked by the measurement system, wherein N is an integer greater than or equal to one.