Exploiting web search engines to search structured databases

ABSTRACT

Web search engines often federate many user queries to relevant structured databases. For example, a product related query might be federated to a product database containing their descriptions and specifications. The relevant structured data items are then returned to the user along with web search results. However, each structured database is searched in isolation. Hence, the search often produces empty or incomplete results as the database may not contain the required information to answer the query. In this paper, we propose a novel integrated search architecture. We establish and exploit the relationships between web search results and the items in structured databases to identify the relevant structured data items for a much wider range of queries.Our architecture leverages existing search engine components to implement this functionality at very low overhead. We demonstrate the quality and efficiency of our techniques through an extensive experimental study.

REFERENCES

• 1: http://search.live.com/products/.
• 2: http://search.live.com/xrank?form=xrank1.
• 3: http://www.google.com/products.
• 4: www.wikipedia.org.
• 5: DBXplorer: A System for Keyword-Based Search over Relational Databases, Proceedings of the 18th International Conference on Data Engineering, p.5, February 26-March 01, 2002
• 6: Mikhail Bautin , Steven Skiena, Concordance-Based Entity-Oriented Search, Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, p.586-592, November 02-05, 2007 [doi>10.1109/WI.2007.37]
• 7: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 8: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 9: M. Cafarella, M. Banko, and O. Etzioni. Relational Web Search. In WWW Conference, 2006.
• 10: Kaushik Chakrabarti , Surajit Chaudhuri , Venkatesh Ganti , Dong Xin, An efficient filter for approximate membership checking, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376697]
• 11: Soumen Chakrabarti, Breaking through the syntax barrier: searching with entities and relations, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.9-16, September 20-24, 2004, Pisa, Italy
• 12: Soumen Chakrabarti, Dynamic personalized pagerank in entity-relation graphs, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242650]
• 13: Soumen Chakrabarti , Kriti Puniyani , Sujatha Das, Optimizing scoring functions and indexes for proximity search in type-annotated corpora, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135882]
• 14: Surajit Chaudhuri , Venkatesh Ganti , Dong Xin, Exploiting web search to generate synonyms for entities, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526731]
• 15: W. Cohen and A. McCallum. Information Extraction and Integration: an Overview. In SIGKDD Conference, 2004.
• 16: William W. Cohen , Sunita Sarawagi, Exploiting dictionaries in named entity extraction: combining semi-Markov extraction processes and data integration methods, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014065]
• 17: O. et. al. Web-scale information extraction in knowitall. In WWW Conference, 2004.
• 18: R. Grishman. Information Extraction: Techniques and Challenges. In SCIE, 1997.
• 19: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 20: Vagelis Hristidis , Yannis Papakonstantinou, Discover: keyword search in relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.670-681, August 20-23, 2002, Hong Kong, China
• 21: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 22: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 23: Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150429]
• 24: Gonzalo Navarro , Veli Mäkinen, Compressed full-text indexes, ACM Computing Surveys (CSUR), v.39 n.1, p.2-es, 2007 [doi>10.1145/1216370.1216372]
• 25: Gonzalo Navarro , Mathieu Raffinot, Flexible pattern matching in strings: practical on-line search algorithms for texts and biological sequences, Cambridge University Press, New York, NY, 2002
• 26: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 27: V. Vapnik. Statistical Learning Theory. Whiley, 2000.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

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

General Terms:
Design, Experimentation, Performance

Keywords:
entity extraction, entity ranking, entity search, structured database search