Hash based filter

A non-transitory computer readable medium for cluster based searching for a value range stored in a storage system, the non-transitory computer readable medium stores instructions for:

• Receiving a request to find information elements having values within a certain value range, wherein the information elements to be found are included in a set of information elements that are stored in a storage system;
• wherein the set of information elements comprises subsets of information elements, wherein each subset is associated with a subset hash based filter;
• Wherein values of the information elements of the set are clustered using a clustering mechanism into multiple clusters, and wherein each cluster is assigned with a cluster value and represents different members having different values that belong to the cluster;
• Wherein at least one subset includes information elements having values that are clustered into different clusters, and wherein at least one cluster includes at least one member that matches values of information elements from multiple subsets;
• Determining a certain cluster value for a certain cluster of the multiple clusters that comprises a member within the certain value range;
• Applying one or more hash functions on the certain cluster value to provide one or more hash results;
• Determining whether one or more members of the certain cluster are possibly in a subset of information elements, based on applying the one ore more hash results on a subset hash based filter of the subset of information elements;
• When determining that the one or more members of the certain cluster are possibly in the subset then searching, within the subset, a matching information element that matches the certain value range;
• and
• Adjusting the clustering mechanism to improve a balance of information elements among the multiple clusters while maintaining versions of subset hash based filters of the subsets of information elements;
• wherein the adjusting of the clustering mechanism is followed by transforming, using a background process, fields that were clustered by the clustering mechanism before being adjusted to fields of newly generated clusters generated by the clustering mechanism following the adjusting.

A storage system that comprises at least one controller that is configured to:

• receive a request to find information elements having values within a certain value range, wherein the information elements to be found are included in a set of information elements that are stored in a storage system;
• wherein the set of information elements comprises subsets of information elements, wherein each subset is associated with a subset hash based filter;
• wherein values of the information elements of the set are clustered using a clustering mechanism into multiple clusters, and wherein each cluster is assigned with a cluster value and represents different members having different values that belong to the cluster;
• wherein at least one subset includes information elements having values that are clustered into different clusters, and wherein at least one cluster includes at least one member that matches values of information elements from multiple subsets;
• determine a certain cluster value of a certain cluster of the multiple clusters that comprises a member within the certain value range;
• apply one or more hush functions on the certain cluster value to provide one or more hash results;
• and
• determine whether one or more members of the certain cluster are possibly in a subset of information elements, based on applying the one or more hash results on a subset hash based filter of the subset of information elements;
• and
• when determining that the one or more members of the certain cluster are possibly in the subset then searching, within the subset, a matching information element that matches the certain value range;
• and
• adjusting the clustering mechanism to improve a balance of information elements among the multiple clusters while maintaining versions of subset hash based filters of the subsets of information elements;
• wherein the adjusting of the clustering mechanism is followed by transforming, using a background process, fields that were clustered by the clustering mechanism before being adjusted to fields of newly generated clusters generated by the clustering mechanism following the adjusting.