发明名称 |
Platform for continuous graph update and computation |
摘要 |
A continuous stream data (e.g., messages, tweets) is received by ingest nodes of a platform. The ingest nodes may analyze the data to create a transaction of graph updates, assign a sequence number to the transaction, and distribute the graph updates with the sequence number to graph nodes of the platform. The graph nodes may store graph updates from ingest nodes, and then the ingest nodes may report graph update progresses in a progress table. A snapshot may be taken based on the progress table, and then graph-mining computation may be implemented. Tolerate failures and decaying may be supported and incremental expansion may be allowed to cope with increasing update rates and computation needs. |
申请公布号 |
US9589069(B2) |
申请公布日期 |
2017.03.07 |
申请号 |
US201615003266 |
申请日期 |
2016.01.21 |
申请人 |
Microsoft Technology Licensing, LLC |
发明人 |
Yang Fan;Kyrola Aapo;Weng Xuetian;Cheng Raymond;Wu Ming;Hong Ji;Zhou Lidong;Miao Youshan |
分类号 |
G06F17/30;G06F11/14 |
主分类号 |
G06F17/30 |
代理机构 |
Lee & Hayes, PLLC |
代理人 |
Swain Sandy;Minhas Micky;Lee & Hayes, PLLC |
主权项 |
1. A system comprising:
one or more processors; memory communicatively coupled to the one or more processors; one or more ingest nodes configured to, when executed by the one or more processors, perform operations comprising:
analyzing a record of a continuous data stream;generating one or more graph-update operations based on the record;assigning a sequence number to the one or more graph-update operations; anddistributing the one or more graph-update operations to one or more graph nodes; a global progress table stored in the memory and configured to record sequence numbers assigned to the one or more graph-update operations, the global progress table comprising a vector including the sequence number and another sequence number, the sequence number and the other sequence number being assigned by different ingest nodes of the one or more ingest nodes; a snapshooter stored in the memory and configured to, when executed by the one or more processors, define an end of an epoch based on the global progress table; and the one or more graph nodes configured to, when executed by the one or more processors, perform operations comprising:
storing the one or more graph-update operations in a storage layer of the one or more graph nodes; andproducing a graph structure snapshot by executing the one or more graph-update operations that are stored in the storage layer and are within the epoch. |
地址 |
Redmond WA US |