IP Library › Granted Patent US 12,149,266

Granted Patent B2

US 12,149,266 · App. 17/923,499 · Granted Nov 19, 2024

Exploiting locality of prime data for efficient retrieval of data that has been losslessly reduced using a prime data sieve

Inventors: Harshvardhan Sharangpani (Los Altos Hills, CA); Shekhar S. Deshkar (Pune, IN)

Assignee: Ascava, Inc.

H03M7/3091 H03M7/6058

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 12,149,266
App. No.: 17/923,499
Granted: Nov 19, 2024
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

An amount of memory needed to hold prime data elements during reconstitution may be determined by examining the creation and usage of prime data elements and their spatial and temporal characteristics during data distillation.

Claims (86)

1. A method, comprising:

factorizing a dataset into a sequence of data elements;

generating a losslessly reduced dataset by, for each data element in the sequence of data elements, either (1) converting the data element into a prime data element and setting a creation locator address and a last-used locator address associated with the prime data element to be equal to an address of the data element in the dataset, (2) if the data element is a duplicate of a first previously created prime data element, replacing the data element with a reference to the first previously created prime data element and setting a last-used locator address associated with the first previously created prime data element to be equal to the address of the data element in the dataset, or (3) if the data element is not a duplicate of any previously created prime data elements, replacing the data element with a reference to a second previously created prime data element and a sequence of transformations which, when applied to the second previously created prime data element, results in the data element, and setting a last-used locator address associated with the second previously created prime data element to be equal to the address of the data element in the dataset; and

using creation locator addresses and last-used locator addresses associated with the prime data elements to determine an amount of memory that is expected to be used during reconstitution of the dataset from the losslessly reduced dataset, wherein the amount of memory allows prime data elements to be streamed in from storage and retained in memory as needed for reconstitution, thereby eliminating the need for random storage accesses to fetch prime data elements during reconstitution.

2. The method of claim 1 , wherein said using creation locator addresses and last-used locator addresses associated with the prime data elements to determine the amount of memory used during reconstitution of the dataset from the losslessly reduced dataset comprises:

stepping through locator addresses, wherein for a given locator address,

determining a first set of prime data elements by computing a difference between (1) a second set of prime data elements whose associated creation locator addresses are less than or equal to the given locator address, and (2) a third set of prime data elements whose associated last-used locator addresses are less than the given locator address, and

determining a memory amount value associated with the given locator address by summing sizes of the first set of prime data elements; and

determining a maximum memory amount value from the memory amount values associated with the locator addresses.

3. The method of claim 1 , wherein said using creation locator addresses and last-used locator addresses associated with the prime data elements to determine the amount of memory used during reconstitution of the dataset from the losslessly reduced dataset comprises:

partitioning locator addresses into a set of locator address ranges;

stepping through the set of locator address ranges, wherein for a given locator address range,

determining a first set of prime data elements by computing a difference between (1) a second set of prime data elements whose associated creation locator addresses is less than or equal to the ending address of the given locator address range, and (2) a third set of prime data elements whose associated last-used locator addresses is less than the starting address of the given locator address range, and

determining a memory amount value associated with the given locator address range by summing sizes of the first set of prime data elements; and

determining a maximum memory amount value from the memory amount values associated with the set of locator address ranges.

4. The method of claim 1 , further comprising:

allocating memory of a size that is greater than or equal to the determined amount of memory; and

reconstituting the dataset from the losslessly reduced dataset using the allocated memory, wherein prime data elements are streamed in from storage into the allocated memory as needed, and wherein when a given prime data element is used to reconstitute a data element, the given prime data element is removed from the allocated memory after reconstituting the data element if the last-used locator address of the given prime data element is equal to the address of the reconstituted data element.

5. The method of claim 1 , wherein each prime data element is associated with a re-use count which is incremented each time the prime data element is re-used for losslessly reducing the data element by replacing the data element with either a reference to the prime data element or the reference to the prime data element and a sequence of transformations, the method further comprising:

allocating memory of a size greater than or equal to the determined amount of memory; and

