Patent Description:
Bloom filters have been implemented in some very successful and widely deployed systems. For example, Google's Bigtable and Facebok's RocksDB employ Bloom filter to avoid performing disk lookups for non existing data.

Recently a Bloom filter variant has been proposed to improve the performance of small hardware tables like processor caches. The blocked bloom filter [BLO], developed by Putze [<NUM>] provide a potential solution for the poor memory locality of standard bloom filters. A BLO filter is composed of b smaller and equal size blocks, each managed as a standard bloom filters. In addition, each element is mapped to k bits within a single randomly assigned bloom filter block. Putze [<NUM>] claims that BLO filter is more cache efficient by suffering less cache misses.

In this document we describe a novel Bloom filter variant for big data sets containing billion of elements. We present of a novel big data bloom filter (BDBF) algorithm that improves the I/O and access times of key search in big tables.

<CIT> discloses a cache-aware Bloom filter system that segments a bit vector of a cache-aware Bloom filter into fixed-size blocks.

The present invention relates to efficient searching of big data using space-efficient probabilistic data structure like bloom filter. Most applicable usage is searching large key-value stores and/or big database tables.

The present invention provides a method according to appended claim <NUM> and a systema according to appended claim <NUM>.

The scope of protection is defined by the independent claims.

The present invention will be more readily understood from the detailed description of embodiments thereof made in conjunction with the accompanying drawings of which:.

Following is a table of definitions of the terms used throughout this application.

The present invention provides a new solution for applying SELECT query for a big dataset consisting of key values pairs. The simple SELECT query, below, exemplify the problem:.

Bloom filter acts as "index like" method; it can filter out key values that we definitely know not to be in big table.

Dividing a big table into chunks enables to create a collection of bloom filters which can be easily managed , such that each chunk may be filtered out separately. For more effective chunks filtering , it is suggested according to the present invention to build a Segmented Bloom Filter for each chunk, and pack the segments with the same index into extent data structures. This novel approach facilitates an extent structure having the same size as the original segmented bloom filters which enables to filter out multiple chunks, rather than processing of single chunks as known in prior art.

<FIG> depicts a block diagram, presenting components for applying enhance the bloom filter on big data processing according to some embodiments of the invention. A big data table of key-value pairs is partitioned into chunks. Each chunk key values are processed by segmented bloom filter module <NUM>. At the first stage are generated Bloom filter segments (<NUM>), into these segments are encoded key values (<NUM>). At the next stage the Bloom filter segments with encoded keys values , are packed into data structure of extents. Each extent only includes segments with the same index; the extent may include some of the segments with the same index or all of them , according to predefined packing factor. The extents are saved in a bit array structure , ordered by their number. To enable efficient data retrieval the extents are mapped to be associated with the segment ID and chunk ID.

<FIG> depicts a flow diagram elaborating the processing of generating of Bloom filter segments , according to some embodiments of the present invention. This processing includes the following steps:.

Determining Bloom filter Vector and number of segments in the vector (step <NUM>);.

Encoding All Keys of a given Chunk into a Bloom filter vector (step <NUM>);.

Determining the segment ID of a given key using H0 hash function (step <NUM>).

Encoding Key into Bloom filter segment using a K-bit array produced by H1,. Hk functions (step <NUM>).

<FIG> is a flow diagram of Key values encoding of encoding process , according to some embodiments of the invention. This processing includes the following steps:.

Given a Bloom filter with s segments of size Z bytes, and k hash functions(<NUM>), apply key-value insertion by set all bit of segment sj to false (<NUM>), Determine which bit of segment sj are set to true by applying hi(key-value) (<NUM>).

<FIG> is a flow diagram, depicting the processing of packing bloom filter segments, according to some embodiments of the invention. This processing includes the following steps:
packing of segments into extents (data structure) where each extent include on segments of different chunks with the same id. /index (step <NUM>).

Determining packing factor (The number of the segments in each extent) for example can be determined by read memory size ( packing factor ) (step <NUM>).

Packing into a single extent consecutive P segments of the same index according to chunk order (step <NUM>);.

