Fast distributed database frequency summarization

摘要

A mechanism is provided for computing the frequency packets in network devices. Respective packets are associated with entities in a vector, where each of the entities is mapped to corresponding ones of the respective packets, and the entities correspond to computers. Upon a network device receiving the respective packets, a count is individually increased for the respective packets in the vector respectively mapped to the entities, and computing a matrix vector product of a matrix A and the vector. The matrix A is a product of at least a first matrix and a second matrix. The first matrix includes rows and columns where each of the rows has a single random location with a one value and remaining locations with zero values. The matrix vector product is transmitted to a centralized computer for aggregating with other matrix vector products.

主权项

1. An apparatus for computing a frequency of packets in network devices, comprising:
memory comprising computer-executable instructions; and a processor executing the computer-executable instructions, the computer-executable instructions, when executed by the processor, cause the processor to perform operations comprising: associating respective packets with a plurality of entities in a vector, each of the plurality of entities being mapped to corresponding ones of the respective packets and corresponding to a plurality of computers; upon at least one network device receiving the respective packets, individually increasing a count for the respective packets mapped to the plurality of entities in the vector; computing a matrix vector product of a matrix A and the vector, the matrix A being a product of at least a first matrix and a second matrix, the first matrix comprising rows and columns where each of the rows has a single random location with a one value and remaining locations with zero values; and transmitting the matrix vector product to a centralized computer for aggregation with other matrix vector products; wherein coordinates of the vector and an approximation vector are identical such that each has identical ones of the plurality of entities mapped at corresponding coordinates.