Browse Prior Art Database

Means for Dynamic Allocation of Sparse Tables

IP.com Disclosure Number: IPCOM000036163D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 4 page(s) / 84K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

This article describes an enhancement of a computer system that permits efficient initialization, allocation, search, and update of sparse bit-vectors. Sparse tables are tables in which most entries are empty. Often such tables are represented as bit vectors in which 1s indicate the presence of an item, 0s indicate the absence, and the number of 1s in the vector is a very small fraction of the length of the vector.

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 48% of the total text.

Page 1 of 4

Means for Dynamic Allocation of Sparse Tables

This article describes an enhancement of a computer system that permits efficient initialization, allocation, search, and update of sparse bit-vectors. Sparse tables are tables in which most entries are empty. Often such tables are represented as bit vectors in which 1s indicate the presence of an item, 0s indicate the absence, and the number of 1s in the vector is a very small fraction of the length of the vector.

For many algorithms that deal with sparse entities, it is desirable to be able to perform operations on sparse vectors in a time that grows with the number of 1s in the vector rather than a time that depends on the full length of the vector. The operations of interest are: 1. initialize the vector to all 0s,

2. update the ith bit of the vector, and

3. search the vector to locate the first cell with a 1

bit.

The mechanism described here initializes the vector in constant time, and allocates new cells dynamically as needed. The update time is constant, and the search time to find the first 1 bit is constant as well. To find all 1 bits takes a time proportional to the number of 1 bits in the vector. Moreover, the representation is efficient in the sense that the amount of physical memory actually allocated for storing the sparse vector is enough to hold the cells with 1 bits, and just enough more to support access to these cells. Thus, actual memory utilization is proportional to the minimun amount of memory required to hold just the 1 bits of the sparse vector.

The mechanism for accessing and updating the sparse bit vector is viewed as a hardware device for the purposes of this discussion, but its implementation can be accomplished by means of a body of software subroutines that perform the same functions.

The conceptual role of the mechanism is shown in the figure, where the access mechanism is shown as a device that translates addresses of elements in a virtual sparse vector into the true physical address of a real vector. In this sense, the access mechanism may be viewed to have a function similar to an address-translation unit that is used to map virtual addresses to real addresses in large-scale computers, or is used to map main-memory addresses into cache addresses for those computers that have cache memories to hold frequently- used items.

The complete behavior of the translation mechanism is specified by giving its behavior for each of the operations of initialize, update, and search. In the discussion below, note that initialize causes the translation mechanism to clear its tables. The update operation maps a virtual index into a physical index if the index has been allocated. If the index has not been allocated, the update operation first allocates a new entry in physical memory for portion of the sparse vector that is to be accessed, then it creates an entry in the table that causes a reference to the virtual index for the data to be mapped to the physical index of...