The extent data structure enable to reduce the number of files required for holding the Bloom filter, and improve I/O, by packing multiple segments having the same segment ID into a single extent and save it to disk. For example, a bloom filter for a chunk of size 1MB, may include <NUM> segments size 64KB each. When using packing factor of <NUM>, each consecutive group of <NUM> chunks, all SBF segments with segment-id = <NUM> of the <NUM> chunks in the group are packed into extent. <NUM>, and all segments with segment-id = <NUM> for the <NUM> chunks in the group are packed into extent. <NUM> and so on, as illustrated in <FIG>. At the end of the packing procedure for each group of <NUM> chunks we end up with <NUM> extents with a total size of 16MB. (the same size of <NUM> classical Bloom filter for corresponding chunks). However, each extent of 1MB can be used for filtering <NUM> chunks. :Several parameters affect the performance of a Bloom filter.

according to some embodiments of the present invention a single extent can filter multiple chunks, depending on a packing factor (the number of segments packed into a single extent), hence this structure of the extent is much more efficient than using the orthogonal Bloom Filter algorithm to filter a single chunk at atme.

<FIG> is a flow diagram, depicting the computation module for processing of computing segment ID and hash bits vector according to some embodiments of the invention. This processing includes the following steps:.

Applying h<NUM> function on key value to compute segment id/index (step <NUM>);.

Applying h; function on key value to compute hash bits vector for Each key-value (step <NUM>);.

<FIG> is a flow diagram of chunk filtering module processing according to some embodiments of the invention. select all big-table extents and for each extent E, determine whether, or not, the chunks represented by E needs to be included in the SELECT by applying extent processing (step <NUM>).

<FIG> illustrates Extent module Processing, according to some embodiments of the invention. This processing includes the following steps:
processing the segments stored in that extents. These segments can be identified using the segment map using the key, segment id and extent number values, (step <NUM>).

Applying key-value membership test to each segment (step <NUM>).

<FIG> is a flow diagram of key-value membership test module processing, processing according to some embodiments of the invention.

Test membership for key value of Bloom filter for segment sj of size Z bytes, by applying k hash functions (step <NUM>).

Calculate x key value by applying hi(key-value) (step <NUM>).

Check if X bit is true or false in segment (step <NUM>).

<FIG> is a flow diagram of mapping module processing according to some embodiments of the invention. This processing includes the following steps:.

Maintaining relationships between data chunks, extents and segments by maintaining three map tables (step <NUM>).

Maintaining chunk-map table by storing information about data chunks associate given chunk-number to chunk_ file path (step <NUM>).

Maintaining extent-map table by storing information about extents; associate a given extent number to extent file path (step <NUM>).

Mapping segment table (sbf-map table ) by storing information about all segments maintaining the relationship between segments, extents and chunks (step <NUM>).

The chunk-map table stores information about data chunks; it maps a given chunk-number to chunk_ file path.

The extent-map table stores information about extents; it maps a given extent number to extent file path.

The sbf-map table stores information about all segments; it keeps the relationship between segments, extents and chunks.

According to some embodiment of the present invention the above map tables are implemented using SQL tables so that they can be queries using SQL as follows:.

The main benefit of employing a bloom filter for filtering records with a given <key> value is by avoiding reading chunks having no record with the provided <key> value. This can be done efficiently using the BDBF filter as suggested by the present invention.

The segmented bloom filtering algorithm according to the present invention guarantees that each key is hashed into exactly a single segment. Accordingly , once the segment id for a given <key> value is computed, there is a need to read all segments, requiring only to inspect the SBF segments corresponding to the segment-id. In other words, it is only required to read and inspect the extents corresponding to that segment-id.

This BDBF algorithm filter and minimizes the I/O cost in case of false filtering results. The benefits directly affect the cost of chunk access. this benefit has greater impact when the data chunks are distributed over multiple processor nodes.

This section presents the principles of membership testing when using the BDBF filter algorithm. The following paragraph exemplify implementation of SQL SELECT operations of -selecting predicate of the form key=<key-value>. For example,
<IMG>.

