Interwoven AMQ Data Structure

An interwoven approximate membership query (AMQ) data structure interweaves multiple AMQ data sets. The interwoven AMQ data structure collapses the AMQ data sets into a composite membership representation. The interwoven AMQ data structure still represents a computer database, but the interwoven AMQ data structure yields far faster membership results. The interwoven AMQ data structure requires orders of magnitude less data reads. Memory allocation is reduced, processor cycles are reduced, input/output operations are reduced, and translations from kernel space to user space are reduced. The interwoven AMQ data structure greatly improves computer functioning.

BACKGROUND

The subject matter described herein generally relates to computers and, more particularly, the subject matter relates to membership testing of approximate membership query (or AMQ) data structures.

Searching data is hardware intensive. As cloud computing grows in usage, computer databases have grown exceptionally large. It is common, for example, for a cloud-distributed database to process and store ten million (10,000,000) messages per second. Because these exceptionally large databases must be searched, data lookups require much time and hardware resources.

SUMMARY

A new and elegant approximate membership query (or AMQ) data structure greatly improves computer functioning. The interwoven AMQ data structure is generated by aggregating and interweaving multiple approximate membership query (or AMQ) data sets. The interwoven AMQ data structure thus represents a computer database or any other datastore, but the interwoven AMQ data structure is much smaller (in bytes) than its corresponding computer database. Moreover, the interwoven AMQ data structure is uniquely designed to yield far faster results in database searches and membership checks from multiple separate AMQ filters. So, when any computer needs to perform a search of the much larger computer database, the computer, instead, first conducts a preliminary membership test using the interwoven AMQ data structure. By interweaving bits of data from different AMQ data sets (such as Bloom filters), the interwoven AMQ data structure is a blend or composite of membership filter/bit traits. The interwoven AMQ data structure still represents the computer database, but the interwoven AMQ data structure consumes orders of magnitude less memory space. Because the interwoven AMQ data structure is much faster to search, the interwoven AMQ data structure requires orders of magnitude fewer data reads. In some examples, memory allocation is reduced, processor cycles are reduced, input/output operations are reduced, and translations from kernel space to user space are reduced. The interwoven AMQ data structure greatly improves computer functioning.

DETAILED DESCRIPTION

Some examples relate to preliminary searches of computer databases. A computer database is stored within a server, a smartphone, or other computer. The computer database stores hundreds, thousands, millions, or more of electronic records (such as movies, music, messages, documents, or other electronic files). Whatever the electronic records, the computer database may thus be very large, especially in cloud computing environments. Because many databases are large, these large databases burden processors and memory. Large databases are slow to search, as the hardware processor and memory require more operations and more time. Large databases require more electrical power, as the hardware processor and memory consume more electricity when performing searches. Large databases also consume more memory/storage space, which further bogs down performance. As a general rule, then, as databases grow in size, their costs also grow.

Some examples relate to membership search schemes. The examples describe a new and elegant interwoven approximate membership query (or AMQ) data structure. This interwoven AMQ data structure is sometimes referred to herein as a “Lyons data structure.” The interwoven AMQ data structure can substantially reduce the burdens associated with any computer database or any other datastore. A computer is programmed to generate the interwoven AMQ data structure as a binary bit-set membership representation of the computer database. The interwoven AMQ data structure, though, is much smaller (in bytes) than its corresponding computer database. Moreover, the interwoven AMQ data structure is uniquely designed to yield far faster results in database searches. So, when any computer needs to perform a search of the computer database, the computer, instead, first conducts a preliminary membership test using the interwoven AMQ data structure, which can be much smaller than the computer database itself. The preliminary membership test reveals whether a data element is a member of the interwoven AMQ data structure. If the preliminary membership test is negative (i.e., the data element is not a member of the interwoven AMQ data structure), then the computer may immediately decline to search the larger computer database. That is, because the data element is not a member of the interwoven AMQ data structure, there is no need, reason, or advantage in searching the corresponding computer database. The computer, in other words, would waste time, energy, and cost searching the larger computer database. However, if the preliminary search is positive (i.e., the data element might be a member of the interwoven AMQ data structure), then the computer may perform a more thorough search of the larger computer database. In other words, because the preliminary membership test is satisfied, the time, energy, and cost of searching the larger computer database is justified. The interwoven AMQ data structure is thus designed to make a quick and simple go-no-go decision for a more expensive and resource-intensive search of the larger computer database.

The interwoven AMQ data structure can greatly improve computer functioning. The interwoven AMQ data structure (or the “Lyons data structure) is ingeniously designed to interweave different approximate membership query (or AMQ) data sets. While there are many different types of AMQ data sets, Bloom filters are well-known examples. The interwoven AMQ data structure may thus represent interwoven Bloom filters. The computer is programmed to identify and to read individual bits of data from within different Bloom filters. The computer is programmed to then elegantly interweave the bits of data to create an interwoven AMQ data structure. By interweaving the bits of data from different Bloom filters, the interwoven AMQ data structure is a blend or composite of membership bit-set filters or traits described by the different Bloom filters. The interwoven AMQ data structure still represents the computer database, but the interwoven AMQ data structure consumes orders of magnitude less memory space. Moreover, the interwoven AMQ data structure is much faster to search, perhaps requiring orders of magnitude less data reads. Memory allocation is reduced, processor cycles are reduced, input/output operations are reduced, and translations from kernel space to user space are reduced.

