Integration of heterogeneous databases without common domains using queries based on textual similarity

ABSTRACT

Most databases contain “name constants” like course numbers, personal names, and place names that correspond to entities in the real world. Previous work in integration of heterogeneous databases has assumed that local name constants can be mapped into an appropriate global domain by normalization. However, in many cases, this assumption does not hold; determining if two name constants should be considered identical can require detailed knowledge of the world, the purpose of the user's query, or both. In this paper, we reject the assumption that global domains can be easily constructed, and assume instead that the names are given in natural language text. We then propose a logic called WHIRL which reasons explicitly about the similarity of local names, as measured using the vector-space model commonly adopted in statistical information retrieval. We describe an efficient implementation of WHIRL and evaluate it experimentally on data extracted from the World Wide Web. We show that WHIRL is much faster than naive inference methods, even for short queries. We also show that inferences made by WHIRL are surprisingly accurate, equaling the accuracy of hand-coded normalization routines on one benchmark problem, and outperforming 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: Yigal Arens, Craig A. Knoblock, and Chun-Nan Hsu. Query processing in the SIMS information mediator. In Austin Tate, editor, Advanced Planning Technology. AAAI Press, Menlo Park, CA, 1996.
• 3: Paolo Atzeni, Giansalvatore Mecca, and Paolo Merialdo. Semistructured and structured data on the Web: going back and forth. In Dan Suciu, editor, Proceedings of the Workshop on Management of Semistructured Data, Tucson, Arizona, May 1997. Available on-line from http://www.research.at t.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: Justin Boyan, Dane Freitag, and Thorsten Joachims. A machine learning architecture for optimizing web search engines. Technical Report WS-96-05, American Association of Artificial Intelligence, 1994.
• 8: 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
• 9: William W. Cohen. Knowledge integration for structured information sources containing text (extended abstract). In The SIGIR-97 Workshop on Networked Information Retrieval, 1997.
• 10: 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]
• 11: 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
• 12: 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]
• 13: 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]
• 14: 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]
• 15: Douglas Fang, Joachim Hammer, and Dennis McLeod. The identification and resolution of semantic heterogeneity in multidatabase systems. In Multidatabase Systems: An Advanced Solution for Global Information Sharing, pages 52- 60. IEEE Computer Society Press, Los Alamitos, California, 1994.
• 16: I. P. Felligi and A. B. Sunter. A theory for record linkage. Journal of the American Statistical Society, 64:1183-1210, 1969.
• 17: Thorsten Fiebig, Jurgen Weiss, and Guido Moerkotte. RAW: a relational algebra for the Web. In Dan Suciu, editor, 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.
• 18: 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]
• 19: H. Garcia-Molina, Y. Papakonstantinou, D. Quass, A. Rajaraman, Y. Sagiv, 3. Ullman, and J. Widom. The TSIM- MIS approach to mediation: Data models and languages (extended abstract). In Next Generation Information Technologies and Systems (NGITS-95), Naharia, Israel, November 1995.
• 20: 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
• 21: Scott Huffman and David Steier. Heuristic joins to integrate structured heterogeneous data. In Working notes of the AAAI spring symposium on information gathering in heterogeneous distributed environments, Palo Alto, CA, March 1995. AAAI Press.
• 22: B. Kilss and W. Alvey (ed). Record linkage techniques-- 1985. Statistics of Income Division, Internal Revenue Service Publication 1299-2-96. Available from http: / / www.bt s.gov/fcsm / methodology/, 1985.
• 23: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 24: 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
• 25: 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]
• 26: Alon Y. Levy, Anand Rajaraman, and Joann J. Ordille. Query answering algorithms for information agents. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96), Portland, Oregon, august 1996.
• 27: 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
• 28: David Dolan Lewis, Representation and learning in information retrieval, University of Massachusetts, Amherst, MA, 1992
• 29: 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]
• 30: A. Monte and C. Elkan. The field-matching problem: algorithm and applications. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, August 1996.
• 31: A. Monte and C. Elkan. An efficient domain-independent algorithm for detecting approximately duplicate database records. In The proceedings of the SIGMOD 1997 workshop on data mining and knowledge discovery, May 1997.
• 32: H. B. Newcombe, J. M. Kennedy, S. J. Axford, and A. P. James. Automatic linkage of vital records. Science, 130:954- 959, 1959.
• 33: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 34: M. F. Porter. An algorithm for suffix stripping. Program, 14(3):130-137, 1980.
• 35: J. R. Quinlan, Learning Logical Definitions from Relations, Machine Learning, v.5 n.3, p.239-266, Aug. 1990 [doi>10.1023/A:1022699322624]
• 36: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 37: 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]
• 38: 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
• 39: Dan Suciu, editor. Proceedings of the Workshop on Management of Semistructured Data. Available on-line from http://ww w. research, at t. corn / suciu /workshop-papers.html, Tucson, Arizona, May 1997.
• 40: 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
• 41: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Experimentation, Languages, Measurement