SYSTEMS AND METHODS FOR STORING DATA IN AN INTEGRATED ARRAY AND LINKED LIST BASED STRUCTURE

• US 20200133942A1
• Filed: 10/25/2019
• Published: 04/30/2020
• Est. Priority Date: 10/26/2018
• Status: Active Grant

• Current Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Original Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Inventors: BARVE, Mahesh Damodar, PURANIK, Sunil Anant, NAMBIAR, Manoj, RODI, Swapnil
• Granted Patent: US 11,263,203 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Data processing and storage is an important part of a number of applications. Conventional data processing and storage systems utilize either a full array structure or a full linked list structure for storing data wherein the array consumes large amount of memory and linked list provides slow processing. Thus, conventional systems and methods are not capable of providing simultaneous optimization of memory consumption and time efficiency. The present disclosure provides an efficient way of storing data by creating an integrated array and linked list based structure. The data is stored in the integrated array and linked list based structure by using a delta based mechanism. The delta based mechanism helps in determining the location in the integrated array and linked list based structure where the data should be stored. The present disclosure incorporates the advantages of both array and linked list structure resulting in reduced memory consumption and latency.

Claims

1. A processor-implemented method, comprising:

receiving, by a processor, a plurality of input data and a corresponding reference data for each of the plurality of input data;

creating a data structure for storing the plurality of input data, wherein the data structure is created in at least one form comprising an array structure or a linked list, and wherein the created data structure further comprises a plurality of data pointers defined for each of the plurality of input data;

determining a unique set of data pointers from the plurality of data pointers for each of the plurality of input data, wherein the unique set of data pointers is determined by computing a range of candidate data pointers varying around the corresponding reference data;

defining (i) the unique set of data pointers in the array structure and (ii) remaining data pointers from the plurality of data pointers, in the linked list;

determining for a new input data, using a delta based mechanism, a data pointer from one of (i) the unique set of data pointers defined in the array structure or (ii) the remaining data pointers from the plurality of data pointers, in the linked list, wherein during determination of the data pointer a node corresponding to the determined data pointer is created; and

storing the new input data at an address of the created node corresponding to the determined data pointer comprised in one of the array structure or the linked list.

2. The method of claim 1, wherein the range is configurable and is determined based on the corresponding reference data.

3. The method of claim 1, wherein the delta based mechanism determines a difference between value of the reference data and the new input data, and wherein the difference is indicative of an index value for determining the data pointer.

4. The method of claim 1, further comprising forming another linked list from the created node corresponding to the determined data pointer for storing subsequent input data.

5. The method of claim 1, further comprising dynamically updating at least one of the array structure and the linked list based on the new input data and the reference data.

6. A system, comprising:

a memory;

one or more communication interfaces; and

one or more hardware processors coupled to said memory through said one or more communication interfaces, wherein said one or more hardware processors are configured to;

receive a plurality of input data and a corresponding reference data for each of the plurality of input data;

create a data structure for storing the plurality of input data, wherein the data structure is created in at least one form comprising an array structure or a linked list, and wherein the created data structure further comprises a plurality of data pointers defined for each of the plurality of input data;

determine a unique set of data pointers from the plurality of data pointers for each of the plurality of input data, wherein the unique set of data pointers is determined by computing a range of candidate data pointers varying around the corresponding reference data;

define (i) the unique set of data pointers in the array structure and (ii) remaining data pointers from the plurality of data pointers, in the linked list;

determine for a new input data, using a delta based mechanism, a data pointer from one of (i) the unique set of data pointers defined in the array structure or (ii) the remaining data pointers from the plurality of data pointers, in the linked list, wherein during determination of the data pointer a node corresponding to the determined data pointer is created; and

store the new input data at an address of the created node corresponding to the determined data pointer comprised in one of the array structure or the linked list.

7. The system of claim 6, wherein the range is configurable and is determined based on the corresponding reference data.

8. The system of claim 6, wherein the delta based mechanism determines a difference between value of the reference data and the new input data, and wherein the difference is indicative of an index value for determining the data pointer.

9. The system of claim 6, wherein said one or more hardware processors are further configured to form another linked list from the created node corresponding to the determined data pointer for storing subsequent input data.

10. The system of claim 6, wherein said one or more hardware processors are further configured to dynamically update at least one of the array structure and the linked list based on the new input data and the reference data.

11. One or more non-transitory machine readable information storage media comprising instructions which, when executed by one or more hardware processors, cause the one or more hardware processors to execute a method comprising:

receiving a plurality of input data and a corresponding reference data for each of the plurality of input data;

creating a data structure for storing the plurality of input data, wherein the data structure is created in at least one form comprising an array structure or a linked list, and wherein the created data structure further comprises a plurality of data pointers defined for each of the plurality of input data;

determining a unique set of data pointers from the plurality of data pointers for each of the plurality of input data, wherein the unique set of data pointers is determined by computing a range of candidate data pointers varying around the corresponding reference data;

defining (i) the unique set of data pointers in the array structure and (ii) remaining data pointers from the plurality of data pointers, in the linked list;

determining for a new input data, using a delta based mechanism, a data pointer from one of (i) the unique set of data pointers defined in the array structure or (ii) the remaining data pointers from the plurality of data pointers, in the linked list, wherein during determination of the data pointer a node corresponding to the determined data pointer is created; and

storing, the new input data at an address of the created node corresponding to the determined data pointer comprised in one of the array structure or the linked list.

12. The one or more non-transitory machine readable media of claim 11, wherein the range is configurable and is determined based on the corresponding reference data.

13. The one or more non-transitory machine readable media of claim 11, wherein the delta based mechanism determines a difference between value of the reference data and the new input data, and wherein the difference is indicative of an index value for determining the data pointer.

14. The one or more non-transitory machine readable media of claim 11, wherein said one or more hardware processors are further configured to form another linked list from the created node corresponding to the determined data pointer for storing subsequent input data.

15. The one or more non-transitory machine readable media of claim 11, wherein said one or more hardware processors are further configured to dynamically update at least one of the array structure and the linked list based on the new input data and the reference data.