Dynamic updating of a force approximation data model
Inventors
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-11087048-B2
Publication Date
2021-08-10
Expiration Date
Abstract
One example method of operation may include creating a force approximation of a number of nodes in a defined space at an initial time (t0), the force approximation being based on a data realization simulation model of an n-body simulation, where n is an integer greater than one. The method may also include determining initial displacement changes of one or more of the nodes within the defined space has occurred in the force approximation, summing the initial displacement changes of the one or more of the nodes to create a summed total displacement, creating an initial displacement threshold (Td) based on the summed total displacement. At a later time (t1), determining additional displacement changes of one or more of the nodes have occurred, summing the additional displacement changes of the one or more of the nodes to create a new summed total displacement, comparing the new summed total displacement to the summed total displacement, and determining whether to create a new force approximation based on the comparison of the new summed total displacement to the summed total displacement.
Core Innovation
The invention creates a force approximation of a plurality of nodes in a defined space at an initial time (t0) using a data realization simulation model of a n-body simulation. It determines initial displacement changes of one or more of the plurality of nodes within the defined space, sums the initial displacement changes to create a summed total displacement, and creates an initial displacement threshold (Td) based on the summed total displacement.
At a later time (t1), the invention determines additional displacement changes of one or more of the plurality of nodes, sums the additional displacement changes to create a new summed total displacement, and compares the new summed total displacement to the summed total displacement. The determination of whether to create a new force approximation is based on the comparison and on comparing the new summed total displacement to the initial displacement threshold (Td).
In implementations with threshold updating, when the new summed total displacement is greater than or equal to the initial displacement threshold, the invention creates a new force approximation of the plurality of nodes, updates the initial displacement threshold to equal the new summed total displacement, and resets a current summed total value of displacement to zero. In further implementations, the invention updates a new displacement threshold value based on summed displacement over continuing time intervals.
Claims Coverage
The independent claims cover a method, an apparatus, and a non-transitory computer readable storage medium that dynamically decide whether to create a new force approximation for a plurality of nodes by monitoring summed displacement changes and comparing summed totals against an initial displacement threshold (Td). Across the independent claims, the inventive logic includes multiple summed displacement totals, an initial displacement threshold (Td), and a comparison-driven decision to create a new force approximation.
Create initial force approximation and displacement-threshold from summed displacement
Creating a force approximation of a plurality of nodes in a defined space at an initial time (t0) based on a data realization simulation model of a n-body simulation; determining initial displacement changes; summing the initial displacement changes to create a summed total displacement; and creating an initial displacement threshold (Td) based on the summed total displacement.
Compare new summed displacement to prior totals and decide whether to recreate the approximation
At a later time (t1), determining additional displacement changes; summing the additional displacement changes to create a new summed total displacement; comparing the new summed total displacement to the summed total displacement; and determining whether to create a new force approximation based on the comparison.
Threshold-conditioned recreation when new summed displacement meets or exceeds Td
Comparing the new summed total displacement to the summed total displacement by determining whether the new summed total displacement is greater than or equal to the initial displacement threshold (Td), and based on the determination, creating a new force approximation of the plurality of nodes.
State update by updating Td and resetting current summed displacement
When the new summed total displacement is greater than or equal to the initial displacement threshold, creating a new force approximation and updating the initial displacement threshold to equal the new summed total displacement and resetting the current summed total value of displacement to zero.
Force approximation implemented using Barnes-Hut
The force approximation uses a Barnes-Hut approximation.
The independent claims consistently require forming an initial force approximation, computing a summed total displacement from node displacement changes, deriving an initial displacement threshold (Td), and later computing a new summed total displacement to compare against prior totals and the threshold so the system determines whether to create a new force approximation. Dependent refinements include a greater-than-or-equal threshold trigger, optional updating of Td with resetting of summed displacement, and specifying the force approximation as Barnes-Hut.
Stated Advantages
Reduces unnecessary quadtree/force recalculations by selectively updating the force approximation based on summed node displacement changes.
Reports graph layout runtime reductions versus standard Barnes-Hut (up to ~51% with median ~18%, and worst ~6%).
Reports runtime reductions versus a scheduled ⌈5·log(i)⌉ update scheme (as stated in the provided summary text).
Documented Applications
Use in graph datasets and related simulation domains for dynamic force approximation in n-body simulation and force-directed graph layout contexts (as stated in the provided summary text).
Use on a server/computing node implementing the dynamic approximation model and decision logic (as stated in the provided summary text).
Referenced use with datasets including KONECT and SUITESPARSE (as stated in the provided summary text).
Interested in licensing this patent?