Extracting and visualizing branching patterns from temporal event sequences

Patent metadata

Field	Value
Publication number	US-10466869-B2
Application number	US-201715583275-A
Country	US
Kind code	B2
Filing date	May 1, 2017
Priority date	May 1, 2017
Publication date	Nov 5, 2019
Grant date	Nov 5, 2019

Abstract

The present disclosure is directed toward systems and methods for extracting a branching pattern from a dataset of event sequences. For example, one or more embodiments described herein extract a branching pattern from a dataset that illustrates patterns of events within the dataset. Additionally, one or more embodiments described herein generate one or more interactive visualizations based on the extracted branching pattern that enable an analyst to query specific portions of the extracted branching pattern.

First claim

What is claimed is:

1. In a digital environment for analyzing event sequence data, a method of identifying branching patterns within the event sequence data comprising:
accessing a dataset comprising a plurality of event sequences associated with a plurality of users, each of the plurality of event sequences comprising one or more events, wherein each of the one or more events comprises a single user interaction in connection with electronic content;
analyzing a plurality of event metrics with respect to the one or more events of the plurality of event sequences to identify a first key event;
extracting a branching pattern from the dataset, wherein the branching pattern comprises one or more flow paths comprising the first key event identified from the one or more events of the plurality of event sequences within the dataset; and
providing an interactive visualization of the extracted branching pattern, the interactive visualization comprising display elements corresponding to one or more key events connecting the one or more flow paths, the one or more key events comprising the first key event.

2. The method as recited in claim 1 , wherein analyzing the plurality of event metrics with respect to the one or more events to identify the first key event comprises:
applying a ranking function that utilizes the plurality of event metrics to each event of the one or more events of the plurality of event sequences;
identifying, based on the ranking function, a top-ranked event from the one or more events; and
labeling the top-ranked event as the first key event.

3. The method as recited in claim 2 , wherein extracting the branching pattern further comprises:
dividing the plurality of event sequences by:
assigning event sequences from the plurality of event sequences that comprise at least on instance of the first key event to a first group event sequences; and
assigning one or more event sequences from the plurality of event sequences not assigned to the first group of event sequences to a second group of event sequences.

4. The method as recited in claim 3 , wherein extracting the branching pattern further comprises trimming each of the event sequences in the first group of event sequences by removing events in each of the event sequences from a beginning event to the first instance of the first key event to generate trimmed event sequences of the first group of event sequences.

5. The method as recited in claim 4 , further comprising analyzing the plurality of event metrics with respect to one or more events of the trimmed event sequences of the first group of event sequences to identify a second key event.

6. The method as recited in claim 4 , wherein:
trimming each of the event sequences in the first group of event sequences is based on a minimum support threshold being satisfied; and
the minimum support threshold comprises a minimum number of event sequences in the first group of event sequences that contain the top-ranked event.

7. The method as recited in claim 1 , wherein analyzing the plurality of event metrics comprises utilizing two or more of:
an event sequence occurrence frequency algorithm;
a head of sequence occurrence frequency algorithm;
an average index function;
a median index function,
an average timestamp function; or
a median timestamp function.

8. The method as recited in claim 1 , wherein providing the interactive visualization of the extracted branching pattern comprises providing one of an interactive icicle plot, an interactive node-link visualization, or an interactive hybrid of both the icicle plot and the node-link visualization.

9. The method as recited in claim 8 , further comprising:
receiving a user interaction with respect a first display element corresponding to the first key event of the display elements corresponding to one or more key events of the interactive visualization; and
providing, in response to the received user interaction of the first display element, additional information about the first key event or a flow path corresponding to the first key event within a branching pattern.

10. The method as recited in claim 8 , wherein the interactive icicle plot comprises the display elements corresponding to one or more key events, each of the display elements displaying a key event of the one or more key events, and wherein a width of each of the display elements is sized to indicate a volume of the flow path across an associated key event.

11. The method as recited in claim 8 , wherein:
the interactive node-link visualization comprises a tree-like structure of nodes, each node displaying a key event and connected by links corresponding to the one or more flow paths;
the links within the one or more flow paths each comprise a width that indicates a volume of event sequences that pass through that link within the flow path; and
the interactive hybrid of both the icicle plot and the node-link visualization comprises the node-link visualization overlaid on the icicle plot.

12. The method as recited in claim 1 , wherein the first key event comprises a statistically significant event across the plurality of users within the dataset comprising the plurality of event sequences.

13. The method as recited in claim 8 , wherein the first key event is a single event from an event sequence comprising a plurality of individual events, and wherein the first key event is a single user interaction in connection with electronic content.

14. A system comprising:
a non-transitory memory comprising:
a dataset comprising a plurality of event sequences associated with a plurality of users, each of the plurality of event sequences comprises one or more events, wherein each event of the one or more events comprises a single user interaction in connection with electronic content; and
computer readable instructions that, when executed by one or more computer processors, cause the system to:
utilize a rank-divide-trim procedure to identify a first key event based on a plurality of event metrics with respect to the one or more events of the plurality of event sequences;
extract a branching pattern from the dataset based on one or more key events to generate one or more flow paths with respect to the one or more key events, the one or more key events comprising the first key event; and
provide an interactive visualization of the extracted branching pattern, the interactive visualization comprising nodes corresponding to the one or more key events connected by the one or more generated flow paths.

15. The system as recited in claim 14 , wherein the rank-divide-trim procedure further comprises:
applying a ranking function utilizing the plurality of event metrics to each event of the one or more events of the plurality of event sequences;
identifying, based on the ranking function, a top-ranked event from the one or more events; and
labeling the top-ranked event as the first key event.

16. The system as recited in claim 15 , wherein the rank-divide-trim procedure further comprises:
dividing the plurality of sequences by:
assigning event sequences from the plurality of event sequences that comprise at least one instance of the first key event to a first group event sequences; and
assigning one or more event sequences from the plurality of event sequences not assigned to the first group of event sequences to a second group of event sequences.

17. The system as recited in claim 16 , wherein the rank-divide-trim procedure further comprises trimming each of the event sequences in the first group of event sequences by removing

Assignees

• Adobe Inc

Inventors

• Liu Zhicheng

Classifications

• G06T11/26 Primary

  Drawing of charts or graphs · CPC title

• G06F3/0482 Primary

  Interaction with lists of selectable items, e.g. menus · CPC title

• G06T2200/24

  involving graphical user interfaces [GUIs] · CPC title

• G06T11/60

  Creating or editing images; Combining images with text · CPC title

• G06F16/26

  Visual data mining; Browsing structured data · CPC title