The design, construction, and usage of the interwoven AMQ data structure will now be described more fully hereinafter with reference to the accompanying drawings. The interwoven AMQ data structure, however, may be embodied in many different forms and should not be construed as limited to the examples set forth herein. These examples are provided so that this disclosure will be thorough and complete and fully convey the interwoven AMQ data structure to those of ordinary skill in the art. Moreover, all the examples of the interwoven AMQ data structure are intended to encompass both structural and functional equivalents thereof. Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future (i.e., any elements developed that perform the same function, regardless of structure).

FIG.1illustrates some examples of the interwoven AMQ data structure20. A computer system22is programmed to generate the interwoven AMQ data structure20. The interwoven AMQ data structure20is sometimes referred to herein as a “Lyons data structure20.”FIG.1illustrates the computer system22as a server24, but the computer system22may be any processor-controlled device (as later paragraphs will explain). The server24stores and executes an operating system26. The server24also stores a software application28in a memory device30. The server24has a hardware processor32(illustrated as “CPU”) that reads and executes the software application28. The software application28has programming code or instructions that cause the server24to perform operations, such as generating the interwoven AMQ data structure20using two (2) or more approximate membership query (AMQ) data sets (illustrated as reference numerals34aand34b). Again, while the interwoven AMQ data structure20may be generated using any bit-setting AMQ data structures, Bloom filters (illustrated as reference numerals36aand36b) are well-known examples of bit-setting AMQ data structures. The software application28instructs the hardware processor32to retrieve the Bloom filters36aand36bas inputs. While the Bloom filters36aand36bmay be retrieved from any networked location,FIG.1simply illustrates local retrieval from the memory device30.

The Lyons data structure20is elegantly created. The software application28instructs the hardware processor32to identify one or more binary bits38acontained within, associated with, or representing the first Bloom filter36a. The software application28instructs the hardware processor32to identify one or more binary bits38bcontained within, associated with, or representing the second Bloom filter36b. The software application28instructs the hardware processor32to read or to retrieve the binary bits38aand38bfrom the memory device30. Once the binary bits38aand38bare acquired, the software application28instructs the hardware processor32to aggregate the Bloom filters36a-b. The hardware processor32performs an interweave operation40using the binary bits38aand38b. The hardware processor32, executing the interweave operation40, then generates the interwoven AMQ (or Lyons) data structure20as an output. The interweave operation40collapses and merges the multiple Bloom filters36aand36binto at least one interwoven AMQ data structure20. By interweaving the binary bits38aand38b, the interwoven AMQ (or Lyons) data structure20represents a blend or composite of membership filters or bit traits represented by the different Bloom filters36aand36b. Once the interwoven AMQ data structure20is generated, the hardware processor32may then store the interwoven AMQ data structure20in the memory device30.

The interwoven AMQ (or Lyons) data structure20collapses the two (2) Bloom filters36aand36b. Because there are only two (2) Bloom filters36a-bin these simple examples, the interweave operation40may read each bit38a-band perform a bitwise OR operation. In other words, if the first bit38aof Bloom filter36ais zero (0), and the first bit38bof Bloom filter36bis one (1), then the interweave operation40may collapse bits38a-bas a single bit value of one (1). Conversely, if both bits38a-bwere zero (0), then the bits38a-bcollapse to a bit value of zero (0). The interweave operation40, however, may use any other bitwise operation to suit any objective. Similarly, the interwoven AMQ data structure20may also be generated using any bitwise operations to collapse bits38from multiple Bloom filters36. The aggregated positional bits38a-bfrom different Bloom filters36a-bmay be collapsed (such as using the OR operation) and the resultant value written to the interwoven AMQ data structure20.

FIGS.2-4illustrate examples of membership testing the interwoven AMQ (or Lyons) data structure20. The server24receives a search query50. The search query50specifies a query parameter52, and the search query50requests a search of a computer database54. However, because the database search may be resource intensive and relatively expensive, the server24may first conduct a membership test56using the interwoven AMQ data structure20. The interwoven AMQ (or Lyons) data structure20represents a blend or composite of membership filters or bit traits (as explained with reference toFIG.1). The interwoven AMQ (or Lyons) data structure20may thus be stored as a data blob in the memory30(such as a database entry or in cache memory). The interwoven AMQ data structure20may also be stored as a series of bytes in the memory30). The interwoven AMQ (or Lyons) data structure20may also be represented as a file on disk, a file over the network, the data blob, or the series of bytes.FIG.2illustrates an example of OS origination in which the search query50issues from the operating system26.FIG.3illustrates an example of cloud origination in which the search query50issues from a network member60associated with a cloud computing environment62.FIG.4illustrates an example of endpoint origination in which the search query50is received via a communications network64from a remote endpoint device66. However the search query50is received, the search query50requests a search of the computer database54according to the query parameter52. When the server24receives the search query50, the server24may thus act as a query handler of client requests for searching the computer database54. However, instead of a resource-intensive search of the computer database54, the server24first conducts the membership test56using the interwoven AMQ (or Lyons) data structure20. The membership test56may thus be a preliminary procedure based on the much smaller and nimble Lyons data structure20.

