Compressing sets of integers

Details Compressing sets of integers Compressing sets of integers

1996-07-12

1999-08-17

Kulik, Paul V.

Data processing: database and file management or data structures

Database design

Data structure types

707101, 341 51, G06F 1730

Patent

active

059408332

ABSTRACT:
In one aspect, the disclosed technique detects common leading byte patterns in the integers so that these patterns need only be stored once in the encoded byte stream. Those integers that share a common leading byte pattern are stored in truncated form, without their common leading bytes. These truncated integers may themselves be further examined to determine if any of them share additional common leading bytes beyond those already detected. Thus, the technique lends itself naturally to description using the language of trees. Integers with a common leading byte pattern are stored as child nodes, their parent being the node containing the common byte pattern. Child nodes consist only of those bytes remaining after the initial byte pattern has been extracted; the greater the number of children, the greater are the efficiency gains. All the children of a given tree or subtree are similarly examined for common leading byte patterns, ignoring those bytes that are already accounted for in their ancestor nodes. In a second aspect, the disclosed technique makes use of "clustering", a second type of locality that is not reached by the interval concept. A cluster is a sequence of singleton integers that are very close together but do not form a contiguous interval. The technique recognizes that such a cluster can be compactly stored as a bitmap, in which each active bit ("1-bit") represents a member of the cluster. The choice of bitmap size (e.g., 1 byte, 2 bytes, etc.) can be calibrated to suit the clustering characteristics of the input data set.

REFERENCES:
patent: 3656178 (1972-04-01), De Maine et al.
patent: 4606002 (1986-08-01), Waisman et al.
patent: 5218699 (1993-06-01), Brandle et al.
patent: 5247676 (1993-09-01), Ozur et al.
patent: 5274805 (1993-12-01), Ferguson et al.
patent: 5283856 (1994-02-01), Gross et al.
patent: 5363098 (1994-11-01), Antoshenkov
patent: 5406278 (1995-04-01), Graybill et al.
patent: 5530957 (1996-06-01), Koenig
patent: 5546575 (1996-08-01), Potter et al.
patent: 5551018 (1996-08-01), Hansen
patent: 5551020 (1996-08-01), Flax et al.
patent: 5585793 (1996-12-01), Antoshenkov et al.
patent: 5615366 (1997-03-01), Hansen
Shirley, John and Rosenberry, Ward, "Microsoft RPC Programming Guide", O'Reilly & Associates, 1995.
Kramer, Matt, "Baranof's MailCheck 2.6 Delivers Improved Tools", PC Week, Sep. 11, 1995, Ziff-Davis Publishing Company 1995.
Frenkel, Gary, "cc:Mail View Keeps and Eye on Your Messaging System", Network Computing, Jun. 1, 1995, CMP Publications, Inc., 1995.

Affiliated with

Also associated with

Rating

Compressing sets of integers does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Compressing sets of integers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressing sets of integers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-325835