This example provides an example of how a bloom filter can aid in the performance of an application.
Document filtering involves looking at an incoming stream of documents and finding the ones that best match a user's interest. An example of such a system would be the use of a filtering mechanism, which monitors news feeds and sends relevant articles to a user's email account. In general, this application is an example of performing analytics on unstructured data, such as text files, HTML pages, emails, and video files. It has been estimated that up to 80% of all relevant data for businesses is in unstructured form.
The algorithm attempts to find the best matching documents for a specific search profile. The search profile is the filter that matches documents against the user's topic of interest. To this end, each document is reduced to a set of words, and the frequency of appearance of each word in the document. Each term- frequency pair (t_i; f_i) in the document is represented as a 32 bit integer, with a 24 bit term ID, and a 8 bit frequency of occurrence. Terms are generally words in the document. A 24 bit ID allows for a vocabulary of over 16 million terms. The search profile consists of a smaller set of terms, and a weight for each term specifying its relative importance in the search profile. The weights consist of a 64 bit number in fixed point representation. To perform an unstructured search, a score is computed for every document to determine its relevance to the given profile.
The input data to the kernel is as follows:
- docWordFrequencies represents all the documents you want to run through the kernel. Each 32 bit integer represents a term, or word, in the document. The first 24 bits is the term ID, and the last 8 bits is the frequency of occurrence of this term in the document.
- profileWeights is the search profile. It consists of a smaller set of terms, and a weight for each term specifying its relative importance in the search profile. The weights consist of a 64 bit number in fixed point representation.
- isWordInProfileHash is the bloom filter. For each term ID present in the profileWeights array that has a non-zero weight, we compute two hash values from it on the host. We then insert the computed values into the Bloom Filter. Then, during kernel execution, the two hash values are computed for every term ID present in the document. We look up these hash values in the Bloom Filter. If either hash value is not present, it means that the word ID is not in the search profile. If both hash values are found, we will perform a memory access to the profileWeights array.
The output data to the kernel is:
- profileScorePerGroup_highbits are the higher 32 bit of the score for each document we computed.
- profileScorePerGroup_lowbits are the lower 32 bit of the score for each document we computed.
Combined, this represents the score of the document that indicates its relevance to the given profile. To further improve the throughput of this application, we divided the inputs into two equal sized portions, one residing on each DDR memory bank. This is indicated by the _dimm1 (for the first DIMM), and _dimm2 (for the second DIMM) appended to parameters of the kernel. This further improves our performance by taking advantage of the two available memory banks.
The design example provides source code for the OpenCL™ device (.cl) as well as the host application. For compiling the host application, the Linux* package includes a Makefile and the Windows package includes a Microsoft Visual Studio 2010 project.
The following downloads are provided for this example:
The use of this design is governed by, and subject to, the terms and conditions of the hardware reference design license agreement.
To download the Intel design tools, visit the OpenCL download page. The requirements for the underlying operating system are the same as those of the Intel® FPGA SDK for OpenCL.
OpenCL and the OpenCL logo are trademarks of Apple Inc. used by permission by Khronos.
* Product is based on a published Khronos Specification, and has passed the Khronos Conformance Testing Process. Current conformance status can be found at www.khronos.org/conformance.