Dynamic interaction graphs with probabilistic edge decay
US10249070B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 11, 2018 |
| Grant date | Apr 2, 2019 |
| Priority date | — |
| Expiry date | Apr 11, 2038 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F18/29
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A computer-implemented method, according to one embodiment, includes: generating two or more sample graphs by sampling edges of a current snapshot of a dynamic graph, generating two or more partial results by executing an algorithm on the two or more sample graphs, combining the partial results into a final result, and incrementally maintaining the sample graphs. Edges included in the current snapshot of a dynamic graph and which were added to the dynamic graph in a most recent update thereto are included in each of the generated two or more sample graphs. Moreover, incrementally maintaining the sample graphs includes: subsampling each of the edges of each of the sample graphs at a given time by applying a Bernoulli trial, and combining a result of the subsampling with new edges received in a batch corresponding to the given time to form new sample graphs.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.