The interwoven AMQ (or Lyons) data structure20is uniquely designed to consume far less computer resources and to yield far faster search results. The server24may thus be programmed to first conduct the membership test56, based on the interwoven AMQ data structure20, as a go-no-go decision70. The server24conducts the membership test56based on the query parameter52. However, because the interwoven AMQ data structure20aggregates and interweaves the Bloom filters36a-b, the interwoven AMQ data structure20contains a composite membership representation of all the multiple Bloom filters36aand36b. The server24may thus conduct a single, simultaneous query (e.g., the membership test56) of both Bloom filters36aand36b. In the simple examples illustrated byFIGS.1-4, there are only two (2) Bloom filters36aand36b. The server24may thus execute the single membership test56that simultaneously inspects both Bloom filters36aand36b. A conventional membership scheme would require two (2) data lookups (e.g., one membership test for each Bloom filter). Yet, because of the ingenious interwoven AMQ data structure20, the server24need only perform the single, simultaneous membership test56, thus yielding a 50% reduction in processor reads. Indeed, in actual production use, there may be thousands or even millions of different Bloom filters36. The server24may still aggregate and interweave these thousands or even millions of different Bloom filters36into the single interwoven AMQ (or Lyons) data structure20. The server24still needs only to perform the single, simultaneous membership test56, thus yielding an orders of magnitude reduction in hardware lookups. The reduction may be directly proportional to the number of AMQ filters represented by the interwoven AMQ (or Lyons) data structure20, thus yielding orders of magnitude reductions in hardware lookups for large numbers of filters.

The examples of the interwoven AMQ (or Lyons) data structure20are continued. When the search query50is received, the server24may generate and/or retrieve a key72that represents the query parameter52. While the key72may have any element form or value, the key72may be a cryptographic hash value. As a simple example, the query parameter52(specified by the search query50) may be hashed by a hashing function to generate the cryptographic key72. The key72represents the query parameter52. However the key72is determined, the server24may then membership query or test the interwoven AMQ data structure20for a bit-set membership of the key72. If the membership test56is negative (i.e., the key72is not a member of the interwoven AMQ data structure20), then the server24may decline to search the computer database54. That is, because the key72fails the membership test56, the server24determines that the corresponding query parameter52will not be found in the larger computer database54. The server24would thus waste time, energy, and cost conducting a fruitless search of the computer database54for the query parameter52. However, if the membership test56is positive (i.e., the key72satisfies the membership test56and can be a member of the interwoven AMQ data structure20), then the server24may perform a more thorough search of the larger computer database54. The query parameter52, in other words, could be found in the larger computer database54, so the search time, energy, and cost are justified. The server24may then generate a query response74. The query response74may indicate a result of the membership test56(such as whether the key72is the member of the interwoven AMQ data structure20). The query response74, in other words, may indicate that the query parameter52is not found in the computer database54, based merely on the failed membership test56. When, however, the membership test56is satisfied, the query response74may indicate a search result of the larger computer database54. The interwoven AMQ (or Lyons) data structure20is thus designed to make the very quick and the very simple go-no-go decision70for a more expensive and resource-intensive search of the larger database54.

The interwoven AMQ (or Lyons) data structure20can greatly improve computer functioning. The interwoven AMQ data structure20is ingeniously designed to interweave the multiple AMQ data sets34aand34b(illustrated inFIG.1), thus collapsing and merging their bit contents into the single interwoven AMQ data structure20. The binary bits38aand38b(illustrated inFIG.1) are identified and read from the different AMQ data sets34a-b. The server24executes the interweave operation40(illustrated inFIG.1) that elegantly interweaves the bits38aand38bto create the interwoven AMQ data structure20. Again, while there are many different types of bit-setting AMQ data sets, this disclosure mostly discusses and explains the examples using the Bloom filters36aand36b(illustrated inFIG.1). The interwoven AMQ data structure20may thus represent interwoven Bloom filters36aand36b. The software application28causes the server24to identify and to read the individual bits38aand38bfrom within the different Bloom filters36aand36b. By interweaving the bits38aand38bfrom the different Bloom filters36aand36b, the interwoven AMQ data structure20blends their respective filters or membership bit traits to generate a comprehensive and more concise composite membership representation. The single interwoven AMQ data structure20consumes orders of magnitude less memory space for read operations, is much faster to search, and requires orders of magnitude less data reads. Memory allocation is reduced, processor cycles are reduced, input/output operations are reduced, and translations from kernel space to user space are reduced. The interwoven AMQ data structure20greatly improves computer functioning.

FIG.5illustrates examples of byte level adaptations. The above examples describe the interwoven AMQ (or Lyons) data structure20using bit level interweaving. The examples, however, may be easily adapted to byte level interweaving. The interweave operation40, in other words, may interweave different bytes80a-bof data read from the different approximate membership query (AMQ) data sets34a-b. Again, because there are many different types of bit-setting AMQ data sets, the interwoven AMQ data structure20may be generated to represent any filters, such as Counting Bloom filters, Cuckoo filters, Xor filters, and Quotient filters, regardless of bit/byte size. The examples may be easily adapted to identify, read, and interweave bytes80of data selected from different AMQ data structures.

FIG.6illustrates a time-series of AMQ data sets34. Again, while the examples may be applied to any bit-setting AMQ data structure,FIG.6illustrates a time-series of the Bloom filters36. Each unit of time t (illustrated as reference numeral90) is represented by N relatively small Bloom filters361-N, where N is an integer value. Each Bloom filter361-Nhas a bit length of n bits (illustrated as reference numeral92) and their corresponding bit positions 0, 1, 2, . . . , n. When storing the key72to the Bloom filters361-N, the key72may first be hashed to determine which Bloom filter361-Nin the time-series correlates to the key's hash value. The aggregate of multiple time units occurs over a fixed window T (illustrated as reference numeral94). While the times-series of the Bloom filters361-Nmay be generated using any interval of time,FIG.6illustrates the common example of daily filtering. That is, the Bloom filters361-Nare generated every minute (t=60 secs or 1 min) of every hour of every day (e.g., T=24 hours).

