Encoding Semi-Structured Data for Efficient Search and Browsing

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.

What is claimed is: 
     
         1 . A method for transforming Extensible Markup Language (XML) for querying, the method comprising:
 a. receiving a semi-structured data input, the semi-structured data input being an XML data input;   b. transforming said XML data input into transformed objects, each of said transformed objects including both: non-structural and structural information from said XML data input, said transformed objects being keys to be indexed to allow efficient access to information of interest,   wherein the structural information is a representation of 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 transformed objects are the keys being indexed, constituting an index, to allow efficient access to information of interest. 
     
     
         3 . The method of  claim 2 , wherein said index represents the parent/child relationship of components from the XML data input. 
     
     
         4 . The method of  claim 1 , wherein said step of transforming said XML data input includes creating or updating an index to include hierarchical information about said XML document. 
     
     
         5 . The method of  claim 1 , wherein said step of transforming said XML data input includes creating an index that maintains an order of components in said XML data input. 
     
     
         6 . A method for transforming Extensible Markup Language (XML) for querying, the system comprising:
 a. receiving a semi-structured data input, the semi-structured data input being an XML data input;   b. transforming said XML data input into keys, each of said keys including non-structural and structural information from said XML document, the keys being used to facilitate access to searched data,   wherein the structural information is the markup of said XML data input and the non-structural information is the content of said XML data input.   
     
     
         7 . The method of  claim 6 , wherein said transformation creates an index to allow efficient search. 
     
     
         8 . The method of  claim 6 , wherein said transformation creates an index containing parent/child relationship for elements in the XML document. 
     
     
         9 . The method of  claim 7 , wherein said index is a designated index. 
     
     
         10 . The method of  claim 1 , wherein said index is a designated index. 
     
     
         11 . The method of  claim 7 , wherein said index is a layered index, 
     
     
         12 . The method of  claim 1 , wherein said index is a layered index. 
     
     
         13 . The method of  claim 7 , wherein said index is based on a Patricia Trie. 
     
     
         14 . The method of  claim 1 , wherein said index is based on a Patricia Trie. 
     
     
         15 . A method for mapping semi-structured data into keys, comprising:
 determining an element within the semi-structured data;   creating one or more keys representing said element, each of the keys including both: structural and non-structural information from the semi-structured data,   wherein the structural information is derived from structural markup and attributes of said XML data input, and the non-structural information is derived from content of said XML data input.   
     
     
         16 . A computer program product that includes a storage for storing an index over keys, and
 said keys were created according to the method in  claim 15 .   
     
     
         17 . The computer program product of  claim 16 , wherein said index is a designated index. 
     
     
         18 . The computer program product of  claim 16 , wherein said index is a layered index. 
     
     
         19 . The computer program product of  claim 16 , wherein said index is based on a Patricia Trie. 
     
     
         20 . The computer program product of  claim 16 , wherein said index is partitioned into blocks, and the structure within the blocks of the said index is based on a Patricia Trie.