Sparse and non-sparse data management method and system

Details Sparse and non-sparse data management method and system Sparse and non-sparse data management method and system

2006-03-07

2006-03-07

Ali, Mohammad (Department: 2167)

Data processing: database and file management or data structures

Database design

Data structure types

C710S028000, C370S401000

Reexamination Certificate

active

07010548

ABSTRACT:
A method and system for tracking data packets that utilizes a tree data structure with a recursive pruning algorithm that collapses the branches of the tree that represent contiguous ranges or regions to maintain a minimally optimum memory size. Each contiguous region is identified by a node, which includes the start and end range of packets. Each node further includes left and right pointer elements, which point to adjacent lower and higher nodes, respectively. When a packet sequence number is not contiguous with any other sequence numbers previously received, a new node is created that contains only a single value range. When a new packet is received that has a contiguous sequence number (i.e., immediately preceding or succeeding sequence number), the original node is updated so as to reflect the new contiguous range. Additionally, if this new contiguous range is contiguous with another node's range, the two nodes are “collapsed” into a new single node containing the new expanded contiguous range. Furthermore, the algorithm can quickly and efficiently determine whether there are any missing packets by simply determining if there is only a single node remaining after a designated “last packet” has been received.

REFERENCES:
patent: 5430727 (1995-07-01), Callon
patent: 5463777 (1995-10-01), Bialkowski et al.
patent: 5873078 (1999-02-01), Angle et al.
patent: 6014659 (2000-01-01), Wilkinson et al.
patent: 6615383 (2003-09-01), Talluri et al.
patent: 6735647 (2004-05-01), Boyd et al.

Affiliated with

Also associated with

Rating

Sparse and non-sparse data management method and system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sparse and non-sparse data management method and system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse and non-sparse data management method and system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3536777