Network analysis
Methods and a device for providing a compressed index of binary records. A method includes: sorting the records by content of a predetermined field of the record, indexing the field from one of the records in a line of a bitmap index, compressing bits in a column of the bitmap index by replacing a group of successive bits with a code, where the sorting includes the steps of assigning, for each record, a hash bucket of a hash table on a basis of a locality sensitive hash function on the contents of the predetermined field, so that the probability for two of the records to be assigned to the same has bucket increases with the similarity of the contents of the predetermined field between the records, and where at least one step of the computer implemented method is executed on a computer device.
1. A computer implemented method for providing a compressed index for a stream of binary records, the method comprising the steps of:
sorting the stream of binary records by content of a predetermined field of each of the binary records;
transforming the predetermined field from each of the binary records into a bitmap index, wherein the bitmap index is a matrix having a separate column corresponding to each possible value in the predetermined field;
compressing bits in a column of the bitmap index by replacing a group of successive bits with a code;
wherein the sorting comprises the step of assigning, for each binary record, a hash bucket of a hash table on a basis of a locality sensitive hash function on the contents of the predetermined field, so that the probability for two of the binary records to be assigned to the same hash bucket increases with the similarity of the contents of the predetermined field between the binary records;
wherein if a total number of binary records held in the hash table exceeds a first predetermined number, the hash bucket that is assigned greatest number of binary records is output to an output stream until the total number of binary records held in the hash table falls below a second predetermined number;
wherein if a number of binary records held in one of the hash buckets exceeds a third predetermined number, the binary records in that hash bucket are output to the output stream; and
wherein at least one step of the computer implemented method is executed on a computer device.
2. The method according to claim 1 , wherein the locality sensitive hash function is generated by:
creating a first vector with the predetermined fields as elements;
creating a second vector with random numbers of a Gaussian distribution as elements;
projecting the first vector onto a scalar by generating the dot product of the first vector and the second vector; and
determining the hash bucket on the basis of the scalar.
3. The method according to claim 2 , wherein determining the hash bucket comprises the steps of:
determining a predetermined number of scalars for the first vector on the basis of different second vectors by means of the locality sensitive hash function;
determining a sum of the scalars; and
assigning the hash bucket on the basis of a modulo division of the sum by the number of hash buckets in the hash table.
4. The method according to claim 2 , wherein the stream is a communication data stream between computers in a computer network.
5. The method according to claim 3 , wherein the stream is a communication data stream between computers in a computer network.
6. The method according to claim 1 , further comprising the steps of:
assigning, for each binary record, a scalar quantity on a basis of another locality sensitive hash function that is independent from the first locality sensitive hash function; and
sorting the binary records inside each hash bucket according to the determined quantities of the binary records.
7. The method according to claim 6 , wherein the stream is a communication data stream between computers in a computer network.
8. The method according to claim 1 , wherein the stream is a communication data stream between computers in a computer network.
9. The method according to claim 8 , wherein the predetermined field comprises a source address, a destination address, a source port, a destination port and a protocol type of a communication between computers on a network.
10. A computer readable storage medium tangibly embodying a computer readable program code having non-transitory computer readable instructions which, when implemented, cause a computer to carry out the steps of a method according to claim 1 .
11. A computer implemented method for providing a compressed index for a stream of binary records, the method comprising the steps of:
sorting the stream of binary records based on a similarity of a content of a predetermined field associated with the binary records, wherein part of the sorting is accomplished by assigning each binary record to a hash bucket of a hash table on a basis of a locality sensitive hash function on the contents of the predetermined fields, so that the probability for two of the binary records to be assigned to the same hash bucket increases with the similarity of the contents of the predetermined field between the two binary records;
transforming the predetermined field from each of the binary records into a bitmap index, wherein the bitmap index is a matrix having a separate column corresponding to each possible value in the predetermined field;
compressing bits in a column of the bitmap index by replacing a group of successive bits with a code;
wherein if a total number of binary records held in the hash table exceeds a first predetermined number, the hash bucket that is assigned greatest number of binary records is output to an output stream until the total number of binary records held in the hash table falls below a second predetermined number;
wherein if a number of binary records held in one of the hash buckets exceeds a third predetermined number, the binary records in that hash bucket are output to the output stream; and
wherein at least one step of the computer implemented method is executed on a computer device.
12. The method according to claim 11 , wherein the locality sensitive hash function is generated by:
creating a first vector with the predetermined fields as elements;
creating a second vector with random numbers of a Gaussian distribution as elements;
projecting the first vector onto a scalar by generating the dot product of the first vector and the second vector; and
determining the hash bucket on the basis of the scalar.
13. The method according to claim 12 , wherein determining the hash bucket comprises the steps of:
determining a predetermined number of scalars for the first vector on the basis of different second vectors by means of the locality sensitive hash function;
determining a sum of the scalars; and
assigning the hash bucket on the basis of a modulo division of the sum by the number of hash buckets in the hash table.
14. A computer readable storage medium tangibly embodying a computer readable program code having non-transitory computer readable instructions which, when implemented, cause a computer to carry out the steps of a method according to claim 11 .