Distributed kernel density estimation
AssigneeMicrosoft Corporation
InventorsYusuo Hu, Jian-guang Lou, Jiang Li
Life of this patent
Estimating the term…
Abstract
The described systems and methods can be used to estimate the global distributed kernel density without prior information of data using a gossip based method. In the gossip based method, a node in a distributed network periodically selects and exchanges kernels with a random node in the network. After exchanging, both the initiating and the target node use the received kernels to update their local estimates. In addition, a data reduction method can be used to optimize the size of the kernel set at each node.
Claims20
A system comprising:
- a distributed network;
- and
- plurality of node devices connected to the distributed network, each node device having local measurements that are independent and identical distributed samples of a random variable, wherein each node device uses gossip-based distributed kernel density estimation to estimate an unknown distribution from the distributed samples using kernel density estimation comprising:
- obtaining the random values with an unknown distribution from each of the node devices;
- maintaining a local kernel set of each of the node devices;
- selecting from the plurality of node devices, a random node as a gossip target node;
- exchanging kernels from the gossip target node with each one of the remaining node devices;
- merging kernels with target node and kernels of each of the remaining nodes devices;
- determining whether the merged kernels exceed the resources of a particular node device of the remaining node devices;
- and
- performing a data reduction if the merged kernels exceed the resources of the particular node device.
A method to estimate kernel density comprising of:
- obtaining a sample random value with an unknown distribution from each node of a plurality of nodes in a computing system;
- maintaining a local kernel set of each of the nodes;
- selecting from the plurality of nodes, a random node as a gossip target node;
- exchanging kernels from the gossip target node with each one of the remaining nodes;
- merging kernels with target node and kernels of each of the remaining nodes;
- determining whether the merged kernels exceed the resources of a particular node of the remaining nodes;
- and
- performing a data reduction, if the merged kernels exceed the resources of the particular node.
A method of data reduction in a computing system comprising of:
- receiving a value representing a kernel set of a number of kernels in a node of the computing system;
- receiving a value representing a value of compressed kernel set of the node;
- determining whether the value representing the kernel set is greater than the value of the compressed kernel set;
- determining two kernels of the node form the kernel set if the value representing the kernel set is greater than the value of the compressed kernel set, wherein the centers of the two determined kernels are selected having minimal distance between one another;
- merging the two kernels into a new kernel;
- removing the two kernels form the kernel set;
- and
- creating a kernel set.
Dependencies are inferred from the claim text.