Measuring similarity between collection of values

ABSTRACT

In this paper, we propose a set of similarity metrics for manipulating collections of values occuring in XML documents.

Following the data model presented in TAX algebra, we treat an XML element as a labeled ordered rooted tree. Consider that XML nodes can be either atomic, i.e, they may contain single values such as short character strings, date, etc, or complex, i.e., nested structures that contain other nodes, we propose two types of similarity metrics: MAVs, for atomic nodes and MCVs, for complex nodes. In the first case, we suggest the use of several application domain dependent metrics. In the second case, we define metrics for complex values that are structure dependent, and can be distinctly applied for it and collections of values. We also present experiments showing the effectiveness of our method.

REFERENCES

• 1: Shurug Al-Khalifa , Cong Yu , H. V. Jagadish, Querying structured text in an XML database, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872761]
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Carmel, D., Efrati, N., Landau, G. M., Maarek, Y., and Mass, Y. An extension of the vector space model for querying XML documents via XML fragments. In Workshop On XML and Information Retrieval, SIGIR (2002).
• 4: Joyce C. P. Carvalho , Altigran S. da Silva, Finding similar identities among objects from multiple web sources, Proceedings of the 5th ACM international workshop on Web information and data management, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956699.956719]
• 5: Surajit Chaudhuri , Kris Ganjam , Venkatesh Ganti , Rajeev Motwani, Robust and efficient fuzzy match for online data cleaning, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872796]
• 6: William W. Cohen, Data integration using similarity joins and a word-based information representation language, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.288-321, July 2000 [doi>10.1145/352595.352598]
• 7: Cohen, W., Ravikumar, P., and Fienberg, S. A comparison of string metrics for matching names and records. In KDD-2003 Workshop on Data Cleaning and Object Consolidation (2003).
• 8: Alberto Del Bimbo, Visual information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 9: Dorneles, C. F., Lima, A. E. N., Heuser, C. A., da Silva, A., and de Moura, E. S. Acessing xml data by allowing imprecise query arguments. Tech. Rep. RP-342, UFRGS, 2004.
• 10: Daniela Florescu , Donald Kossmann , Ioana Manolescu, Integrating keyword search into XML query processing, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.119-135, June 2000, Amsterdam, The Netherlands
• 11: Fuhr, and Grossjohann. XIRQL: an extension of XQL for information retrieval. In ACM SIGIR Workshop On XML and Information Retrieval (2000).
• 12: Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
• 13: Luis Gravano , Panagiotis G. Ipeirotis , Nick Koudas , Divesh Srivastava, Text joins in an RDBMS for web data integration, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775166]
• 14: Jin, L., Li, C., and Mehrotra, S. Efficient similarity string joins in large data sets. In VLDB (April 2002).
• 15: Jaap Kamps , Maarten Marx , Maarten de Rijke , Börkur Sigurbjörnsson, XML retrieval: what to retrieve?, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860525]
• 16: Steve Lawrence , C. Lee Giles , Kurt D. Bollacker, Autonomous citation matching, Proceedings of the third annual conference on Autonomous Agents, p.392-393, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301255]
• 17: Jean-Michel Jolion, Feature similarity, Principles of visual information retrieval, Springer-Verlag, London, 2000
• 18: Amihai Motro, VAGUE: a user interface to relational databases that permits vague queries, ACM Transactions on Information Systems (TOIS), v.6 n.3, p.187-214, July 1988 [doi>10.1145/45945.48027]
• 19: Nadvorny, C. F., and Heuser, C. A. Twisting the metric space to achieve better metric trees. In Brazilian Symp. on Database, SBBD (2004).
• 20: Sheila Tejada , Craig A. Knoblock , Steven Minton, Learning object identification rules for information integration, Information Systems, v.26 n.8, p.607-633, December 2001 [doi>10.1016/S0306-4379(01)00042-4]
• 21: Sheila Tejada , Craig A. Knoblock , Steven Minton, Learning domain-independent string transformation weights for high accuracy object identification, 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.775099]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Experimentation, Measurement

Keywords:
XML, imprecise queries, similarity functions, vague queries