Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

An efficient method to store data of unknown amounts

IP.com Disclosure Number: IPCOM000038328D
Original Publication Date: 2005-Jan-31
Included in the Prior Art Database: 2005-Jan-31
Document File: 2 page(s) / 92K

Publishing Venue

IBM

Abstract

Disclosed is a solution for rapidly storing large amounts of data of unknown final size while minimising the memory used for the structure’s definition, and while allowing insertion and deletion within the data. It consists in a compromise between an fixed amounts of available memory (i.e. an array) and a linked list, in order to profit from the advantages of both structures.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

An efficient method to store data of unknown amounts

A data structure for efficiently storing large amounts of data from an input stream without any knowledge about its final size, that allows the insertion and deletion of elements within the data, is described. The two typical solutions for this problem is either allocating once an arbitrarily fixed amount of memory (an array), or allocating element by element every time one is read (a linked list). The use of an array of fixed size suggests prior knowledge of the amount of data to store furthermore, insertion and deletion implies manipulation of the entire data. The use of linked lists avoids a memory overflow, but requires more memory for the structure definition (in each link, the address of the next link in the chain is stored), and implies frequent memory allocations.

    The presented solution consists of a merge of the above alternatives: the structure is a linked list, except that each link stores an array of elements, each array initially having the same length, but which can be reduced or increased according to the ensuing deletions or insertions. This solution optimizes the amount of allocated but unused memory, avoids any risk of overflow, reduces the number of memory allocations by a factor proportional to the initial size of the arrays in each link, diminishes the time needed to access a specific position by the same factor, and uses a negligible portion of the allocated memory for the structure definition. Even though the action of inserting or deleting an element is slightly less obvious with this solution compared to a standard linked list, only the subset of data contained in the considered link and, in the worst case, in a neighbouring link, need to be manipulated.

    This method defines a link with one more information than the basic linked list: the amount of data in that link, since they do not have to be of...