FIG.7illustrates multiple versions of the interwoven AMQ (or Lyons) data structure20. All the Bloom filters36occurring within an aggregate window of time may be saved to the memory device30(illustrated inFIGS.1-2) as A number of the interwoven AMQ data structures20. Recall that each Bloom filter361-Nhas the bit length of n bits and their corresponding bit positions 0, 1, 2, . . . , n. Each interwoven AMQ data structure20may thus represent a correspondingly single Bloom filter index. That is, interwoven AMQ data structure (or IAMQ)200represents the binary bits38within the Bloom filters36occurring at index 0 (e.g., bit position 0) from each Bloom filter361-Nat each unit of time. The IAMQ20/represents the binary bits38within the Bloom filters36occurring at index 1 (such as bit position 1) from each unit of time. The IAMQ202represents the binary bits38within the Bloom filters36occurring at index 2 (such as bit position 2) from each unit of time. The IAMQ20wrepresents the binary bits38within the Bloom filters36occurring at index N (such as bit position n) from each unit of time. The aggregate bits38may be sorted by bit index (e.g., bit positions 0, 1, 2, . . . , n), perhaps then by time unit, such that all of the bits38for a given bit index are aggregated and co-located with the interwoven AMQ data structure20.

FIGS.8-11illustrate more bit level examples of the interwoven AMQ (or Lyons) data structure20.FIG.8illustrates an example of simple Bloom filters36generated over eight (8) minutes. That is, let t=1 minute, T=8 minutes, and N=3.FIG.8thus illustrates three (3) Bloom filters361-3generated every sixty (60) seconds. Moreover, in these examples, the membership of each Bloom filter361-3is described using n=10 bits (illustrated as reference numeral380-9). Because each Bloom filter361-3is represented with n=10 bits, each Bloom filter367-3has a corresponding ten (10) bit positions 0, 1, 2, . . . , 9 (illustrated as reference numeral940-9). Again,FIGS.8-11illustrate simple examples. In actual practice, the Bloom filters36would have far more than ten (10) bits380-9and their corresponding ten (10) bit positions940-9.

FIG.9thus illustrates the interwoven Bloom filters36. The interwoven AMQ (or Lyons) data structure20is generated by interweaving the bits38from different AMQ data structures (again illustrated as the Bloom filters36). While any interweaving bit (or byte) scheme may be used to generate the interwoven AMQ data structure20,FIG.9illustrates interweaving according to the bit position94.FIG.9, for example, illustrates a first version of the interwoven AMQ data structure (illustrated as 0.IAMQ20) generated by reading, copying, and aggregating the bits38according to the bit position94. Each bit380(at the first index or bit position940) is read from the first Bloom filters361generated at each interval of time t (illustrated as reference numeral90). These bits380(at the first index or bit position940) are copied, grouped together in a series, and written as an entry to the interwoven AMQ data structure20. Similarly, the bits38/(at the second index or bit position941) are copied, grouped together in a chronological series, and written as another entry to the interwoven AMQ data structure20. The bits382(at the second index or bit position942) are copied, grouped together in a chronological series, and written as another entry to the interwoven AMQ data structure20. The examples may continue interweaving the bits38and writing additional entries to the interwoven AMQ data structure20. InFIG.9, the examples write a final entry in the interwoven AMQ data structure20that interweaves the bits389(at the tenth index or bit position949). The interwoven AMQ data structure20(e.g., 0.IAMQ) may thus contain the first 10 bits from each time unit, ordered by index/column first. The interwoven AMQ data structure20may thus be a single file that contains a complete and composite filter/bit representation of all the bit-set Bloom filters36captured at N=0 over the total time T=8 minutes.

FIG.10illustrates another example of the interwoven AMQ (or Lyons) data structure20. This second version of the interwoven AMQ data structure20is generated by interweaving the bits38from the Bloom filters36captured at N=1 over the total time T=8 minutes. Again, while any interweaving bit (or byte) scheme may be used,FIG.10starts at the first index (bit position940) and interweaves according to the bit position94. The server24(illustrated inFIGS.1-4) reads, copies, and/or aggregates the bits38according to the bit position94. Each bit380(at the first index or bit position940) is read from the first Bloom filters36generated at each interval of time1(illustrated as reference numeral90). These bits380(at the first index or bit position940) are copied, grouped together in a series, and written as an entry to the interwoven AMQ data structure20. Similarly, the bits38/(at the second index or bit position941) are copied, grouped together in a chronological series, and written as another entry to the interwoven AMQ data structure20. The bits382(at the second index or bit position942) are copied, grouped together in a chronological series, and written as another entry to the interwoven AMQ data structure20. The examples may continue interweaving the bits38and writing additional entries to the interwoven AMQ data structure20. The interwoven AMQ data structure20(e.g., 1.IAMQ) contains the first 10 bits from each time unit, ordered by index/column first. The interwoven AMQ data structure20may thus be a single file that contains a complete and composite filter/bit representation of all the bit-set Bloom filters36captured at N=1 over the total time T=8 minutes.

FIG.11illustrates yet another example of the interwoven AMQ (or Lyons) data structure20. This third version of the interwoven AMQ data structure20is generated by interweaving the bits38from the Bloom filters36captured at N=2 over the total time T=8 minutes. Again, while any interweaving bit (or byte) scheme may be used,FIG.11starts at the first index (bit position940) and interweaves according to the bit position94. The interwoven AMQ data structure20(e.g., 2.IAMQ) contains the first 10 bits from each time unit, ordered by index/column first. The interwoven AMQ (or Lyons) data structure20may thus be a single file that contains a complete and composite filter/bit representation of all the Bloom filters36captured at N=2 over the total time T=8 minutes.

