Extracting and visualizing branching patterns from temporal event sequences

Patent metadata

Field	Value
Publication number	US-2018314700-A1
Application number	US-201715583275-A
Country	US
Kind code	A1
Filing date	May 1, 2017
Priority date	May 1, 2017
Publication date	Nov 1, 2018
Grant date	—

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, each event sequence comprising one or more events; extracting a branching pattern from the dataset, wherein the branching pattern comprises one or more flow paths comprising one or more key events from 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 the one or more key events across the one or more flow paths.

2 . The method as recited in claim 1 , wherein extracting the branching pattern comprises:
applying a ranking function to the one or more events in each event sequence from the plurality of event sequences; identifying, based on the ranking function, a first top-ranked event; and labeling the first top-ranked event as a first key event within the branching pattern.

3 . The method as recited in claim 2 , wherein extracting the branching pattern further comprises:
dividing the plurality of sequences into a first group of event sequences that include the first top-ranked event and a second group of event sequences that do not include the first top-ranked event; for the first group, trimming each event sequence in the first group from a beginning event within the event sequence to a first occurrence of the first top-ranked event within the event sequence to generate one or more trimmed sequences of the first group; applying the ranking function to the one or more trimmed sequences of the first group to identify a second top-ranked event; and labeling the second top-ranked event as a second key event within the branching pattern.

4 . The method as recited in claim 3 , wherein extracting the branching pattern further comprises:
for the second group of event sequences that do not include the first top-ranked event, applying a ranking function to each event sequence in the second group; identifying, based on the ranking function, a third top-ranked event; labeling the third top-ranked event as a third key event within the branching pattern; and for the second group, trimming each event sequence in the second group from a beginning event within the event sequence to a first occurrence of the third top-ranked event within the event sequence to generate one or more trimmed sequences of the second group.

5 . The method as recited in claim 2 , wherein applying the ranking function to the one or more events in each sequence in the dataset comprises applying one of: a 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.

6 . The method as recited in claim 4 , wherein:
trimming each event sequence in the first group is in response to determining that a minimum support is met; and trimming each event sequence in the second group is in response to determining that the minimum support is met.

7 . The method as recited in claim 6 , further comprising:
determining a number of event sequences in the first group that include the first top-ranked event; wherein the minimum support is met for the first group when the number of event sequences in the first group that include the first top-ranked event is greater than the minimum support; determining a number of event sequences in the second group that include the third top-ranked event; and wherein the minimum support is met for the second group when the number of event sequences in the second group that include the third top-ranked event is greater than the minimum support.

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 to the interactive visualization; and providing, in response to the received user interaction, additional information about a key event or flow path within a branching pattern.

10 . The method as recited in claim 8 , wherein the interactive icicle plot comprises a plurality of display elements, each of the plurality of display elements associated with a key event, and wherein each of the plurality of display elements is sized to indicate a volume of the flow path across the associated key event.

11 . The method as recited in claim 8 , wherein the interactive node-link visualization comprises a plurality of nodes, each node corresponding to a key event and connected by links corresponding to the one or more flow paths.

12 . The method as recited in claim 11 , wherein 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.

13 . The method as recited in claim 8 , wherein the interactive hybrid of both the icicle plot and the node-link visualization comprises the node-link visualization overlaid on the icicle plot.

14 . A system comprising:
a non-transitory memory comprising: a data storage comprising a dataset comprising a plurality of event sequences, each event sequence comprises one or more events; and computer readable instructions that, when executed by one or more computer processors, cause the system to: extract a branching pattern from the dataset utilizing a rank-divide-trim procedure that identifies one or more key events and one or more flow paths across one or more key events within the plurality of event sequences within the dataset; 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 links to form the one or more flow paths.

15 . The system as recited in claim 14 , wherein the rank-divide-trim procedure comprises:
applying a ranking function to the one or more events in each event sequence in the dataset; identifying, based on the ranking function, a first top-ranked event; and labeling the first top ranked event as a first key event within the branching pattern.

16 . The system as recited in claim 15 , wherein extracting the branching pattern further comprises:
dividing, based on a determination of whether a given event sequence of the plurality of event sequences includes the first top-ranked event, the plurality of sequences into a first group of event sequences that include the first top-ranked event and a second group of event sequences that do not include the first top-ranked event; for the first group, trimming each event sequence in the first group from a beginning event within the event sequence to a first occurrence of the top-ranked event within the event sequence to generate one or more trimmed sequences of the first group; applying the ranking function to the one or more trimmed sequences to identify a second top-ranked event; and labeling the second top-ranked event as a second key event within the branching pattern.

17 . The system as recited in claim 16 , wherein providing the interactive visualization of the extracted branching pattern comprises providing one of an interactive icicle plot, an interactive node-link

Assignees

• Adobe Systems 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

• G06F16/26

  Visual data mining; Browsing structured data · CPC title

• G06T11/60

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

• G06T2200/24

  involving graphical user interfaces [GUIs] · CPC title