XML documents change detection system based on boolean linear programming task

• Autorzy: Globa L. , Alieksieiev M. , Molchanov I.
• Języki publikacji: EN

Abstrakty

EN

This paper describes the main ideas of XML change detection system which is based on developed linear programming algorithm for XML change detection. The linear programming algorithm for XML change detection is developed to compare the trees of old web page and modified web page to find the changes between them. The approach presented in this paper differs from the previously cited ones. The first main idea of proposed algorithm is in paying attention only to quantitative changes in the tracked documents, instead of searching the exact changes sequence that produces the new document. The second main idea is in comparison of two document versions as if they are different documents. Such approach doesn’t need the reference map between XML tags of two documet versions. The proposed technique represents the change detection problem as the Boolean linear programming task and proposes effective solution method.

Słowa kluczowe

EN

XML; change detection; publish/subscribe system; Boolean linear programming task

PL

XML; wykrywanie zmiennych; system publikacje/subskrypcje; liniowe programowe zadanie Booleana

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2011
• Tom: nr 2
• Strony: 25--35
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Globa L.

autor

Alieksieiev M.

autor

Molchanov I.

• National technical university of Ukraine, Institute of telecommunication system

Bibliografia

• [1] Abiteboul S., Chawathe S., Widom J., Representing and querying changes in semistructured data, Proceedings of the International Conference on Data Engineering, Orlando, Florida, February 1998: pp. 4–13.
• [2] Eugster P., Felber P.A., Guerraoui R., Kermarrec A.-M.. The many faces of Publish /Subscribe, ACM Computing Surveys, Vol 35, No 2, June, 2003, pp. 114-131.
• [3] Rowstron A.I.T., Kermarrec A.-M., Castro M., Druschel P., SCRIBE: The design of a large-scale event notification infrastructure, Networked Group Communication, 2001, pp. 30-43.
• [4] Ramasubramanian V., Peterson R., Sirer E.G.. Corona: A High Performance Publish-Subscribe System for the World Wide Web. Proc. USENIX Symposium on Networked Systems Design and Implementation, 2006, pp. 15-28.
• [5] Pietzuch P.R., Bacon J.M., Hermes: A Distributed Event-Based Middleware Architecture. Submitted to the Workshop on Distributed Event-Based Systems (DEBS), 2002, pp. 132-156.
• [6] Heimbigner D., Extending the Siena Publish/Subscribe System. Technical Report, Department of Computer Science, January, 2003, pp. 1-15.
• [7] Chand R., Felber P., Antipolis S. XNET: a reliable content-based publish/subscribe system, Reliable Distributed Systems, 2004, pp. 264-273.
• [8] Barroso L., Dean J., Holze U., Web Search for a Planet: The Google Cluster Architecture. IEEE Computer Science, 2003, pp. 22-28.
• [9] Khandagale H.P., Halkarnikar P.P., A Novel Approach for Web Page Change Detection System, International Journal of Computer Theory and Engineering, Vol. 2, No. 3, June, 2010, pp.421-435.
• [10] Khoury I., El-Mawas R.M., El-Rawas O., Mounayar E.F., Artail H., An Efficient Web Page Change Detection System Based on an Optimized Hungarian Algorithm, IEEE Transactions on Knowledge and Data Engineering, Vol. 19, No. 5, May 2007, pp. 463-478
• [11] Leonardi E., Bhowmick S. S., Xandy: A Scalable Change Detection Technique for Ordered XML Documents Using Relational Databases. DKE Journal, 59(2), Elsevier Science, 2006, pp.212-223.
• [12] Een N., Sorensson N., Translating Pseudo-Boolean Constraints into SAT, Journal on Satisfiability, Boolean Modeling and Computation, vol. 2, pp. 1–26, February 2006.
• [13] Brady B., Catanzaro B., Pseudo-Boolean Heuristics for 0-1 Integer Linear Programming, Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, pp. 132–135, 2008.
• [14] Kyong-Ho Lee, Yoon-Chul Choy, Sung-Bae Cho, An Efficient Algorithm to Compute Differences between Structured Documents, IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 8, August 2004.
• [15] Seung-Jin Lim, Yiu-Kai Ng, An Efficient Algorithm to Compute Differences between Structured Documents, 2001 IEEE.
• [16] Khoury I., El-Mawas R.M., El-Rawas O., Mounayar E.F., Artail H., An Efficient Web Page Change Detection System Based on an Optimized Hungarian Algorithm, IEEE Transactions on Knowledge and Data Engineering, Vol. 19, No. 5, May 2007
• [17] Alieksieiev M.O., Alekseyev O.M., Molchanov Y.M., Publish/Subscribe System for R&D Information Resources, Visnyk SumDU, #2, Sumy 2009: pp. 22-30.