Modeling multi-dimensional sequence data over streams

• US 9,767,427 B2
• Filed: 04/30/2009
• Issued: 09/19/2017
• Est. Priority Date: 04/30/2009
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Liu, Mo, Wang, Song, Gupta, Chetan Kumar, Ari, Ismail, Mehta, Abhay
• Primary Examiner(s): NGUYEN, THU N
• Application Number:
  US12/432,951
• Publication Number:
  US 20100280857A1
• Time in Patent Office: 3,064 Days
• Field of Search: None
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

One embodiment is a method that builds a model of multi-dimensional sequence data in real-time with cuboids that aggregate the multi-dimensional sequence data over both patterns and dimensions. The model provides search results for a query.

Claims

1. A method comprising:

building, with a computer, a model of multi-dimensional sequence data in real-time with cuboids that aggregate the multi-dimensional sequence data over both patterns and dimensions, wherein building the model in real-time includes;

processing event instances into a base cuboid of the model as the event instances come; and

incrementally updating one or more other cuboids in the model by propagating the event instances bottom-up through a pattern hierarchy and a category hierarchy; and

providing, with a computer, search results for a query in real-time as events that are aggregated into the multi-dimensional sequence data occur.

2. The method of claim 1, wherein the multi-dimensional sequence data is a stream of radio-frequency identification (RFID) data.

3. The method of claim 1 further comprising, integrating in real-time both complex event processing (CEP) which includes detection of a sequence or a set of events that are related spatially or temporarily and online analytical processing (OLAP) techniques to provide pattern analysis functionalities.

4. The method of claim 3, wherein the pattern analysis functionalities include negation and querying over multi-dimensional spatio-temporal stream data.

5. The method of claim 1 further comprising, using online analytical processing (OLAP) techniques to analyze event patterns in real-time for the multi-dimensional sequence data.

6. The method of claim 1 further comprising, displaying search results on a display of a computer.

7. The method of claim 1, wherein the query requests tracking of radio-frequency identification (RFID) data for supply chain management of products using E-Cube.

8. The method of claim 1, wherein the model is an E-Cube that is a collection of cuboids in which the base cuboid corresponds to a most general pattern in the pattern hierarchy, and the one or more other cuboids are obtained by rolling up an event pattern or categories of an attribute.

22. The method of claim 1, wherein processing the event instances into the base cuboid comprises:

associating the event instances respectively with stacks corresponding to types of the event instances; and

linking the event instances associated a first of the stacks to the event instances associated with a second of the stacks, wherein the first stack and the second stack correspond to consecutive states in a pattern over which events are aggregated.

23. The method of claim 22, wherein linking event instances employs a pointer associated with one of the event instances and pointing to another of the event instances.

9. A tangible computer readable storage medium having instructions for causing a computer to execute a method, comprising:

building a model of multi-dimensional sequence data in real-time with cuboids that aggregate the multi-dimensional sequence data over both patterns and dimensions, wherein building the model in real-time includes;

processing event instances into a base cuboid of the model as the event instances come; and

incrementally updating one or more other cuboids in the model by propagating the event instances bottom-up through a pattern hierarchy and a category hierarchy.

10. The tangible computer readable storage medium of claim 9, wherein the model is an E-Cube that is a collection of cuboids such that the base cuboid corresponds to a most general pattern in the pattern hierarchy, and the one or more other cuboids are obtained by rolling up an event pattern or categories of an attribute.

11. The tangible computer readable storage medium of claim 9, wherein the multi-dimensional sequence data is stream data from a sensor or radio-frequency identification (RFID).

12. The tangible computer readable storage medium of claim 9 further comprising, detecting patterns in the multi-dimensional sequence data.

13. The tangible computer readable storage medium of claim 9 further comprising, querying the E-Cube to track movement and status of products in a supply chain.

14. A computer system, comprising:

a database that stores an E-Cube model of multi-dimensional sequence data in real-time with cuboids that aggregate the multi-dimensional sequence data over both patterns and dimensions, wherein the database;

processes event instances into a base cuboid of the E-Cube model as events that are aggregated into the multi-dimensional sequence data occur; and

incrementally updates one or more other cuboids in the E-Cube model by propagating the event instances bottom-up through a pattern hierarchy and a category hierarchy; and

a computer that processes a query and provides results for the query in real time as the events occur.

15. The computer system of claim 14, wherein patterns in the multi-dimensional sequence data are rolled up and aggregated in the pattern hierarchy.

16. The computer system of claim 14, wherein the E-Cube model that is a collection of cuboids such that the base cuboid corresponds to a most general pattern in the pattern hierarchy, and the one or more other cuboids are obtained by rolling up an event pattern or categories of an attribute.

17. The computer system of claim 14, wherein the computer processes the query over multi-dimensional stream data in real time.

18. The computer system of claim 14, wherein the E-Cube model integrates both complex event processing (CEP) and online analytical processing (OLAP) techniques to provide pattern analysis functionalities for queries to the database.

19. The computer system of claim 14, wherein the E-Cube model is a collection of cuboids with each cuboid having one pattern and multiple attribute dimensions, and patterns and attributes are aggregated.

20. The computer system of claim 14, wherein for each of the cuboids in the E-Cube model, all event instances in the cuboid have a same pattern and a same aggregated attribute level.

21. The computer system of claim 14, wherein processing the event instances into the base cuboid comprises:

associating the event instances respectively with stacks corresponding to types of the event instances; and

linking the event instances associated a first of the stacks to the event instances associated with a second of the stacks, wherein the first stack and the second stack correspond to consecutive states in a pattern over which events are aggregated.