Propagation-vectors for trees (PVT): concise yet effective summaries for hierarchical data and trees

ABSTRACT

Summarization of hierarchical data and metadata is a fundamental operation in applications in many domains. In particular, similarity search of hierarchical data, such as XML, would benefit greatly from concise and indexable summaries. This is especially true in P2P scenarios, where the search needs to be done in a distributed fashion on multiple peers. This situation requires summaries which are small, yet effective in identifying potential peers that need to be further explored. In this paper, we propose a method, called propagation-vectors for trees (PVT) which constructs very concise and accurate summaries of hierarchical data, such as XML trees. We then show how to use this summary to perform similarity search on summarized data. The proposed summarization scheme relies on a label-propagation mechanism, which constructs an n-dimensional vector from a given tree with n unique data labels. Experimental results have shown that the constructed PVT summaries capture the structure of the input trees very accurately, the representations are highly concise, and that the search based on these summaries are faster than the existing approaches.

REFERENCES

• 1: P. Bille. Tree edit distance, alignment distance and inclusion. IT Univ. of Copenhagen TR-2003-23, 2003
• 2: D. Buttler. A short survey of document structure similarity algorithms. ICIT 2004.
• 3: 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
• 4: R. Cilibrasi and P. Vitanyi. Clustering by compression. IEEE Transactions on Information Theory, 2005.
• 5: F. Crestani, Application of Spreading Activation Techniques in InformationRetrieval, Artificial Intelligence Review, v.11 n.6, p.453-482, Dec. 1997 [doi>10.1023/A:1006569829653]
• 6: Martin Farach , Mikkel Thorup, Sparse Dynamic Programming for Evolutionary-Tree Comparison, SIAM Journal on Computing, v.26 n.1, p.210-230, Feb. 1997 [doi>10.1137/S0097539794262422]
• 7: 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]
• 8: F. Gelgi, S.Vadrevu, H. Davulcu. Improving web data annotations with spreading activation. WISE 2005.
• 9: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 10: R. Goldman and J. Widom. Approximate dataguides. In Workshop on Query Processing for Semistructured Data and Non-Standard Data Formats, 1999.
• 11: Sven Helmer, Measuring the structural similarity of semistructured documents using entropy, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 12: IBM XML Generator. http://www.alphaworks.ibm.com/tech/xmlgenerator.
• 13: Hierarchical Clustering. http://www.cs.rpi.edu/~zaki/dmcourse/notes /chapter12.pdf
• 14: Jong Wook Kim , K. Sel#231;uk Candan, CP/CV: concept similarity mining without frequency information from domain describing taxonomies, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183684]
• 15: K. Kintigh. The promise and challenge of archaeological data integration. American Antiquity, 71(3):567--578, 2006.
• 16: Philip N. Klein, Computing the Edit-Distance between Unrooted Ordered Trees, Proceedings of the 6th Annual European Symposium on Algorithms, p.91-102, August 24-26, 1998
• 17: S. Lu. A tree-to-tree distance and its application to cluster analysis. IEEE Trans. PAMI, 1:219--224, 1979.
• 18: Fabrizio Luccio , Linda Pagli, Approximate matching for two families of trees, Information and Computation, v.123 n.1, p.111-120, Nov. 15, 1995 [doi>10.1006/inco.1995.1160]
• 19: A. Nierman and H. V. Jagadish. Evaluating structural similarity in XML documents. WebDB 2002.
• 20: Yan Qi , K. Selçuk Candan , Maria Luisa Sapino, FICSR: feedback-based inconsistency resolution and query processing on misaligned data sources, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247499]
• 21: Yan Qi , K. Selçuk Candan , Maria Luisa Sapino , Keith W. Kintigh, Integrating and querying taxonomies with quest in the presence of conflicts, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247639]
• 22: Davood Rafiei , Daniel L. Moise , Dabo Sun, Finding Syntactic Similarities Between XML Documents, Proceedings of the 17th International Conference on Database and Expert Systems Applications, p.512-516, September 04-08, 2006 [doi>10.1109/DEXA.2006.62]
• 23: R. Richardson and A. F. Smeaton. Using WordNet in a knowledge-based approach to information retrieval. Technical Report CA-0395, Dublin, Ireland, 1995.
• 24: R. Rada, H. Mili, E. Bicknell, and M. Blettner. Development and application of a metric on semantic nets. IEEE Transactions on Systems, Man and Cybernetics, 19(1), 1989.
• 25: Gerard Salton , Edward A. Fox , Harry Wu, Extended Boolean information retrieval, Communications of the ACM, v.26 n.11, p.1022-1036, Nov. 1983 [doi>10.1145/182.358466]
• 26: S. Selkow. The tree-to-tree editing problem. Information Processing Letters, 6(6):184--186, 1977.
• 27: Kaizhong Zhang , Dennis Shasha, Tree pattern matching, Pattern matching algorithms, Oxford University Press, Oxford, 1997
• 28: Kuo-Chung Tai, The Tree-to-Tree Correction Problem, Journal of the ACM (JACM), v.26 n.3, p.422-433, july 1979 [doi>10.1145/322139.322143]
• 29: Zhibiao Wu , Martha Palmer, Verbs semantics and lexical selection, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.133-138, June 27-30, 1994, Las Cruces, New Mexico [doi>10.3115/981732.981751]
• 30: Kaizhong Zhang , Dennis E. Shasha, The editing distance between trees: algorithms and applications, New York University, New York, NY, 1989
• 31: K. Zhang , D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, v.18 n.6, p.1245-1262, Dec. 1989 [doi>10.1137/0218082]
• 32: K. Zhang, J. T. L. Wang, and D. Shasha. On the editing distance between undirected acyclic graphs and related problems. SoCPM 1995.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Experimentation

Keywords:
p2p search, tree summarization