Temporally ordered binary search method and system

Details Temporally ordered binary search method and system Temporally ordered binary search method and system

1997-01-14

1999-11-02

Amsbury, Wayne

Data processing: database and file management or data structures

Database design

Data structure types

707 4, 707 6, G06F 1730

Patent

active

059787953

ABSTRACT:
A method and system for maintaining a binary tree of pointers to a stream of data and for searching same. A novel binary tree is created by a search engine in which the nodes associated with strings in the data stream which are closer to the current data stream position are nearer the root of the tree than nodes associated with strings which are farther. As the current position in the stream is advanced, the search engine inserts a new node to the tree for that position as the root node. The tree is then restructured based on the relative value of the strings of each node while preserving the temporal order of the tree such that strings nearer the current position are associated with nodes which are closer to the root. The tree is ideal for searching data for LZ77-based data compression, since a single traversal of the tree returns the longest match length with the smallest offset.

REFERENCES:
patent: 4677550 (1987-06-01), Ferguson
patent: 5051745 (1991-09-01), Katz
patent: 5086504 (1992-02-01), Nemeth-Johannes et al.
patent: 5140321 (1992-08-01), Jung
patent: 5146571 (1992-09-01), Longan
patent: 5202986 (1993-04-01), Nickel
patent: 5281967 (1994-01-01), Jung
patent: 5446887 (1995-08-01), Berkowitz
patent: 5454102 (1995-09-01), Tang et al.
patent: 5497485 (1996-03-01), Ferguson et al.
patent: 5557786 (1996-09-01), Johnson, Jr.
patent: 5619615 (1997-04-01), Pitchaikani et al.
patent: 5619693 (1997-04-01), Troisi
patent: 5651009 (1997-07-01), Perreault et al.
patent: 5664179 (1997-09-01), Tucker
patent: 5724517 (1998-03-01), Cook et al.
patent: 5758353 (1998-05-01), Marquis
patent: 5784557 (1998-07-01), Oprescu
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5870735 (1999-02-01), Agrawal et al.
Knuth, "The Art of Computer Programming" second edition, Addison-Wesley Publishing Company, Inc, 1973, pp. 347-351.
Robert Kruse, "Data Structures & Program Design", Prentice-Hall, Inc., Englewood cliffs, New Jersey 07632, pp. 93-100, 1984.
Lin Chen and Rene Schott, "Optimal Operations on Red-Black Trees", IEEE, pp. 529-533, 1993.

Affiliated with

Also associated with

Rating

Temporally ordered binary search 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 Temporally ordered binary search method and system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Temporally ordered binary search method and system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2149766