The interwoven AMQ data structure20collapses the Bloom filters36. The interwoven AMQ data structure20combines and interweaves the multiple Bloom filters361-N, but the interwoven AMQ data structure20may arrange the bits38in time series as opposed to bit series. The bit38a, at a specified bit position94within Bloom filter38a, is arranged next to the bit38bread from the same specified bit position94within Bloom filter38b. If this collapsing is repeated over 24 times x 60 minutes, the hardware processor36would read 1,440 bits (or 180 bytes) a maximum of k times. While k may be any value, a value of k=6 is often sufficient. A bitmask AND operation is performed across the read values of k (e.g., Read0&& Read1&& . . . && Readk), thus allowing a simple bit inspection. Where any bit is set to logical 1, then that key72was probably seen at that time offset. So, after collapsing all of those k Bloom filters36, the basic result is a picture of which minutes would this key72possibly have occurred. The examples thus narrow down a lookup search of the computer database54to those specific minutes.

Yet another membership example is provided using the interwoven AMQ data structure20. Suppose the Bloom filters36use k=3 hashes, and for a key abcd:cdef the hashN function gives us 0.IAMQ and the Bloom hashes give indices 0, 3, and 5 In order to check which minutes the key72(e.g., abcd:cdef) may have been seen, the examples may first open the 0.IAMQ (illustrated inFIG.9). The server24may read chunks of the bits38equivalent to T/t. In this example, this is 0:8, 24:32, and 40:48. Using bit AND operations, these bit chunks correspond to00100000 AND 11111111 AND 11111111=00100000.
Here, the bit38at index 2 (e.g., bit position 3) is flipped on (or logical/binary 1) for all k=3 chunks. This means that the only time the key72may be present is minute2.

The interweave operation40(illustrated inFIGS.1&9-11) thus breaks up each Bloom filter36. Each Bloom filter36may be broken up into its individual bit portions. The corresponding bits38from each Bloom filter36, associated with the same bit position94, may be combined, interweaved, and/or positioned next to each other, perhaps according to consecutive Bloom filter time, numbering, or other order. Interweaving, in other words, is akin to straws of hay bales being combined together. Interleaving, on the other hand, stacks individual Bloom leaves on top of each other. Interleaving implies that there are distinct sections of the Bloom filter that are placed next to each other. Interweaving breaks up the entire Bloom filter36into its individual bit portions, and then those bits are combined next to each other with bits at common bit positions read from other Bloom filters.

The examples further improve computer functioning. Long-term storage of data benefits from Bloom filters which indicate where the key72is present within time ordered sets of data and to be able to query efficiently. For example, in the last 90 days, which minutes contain the data for key abcd:cdef. If data is stored in a time-based way, then a time-series Bloom filter provides insight into where data is stored and helps in efficient data retrieval. A time-series Bloom filter can be used to identify if a key72has been seen recently, and therefore which data store to query (e.g., last hour, last day, or 30 days ago). If data is expected to be infrequently accessed or possibly never accessed, then such data can be saved to a cheaper storage service. Such a storage service is cost effective if the number of reads performed are relatively few. The examples organize the bit/byte data in such a way as to minimize reads and file loads. The examples easily scale for large, long-term storage of data and provide time granularity. The examples eliminate individually and costly checking multiple Bloom filters. The examples may thus may not only save Bloom filters on a time basis, but the examples also interweave multiple Bloom filters together in such a way as to minimize the number of disk reads and memory allocations required to check if a key72exists and when that key72may have been seen.

Still another example is provided. Suppose t=1 minute, T=24 hours, n=4096 bits, N=2048, and k=6. For 800,000 keys per minute (hashed evenly), the odds of a false positive are approximately 0.69%. Each minute would contain approximately 1 MB of Bloom filters. The number of aggregate files would be 2048 for a given day. Each would be approximately 1.4 MB in size and sum to 2.81 GB total. A key72could be hashed with SHA-1 once and the bits used to represent between 0 and 2048 once and 0 to 4096, six more times. One interwoven AMQ (or Lyons) data structure20would be opened and up to 6 reads would occur, each totaling 1440 bits or 180 bytes. Fewer than 6 reads may occur if the AND combination of reads equals all 0s within <6 reads.

The interwoven AMQ data structure20may thus be one file for an entire window. Again using a per minute example, there would be 1,440 Bloom filters collapsed and co-located within the single interwoven AMQ data structure20. Moreover, rather than merely sequentially writing the 1,440 Bloom filters, the examples interweave the 1,440 Bloom filters based on the bits94of interest. The first24by 60 bits, for example, is the first bit380of every Bloom filter36using bitwise AND operation. Then the next 24 by 60 bits is the second bit381of every filter36. The next 24 by 60 bits is the third bit382of every filter36, and so on. Because when looking up for a filter, the examples need only look up those bits38that are to be found. So, if looking across24by 60 filters, the interwoven AMQ data structure20locates all those bits38next to each other, so only one read operation need be performed to get that bit38across every filter36.

The interweave operation40greatly improves computer functioning. The interweave operation40co-locates bit/byte data read from AMQ filters using bit operations. Because the interwoven AMQ data structure20merges and collapses a large number of the AMQ filters (such as the Bloom filters36), the interwoven AMQ data structure20greatly reduces the number of read/writes proportional to the number of filters used. By combining the multiple Bloom filters36, for example, only k reads of the interwoven AMQ data structure20are needed. Conventional schemes would read k times the number of individual Bloom filters38. Examples reduce the number of lookups for a large number of filters by orders of magnitude. For example, if a Bloom filter36is generated for every minute of the day, then the interwoven AMQ data structure20reduces the number of reads, the number of memory allocations, the number of CPU cycles, the number of I/O operations, and the number of translations from kernel space to user space.

