ADAPTIVE TREE STRUCTURE FOR VISUALIZING DATA

• US 20120137308A1
• Filed: 11/30/2010
• Published: 05/31/2012
• Est. Priority Date: 11/30/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Agarwal, Mayank, Dadiomov, Alexander, Ji, Xinhua
• Granted Patent: US 8,595,750 B2
• Time in Patent Office: Days
• US Class Current: 719/318
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

One or more systems and/or techniques for generating an adaptive tree structure for storing event data based upon data density of events are disclosed. In particular, the adaptive tree structure may comprise one or more levels of nodes, where a level may correspond to a resolution of events. Nodes may correspond to particular time spans over which event data was recorded. A node may be designated as a raw node comprising raw events or a summary node comprising summary events based upon the number of events occurring within a time span covered by the node.

Claims

1. A method for generating an adaptive tree structure based upon data density of an event dataset comprising a plurality of raw events, comprising:

specifying a first level within an adaptive tree structure, the first level comprising a root node assigned a threshold number of summary events from an event dataset, a time span of the root node corresponding to a total time span of the event dataset, the root node designated as a summary node; and

specifying one or more additional levels within the adaptive tree structure, the specifying comprising;

for a current level of the adaptive tree structure;

determining whether a previous level immediately before the current level comprises one or more summary nodes; and

if the previous level comprises one or more summary nodes, then for respective summary nodes;

generating a predetermined number of child nodes for a summary node, a time span of a child node corresponding to fraction of a time span of the summary node; and

for respective child nodes;

 

if a number of raw events within the event dataset covered by a time span of a child node is less than or equal to the threshold number, then designating the child node as a raw node and assigning the raw events to the raw node, else designating the child node as a summary node and assigning a number of summary events derived from raw events within the event dataset covered by the time span of the child node, the number of summary events equal to the threshold number.

2. The method of claim 1, comprising:

receiving a requested time span;

calculating a level (L) corresponding to;

3. The method of claim 1, the assigning a number of summary events comprising:

aggregating raw events as summary events for the summary node.

4. The method of claim 1, at least one summary event indicative of two or more raw events.

5. The method of claim 2, the node data derived from no more than two nodes.

6. The method of claim 2, comprising:

presenting a timeline comprising event data represented by the node data.

7. The method of claim 6, comprising:

receiving user input corresponding to a zoom action within the timeline, the user input comprising a second requested time span different than the requested time span; and

determining second node data within the adaptive tree structure corresponding to the second requested time span.

8. The method of claim 6, comprising:

receiving user input corresponding to a scroll action within the timeline, the user input comprising a second requested time span different than the requested time span; and

determining second node data within the adaptive tree structure corresponding to the second requested time span.

9. The method of claim 2, comprising:

if the node data corresponds to a raw node, then;

aggregating raw events of a raw node into summary events; and

storing the summary events within the node data.

10. The method of claim 1, comprising:

determining the threshold number for events based upon a desired user interface draw time of a timeline.

11. The method of claim 1, respective time spans of child nodes of a summary node comprising equal lengths, where a sum of respective time spans of child nodes equals a time span of the summary node.

12. A system for generating an adaptive tree structure based upon density of an event dataset comprising a plurality of raw events, comprising:

an adaptive tree generator configured to;

specify a first level within an adaptive tree structure, the first level comprising a root node assigned a threshold number of summary events from an event dataset, a time span of the root node corresponding to a total time span of the event dataset, the root node designated as a summary node; and

specify one or more additional levels within the adaptive tree structure, the specifying comprising;

for a current level of the adaptive tree structure;

determine whether a previous level immediately before the current level comprises one or more summary nodes; and

if the previous level comprises one or more summary nodes, then for respective summary nodes;

generate a predetermined number of child nodes for a summary node, a time span of a child node corresponding to fraction of a time span of the summary node; and

for respective child nodes;

 

if a number of raw events within the event dataset covered by a time span of a child node is less than or equal to the threshold number, then designate the child node as a raw node and assigning the raw events to the raw node, else designate the child node as a summary node and assigning a number of summary events derived from raw events within the event dataset covered by the time span of the child node, the number of summary events equal to the threshold number.

13. The system of claim 12, comprising:

a node extractor configured to;

receive a requested time span;

calculate a level (L) corresponding to;

14. The system of claim 13, comprising:

a timeline presentation component configured to;

present a timeline of event data represented by the node data.

15. The system of claim 14, the timeline presentation component configured to:

update the timeline with second event data represented by second node data determined by the node extractor in response to user input corresponding to at least one of a scroll action and a zoom action within the timeline.

16. The system of claim 13, the node extractor configured to:

if the node data corresponds to a raw node, then;

aggregate raw events of a raw node into summary events; and

store the summary events within the node data.

17. A method for determining node data corresponding to events, comprising:

receiving a requested time span;

calculating a level (L) corresponding to;

18. The method of claim 17, comprising:

presenting a timeline comprising event data represented by the node data.

19. The method of claim 18, comprising:

receiving user input corresponding to at least one of a zoom action and a scroll action within the timeline, the user input comprising a second requested time span different than the requested time span; and

determining second node data within the adaptive tree structure corresponding to the second requested time span.

20. The method of claim 17, comprising:

if the node data corresponds to a raw node, then;

aggregating raw events of a raw node into summary events; and

storing the summary events within the node data.