reconstituting the dataset from the losslessly reduced dataset using the allocated memory, wherein prime data elements are streamed in from storage into the allocated memory as needed, wherein a re-use count associated with a given prime data element is decremented each time the given prime data element is re-used for reconstituting a data element, and wherein the given prime data element is removed from the allocated memory when the re-use count associated with the given prime data element is equal to zero.

6. The method of claim 1 , wherein the address of the data element is a sequence number of the data element in the sequence of data elements.

7. The method of claim 1 , further comprising:

receiving a memory budget value which is a maximum amount of memory that is allowed to be used during reconstitution of the dataset from the losslessly reduced dataset; and

while said generating the losslessly reduced dataset,

periodically estimating a partial amount of memory that is expected to be used during reconstitution of the dataset from the losslessly reduced dataset thus far, wherein the partial amount of memory is estimated based on creation locator addresses and last-used locator addresses,

in response to determining that the partial amount of memory is within a threshold distance from the memory budget value, creating a losslessly reduced data lot that corresponds to a portion of the dataset that has been losslessly reduced thus far, and

resuming said generating the losslessly reduced dataset using a new data lot that starts at a current location in the dataset.

8. A non-transitory computer-readable medium storing instructions, which when executed by a computer, cause the computer to:

factorize a dataset into a sequence of data elements;

generate a losslessly reduced dataset by, for each data element in the sequence of data elements, either (1) converting the data element into a prime data element and setting a creation locator address and a last-used locator address associated with the prime data element to be equal to an address of the data element in the dataset, (2) if the data element is a duplicate of a first previously created prime data element, replacing the data element with a reference to the first previously created prime data element and setting a last-used locator address associated with the first previously created prime data element to be equal to the address of the data element in the dataset, or (3) if the data element is not a duplicate of any previously created prime data elements, replacing the data element with a reference to a second previously created prime data element and a sequence of transformations which, when applied to the second previously created prime data element, results in the data element, and setting a last-used locator address associated with the second previously created prime data element to be equal to the address of the data element in the dataset; and

use creation locator addresses and last-used locator addresses associated with the prime data elements to determine an amount of memory that is expected to be used during reconstitution of the dataset from the losslessly reduced dataset, wherein the amount of memory allows prime data elements to be streamed in from storage and retained in memory as needed for reconstitution, thereby eliminating the need for random storage accesses to fetch prime data elements during reconstitution.

9. The non-transitory computer-readable medium of claim 8 , wherein said using creation locator addresses and last-used locator addresses associated with the prime data elements to determine the amount of memory used during reconstitution of the dataset from the losslessly reduced dataset comprises:

stepping through locator addresses, wherein for a given locator address,

determining a memory amount value associated with the given locator address by summing sizes of the first set of prime data elements; and

determining a maximum memory amount value from the memory amount values associated with the locator addresses.

10. The non-transitory computer-readable medium of claim 8 , wherein said using creation locator addresses and last-used locator addresses associated with the prime data elements to determine the amount of memory used during reconstitution of the dataset from the losslessly reduced dataset comprises:

partitioning locator addresses into a set of locator address ranges;

stepping through the set of locator address ranges, wherein for a given locator address range,

determining a memory amount value associated with the given locator address range by summing sizes of the first set of prime data elements; and

determining a maximum memory amount value from the memory amount values associated with the set of locator address ranges.

11. The non-transitory computer-readable medium of claim 8 , storing further instructions, which when executed by the computer, cause the computer to:

allocate memory of a size that is greater than or equal to the determined amount of memory; and

reconstitute the dataset from the losslessly reduced dataset using the allocated memory, wherein prime data elements are streamed in from storage into the allocated memory as needed, and wherein when a given prime data element is used to reconstitute a data element, the given prime data element is removed from the allocated memory after reconstituting the data element if the last-used locator address of the given prime data element is equal to the address of the reconstituted data element.

12. The non-transitory computer-readable medium of claim 8 , wherein each prime data element is associated with a re-use count which is incremented each time the prime data element is re-used for losslessly reducing the data element by replacing the data element with either a reference to the prime data element or the reference to the prime data element and a sequence of transformations, and wherein the non-transitory computer-readable medium storing further instructions, which when executed by the computer, cause the computer to:

allocate memory of a size greater than or equal to the determined amount of memory; and

