Data integration using similarity joins and a word-based information representation language

ABSTRACT

The integration of distributed, heterogeneous databases, such as those available on the World Wide Web, poses many problems. Herer we consider the problem of integrating data from sources that lack common object identifiers. A solution to this problem is proposed for databases that contain informal, natural-language “names” for objects; most Web-based databases satisfy this requirement, since they usually present their information to the end-user through a veneer of text. We describe WHIRL, a “soft” database management system which supports “similarity joins,” based on certain robust, general-purpose similarity metrics for text. This enables fragments of text (e.g., informal names of objects) to be used as keys. WHIRL includes textual objects as a built-in type, similarity reasoning as a built-in predicate, and answers every query with a list of answer substitutions that are ranked according to an overall score. Experiments show that WHIRL is much faster than naive inference methods, even for short queries, and efficient on typical queries to real-world databases with tens of thousands of tuples. Inferences made by WHIRL are also surprisingly accurate, equaling the accuracy of hand-coded normalization routines on one benchmark problem, and outerperforming exact matching with a plausible global domain on a second.

REFERENCES

• 1: Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.122-133, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263676]
• 2: ARENS, Y., KNOBLOCK,C.A.,AND HSU, C.-N. 1996. Query processing in the SIMS informa-tion mediator. In A. Tate Ed., Advanced Planning Technology. Menlo Park, CA: AAAI Press.
• 3: ATZENI, P., MECCA, G., AND MERIALDO, P. 1997. Semistructured and structured data on the Web: going back and forth. In D. Suciu Ed., Proceedings of the Workshop on Management of Semistructured Data (Tucson, Arizona, May 1997). Available on-line from http://www.re-search. att.com/ ; suciu/workshop-papers.html.
• 4: D. Barbará , H. Garcia-Molina , D. Porter, The Management of Probabilistic Data, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.487-502, October 1992 [doi>10.1109/69.166990]
• 5: Brian T. Bartell , Garrison W. Cottrell , Richard K. Belew, Automatic combination of multiple ranked retrieval systems, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.173-181, July 03-06, 1994, Dublin, Ireland
• 6: R. J. Bayardo, Jr. , W. Bohrer , R. Brice , A. Cichocki , J. Fowler , A. Helal , V. Kashyap , T. Ksiezyk , G. Martin , M. Nodine , M. Rashid , M. Rusinkiewicz , R. Shea , C. Unnikrishnan , A. Unruh , D. Woelk, InfoSleuth: agent-based semantic integration of information in open and dynamic environments, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.195-206, May 11-15, 1997, Tucson, Arizona, United States
• 7: BORGMAN,C.L.AND SIEGFRIED, S. L. 1992. Getty's Synoname and its cousins: a survey of applications of personal name-matching algorithms. Journal of the American Society for Information Science 43, 7, 459-476.
• 8: BOSC,P.AND PRADE, H. 1997. An introduction to the fuzzy set and possibility theory-based treatment of queries and uncertain or imprecise databases. In Uncertainty management in information systems. Kluwer Academic Publishers.
• 9: BOYAN, J., FREITAG, D., AND JOACHIMS, T. 1994. A machine learning architecture for optimiz-ing web search engines. Technical Report WS-96-05, American Association of Artificial Intelligence.
• 10: Surajit Chaudhuri , Umeshwar Dayal , Tak W. Yan, Join queries with external text sources: execution and optimization techniques, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.410-422, May 22-25, 1995, San Jose, California, United States
• 11: COHEN, W. W. 1997. Knowledge integration for structured information sources containing text (extended abstract). In The SIGIR-97 Workshop on Networked Information Retrieval (1997).
• 12: William W. Cohen, Integration of heterogeneous databases without common domains using queries based on textual similarity, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.201-212, June 01-04, 1998, Seattle, Washington, United States
• 13: William W. Cohen, A Web-based information system that reasons with structured collections of text, Proceedings of the second international conference on Autonomous agents, p.400-407, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280870]
• 14: COHEN,W.W.AND HIRSH, H. 1998. Joins that generalize: Text categorization using WHIRL. In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (New York, NY, 1998), pp. 169-173.
• 15: William W. Cohen , Yoram Singer, Context-sensitive learning methods for text categorization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.307-315, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243278]
• 16: William W. Cohen , Robert E. Schapire , Yoram Singer, Learning to order things, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.451-457, July 1998, Denver, Colorado, United States
• 17: Mark Craven , Dan DiPasquo , Dayne Freitag , Andrew McCallum , Tom Mitchell , Kamal Nigam , Seán Slattery, Learning to extract symbolic knowledge from the World Wide Web, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.509-516, July 1998, Madison, Wisconsin, United States
• 18: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 19: Oliver M. Duschka , Michael R. Genesereth, Query planning in infomaster, Proceedings of the 1997 ACM symposium on Applied computing, p.109-111, April 1997, San Jose, California, United States [doi>10.1145/331697.331719]
• 20: Joel L. Fagan, The effectiveness of a nonsyntatic approach to automatic phrase indexing for document retrieval, Journal of the American Society for Information Science, v.40 n.2, p.115-132, March 1989 [doi>10.1002/(SICI)1097-4571(198903)40:2<115::AID-ASI6>3.0.CO;2-B]
• 21: Ronald Fagin, Fuzzy queries in multimedia database systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275488]
• 22: FANG, D., HAMMER, J., AND MCLEOD, D. 1994. The identification and resolution of semantic heterogeneity in multidatabase systems. In Multidatabase Systems: An Advanced Solution for Global Information Sharing, pp. 52-60. IEEE Computer Society Press, Los Alamitos, California.
• 23: FELLIGI,I.P.AND SUNTER, A. B. 1969. A theory for record linkage. Journal of the American Statistical Society 64, 1183-1210.
• 24: FIEBIG, T., WEISS, J., AND MOERKOTTE, G. 1997. RAW: a relational algebra for the Web. In D. Suciu Ed., Proceedings of the Workshop on Management of Semistructured Data (Tucson, Arizona, May 1997). Available on-line from http://www.research.att.com/ ; suciu/workshop-papers. html.
• 25: Norbert Fuhr, Probabilistic Datalog—a logic for powerful retrieval methods, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.282-290, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215372]
• 26: GARCIA-MOLINA, H., PAPAKONSTANTINOU, Y., QUASS, D., RAJARAMAN, A., SAGIV, Y., ULLMAN, J., AND WIDOM, J. 1995. The TSIMMIS approach to mediation: Data models and languages (extended abstract). In Next Generation Information Technologies and Systems (NGITS-95) (Naharia, Israel, November 1995).
• 27: Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States
• 28: HUFFMAN,S.AND STEIER, D. 1995. Heuristic joins to integrate structured heterogeneous data. In Working notes of the AAAI spring symposium on information gathering in heteroge-neous distributed environments (Palo Alto, CA, March 1995). AAAI Press.
• 29: KILSS,B.AND ALVEY, W. 1985. Record linkage techniques:1985. Statistics of Income Division, Internal Revenue Service Publication 1299-2-96. Available from http://www.bts. gov/fcsm/methodology/.
• 30: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 31: David Konopnicki , Oded Shmueli, W3QS: A Query System for the World-Wide Web, Proceedings of the 21th International Conference on Very Large Data Bases, p.54-65, September 11-15, 1995
• 32: Richard E. Korf, Linear-space best-first search, Artificial Intelligence, v.62 n.1, p.41-78, July 1993 [doi>10.1016/0004-3702(93)90045-D]
• 33: LEVY,A.Y.,RAJARAMAN, A., AND ORDILLE, J. J. 1996a. Query answering algorithms for information agents. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96) (Portland, Oregon, August 1996).
• 34: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 35: David D Lewis, Representation and Learning in Information Retrieval, University of Massachusetts, Amherst, MA, 1991
• 36: Alberto O. Mendelzon , Tova Milo, Formal models of Web queries, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.134-143, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263677]
• 37: MONGE,A.AND ELKAN, C. 1996. The field-matching problem: algorithm and applications. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (August 1996).
• 38: MONGE,A.AND ELKAN, C. 1997. An efficient domain-independent algorithm for detecting approximately duplicate database records. In The proceedings of the SIGMOD 1997 work-shop on data mining and knowledge discovery (May 1997).
• 39: NEWCOMBE,H.B.,KENNEDY,J.M.,AXFORD,S.J.,AND JAMES, A. P. 1959. Automatic linkage of vital records. Science 130, 954-959.
• 40: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 41: Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 42: PORTER, M. F. 1980. An algorithm for suffix stripping. Program 14, 3, 130-137.
• 43: Pat Langley, Editorial: Advice to Machine Learning Authors, Machine Learning, v.5 n.3, p.233-237, Aug. 1990 [doi>10.1023/A:1022647305786]
• 44: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 45: Peter Schäuble, SPIDER: a multiuser information retrieval system for semistructured and dynamic data, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-327, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160756]
• 46: Dan Suciu, Query Decomposition and View Maintenance for Query Languages for Unstructured Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.227-238, September 03-06, 1996
• 47: SUCIU,D.ED. 1997. Proceedings of the Workshop on Management of Semistructured Data. Available on-line from http://www.research.att.com/suciu/workshop-papers.html, Tucson, Arizona.
• 48: Anthony Tomasic , Rémy Amouroux , Philippe Bonnet , Olga Kapitskaia , Hubert Naacke , Louiqa Raschid, The distributed information search component (Disco) and the World Wide Web, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.546-548, May 11-15, 1997, Tucson, Arizona, United States
• 49: Howard Turtle , James Flood, Query evaluation: strategies and optimizations, Information Processing and Management: an International Journal, v.31 n.6, p.831-850, Nov. 1995 [doi>10.1016/0306-4573(95)00020-H]
• 50: ZADEH, L. A. 1965. Fuzzy sets. Information and Control 8, 338-353.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data manipulation languages (DML); Query languages
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Reliability