Self-adaptive prefix encoding for stable node identifiers

Details Self-adaptive prefix encoding for stable node identifiers Self-adaptive prefix encoding for stable node identifiers

2011-05-03

2011-05-03

Pham, Khanh B (Department: 2166)

Data processing: database and file management or data structures

Database design

Database and data structure management

C707S790000

Reexamination Certificate

active

07937413

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.

REFERENCES:
patent: 4794528 (1988-12-01), Hirose et al.
patent: 5151697 (1992-09-01), Bunton
patent: 5608904 (1997-03-01), Chaudhuri et al.
patent: 5706498 (1998-01-01), Fujimiya et al.
patent: 5883589 (1999-03-01), Takishima et al.
patent: 6058397 (2000-05-01), Barrus et al.
patent: 6085188 (2000-07-01), Bachmann
patent: 6263332 (2001-07-01), Nasr et al.
patent: 6295526 (2001-09-01), Kreiner et al.
patent: 6313766 (2001-11-01), Langendorf et al.
patent: 6353820 (2002-03-01), Edwards et al.
patent: 6381605 (2002-04-01), Kothuri et al.
patent: 6437799 (2002-08-01), Shinomi
patent: 6510434 (2003-01-01), Anderson et al.
patent: 6539369 (2003-03-01), Brown
patent: 6539396 (2003-03-01), Bowman-Amuah
patent: 6563441 (2003-05-01), Gold
patent: 6587057 (2003-07-01), Scheuermann
patent: 6610104 (2003-08-01), Lin et al.
patent: 6647391 (2003-11-01), Smith et al.
patent: 6810414 (2004-10-01), Brittain
patent: 6889226 (2005-05-01), O'Neil et al.
patent: 7072904 (2006-07-01), Najork et al.
patent: 7080065 (2006-07-01), Kothuri et al.
patent: 7246138 (2007-07-01), McCauley et al.
patent: 7274671 (2007-09-01), Hu
patent: 7293005 (2007-11-01), Fontoura et al.
patent: 7293028 (2007-11-01), Cha et al.
patent: 2002/0099715 (2002-07-01), Jahnke et al.
patent: 2002/0120679 (2002-08-01), Hayton et al.
patent: 2002/0145545 (2002-10-01), Brown
patent: 2003/0014397 (2003-01-01), Chau et al.
patent: 2003/0023528 (2003-01-01), Wilce et al.
patent: 2003/0088639 (2003-05-01), Lentini et al.
patent: 2004/0002939 (2004-01-01), Arora et al.
patent: 2004/0044959 (2004-03-01), Shanmugasundaram et al.
patent: 2004/0111672 (2004-06-01), Bowman et al.
patent: 2004/0128296 (2004-07-01), Krishnamurthy et al.
patent: 2004/0167864 (2004-08-01), Wang et al.
patent: 2004/0167915 (2004-08-01), Sundararajan et al.
patent: 2004/0205638 (2004-10-01), Thomas et al.
patent: 2005/0055336 (2005-03-01), Hui et al.
patent: 2005/0125431 (2005-06-01), Emmick et al.
patent: 2005/0192955 (2005-09-01), Farrell
patent: 2005/0210052 (2005-09-01), Aldridge
patent: 08190543 (1996-07-01), None
patent: 2001034619 (2001-02-01), None
patent: 2002269139 (2002-09-01), None
patent: 2004178084 (2004-06-01), None
patent: 0142881 (2001-06-01), None
patent: 0203245 (2002-01-01), None
Peter Elias, “Interval and Recency Rank Source Coding Two On-Line Adaptive Variable Length Schemes” IEEE Transactions on Information Theory, vol. IT-33, No. 1, Jan. 1987, pp. 3-10.
Nasser Tadayon et al., “Grouping Algorithm for Lossless Data Compression” IEEE Computer Society, Data Compression Conference Mar.-Apr. 1998.
Grust, “Accelerating XPath Location Steps,”ACM SIGMOD 2002, Jun. 4-6, 2002, Madison, Wisconsin, pp. 109-120.
Bremer et al., “An Efficient XML Node Identification and Indexing Scheme,” Technical Report CSE-2003-04, Dept. of Computer Science, University of California at Davis, 2003, 14pgs.
Bruno et al., “Holistic Twig Joins: Optimal XML Pattern Matching,”ACM SIGMOD 2002, Jun. 4-6, 2002, Madison, Wisconsin, pp. 310-321.
Li et al., “Indexing and Querying XML Data for Regular Path Expressions”Proceedings of the 27thInternational Conference on Very Large Data Bases, Sep. 11-14, 2001, Rome, Italy, pp. 361-370.
Cohen et al., “Labeling Dynamic XML Trees,”Proceedings of the 21stACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Jun. 4-6, 2002, Madison, Wisconsin, pp. 271-281.
Jagadish et al., “On Effective Multi-Dimensional Indexing for Strings,”ACM SIGMOD 2000, May 14-19, 2000, Dallas, Texas, pp. 403-414.
“Technique for Performing Generalized Prefix Matches,”IBM Technical Disclosure Bulletin, V40, N3, Mar. 1997, pp. 189-200.
Wang et al., “ViST: A Dynamic Index Method for Querying XML Data by Tree Structures,”ACM SIGMOD 2003, Jun. 9-12, 2003, San Diego, California, pp. 110-121.
Guo et al., “XRANK: Ranked Keyword Search over XML Documents,”ACM SIGMOD 2003, Jun. 9-12, 2003, San Diego, California, pp. 16-27.
Garofalakis et al., “XTRACT: A System for Extracting Document Type Descriptors from XML Documents,”ACM SIGMOD 2000, Dallas, Texas, V29, N2, pp. 165-176.
Kanne et al., “Efficient Storage of XML Data,” Universitat Mannheim, Germany, Jun. 16, 1999, pp. 1-20.
Zhang, “XML Data Model Storage,” IBM Confidential, Mar. 17, 2004, pp. 1-10.
Zhang, “XML Data Model Storage Advanced Features,” IBM Confidential, Apr. 25, 2004, pp. 1-4.
Glance et al., “Generalized Process Structure Grammars (GPSG) for Flexible Representations of Work,” Proceedings of the 1996 AMC Conf. on Computer Supported Cooperative Work, pp. 180-189.
Fiebig et al., “Anatomy of a Native XML Base Management System,” VLDB Journal, V11, 2002, pp. 292-314.
Amer-Yahia et al., “Logical and Physical Support for Heterogeneous Data,” Proceedings of the 11th Int'l Conf. on Information and Knowledge Management (CIKM2002), New York, NY, Nov. 4-9, 2002, pp. 270-281.

Affiliated with

Also associated with

Rating

Self-adaptive prefix encoding for stable node identifiers does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Self-adaptive prefix encoding for stable node identifiers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-adaptive prefix encoding for stable node identifiers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2629451