In the following example is shown how the algorithm avoid reading chunks with records not including the predicate key=<key-value>.

Given Bloom filter with s segments each of seg size bytes, and k hash functions, key value insertion is done as following
<IMG>.

Step (<NUM>): select all big-table extents and for each extent E, determine whether, or not, the chunks represented by E needs to be included in the SELECT. The number of chunks that can be filtered by a single extent is determined by the pack factor (see <NUM> definitions). Step(<NUM>) is implemented as follows
<IMG>.

Extent processing is performed to all the segments stored in that extents. These segments can be identified using the segment map using the key, segment id and extent number values, as implemented by the BDBF_PROCESS_EXTENT function.

<FIG> is a visual example of bloom filter segmentation by chunks according to some embodiments of the invention.

In the above description, an embodiment is an example or implementation of the invention. The various appearances of "one embodiment", "an embodiment" or "some embodiments" do not necessarily all refer to the same embodiments.

Although various features of the invention may be described in the context of a single embodiment, the features may also be provided separately or in any suitable combination. Conversely, although the invention may be described herein in the context of separate embodiments for clarity, the invention may also be implemented in a single embodiment.

Furthermore, it is to be understood that the invention can be carried out or practiced in various ways and that the invention can be implemented in embodiments other than the ones outlined in the description above.

The invention is not limited to those diagrams or to the corresponding descriptions. For example, flow need not move through each illustrated box or state, or in exactly the same order as illustrated and described.

Meanings of technical and scientific terms used herein are to be commonly understood as by one of ordinary skill in the art to which the invention belongs, unless otherwise defined.

The apparatus of the present invention may include, according to certain embodiments of the invention, machine readable memory containing or otherwise storing a program of instructions which, when executed by the machine, implements some or all of the apparatus, methods, features and functionalities of the invention shown and described herein. Alternatively or in addition, the apparatus of the present invention may include, according to certain embodiments of the invention, a program as above which may be written in any conventional programming language, and optionally a machine for executing the program such as but not limited to a general purpose computer which may optionally be configured or activated in accordance with the teachings of the present invention. Any of the teachings incorporated herein may wherever suitable operate on signals representative of physical objects or substances.

Unless specifically stated otherwise, as apparent from the following discussions, it is appreciated that throughout the specification discussions, utilizing terms such as, "processing", "computing", "estimating", "selecting", "ranking", "grading", "calculating", "determining", "generating", "reassessing", "classifying", "generating", "producing", "stereo-matching", "registering", "detecting", "associating", "superimposing", "obtaining" or the like, refer to the action and/or processes of a computer or computing system, or processor or similar electronic computing device, that manipulate and/or transform data represented as physical, such as electronic, quantities within the computing system's registers and/or memories, into other data similarly represented as physical quantities within the computing system's memories, registers or other such information storage, transmission or display devices. The term "computer" should be broadly construed to cover any kind of electronic device with data processing capabilities, including, by way of nonlimiting example, personal computers, servers, computing system, communication devices, processors (e.g. digital signal processor (DSP), microcontrollers, field programmable gate array (FPGA), application specific integrated circuit (ASIC), etc.) and other electronic computing devices.

The present invention may be described, merely for clarity, in terms of terminology specific to particular programming languages, operating systems, browsers, system versions, individual products, and the like. It will be appreciated that this terminology is intended to convey general principles of operation clearly and briefly, by way of example, and is not intended to limit the scope of the invention to any particular programming language, operating system, browser, system version, or individual product.

It is appreciated that software components of the present invention including programs and data may, if desired, be implemented in ROM (read only memory) form including CD-ROMs, EPROMs and EEPROMs, or may be stored in any other suitable typically non-transitory computer-readable medium such as but not limited to disks of various kinds, cards of various kinds and RAMs. Components described herein as software may, alternatively, be implemented wholly or partly in hardware, if desired, using conventional techniques. Conversely, components described herein as hardware may, alternatively, be implemented wholly or partly in software, if desired, using conventional techniques.