FIG.12illustrates a method or flowchart for looking up the key72. The key72is hashed to a value between 0 and N hashN (Block100). The [hashN].IAMQ20is opened and membership tested (Block102). If the key72is not a member (Block104), then the key72is not a member of any N IAMQ20(Block106). If, however, the key72is a member of the [hashN].IAMQ20(Block104), then the key72is hashed to k values between 0 and n (Block108), where k is the number of hash functions for a Bloom filter36of length bit length n (e.g., hashK1, hashK2 . . . hashKk). The [hashN].IAMQ20is read k times into buffers of length T/t at offsets (hashK1*T/t),(hashK2*T/t) . . . and (hashKk*T/t) (Block110). A binary AND operation is performed across all buffers to find where any overlap occurs (Block112). After all, if an AND operation yields all 0s at any point between 0-k, then the remaining reads may be skipped. In other words, once an AND operation yields all 0s, further AND operations will always yield 0. Any remaining bit indices indicate which time units the key72is seen (Block114).

The interwoven AMQ (or Lyons) data structure20thus allows a single, simultaneous lookup of the multiple Bloom filters36. In order to look up the key72, the key72may be hashed to some number of values (typically referred to as k values between 1 and K). These individual k values may then be looked up in the single interwoven AMQ data structure20that represents a composite membership filter or bit traits of the multiple Bloom filters36. Because the interwoven AMQ data structure20interweaves and co-locates the bits38of the multiple Bloom filters36, a single simultaneous lookup of the relevant bits is performed in one sweep per hash, per k value. So, in real numbers, normally the hash for the Bloom filter36is converted into six numbers, so six conventional checks are performed in each Bloom filter36. Again using a per minute example, there would be 1,440 Bloom filters, and each Bloom filter would conventionally be read six (6) times (meaning 8,640 conventional lookups). However, by aggregating and interweaving the 1,440 Bloom filters into the single interwoven AMQ data structure20, only six (6) total lookups are needed. The interwoven AMQ data structure20thus requires orders of magnitude less reads, processor operations, memory, and kernel translations.

FIG.13illustrates examples of layering of filters. Any AMQ data structures (again illustrated as the Bloom filters36) may be layered to form long term and short term views, e.g., time units in minutes/hours/days. Given an interwoven AMQ (or Lyons) data structure20with one minute time units, a new interwoven AMQ data structure20may be formed on an hourly basis by collapsing the file n bits at a time (perhaps using an OR operator). AsFIG.13illustrates, suppose the interweave operation40creates a second .IAMQ20based on 4 minute increments. The four minute .IAMQ20can be used first, and the one minute .IAMQ20to further narrow the scope. In actual practice though, these time schemes would be closer to month/day/hour/minute for larger datasets.

Sharding may also be used. For any file-backed filter, regardless of the type the AMQ filter, the file-backed filter may be split into multiple distinct files or shards. Each shard would essentially be an independent filter. In order to insert an element into the set of sharded filters, the element would be passed through a deterministic hash to resolve which shard should be used. The element can then be inserted to that single filter shard using the mechanisms defined by the filter type. To check if the element is a member of a sharded filter set, the deterministic hash is repeated to resolve which shard to inspect. The examples then use the filter as normal to check inclusion. Suppose, for example, that each Bloom filter is 10 MB/minute. Over 60 minutes, then, examples may interweave those separate Blooms361-60as the single interwoven AMQ (or Lyons) data structure20having a 600 MB size. The software application28may further cause the computer system22to perform a sharding operation that breaks up that 600 MB interwoven AMQ data structure20. The software application28may generate smaller Bloom filters36than 10 MB/minute using smaller time intervals. For example, instead of using a 10 MB Bloom filter, the examples may use 1 MB Bloom filters as different shards. When any search element (such as the key72) is received, its corresponding hash value may be used to determine which Bloom shard to which it belongs. The examples may then inspect the time-series Bloom filter36of that shard. Suppose there are ten (10) time-series Bloom filters, and they all cover the same 60 minutes, but they cover different subsets of elements. When the search element is received, its hash value determines which of those (10) time-series Bloom filters is the Bloom filter responsible for the element. The bitwise operations may be performed against just that interwoven AMQ data structure20. And so, the reason to do that is that the smaller Bloom filters may be used because they have less elements in them. So, if ten (10) Bloom filters are used, each Bloom filter may use one-tenth the size for each shard or each sub-filter. Put another way, if a lot of data is inserted into a Bloom filter, then that Bloom filter needs to be very large. More data may be inserted into a 100 MB Bloom filter than a 5 MB Bloom filter. So, if the 5 MB Bloom filter is used, but a 100-megabyte Bloom filter's worth of data is required, the interweave operation40may use twenty (20) individual Bloom filters of 5 MB each. Before data is inserted, examples may determine which of those twenty (20) Bloom filters is associated with the hash of the element to be inserted. Once the correct 5 MB Bloom filter is identified, the k hashes may be performed to check the individual bits of that Bloom filter. The sharding examples thus provide optimizations when using a large time-series or a large number of elements. These situations may cause the interwoven AMQ data structure20grow large, perhaps by a factor of however many time windows are being used. Using 1-minute intervals over one hour (e.g., 60×60), this windowing leads to very large file sizes. The examples mitigate large file sizes, which further helps with optimizing file transfer protocols.