reconstitute the dataset from the losslessly reduced dataset using the allocated memory, wherein prime data elements are streamed in from storage into the allocated memory as needed, wherein a re-use count associated with a given prime data element is decremented each time the given prime data element is re-used for reconstituting a data element, and wherein the given prime data element is removed from the allocated memory when the re-use count associated with the given prime data element is equal to zero.

13. The non-transitory computer-readable medium of claim 8 , wherein the address of the data element is a sequence number of the data element in the sequence of data elements.

14. The non-transitory computer-readable medium of claim 8 , storing further instructions, which when executed by the computer, cause the computer to:

receive a memory budget value which is a maximum amount of memory that is allowed to be used during reconstitution of the dataset from the losslessly reduced dataset; and

while said generating the losslessly reduced dataset,

periodically estimate a partial amount of memory that is expected to be used during reconstitution of the dataset from the losslessly reduced dataset thus far, wherein the partial amount of memory is estimated based on creation locator addresses and last-used locator addresses,

in response to determining that the partial amount of memory is within a threshold distance from the memory budget value, create a losslessly reduced data lot that corresponds to a portion of the dataset that has been losslessly reduced thus far, and

resume said generating the losslessly reduced dataset using a new data lot that starts at a current location in the dataset.

15. An apparatus, comprising:

a processor; and

a non-transitory computer-readable medium storing instructions, which when executed by the processor, cause the processor to:

factorize a dataset into a sequence of data elements;

16. The apparatus of claim 15 , wherein said using creation locator addresses and last-used locator addresses associated with the prime data elements to determine the amount of memory used during reconstitution of the dataset from the losslessly reduced dataset comprises:

stepping through locator addresses, wherein for a given locator address,

determining a memory amount value associated with the given locator address by summing sizes of the first set of prime data elements; and

determining a maximum memory amount value from the memory amount values associated with the locator addresses.

17. The apparatus of claim 15 , wherein said using creation locator addresses and last-used locator addresses associated with the prime data elements to determine the amount of memory used during reconstitution of the dataset from the losslessly reduced dataset comprises:

partitioning locator addresses into a set of locator address ranges;

stepping through the set of locator address ranges, wherein for a given locator address range,

determining a memory amount value associated with the given locator address range by summing sizes of the first set of prime data elements; and

determining a maximum memory amount value from the memory amount values associated with the set of locator address ranges.

18. The apparatus of claim 15 , wherein the non-transitory computer-readable medium storing further instructions, which when executed by the processor, cause the processor to:

allocate memory of a size that is greater than or equal to the determined amount of memory; and

19. The apparatus of claim 15 , wherein each prime data element is associated with a re-use count which is incremented each time the prime data element is re-used for losslessly reducing the data element by replacing the data element with either a reference to the prime data element or the reference to the prime data element and a sequence of transformations, and wherein the non-transitory computer-readable medium storing further instructions, which when executed by the processor, cause the processor to:

allocate memory of a size greater than or equal to the determined amount of memory; and

reconstitute the dataset from the losslessly reduced dataset using the allocated memory, wherein prime data elements are streamed in from storage into the allocated memory as needed, wherein a re-use count associated with a given prime data element is decremented each time the given prime data element is re-used for reconstituting a data element, and wherein the given prime data element is removed from the allocated memory when the re-use count associated with the given prime data element is equal to zero.

20. The apparatus of claim 15 , wherein the address of the data element is a sequence number of the data element in the sequence of data elements.

21. The apparatus of claim 15 , wherein the non-transitory computer-readable medium storing further instructions, which when executed by the processor, cause the processor to:

receive a memory budget value which is a maximum amount of memory that is allowed to be used during reconstitution of the dataset from the losslessly reduced dataset; and

while said generating the losslessly reduced dataset,

resume said generating the losslessly reduced dataset using a new data lot that starts at a current location in the dataset.

Assignments (1)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 19, 2023

From: SHARANGPANI, HARSHVARDHAN; DESHKAR, SHEKHAR S.

To: ASCAVA, INC.

Reel/Frame 063375/0807 →

Continuity (2)

Provisional Application 63022945 · May 11, 2020

Related Publication 20230198549A1 · Jun 22, 2023