XML version detection

ABSTRACT

The problem of version detection is critical in many important application scenarios, including software clone identification, Web page ranking, plagiarism detection, and peer-to-peer searching. A natural and commonly used approach to version detection relies on analyzing the similarity between files. Most of the techniques proposed so far rely on the use of hard thresholds for similarity measures. However, defining a threshold value is problematic for several reasons: in particular (i) the threshold value is not the same when considering different similarity functions, and (ii) it is not semantically meaningful for the user. To overcome this problem, our work proposes a version detection mechanism for XML documents based on Naïve Bayesian classifiers. Thus, our approach turns the detection problem into a classification problem. In this paper, we present the results of various experiments on synthetic data that show that our approach produces very good results, both in terms of recall and precision measures.

REFERENCES

• 1: B. Westfechtel , B. P. Munch , R. Conradi, A Layered Architecture for Uniform Version Management, IEEE Transactions on Software Engineering, v.27 n.12, p.1111-1133, December 2001 [doi>10.1109/32.988710]
• 2: Shu Yao Chien , Vassilis J. Tsotras , Carlo Zaniolo, XML document versioning, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603875]
• 3: Sebastian Rönnau , Jan Scheffczyk , Uwe M. Borghoff, Towards XML version control of office documents, Proceedings of the 2005 ACM symposium on Document engineering, November 02-04, 2005, Bristol, United Kingdom [doi>10.1145/1096601.1096606]
• 4: Randy H. Katz , Ellis E. Chang, Managing Change in a Computer-Aided Design Database, Proceedings of the 13th International Conference on Very Large Data Bases, p.455-462, September 01-04, 1987
• 5: Saul Schleimer , Daniel S. Wilkerson , Alex Aiken, Winnowing: local algorithms for document fingerprinting, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872770]
• 6: Chen, X., Francia, B., Li, M., McKinnon, B., Seker, A.. Shared information and program plagiarism detection. IEEE Transactions on Information Theory, v. 50, n. 7, p-1545--1551, 2004.
• 7: Baeza-Yates, R., Castillo, C.. Relating Web Characteristics with Link based Web Page Ranking. Proc. of the 8th Intl. Symposium on String Processing and Information Retrieval, 2001.
• 8: Stéphane Ducasse , Oscar Nierstrasz , Matthias Rieger, On the effectiveness of clone detection by string matching: Research Articles, Journal of Software Maintenance and Evolution: Research and Practice, v.18 n.1, p.37-58, January 2006 [doi>10.1002/smr.v18:1]
• 9: Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
• 10: Guth, G.J.: Surname spellings and computerized record linkage. Historical Methods Newsletter 10, 10--19, 1976.
• 11: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 12: Sergio Flesca , Giuseppe Manco , Elio Masciari , Luigi Pontieri , Andrea Pugliese, Fast Detection of XML Structural Similarity, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.160-175, February 2005 [doi>10.1109/TKDE.2005.27]
• 13: Nierman, A. e Jagadish, H.V.. Evaluating Structural Similarity in XML Documents. Proc. of the 5th Intl. Workshop on the Web and Databases (WebDB 2002), 2002.
• 14: Carina F. Dorneles , Carlos A. Heuser , Andrei E. N. Lima , Altigran Soares da Silva , Edleno Silva de Moura, Measuring similarity between collection of values, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031465]
• 15: Silva, R.; Stasiu, R. K.; Orengo, V. M.; Heuser, C. A. Measuring quality of similarity functions in approximate data matching. Journal of Informetrics, v. 1, p. 4, 2007.
• 16: Stasiu, R. K.; Heuser, C. A.; Silva, R. Estimating Recall and Precision for vague queries in Databases. In: 17th International Conference Advanced Information Systems Engineering (CAISE), Porto, Portugal, 2005. v. 3520. p. 187--200.
• 17: Deise De Brum Saccol , Nina Edelweiss , Renata De Matos Galante, Detecting, Managing and Querying Replicas and Versions in a Peer-to-Peer Environment, Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, p.881-886, May 14-17, 2007 [doi>10.1109/CCGRID.2007.39]
• 18: Amelie Marian, Detecting Changes in XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.41, February 26-March 01, 2002
• 19: Wang, Y., DeWitt, D. J., Cai, J. X-Diff: An Effective Change Detection Algorithm for XML Documents. Intl. Conf. on Data Engineering, 519--530, 2003.
• 20: Sudarshan S. Chawathe, Comparing Hierarchical Data in External Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.90-101, September 07-10, 1999
• 21: Xiaojun Wan , Jianwu Yang, Using proportional transportation similarity with learned element semantics for XML document clustering, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135965]
• 22: Cohen, W.W., Ravikumar, P., Fienberg, S.: A comparison of string distance metrics for name-matching tasks. In: Proc. of IJCAI-03 Workshop on Information Integration on the Web, Acapulco, Mexico, Morgan Kaufmann, 73--78, 2003.
• 23: Eike Schallehn , Kai-Uwe Sattler , Gunter Saake, Efficient similarity-based operations for data integration, Data & Knowledge Engineering, v.48 n.3, p.361-387, March 2004 [doi>10.1016/j.datak.2003.08.004]
• 24: Mikhail Bilenko , Raymond Mooney , William Cohen , Pradeep Ravikumar , Stephen Fienberg, Adaptive Name Matching in Information Integration, IEEE Intelligent Systems, v.18 n.5, p.16-23, September 2003 [doi>10.1109/MIS.2003.1234765]
• 25: Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775087]
• 26: Langley, P., Iba, W., & Thompson, K. An analysis of Bayesian classifiers. Proc. of the 10th National Conference on Artificial Intelligence (pp. 223--228). San Jose, CA: AAAI Press, 1992.
• 27: Yong Wang , Julia Hodges , Bo Tang, Classification of Web Documents Using a Naive Bayes Method, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.560, November 03-05, 2003
• 28: Pon, R.K., Cárdenas, A.F., Buttler, D., Critchlow, T.. iScore: Measuring the Interestingness of Articles in a Limited User Environment. In: IEEE Symposium on Computational Intelligence and Data Mining, Honolulu, HI, 2007.
• 29: S.-Y. Chien , V. J. Tsotras , C. Zaniolo, Efficient schemes for managing multiversionXML documents, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.332-353, December 2002 [doi>10.1007/s00778-002-0079-4]
• 30: Zografoula Vagena , Mirella M. Moro , Vassilis J. Tsotras, Supporting Branched Versions on XML Documents, Proceedings of the 14th International Workshop on Research Issues on Data Engineering: Web Services for E-Commerce and E-Government Applications (RIDE'04), p.137-144, March 28-29, 2004
• 31: Elisa Bertino , Giovanna Guerrini , Marco Mesiti, A matching algorithm for measuring the structural similarity between an XML document and a DTD and its applications, Information Systems, v.29 n.1, p.23-46, March 2004 [doi>10.1016/S0306-4379(03)00031-0]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Document management

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Version control

General Terms:
Experimentation, Management, Measurement

Keywords:
XML, classification, similarity functions, versioning