Method and system for probabilistic processing of data using a bit matrix, tuples, and hash values

摘要

A method for probabilistic processing of data, wherein the data is provided in form of a data set S composed of multidimensional n-tuples of the form (x1, . . . , xn), is characterized in that an n-dimensional data structure is generated by way of providing a bit matrix, providing a number K of independent hash functions Hk that are employed in order to address the bits in the matrix, and inserting the n-tuples (x1, . . . , xn) into the bit matrix by computing the hash values Hk(x) for all values x of the n-tuple for each of the number K of independent hash functions Hk, and by setting the resulting bits [Hk(x1), . . . , Hk(xn)] of the matrix. Furthermore, a respective system is disclosed.

主权项

1. A method for probabilistic processing of data to be carried out by a processing element in communication with a storing element and an input/output element for receiving said data, wherein said data is provided in form of a data set S composed of multidimensional n-tuples of the form (x1, . . . , xn), the processing element being provided with instructions sufficient to cause the processing element, upon execution of said instructions, to:
generating an n-dimensional data structure by way of
providing a bit matrix,providing a number K of independent hash functions Hk that are employed in order to address the bits in said matrix, andinserting said n-tuples (x1, . . . , xn) into said bit matrix by computing the hash values Hk(x) for all values x of said n-tuple for each of said number K of independent hash functions Hk, and by setting the resulting bits [Hk(x1), . . . , Hk(xn)] of said matrix, wherein said bit matrix includes a number M of rows and a number N of columns, wherein a simple wildcard query, of an n-tuple including a determined value Xi in one dimension only, is performed by way of
computing the hash values Hk(xi) for the determined value xi of said n-tuple for each of said number K of independent hash functions Hk, andcomputing the bitmap Bxi as the logical “or” of the K bitmaps [Hk(x), m]∀k ε1 . . . K, mε1 . . . M, and wherein a compound wildcard query is performed by way of
calculating said bitmaps Bxi of all simple wildcard queries said compound wildcard query is composed of, andcomputing an aggregated bitmap by means of bit-wise operations among said bitmaps Bxi.