XML文档的相似测度和结构索引研究

提出了一个可用于定量度量XML文档间差异的方法(称为XED距离)。利用结点间的模拟关系，一个XML文档可以表示为一棵精简的、带权重的结构索引树，两个XML文档间的相似度可以通过计算它们的索引树间的编辑距离来测定，利用索引树可以大大提高判定两个XML文档结构相似度的效率，XED距离测度可用于XML文档的结构搜索、XML文档聚类、XML文档结构抽取、XML文档的变换检测以及XML视图的增量计算和维护等。     

有向标记根树之间的语义编辑距离

有向标记根树之间的编辑距离(TED)被广泛应用在文档的结构化相似度计算上。文中提出有向标记根树之间的语义编辑距离(TSED)的概念,并给出计算公式。组合TED和TSED形成距离测度,并应用在XML文档的结构聚类上。实验表明该距离模型在结构化聚类的准确率和召回率上明显优于单纯利用TED算法的聚类结果。该算法在时间复杂性上也等同于利用动态规划计算TED的最好算法。     

Using structural similarity for clustering XML documents

In this paper, we describe a method for clustering XML documents. Its goal is to group documents sharing similar structures. Our approach is two-step. We first automatically extract the structure from each XML document to be classified. This extracted structure is then used as a representation model to classify the corresponding XML document. The idea behind the clustering is that if XML documents share similar structures, they are more likely to correspond to the structural part of the same query. Finally, for the experimentation purpose, we tested our algorithms on both real (ACM SIGMOD Record corpus) and synthetic data. The results clearly demonstrate the interest of our approach.     

An efficient and scalable algorithm for clustering XML documents by structure

With the standardization of XML as an information exchange language over the Internet, a huge amount of information is formatted in XML documents. In order to analyze this information efficiently, decomposing the XML documents and storing them in relational tables is a popular practice. However, query processing becomes expensive since, in many cases, an excessive number of joins is required to recover information from the fragmented data. If a collection consists of documents with different structures (for example, they come from different DTDs), mining clusters in the documents could alleviate the fragmentation problem. We propose a hierarchical algorithm (S-GRACE) for clustering XML documents based on structural information in the data. The notion of structure graph (s-graph) is proposed, supporting a computationally efficient distance metric defined between documents and sets of documents. This simple metric yields our new clustering algorithm which is efficient and effective, compared to other approaches based on tree-edit distance. Experiments on real data show that our algorithm can discover clusters not easily identified by manual inspection.     

XML结构聚类

针对当前XML文档结构聚类算法的一些不足,提出采用段匹配的概念来计算两棵XML文档树中的路径相似性,并在此基础上得出两棵树整体的相似度量。在整个聚类过程中,算法还把一组相关文档与一个XML聚类代表相关联,该聚类代表就包含了一个文档集合中所有文档的最相关的特征。为了构建聚类代表,算法通过构造最佳匹配树,合并树,修剪树三步来实现。通过比较聚类代表,发现新的聚类时更新聚类代表来完成文档聚类。实验结果就充分展现了算法的有效性。     

Fast and effective clustering of XML data using structural information

This paper presents the incremental clustering algorithm, XML documents Clustering with Level Similarity (XCLS), that groups the XML documents according to structural similarity. A level structure format is introduced to represent the structure of XML documents for efficient processing. A global criterion function that measures the similarity between the new document and existing clusters is developed. It avoids the need to compute the pair-wise similarity between two individual documents and hence saves a huge amount of computing effort. XCLS is further modified to incorporate the semantic meanings of XML tags for investigating the trade-offs between accuracy and efficiency. The empirical analysis shows that the structural similarity overplays the semantic similarity in the clustering process of the structured data such as XML. The experimental analysis shows that the XCLS method is fast and accurate in clustering the heterogeneous documents by structures.     

XML文档相似性的仿真研究

XML文档相似性的计算是XML文档分类中的一个难题。文中描述了一种基于结构的方法，通过序列化模式挖掘方法，挖掘出两个文档之间的最大相似路径，从而可以通过计算最大相似的路径的节点数目和所有路径的节点数目的比值，得到两个文档之间的相似度。文章提出了一种新的最小化XML文档的方法，并且综合考虑了文档节点的语义相似度和结构相似度，从而进一步地提高了计算文档相似度的精度。实验表明，该方法有着良好的应用前景。     

基于XML结构相似性的名老中医病例聚类分析*

