Method and system for rapid insertion of various data streams into sorted tree structures
US7016904B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 25, 2001 |
| Grant date | Mar 21, 2006 |
| Priority date | — |
| Expiry date | Jul 8, 2021 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99953
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present invention provides the method and system that redistribute the nodes of a sorted tree to enable faster data insertion. Further, the tree typically contains a fixed number of levels, each comprising a fixed number of nodes. Each node in the tree is indexed and each leaf node may comprise a number of data segments. An increment is empirically calculated as space redistributed among non-empty leaf nodes. Furthermore, when a data segment is inserted and certain conditions are met, a data structure with a marked head and tail effectively “traverses” the tree from one end to the other searching for empty leaf nodes. In cases where the data structure encounters an empty leaf node, the data structure continues traversing unless empirically determined conditions stipulate that the process halts until the next data segment insertion before continuing. Moreover, in cases where the data structure encounters a non-empty leaf node, the contents of the node are copied from the head to the tail of the data structure. When the node has been copied, the data structure updates the tree to ensure that a lookup operation on the copied node remains valid and that the invariants of the tree h…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.