# US 2019/0318042 A1 · Optimizing memory usage for a hyperloglog estimator > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0318042 A1 - Document ID: US20190318042A1 - Status: Published application - Kind: A1 - Application number: 15/952,036 - Filed: 2018-04-12 - Published: 2019-10-17 - Earliest claimed: 2018-04-12 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Parag Nandan PAUL; Edgars SEDOLS; Sudin BHAT; Gjorgji GJEORGJIEVSKI - Web page: https://patentgrep.com/patent/US20190318042A1 ## CPC - G06F 16/28: Databases characterised by their database models, e.g. relational or object models - G06F 16/90348: {by searching ordered data, e.g. alpha-numerically ordered data} - G06F 16/901: Indexing; Data structures therefor; Storage structures (for retrieval from the web G06F16/951) - G06F 16/9038: Presentation of query results - G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for optimizing memory usage for a hyperloglog (HLL) estimator is disclosed. When a multiset is applied to an HLL estimator, a sparse representation of a sketch may be created. The sparse representation may be sorted whenever a total number of buckets in the sparse representation is evenly divisible by a sorting threshold and is also less than a transition threshold. The sparse representation may be converted to a dense representation when the number of buckets in the sparse representation reaches the transition threshold. ## Claims ### Claim 1 A method for optimizing memory usage for a hyperloglog (HLL) estimator, comprising: creating a sparse representation of a sketch that represents information generated by applying a multiset to the HLL estimator; sorting the sparse representation of the sketch whenever a total number of buckets in the sparse representation is evenly divisible by a sorting threshold and is also less than a transition threshold; and converting the sparse representation of the sketch to a dense representation of the sketch when the total number of buckets in the sparse representation reaches the transition threshold. ### Claim 2 (depends on 1) The method of claim 1, wherein the sparse representation of the sketch comprises: a sorted portion; a header that comprises a count of the total number of buckets stored in the sparse representation; and an unsorted portion. ### Claim 3 (depends on 1) The method of claim 1, further comprising: obtaining a bucket index and a value corresponding to an element in the multiset; determining that the bucket index is not already represented in the sparse representation of the sketch; and adding a new bucket to the sparse representation of the sketch. ### Claim 4 (depends on 3) The method of claim 3, wherein: the sparse representation of the sketch comprises a sorted portion and an unsorted portion; and adding the new bucket to the sparse representation comprises adding the new bucket to an end of the unsorted portion. ### Claim 5 (depends on 3) The method of claim 3, wherein: the sparse representation of the sketch comprises a header; the header comprises a count of the total number of buckets stored in the sparse representation; and the method further comprises updating the count in response to adding the new bucket. ### Claim 6 (depends on 1) The method of claim 1, wherein the sparse representation of the sketch comprises a sorted portion, a header that comprises a count of the total number of buckets stored in the sparse representation, and an unsorted portion, the method further comprising: obtaining a bucket index and a value corresponding to an element in the multiset; determining, from the header, that the bucket index is outside of a range of bucket indices corresponding to the sorted portion; and searching for the bucket index in the unsorted portion but not the sorted portion. ### Claim 7 (depends on 1) The method of claim 1, wherein each bucket within the sparse representation is represented using no more than eighteen bits. ### Claim 8 (depends on 1) The method of claim 1, further comprising: obtaining a bucket index and a new value corresponding to an element in the multiset; determining that the bucket index is already represented in the sparse representation of the sketch; determining that the new value is greater than an existing value that is stored in a bucket corresponding to the bucket index in the sparse representation; and replacing the existing value in the bucket with the new value. ### Claim 9 (depends on 1) The method of claim 1, further comprising: obtaining a bucket index and a new value corresponding to an element in the multiset; determining that the bucket index is already represented in the sparse representation of the sketch; determining that the new value is less than an existing value that is stored in a bucket corresponding to the bucket index in the sparse representation; and discarding the new value without replacing the existing value in the bucket. ### Claim 10 (depends on 1) The method of claim 1, wherein the sparse representation of the sketch is represented in a compact format comprising contiguous memory locations. ### Claim 11 A system configured to optimize memory usage for a hyperloglog (HLL) estimator, comprising: one or more processors; memory in electronic communication with the one or more processors; and instructions stored in the memory, the instructions being executable by the one or more processors to: create a sparse representation of a sketch that represents information generated by applying a multiset to the HLL estimator; sort the sparse representation of the sketch whenever a total number of buckets in the sparse representation is evenly divisible by a sorting threshold and is also less than a transition threshold; and convert the sparse representation of the sketch to a dense representation of the sketch when the total number of buckets in the sparse representation reaches the transition threshold. ### Claim 12 (depends on 11) The system of claim 11, wherein the sparse representation of the sketch comprises: a sorted portion; a header that comprises a count of the total number of buckets stored in the sparse representation; and an unsorted portion. ### Claim 13 (depends on 11) The system of claim 11, wherein the instructions are also executable by the one or more processors to: obtain a bucket index and a value corresponding to an element in the multiset; determine that the bucket index is not already represented in the sparse representation of the sketch; and add a new bucket to the sparse representation of the sketch. ### Claim 14 (depends on 13) The system of claim 13, wherein: the sparse representation of the sketch comprises a sorted portion and an unsorted portion; and adding the new bucket to the sparse representation comprises adding the new bucket to an end of the unsorted portion. ### Claim 15 (depends on 13) The system of claim 13, wherein: the sparse representation of the sketch comprises a header; the header comprises a count of the total number of buckets stored in the sparse representation; and the instructions are also executable by the one or more processors to update the count in response to adding the new bucket. ### Claim 16 (depends on 11) The system of claim 11, wherein the sparse representation of the sketch comprises a sorted portion, a header that comprises a count of the total number of buckets stored in the sparse representation, and an unsorted portion, and wherein the instructions are also executable by the one or more processors to: obtain a bucket index and a value corresponding to an element in the multiset; determine, from the header, that the bucket index is outside of a range of bucket indices corresponding to the sorted portion; and search for the bucket index in the unsorted portion but not the sorted portion. ### Claim 17 (depends on 11) The system of claim 11, wherein each bucket within the sparse representation is represented using no more than eighteen bits. ### Claim 18 (depends on 11) The system of claim 11, wherein the instructions are also executable by the one or more processors to: obtain a bucket index and a new value corresponding to an element in the multiset; determine that the bucket index is already represented in the sparse representation of the sketch; determine that the new value is greater than an existing value that is stored in a bucket corresponding to the bucket index in the sparse representation; and replace the existing value in the bucket with the new value. ### Claim 19 (depends on 11) The system of claim 11, wherein the instructions are also executable by the one or more processors to: obtain a bucket index and a new value corresponding to an element in the multiset; determine that the bucket index is already represented in the sparse representation of the sketch; determine that the new value is less than an existing value that is stored in a bucket corresponding to the bucket index in the sparse representation; and discard the new value without replacing the existing value in the bucket. ### Claim 20 A method for optimizing memory usage for a hyperloglog (HLL) estimator, comprising: sorting a sparse representation of a sketch whenever a total number of buckets in the sparse representation is evenly divisible by a sorting threshold and is also less than a transition threshold, wherein the sparse representation comprises an indication of the total number of buckets stored in the sparse representation; and converting the sparse representation of the sketch to a dense representation of the sketch when the total number of buckets in the sparse representation reaches the transition threshold.