针对名老中医病例的结构特点,设计了一种基于模拟退火的聚类算法对数据库中病例聚类进行全局优化.病例聚类时,根据一般意义的树间编辑距离,提出一种用于判断XML描述的病例之间是否相似的度量(称为XML编辑距离).利用XML编辑距离,可将XML数据间相似性度量的时间复杂度限制在多项式级,且能保持病例的XML描述文档的节点语义信息和节点间的祖孙嵌套关系.最后,在Tamino数据库上进行实验,结果证实了基于模拟退火的病例聚类算法在名老中医数据挖掘实践中的可行性和有效性.     

一种新的基于B~+树结构的XML元素的索引方法

提出了一种用于搜索XML文档的新的索引方法即RIST。通过采用代码化的结构序列(SES)来表示XML文档和XML查询,得出查询XML数据等同于查找子序列匹配。RIST采用树结构作为查询的基本单元,从而避免了代价高昂的连接操作。另外,RIST还在XML文档的内容和结构上提供了一个统一的索引,所以它的一个很明显的优势就是克服了仅仅根据内容或结构建立索引的弊端。实验表明RIST在支持结构查询上是一种高效的方法。     

一种新的基于B＋树结构的XML元素的索引方法

摘要：本文提出了一种用于搜索XML文档的新的索引方法即RIST。通过采用代码化的结构序列（SES）来表示XML文档和XML查询,我们得出查询XML数据等同于查找子序列匹配。RIST采用树结构作为查询的基本单元,从而避免了代价高昂的连接操作。另外,RIST还在XML文档的内容和结构上提供了一个统一的索引,所以它的一个很明显的优势就是克服了仅仅根据内容或结构建立索引的弊端。实验表明RIST在支持结构查询上是一种高效的方法。     

XSD: A Hierarchical Access Method for Indexing XML Schemata

Search operations and browsing facilities over an XML document database require special support at the physical level. Typical search operations involve path queries. This paper proposes a hierarchical access method to support such operations and to facilitate browsing. It advocates the idea of searching large XML collections by administering efficiently XML schemata. The proposed approach may be used for indexing XML documents according to their structural proximity. This is obtained by organizing the schemata of a large XML document collection in a hierarchical way by merging structurally close schemata. The proposed structure, which is called XML Schema Directory (XSD), is a balanced tree and it may serve two purposes: (1) to accelerate XML query processing and (2) to facilitate browsing. Received 15 March 2001 / Revised 12 April 2001 / Accepted in revised form 11 May 2001     

基于频繁结构的XML文档聚类

研究基于频繁结构的XML文档聚类方法,其频繁结构包括频繁路径和频繁子树。首先介绍一种挖掘XML文档中所有嵌入频繁子树的算法SSTMiner,对SSTMiner算法进行修改,得到FrePathMiner算法和FreTreeMiner算法,分别用于挖掘XML文档中最大频繁路径和最大频繁子树,在此基础上,提出一种凝聚的层次聚类算法XMLCluster,分别以最大频繁路径和最大频繁子树作为XML文档的特征,对文档进行聚类。实验结果表明FrePathMiner算法和FreTreeMiner算法找到频繁结构的数量都比传统的ASPMiner算法多,这就可以为文档聚类提供更多的结构特征,从而获得更高的聚类精度。     

基于特征偏好的XML文档聚类算法

XML文档聚类在众多数据应用领域都具有重要作用。基于特征偏好的XML文档聚类算法是对XML文档进行特征选择,将XML文档描述为[n]维特征向量,再结合CFP（Clustering with Feature order Preference）算法,根据特征偏好为其赋予权重,每次迭代聚类过程中进行权重的更新。实验结果表明当CFP算法中的特征偏好权重和XML文档向量化时所用的层次权重设定相结合时,可弥补XML文档向量化时的弊端,提高了XML文档聚类的精度。     

一种基于结构特征的XML数据查询方法

针对XML数据特有的树型结构模式，提出了一种将树型结构的XML数据和查询语句转化为特定格式的字符串，基于串匹配原理对结构复杂的XML数据进行查询的方法，避免了传统的基于路径的查询方式所必需的路径之间的连接（join）操作，从而提高查询效率。利用本文提出的编码方式，可以建立关于XML数据结构和数据内容舍为一体的索引。实验显示，本文使用的针对XML数据查询的方法比传统的基于连接操作的数据查询方式高效，且本方法具有良好的扩展性。     

XML structural delta mining: Issues and challenges

