Self-adaptive prefix encoding for stable node identifiers
US7937413B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 4, 2004 |
| Grant date | May 3, 2011 |
| Priority date | — |
| Expiry date | Jan 31, 2026 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/80
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A variable-length binary string is utilized to encode node identifiers in a tree for an XML document object model. A general prefix encoding scheme is followed; a node identifier is generated by the concatenation of encodings at each level of a tree along a path from a root node to another particular node. Arbitrary insertions are supported without change to existing node identifier encodings. In addition, the method provides for document order when unsigned binary string comparison is used to compare encoded node identifiers. In support of sub-document concurrency control, prefix encoding provides a way to derive ancestor-descendant relationships among nodes in a tree. Lastly, the encoding method provides a natural pre-order clustering sequence, also known as depth-first clustering. If a prefix is applied to an encoding with a level number, starting with zero at the root, width-first clustering will result. A mixed clustering can also be supported.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.