International Business Machines Corporation

Chen Chen

Nir Naaman

Yoav Tock

Avraham Harpaz

Benjamin Mandler

A method comprising obtaining a Bloom filter array, wherein a size of a first Bloom filter is smaller than a size of a second Bloom filter and modifying at least a portion of the plurality of Bloom filters to create a modified Bloom filter array comprising a modified plurality of Bloom filters each of which having a same size, wherein the same size is greater than the size of the first Bloom filter, wherein said modifying comprises: duplicating the first Bloom filter to create a modified first Bloom filter comprising two or more concatenated copies of the first Bloom filter. The method may also include performing lookup in the Bloom filter array by computing a hash value of a key and accessing a bit in the hash value location in each Bloom filter of the modified Bloom filter array to determine lookup outcome in each Bloom filter.

Efficient lookup in multiple bloom filters

Method, system and product for efficient size reduction of a Bloom filter. The method includes: creating an interleaved Bloom filter based on a Bloom filter, wherein the interleaved Bloom filter is defined so as to have non-sequential cells of the Bloom filter be positioned sequentially, wherein the interleaved Bloom filter interleaves segments of the Bloom filter, wherein a size of the segments is based on an interleaving factor. A reduced size Bloom filter having a number cells below the number of cells of the Bloom filter is computed. The computation includes computing a value of a cell in the reduced size Bloom filter based on two or more values of cells in the interleaved Bloom filter.

Efficient size reduction of a bloom filter

A method, product and apparatus for distributing retained messages information in a clustered publish/subscribe system. The method comprising obtaining a set of Retained Message Filters (RMFs) comprising a RMF for each server in the cluster, wherein the RMF representing a set of topics for which retained messages are retained by the server, the RMF being configured to approximate whether the server retains a retained message that matches a subscription; responsive to receiving a subscription request from a client, applying the set of RMFs to the subscription to obtain an indication of a set of servers that potentially retain retained messages that match the subscription; triggering each server in the set of servers to perform retrieval of retained messages that match the subscription; and sending to the client the retained messages retrieved from the servers in the set of servers.

Distributing retained messages information in a clustered publish/subscribe system

A publish-subscribe data messaging system in which wildcard subscriptions are represented in an approximate membership set or filter, such as a Bloom filter, for distribution to brokers together with formatting rules associated with the wildcard subscriptions, where a broker receiving a publication topic of a data publication for distribution to other brokers uses the formatting rules provided by any given broker to create wildcard versions of the publication topic for matching with the wildcard subscriptions that are represented in the approximate membership sets or filters provided by the given brokers, where, if a match exists, the data publication is forwarded to the given broker.

Growing community of inventors

Haifa, Israel

Chen Chen