Included in the scope of the present invention, inter alia, are electromagnetic signals carrying computer-readable instructions for performing any or all of the steps of any of the methods shown and described herein, in any suitable order; machine-readable instructions for performing any or all of the steps of any of the methods shown and described herein, in any suitable order; program storage devices readable by machine, tangibly embodying a program of instructions executable by the machine to perform any or all of the steps of any of the methods shown and described herein, in any suitable order; a computer program product comprising a computer useable medium having computer readable program code, such as executable code, having embodied therein, and/or including computer readable program code for performing, any or all of the steps of any of the methods shown and described herein, in any suitable order; any technical effects brought about by any or all of the steps of any of the methods shown and described herein, when performed in any suitable order; any suitable apparatus or device or combination of such, programmed to perform, alone or in combination, any or all of the steps of any of the methods shown and described herein, in any suitable order; electronic devices each including a processor and a cooperating input device and/or output device and operative to perform in software any steps shown and described herein; information storage devices or physical records, such as disks or hard drives, causing a computer or other device to be configured so as to carry out any or all of the steps of any of the methods shown and described herein, in any suitable order; a program pre-stored e.g. in memory or on an information network such as the Internet, before or after being downloaded, which embodies any or all of the steps of any of the methods shown and described herein, in any suitable order, and the method of uploading or downloading such, and a system including server/s and/or client/s for using such; and hardware which performs any or all of the steps of any of the methods shown and described herein, in any suitable order, either alone or in conjunction with software. Any computer-readable or machine-readable media described herein is intended to include non-transitory computer- or machine-readable media.

Any computations or other forms of analysis described herein may be performed by a suitable computerized method. Any step described herein may be computer-implemented. The invention shown and described herein may include (a) using a computerized method to identify a solution to any of the problems or for any of the objectives described herein, the solution optionally include at least one of a decision, an action, a product, a service or any other information described herein that impacts, in a positive manner, a problem or objectives described herein; and (b) outputting the solution.

The scope of the present invention is not limited to structures and functions specifically described herein and is also intended to include devices which have the capacity to yield a structure, or perform a function, described herein, such that even though users of the device may not use the capacity, they are, if they so desire, able to modify the device to obtain the structure or function.

Features of the present invention which are described in the context of separate embodiments may also be provided in combination in a single embodiment.

Claim 1:
A method for applying Bloom filter on a large data table consisting of key-value pairs for enabling efficient key-value membership testing to each segment, using at least one processor, the method comprising the step of:
• partitioning the large data table of key-value pairs into data chunks (<NUM>);
• determining Bloom filter vector size and number of segments S in the vector for each data chunk, each segment having Z bytes (<NUM>);
• encoding all keys of a given chunk into a Bloom filter vector (<NUM>) by, for each key:
o determining the segment-id of the key of the large data table using h<NUM> hash function (<NUM>) such that each key is hashed into exactly a single segment;
o encoding the key into a Bloom filter segment with said determined segment-id;
wherein the process of encoding the key into a given Bloom filter segment, is implemented by using k hash functions and setting the appropriate bits of the segment as follows: set all bits of the segment to false and then for each i=<NUM>..k determine which bits of the segment are set to true by applying functions hi(key-value) (<NUM> , <NUM>-<NUM>) to the key,
wherein the method is characterized by:
- determining the number P, packing factor, of the Bloom filter segments to be used for packing segments into extents, where the packing factor defines the number of segments in each extent and where the packing factor is determined by read memory size (<NUM>);
- packing of segments into extents, where consecutive P segments of the same segment-id are packed into a single extent according to chunk order and saving the extents (<NUM>); wherein an extent structure is a bit array structure;
wherein a single extent having segments with same segment-id supports key-value membership testing to each segment of size Z bytes, depending on the number of segments packed into a single extent or packing factor, wherein the key-value membership testing is applied by subsequent steps:
- compute segment-id by applying h<NUM> function on a given key value;
- calculate x key value by applying hi (key-value), where i=<NUM>..k;
- check if x bit is true or false in the segment.