Temporally ordered binary search method and system
US5978795A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jan 14, 1997 |
| Grant date | Nov 2, 1999 |
| Priority date | — |
| Expiry date | Jan 14, 2017 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99936
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.