PathSim : um algoritmo para calcular a similaridade entre caminhos XML

Abstract

Algoritmos de similaridade que comparam dados expressos em XML são importantes em diversas aplicações que manipulam informações armazenadas nesse padrão. Sistemas de integração de dados XML e de consulta a instâncias XML são exemplos dessas aplicações. A utilização de funções de similaridade para efetuar as comparações nessas aplicações melhora seus resultados finais. A melhora ocorre porque as funções de similaridade possibilitam encontrar estruturas não idênticas às apresentadas nos parâmetros das consultas mas que armazenam informações relevantes. Uma característica importante que pode ser utilizada para definir se dois elementos XML representam o mesmo objeto real é os caminhos que chegam a estes elementos nas suas respectivas árvores. No entanto, os nodos que representam um determinado objeto real em duas instâncias XML diferentes podem se acessados por caminhos distintos, devido a opções de modelagem dos documentos. Portanto um algoritmo para calcular a similaridade entre caminhos XML é importante para as aplicações descritas acima. Neste contexto, esta dissertação objetiva desenvolver um algoritmo de similaridade entre caminhos XML. O resultado principal do trabalho é um algoritmo de similaridade entre caminhos XML, nomeado PathSim, que efetua o cálculo de similaridade entre dois caminhos baseado no número mínimo de operações de edição (inserção, remoção e substituição de nomes de elementos) necessárias para transformar um caminho no outro. Além deste algoritmo, foram desenvolvidas três funções de pré-processamento para simplificar os caminhos XML e melhoram os resultados do algoritmo. Adicionalmente, duas variações do algoritmo PathSim são apresentadas, uma incrementada com comparações entre combinações de nomes de elementos, nomeada PathSimC, e a outra auxiliada por técnicas de alinhamento, nomeada PathSimA. Experimentos utilizando documentos XML criados por terceiros, validam empiricamente os algoritmos PathSim e PathSimC.Nos experimentos, os algoritmos foram comparados a uma abordagem para mensurar a similaridade entre caminhos encontrada na literatura. Os algoritmos apresentam melhores resultados que o baseline. Os ganhos variam de acordo com o ambiente onde os caminhos foram extraídos e com as funções de pré-processamento que foram aplicadas aos caminhos.

Similarity algorithms for comparing XML data are important in various applications that manipulate information stored according to this standard. XML data integration systems and XML instance querying systems are examples of such applications. The use of similarity functions to evaluate comparisons in these applications improves their final results. The improvement occurs because similarity functions allow finding structures that are not identical to the query parameter but store relevant information. One important feature that may be used to define if two XML elements represent the same real world object is the paths that lead to those objects in their corresponding trees. However, the nodes that represent a specific real world object in two different XML instances may be accessed by distinct paths, due to XML design decisions. Thus a method for assessing the similarity of XML paths is important in the applications described above. In this context, the goal of this dissertation is to develop a XML path similarity algorithm. The main contribution of this work is a XML path similarity algorithm, named Path- Sim, that calculates the similarity between two paths by computing the minimum number of edit operations (element name insertions, deletions and substitutions) required to transform one path into another. Besides the algorithm, three preprocessing functions were developed to simplify XML paths and improve the results of the algorithm. Additionally, two variations of PathSim algorithm are presented, one enhanced with comparisons among combinations of element names, named PathSimC, and the other one assisted by alignment techniques, named PathSimA. Experiments using XML documents created by third parties validate the algorithms PathSim and PathSimC empirically. On the experiments, the algorithms are compared to a path similarity algorithm found in the literature. The proposed algorithms presents better results than the baseline. The gains vary according to the environment from which the paths were extracted and to the preprocessing functions applied.