Pre-fixing may be used. Any interwoven AMQ data structure20may set a prefix of the n bits38that represent a Bloom filter36that is the result of every unit filter combined. This prefix can first be read into the memory device30and checked prior to checking all subsequent bit positions94. This results in a minimum of1read per lookup and a maximum of k+1 reads.

FIG.14illustrates more examples of interwoven AMQ data structures (again illustrated as the Bloom filters36). The interweave operation40may be programmed to randomly or particularly identify, read, and interweave any bits38from any bit positions94. InFIG.14, for example, the interwoven AMQ (or IAMQ) data structure20is generated by starting at bit position 6 (illustrated as reference numeral946) and reading these positional bits across the time-series from each Bloom filter36. The interweave operation40may then sequentially identify, read, aggregate, and interweave the bits38from bit positions 7, 8, and 9. The interweave operation40may then return and sequentially identify, read, and interweave the bits38from bit positions 0-5 from each Bloom filter36. The interweave operation40may thus be programmed to start from any bit38at any bit position94that suits some performance objective.

FIGS.15-16illustrate examples of untimed interwoven Bloom filters36. Here the interwoven AMQ (or IAMQ) data structures (again illustrated as the Bloom filters36) need not be time-based.FIG.15, for example, illustrates the Bloom filters36representing membership associated with different retail departments.FIG.16illustrates the Bloom filters36representing membership associated with different manufacturing machines. The interwoven AMQ data structure20may thus be generated by interweaving different Bloom filters36, regardless of time. Bits38may be randomly, and/or particularly, identified and read from different Bloom filters36and interweaved as desired. The interweave operation40may thus be programmed to start from any bit38at any bit position94, from any Bloom filter36, that suits some performance objective.

AsFIGS.15-16illustrate, the interweave operation40may be applied to any bit-setting AMQ data structures. The bits38at the bit positions94may be mapped to any arbitrary data. While time (such as reference numeral90illustrated inFIGS.6-11) is perhaps most common, the interweave operation40may merge and interweave any Bloom filters36representing any criterion (such as the above departments and machines). The interweave operation40aggregates any AMQ bit-set filters representing data across different scopes. That scope may be time-based, or the scope may be any other category. Because the interweave operation40aggregates multiple filters from distinct scopes, the interwoven AMQ (or Lyons) data structure20allows a single query to be performed across all the multiple filters.

The examples may interweave any approximate membership query (or AMQ) data sets. While there are many different types of AMQ data sets that implement bit-setting operations, the examples are described using the Bloom filters36. Because Bloom filters are known examples of AMQ data structures, this disclosure need not provide a detailed explanation. A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. An empty Bloom filter is a bit array of bits, with all the bits set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the bit array positions. To add an element, feed it to each of the k hash functions to get k array bit positions. Set the bits at all these bit positions to 1. To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array bit positions. If any of the bits at these positions is 0, the element is definitely not in the set; if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have by chance been set to 1 during the insertion of other elements, resulting in a false positive. More details of the Bloom filters36may be found in U.S. Pat. No. 8,260,910 to Schuba, et al., in U.S. Pat. No. 8,468,134 to McHugh, et al., in U.S. Pat. No. 9,842,132 to McKenna, et al., and in U.S. Pat. No. 11,494,358 to Prasad Abhinav, with all these patents incorporated herein by reference in their entireties.

The examples thus describe methods, computer software, computer systems, and computer program products that reduce search times and unnecessary accesses to memory when determining whether a given item is present in a memory. Multiple AMQ data structures (such as the Bloom filters36) are ingeniously interwoven to generate the compact and nimble interwoven AMQ (or Lyons) data structure20. The examples collapse and co-locate the multiple AMQ data structures (such as the Bloom filters36) into a single filter/bit membership representation. The examples organize the bit/byte data in such a way as to minimize reads and file loads. The interwoven AMQ data structure20eliminates individually and costly checking the multiple Bloom filters36. The examples thus minimize the number of disk reads and memory allocations when membership testing. The examples thus have many benefits, such as smaller memory requirements, faster searching of data, and more compact, effective storage of data.

FIG.17illustrates examples of a method or operations that improves computer functioning using the interwoven AMQ data structure20. The multiple approximate membership query (or AMQ) data sets34a-bare received (Block120). The interwoven AMQ data structure20is generated as a composite membership representation of the multiple AMQ datasets34a-b(Block122). The interwoven AMQ data structure is stored to improve the computer functioning by consuming less of the memory device30(Block124). The interwoven AMQ data structure may be membership tested to further to improve the computer functioning (Block126).

FIG.18illustrates more examples of a method or operations for determining a membership associated with the interwoven AMQ data structure (or IAMQ)20. The key72is received (Block130) and the membership test56is performed based on the key72and the interwoven AMQ data structure20that interweaves the bits38a-bassociated with the multiple Bloom filters36a-b(Block132). The query response74is generated and indicates the membership associated with the key72and the interwoven AMQ data structure20(Block134). If the membership test56fails or is negative (Block136), then the computer22declines to search the computer database54(Block138). If the membership test56is positive or successful (Block136), then the computer22determines a time associated with the interwoven AMQ data structure20and/or any of the Bloom filters36a-b(Block140) and determines the computer database54that is associated with the interwoven AMQ data structure20(Block142). The computer22searches the computer database54(Block144).

FIG.19illustrates still more examples of a method or operations for determining a membership associated with the key72. The multiple Bloom filters36a-bare received (Block150). A bit38of the n bits from each Bloom filter36that corresponds to each bit position 0, 1, 2, . . . , n is read (Block152). The interwoven AMQ data structure (or IAMQ)20is generated by interweaving the bits38read from each Bloom filter36(Block154). The key72(or its associated hash value) is membership tested based on the interwoven AMQ data structure20(Block156). The membership is determined (Block158).

