Encoding semi-structured data for efficient search and browsing

• US 8,065,308 B2
• Filed: 10/12/2007
• Issued: 11/22/2011
• Est. Priority Date: 02/26/2001
• Status: Active Grant

• Current Assignee: DB Software, Inc.
• Original Assignee: Ori Software Development Ltd
• Inventors: Cooper, Brian, Franklin, Michael J., Shadmon, Moshe, Sample, Neal
• Primary Examiner(s): Fleurantin; Jean B
• Assistant Examiner(s): Jami; Hares
• Application Number:
  US11/979,196
• Publication Number:
  US 20080065596A1
• Time in Patent Office: 1,502 Days
• Field of Search: 707790-812, 707/736, 707/741, 707/955, 707/956, 707/999.102, 707/999.103
• US Class Current: 707/741
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/835 Query processing
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method for encoding XML tree data that includes the step of encoding the semi-structured data into strings of arbitrary length in a way that maintains non-structural and structural information about the XML data, and enables indexing the encoded XML data in a way that facilitates efficient search and browsing.

Claims

1. A method for transforming an XML data input to enable search over the XML data input or components thereof, the method comprising:

a. transforming said XML data input into a logical tree in which tags or attributes of said XML data input are nodes of the logical tree, each of said nodes representing non-structural or structural information from said XML data input;

b. labeling each of said nodes of said logical tree with tokens from a token table, the token table including tokens and matching tags or attributes being tags or attributes of said XML data input, thereby obtaining labeled nodes; and

c. creating an index from said tokens to facilitate efficient search of data in said logical tree, said index representing paths of labeled nodes in said logical tree whereas the indexing process includes transforming said paths into keys to be indexed, the keys being indexed being strings of arbitrary length that each includes both;

non-structural and structural information from said XML data input,

wherein one portion of the key comprising of tokens representing structural information and second portion of the key comprising non-structural information,

wherein the structural information is a representation of the structural markup and attributes of said XML data input, and the non-structural information represents content from the XML data input.

2. The method of claim 1, wherein said index represents the structural information, said structural information being the relationships between data items, the relationships between data items consisting of parent-child or sibling relationship.

3. The method of claim 1, wherein said index is a designated index.

4. The method of claim 1, wherein said index is a layered index.

5. The method of claim 1, wherein said index is based on a Patricia Trie.