# US 2020/0401589 A1 · Systems and methods for bitmap filtering when performing funnel queries

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0401589 A1
- Document ID: US20200401589A1
- Status: Published application
- Kind: A1
- Application number: 16/448,394
- Filed: 2019-06-21
- Published: 2020-12-24
- Earliest claimed: 2019-06-21
- Assignees: Shopify Inc.
- Applicants: Shopify Inc.
- Inventors: MIKHAL ARKHANGORODSKY; MOHAMMAD ZEESHAN QURESHI
- Web page: https://patentgrep.com/patent/US20200401589A1

## CPC

- G06F 16/2474: {Sequence data queries, e.g. querying versioned data}
- G06F 16/953: Querying, e.g. by the use of web search engines
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Data may be queried and analyzed in order to draw insights. One type of data query that may be performed is a funnel query. A funnel query is a query characterized by a sequence of events, e.g.: “In the last N days, how many unique users performed event A, then event B, and then event C”. Systems and methods for performing funnel queries are provided herein. In some embodiments, the speed at which a computer can answer a funnel query may be increased. In some embodiments, a bitmap is used to eliminate one or more sequences of events that would otherwise need to be traversed during the funnel query. In some embodiments, a sequence of events is stored across multiple data partitions, each data partition covering a different period of time.

## Claims

### Claim 1

A computer-implemented method comprising:
accessing data stored in memory, the data stored as a plurality of sequences, wherein each sequence of the plurality of sequences corresponds to a respective user, and each sequence of the plurality of sequences records a respective set of events that were performed by the respective user;
performing a query on the data to identify which users performed a series of particular events, the series of particular events being defined by the query, and the series of particular events including a target event;
wherein performing the query includes:
obtaining information that indicates, for each sequence of the plurality of sequences, whether or not the sequence includes the target event;
using the information to identify a subset of the plurality of sequences for which each sequence of the subset of the plurality of sequences includes the target event; and
searching for the series of particular events in each sequence of the subset of the plurality of sequences.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the method further comprises generating the information prior to performing the query, and wherein the information is generated by performing operations including:
searching each sequence of the plurality of sequences for the target event; and
for each sequence of the plurality of sequences: recording whether or not the target event was found in the sequence.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein searching for the series of particular events in the subset of the sequences includes, for each sequence of the subset of the sequences:
traversing the sequence event-by-event in time consecutive order of the events, the traversing including first searching for a first event of the series of the events, and if the first event is found, then continuing the traversing searching next for a second event of the series of events.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, further comprising:
counting how many sequences of the subset of sequences includes the series of particular events; and
counting how many sequences of the subset of the sequences includes a first event of the series of particular events and not a subsequent second event of the series of particular events.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein the target event is a first event of the series of particular events.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein the target event is a first target event, wherein the series of particular events also includes a second target event, wherein the information is a first bitmap that indicates, for each sequence of the plurality of sequences, whether or not the sequence includes the first target event, wherein a second bitmap is obtained that indicates, for each sequence of the plurality of sequences, whether or not the sequence includes the second target event, wherein the second bitmap is also used to identify the subset of the plurality of sequences, and wherein each sequence of the subset of the plurality of sequences includes both the first target event and the second target event.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, further comprising:
receiving x queries over time;
identifying a candidate event that is present in each of at least y≤x of the x queries; and
in response to the candidate event being present in each of at least y of the x queries: searching each sequence of the plurality of sequences for the candidate event and, for each sequence of the plurality of sequences, recording whether or not the candidate event was found in the sequence.

### Claim 8 (depends on 7)

The computer-implemented method of claim 7, wherein the candidate event is always a first event in each of the queries in which the candidate event is present.

### Claim 9 (depends on 1)

The computer-implemented method of claim 1, wherein for each sequence of the plurality of sequences, the respective set of events recorded by the sequence are stored consecutively in order of time, and the series of particular events are also consecutive in order of time.

### Claim 10 (depends on 9)

The computer-implemented method of claim 9, wherein each sequence of the plurality of sequences corresponds to a different user, and wherein each event is recorded as one or more numerical values.

### Claim 11

A system comprising:
a memory to store data, the data stored as a plurality of sequences, wherein each sequence of the plurality of sequences corresponds to a respective user, and each sequence of the plurality of sequences records a respective set of events that were performed by the respective user;
a processor to perform a query on the data to identify which users performed a series of particular events, the series of particular events being defined by the query, and the series of particular events including a target event;
wherein the processor is to perform the query by performing operations including:
obtaining information that indicates, for each sequence of the plurality of sequences, whether or not the sequence includes the target event;
using the information to identify a subset of the plurality of sequences for which each sequence of the subset of the plurality of sequences includes the target event; and
searching for the series of particular events in each sequence of the subset of the plurality of sequences.

### Claim 12 (depends on 11)

The system of claim 11, wherein the processor is further to: generate the information prior to performing the query; and wherein the processor is to generate the information by performing operations including:
searching each sequence of the plurality of sequences for the target event; and
for each sequence of the plurality of sequences: recording whether or not the target event was found in the sequence.

### Claim 13 (depends on 11)

The system of claim 11, wherein searching for the series of particular events in the subset of the sequences includes, for each sequence of the subset of the sequences:
traversing the sequence event-by-event in time consecutive order of the events, the traversing including first searching for a first event of the series of the events, and if the first event is found, then continuing the traversing searching next for a second event of the series of events.

### Claim 14 (depends on 11)

The system of claim 11, wherein the processor is further to:
count how many sequences of the subset of sequences includes the series of particular events; and
count how many sequences of the subset of the sequences includes a first event of the series of particular events and not a subsequent second event of the series of particular events.

### Claim 15 (depends on 11)

The system of claim 11, wherein the target event is a first event of the series of particular events.

### Claim 16 (depends on 11)

The system of claim 11, wherein the target event is a first target event, wherein the series of particular events also includes a second target event, wherein the information is a first bitmap that indicates, for each sequence of the plurality of sequences, whether or not the sequence includes the first target event, wherein the processor is to obtain a second bitmap that indicates, for each sequence of the plurality of sequences, whether or not the sequence includes the second target event, wherein the second bitmap is also used to identify the subset of the plurality of sequences, and wherein each sequence of the subset of the plurality of sequences includes both the first target event and the second target event.

### Claim 17 (depends on 11)

The system of claim 11, wherein the processor is further to:
receive x queries over time;
identify a candidate event that is present in each of at least y≤x of the x queries; and
in response to the candidate event being present in each of at least y of the x queries: search each sequence of the plurality of sequences for the candidate event and, for each sequence of the plurality of sequences, record whether or not the candidate event was found in the sequence.

### Claim 18 (depends on 17)

The system of claim 17, wherein the candidate event is always a first event in each of the queries in which the candidate event is present.

### Claim 19 (depends on 11)

The system of claim 11, wherein for each sequence of the plurality of sequences, the respective set of events recorded by the sequence are stored consecutively in order of time, and the series of particular events are also consecutive in order of time.

### Claim 20 (depends on 19)

The system of claim 19, wherein each sequence of the plurality of sequences corresponds to a different user, and wherein each event is recorded as one or more numerical values.