FIG.20illustrates a more detailed example of the operating environment.FIG.20is a more detailed block diagram illustrating the computer system22. The software application28, implementing the interweave operation40, is stored in the memory subsystem or device30. One or more of the processors32communicate with the memory subsystem or device30and execute the software application28. Examples of the memory subsystem or device30may include Dual In-Line Memory Modules (DIMMs), Dynamic Random Access Memory (DRAM) DIMMs, Static Random Access Memory (SRAM) DIMMs, non-volatile DIMMs (NV-DIMMs), storage class memory devices, Read-Only Memory (ROM) devices, compact disks, solid-state, and any other read/write memory technology. Because the computer system22is known to those of ordinary skill in the art, no detailed explanation is needed.

The computer system22may have any embodiment. As this disclosure explains, the computer system22may be embodied as the server24. The computer system22, though, may be embodied as any component of the cloud computing environment62, such as a switch, a router, a storage component, and/or a management component. The computer system22may also be embodied as a smartphone, a laptop/tablet computer, a smartwatch, a television, an audio device, a remote control, and/or a recorder. The computer system22may also be embodied as a smart appliance, such as washers, dryers, and refrigerators. Indeed, as cars, trucks, and other vehicles grow in electronic usage and in processing power, the software application28, implementing the interweave operation40, may be easily incorporated into any vehicular controller.

The above examples of interwoven AMQ data structures may be applied regardless of the networking environment. The software application28, implementing the interweave operation40, may be easily adapted to execute in stationary or mobile devices having wide-area networking (e.g., 4G/LTE/5G cellular), wireless local area networking (WI-FI®), near field, and/or BLUETOOTH® capability. The software application28, implementing the interweave operation40, may be applied to stationary or mobile devices utilizing any portion of the electromagnetic spectrum and any signaling standard (such as the IEEE 802 family of standards, GSM/CDMA/TDMA or any cellular standard, and/or the ISM band). The software application28, implementing the interweave operation40, however, may be applied to any processor-controlled device operating in the radio-frequency domain and/or the Internet Protocol (IP) domain. The examples may be applied to any processor-controlled device utilizing a distributed computing network, such as the Internet (sometimes alternatively known as the “World Wide Web”), an intranet, a local-area network (LAN), and/or a wide-area network (WAN). The examples may be applied to any processor-controlled device utilizing power line technologies, in which signals are communicated via electrical wiring. Indeed, the many examples may be applied regardless of physical componentry, physical configuration, or communications standard(s).

The computer system22may utilize any processing component, configuration, or system. For example, the examples may be easily adapted to any desktop, mobile, or server central processing unit, graphics processor, ASIC, or chipset offered by INTEL®, ADVANCED MICRO DEVICES®, ARM®, APPLE″, TAIWAN SEMICONDUCTOR MANUFACTURING®, QUALCOMM®, or any other manufacturer. The computer system22may even use multiple central processing units or chipsets, which could include distributed processors or parallel processors in a single machine or multiple machines. The central processing unit or chipset can be used in supporting a virtual processing environment. The central processing unit or chipset could include a state machine or logic controller. When any of the central processing units or chipsets execute instructions to perform “operations,” this could include the central processing unit or chipset performing the operations directly and/or facilitating, directing, or cooperating with another device or component to perform the operations.

The examples may inspect packetized communications. When the computer system22communicates via any communications network, information may be collected, sent, and retrieved. The information may be formatted or generated as packets of data according to a packet protocol (such as the Internet Protocol). The packets of data contain bits or bytes of data describing the contents, or payload, of a message. A header of each packet of data may be read or inspected and contain routing information identifying an origination address and/or a destination address.

The examples may utilize any signaling standard. The cloud computing environment62, for example, may mostly use wired networks to interconnect the network members60. However, the cloud computing environment62may utilize any communications device using the Global System for Mobile (GSM) communications signaling standard, the Time Division Multiple Access (TDMA) signaling standard, the Code Division Multiple Access (CDMA) signaling standard, the “dual-mode” GSM-ANSI Interoperability Team (GAIT) signaling standard, or any variant of the GSM/CDMA/TDMA signaling standard. The cloud computing environment62may also utilize other standards, such as the I.E.E.E. 802 family of standards, the Industrial, Scientific, and Medical band of the electromagnetic spectrum, BLUETOOTH®, low-power or near-field, and any other standard or value.

The software application28, implementing the interweave operation40, may be physically embodied on or in a computer-readable storage medium. This computer-readable medium, for example, may include CD-ROM, DVD, tape, cassette, floppy disk, optical disk, memory card, memory drive, and large-capacity disks. This computer-readable medium, or media, could be distributed to end-subscribers, licensees, and assignees. A computer program product comprises processor-executable instructions for generating and/or searching interwoven AMQ data structures, as the above paragraphs explain.

The diagrams, schematics, illustrations, and the like represent conceptual views or processes illustrating examples of interwoven AMQ data structures. The functions of the various elements shown in the figures may be provided through the use of dedicated hardware as well as hardware capable of executing instructions. The hardware, processes, methods, and/or operating systems described herein are for illustrative purposes and, thus, are not intended to be limited to any particular named manufacturer or service provider.

It will also be understood that, although the terms first, second, and so on, may be used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another. For example, a first computer or container could be termed a second computer or container and, similarly, a second device could be termed a first device without departing from the teachings of the disclosure.