Recently, there is an increasing research efforts in XML data mining. These research efforts largely assumed that XML documents are static. However, in reality, the documents are rarely static. In this paper, we propose a novel research problem called XML structural delta mining. The objective of XML structural delta mining is to discover knowledge by analyzing structural evolution pattern (also called structural delta) of history of XML documents. Unlike existing approaches, XML structural delta mining focuses on the dynamic and temporal features of XML data. Furthermore, the data source for this novel mining technique is a sequence of historical versions of an XML document rather than a set of snapshot XML documents. Such mining technique can be useful in many applications such as change detection for very large XML documents, efficient XML indexing, XML search engine, etc. Our aim in this paper is not to provide a specific solution to a particular mining problem. Rather, we present the vision of the mining framework and present the issues and challenges for three types of XML structural delta mining: identifying various interesting structures, discovering association rules from structural deltas, and structural change pattern-based classification.     

Collaborative clustering of XML documents

Clustering XML documents is extensively used to organize large collections of XML documents in groups that are coherent according to structure and/or content features. The growing availability of distributed XML sources and the variety of high-demand environments raise the need for clustering approaches that can exploit distributed processing techniques. Nevertheless, existing methods for clustering XML documents are designed to work in a centralized way. In this paper, we address the problem of clustering XML documents in a collaborative distributed framework. XML documents are first decomposed based on semantically cohesive subtrees, then modeled as transactional data that embed both XML structure and content information. The proposed clustering framework employs a centroid-based partitional clustering method that has been developed for a peer-to-peer network. Each peer in the network is allowed to compute a local clustering solution over its own data, and to exchange its cluster representatives with other peers. The exchanged representatives are used to compute representatives for the global clustering solution in a collaborative way. We evaluated effectiveness and efficiency of our approach on real XML document collections varying the number of peers. Results have shown that major advantages with respect to the corresponding centralized clustering setting are obtained in terms of runtime behavior, although clustering solutions can still be accurate with a moderately low number of nodes in the network. Moreover, the collaborativeness characteristic of our approach has revealed to be a convenient feature in distributed clustering as found in a comparative evaluation with a distributed non-collaborative clustering method.     

XML文档结构相似测度研究*

为了满足基于Web的XML数据信息的近似搜索、信息分类以及数据交换的需求,提出一种新的有效地鉴定XML文档间结构相似度的标准。该标准包含了XML文档的结构信息和节点嵌套的语义信息,可以有效地给出XML文档间的结构相似测度。通过实验证明该标准具有高度的准确性和有效性。     

一种基于XML文档聚类的XML近似查询算法

提出了一种基于XML文档聚类的XML近似查询算法。给出了基于语义的XML文档间距离的计算方法，结合该语义距离，提出了基于网格的八邻域聚类算法对XML数据库进行聚类划分，进而利用在聚类过程中得到的聚类中心对静态有序选择算法的近似查询评估阶段进行优化，使得不用对XML数据库进行完全遍历就能及时返回满足用户需要的查询结果。最后，在汽车外形智能化设计的实验中表明该算法有效地提高了静态有序选择算法的查询效率。     

Static analysis of XML transformations in Java

XML documents generated dynamically by programs are typically represented as text strings or DOM trees. This is a low-level approach for several reasons: 1) traversing and modifying such structures can be tedious and error prone, 2) although schema languages, e.g., DTD, allow classes of XML documents to be defined, there are generally no automatic mechanisms for statically checking that a program transforms from one class to another as intended. We introduce XACT, a high-level approach for Java using XML templates as a first-class data type with operations for manipulating XML values based on XPath. In addition to an efficient runtime representation, the data type permits static type checking using DTD schemas as types. By specifying schemes for the input and output of a program, our analysis algorithm will statically verify that valid input data is always transformed into valid output data and that the operations are used consistently.     

Structural and semantic aspects of similarity of Document Type Definitions and XML schemas

The natural optimization strategy for XML-to-relational mapping methods is exploitation of similarity of XML data. However, none of the current similarity evaluation approaches is suitable for this purpose. While the key emphasis is currently put on semantic similarity of XML data, the main aspect of XML-to-relational mapping methods is analysis of their structure.In this paper we propose an approach that utilizes a verified strategy for structural similarity evaluation - tree edit distance - to DTD constructs. This approach is able to cope with the fact that DTDs involve several types of nodes and can form general graphs. In addition, it is optimized for the specific features of XML data and, if required, it enables one to exploit the semantics of element/attribute names. Using a set of experiments we show the impact of these extensions on similarity evaluation. And, finally, we discuss how this approach can be extended for XSDs, which involve plenty of “syntactic sugar”, i.e. constructs that are structurally or semantically equivalent.