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

Means for Updating and Searching Sparse Tables

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

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

This article describes an enhancement of a computer system that permits efficient search and updating of sparse bit-vectors. Search time is proportional to the number of 1s in the vector, which is a small fraction of the length of the bit vector. (Image Omitted)

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

Page 1 of 6

Means for Updating and Searching Sparse Tables

This article describes an enhancement of a computer system that permits efficient search and updating of sparse bit-vectors. Search time is proportional to the number of 1s in the vector, which is a small fraction of the length of the bit vector.

(Image Omitted)

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.

The search problem of interest is to conduct a search that examines each entry in the sparse table, and potentially changes it. Occasionally, a new entry is added to the table.

Processing of information in a bit-vector representation often takes a time proportional to the length of the vector, whereas the amount of work to process the useful information in such a vector should only take a time proportional to the number of 1s in the vector, which could be a much smaller number. Schemes that take time proportional to the number of 1s, usually require a list of indices that contain 1s. However, the initialization time is still potentially large if the entire vector has to be filled with 0s. The objective is to have both a small initialization time and a small processing time associated with a sparse vector.

We describe a scheme for which both the initialization time and search time for bit vectors become comparable to similar times for an algorithm that uses the indices of the nonzero elements. By succeeding in reducing initialization and search cost for bit vectors, the use of bit vectors becomes very attractive, since bit vectors generally are faster to update than are lists of indices.

Bit vectors have been used to represent sparse vectors on the CDC-STAR (STring and ARray computer). On this computer, a 64-bit vector represents a 64- element vector of data. If a particular bit position contains a zero, the corresponding vector element has the value 0, and it is not explicitly stored in memory. If a bit position contains a 1, then the corresponding element has the value that is stored in a data vector associated with the bit vector. The data for the ith 1 in the bit vector is stored in the ith cell of the data vector.

Our scheme differs from the CDC STAR scheme in that the representation of sparse data is hierarchical. The CDC STAR scheme gives a maximum reduction in data space of 64 to 1 because a single bit of the bit vector can represent as much as 64 bits of a 64-bit operand whose value is 0. However, sparse matrices can be sparser than one 1 bit per 64 entries. The 64-to-1 reduction in size obtained by the bit vector representation is much less than what might be obtained by other means. The invention produces excellent compression for arbitrarily small sparsity, and produces data structures that can be searched and updated in a time proportional to the number...