A web of concepts

ABSTRACT

We make the case for developing a web of concepts by starting with the current view of web (comprised of hyperlinked pages, or documents, each seen as a bag of words), extracting concept-centric metadata, and stitching it together to create a semantically rich aggregate view of all the information available on the web for each concept instance. The goal of building and maintaining such a web of concepts presents many challenges, but also offers the promise of enabling many powerful applications, including novel search and information discovery paradigms. We present the goal, motivate it with example usage scenarios and some analysis of Yahoo! logs, and discuss the challenges in building and leveraging such a web of concepts. We place this ambitious research agenda in the context of the state of the art in the literature, and describe various ongoing efforts at Yahoo! Research that are related.

REFERENCES

• 1: ]]J. Allan. Topic Detection and Tracking. Kluwer Academic, 2002.
• 2: Rohit Ananthakrishna , Surajit Chaudhuri , Venkatesh Ganti, Eliminating fuzzy duplicates in data warehouses, Proceedings of the 28th international conference on Very Large Data Bases, p.586-597, August 20-23, 2002, Hong Kong, China
• 3: Rie Kubota Ando , Tong Zhang, A Framework for Learning Predictive Structures from Multiple Tasks and Unlabeled Data, The Journal of Machine Learning Research, 6, p.1817-1853, 12/1/2005
• 4: ]]T. Anton. Xpath-wrapper induction by generating tree traversal patterns. In LWA, pages 126--133, 2005.
• 5: ]]J. Atserias, H. Zaragoza, M. Ciaramita, and G. Attardi. Semantically annotated snapshot of the English Wikipedia. In LREC, 2008.
• 6: Holger Bast , Alexandru Chitea , Fabian Suchanek , Ingmar Weber, ESTER: efficient search on text, entities, and relations, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277856]
• 7: Robert Baumgartner , Sergio Flesca , Georg Gottlob, Visual Web Information Extraction with Lixto, Proceedings of the 27th International Conference on Very Large Data Bases, p.119-128, September 11-14, 2001
• 8: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 9: ]]T. Berners-Lee, J. Hendler, and O. Lassila. The semantic web. Scientific American, 284(5):34--43, 2001.
• 10: Philip A. Bernstein , Laura M. Haas, Information integration in the enterprise, Communications of the ACM, v.51 n.9, September 2008 [doi>10.1145/1378727.1378745]
• 11: ]]I. Bhattacharya and L. Getoor. A latent Dirichlet model for unsupervised entity resolution. In SDM, 2006.
• 12: Indrajit Bhattacharya , Lise Getoor, Collective entity resolution in relational data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.5-es, March 2007 [doi>10.1145/1217299.1217304]
• 13: Ronald Brachman , Hector Levesque, Knowledge Representation and Reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 14: Peter Buneman , Sanjeev Khanna , Wang Chiew Tan, Why and Where: A Characterization of Data Provenance, Proceedings of the 8th International Conference on Database Theory, p.316-330, January 04-06, 2001
• 15: Michael J. Cafarella , Alon Halevy , Daisy Zhe Wang , Eugene Wu , Yang Zhang, WebTables: exploring the power of tables on the web, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453916]
• 16: ]]C. Cardie. Empirical methods in information extraction. AI Magazine, 18(4):65--79, 1997.
• 17: Surajit Chaudhuri , Venkatesh Ganti , Rajeev Motwani, Robust Identification of Fuzzy Duplicates, Proceedings of the 21st International Conference on Data Engineering, p.865-876, April 05-08, 2005 [doi>10.1109/ICDE.2005.125]
• 18: Fei Chen , AnHai Doan , Jun Yang , Raghu Ramakrishnan, Efficient Information Extraction over Evolving Text Data, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.943-952, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497503]
• 19: James Cheney , Peter Buneman , Bertram Ludäscher, Report on the Principles of Provenance Workshop, ACM SIGMOD Record, v.37 n.1, March 2008 [doi>10.1145/1374780.1374798]
• 20: ]]W.W. Cohen, P. Ravikumar, and S.E. Fienberg. A comparison of string distance metrics for name-matching tasks. In IJCAI Workshop on Information Integration on the Web, pages 73--78, 2003.
• 21: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 22: Nilesh Dalvi , Philip Bohannon , Fei Sha, Robust web extraction: an approach based on a probabilistic tree-edit model, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA [doi>10.1145/1559845.1559882]
• 23: ]]N. Dalvi, R. Kumar, B. Pang, and A. Tomkins. Matching reviews with objects using a language model. In Manuscript, 2008.
• 24: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.4, p.523-544, October 2007 [doi>10.1007/s00778-006-0004-3]
• 25: Pedro DeRose , Warren Shen , Fei Chen , AnHai Doan , Raghu Ramakrishnan, Building structured web community portals: a top-down, compositional, and incremental approach, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 26: ]]A. Doan, J. Madhavan, P. Domingos, and A.Y. Halevy. Ontology matching: A machine learning approach. In Handbook on Ontologies, pages 385--404, 2004.
• 27: AnHai Doan , Raghu Ramakrishnan , Shivakumar Vaithyanathan, Managing information extraction: state of the art and research directions, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142595]
• 28: ]]P. Domingos. Multi-relational record linkage. In KDD Workshop on Multi-Relational Data Mining, pages 31--48, 2004.
• 29: Xin Dong , Alon Halevy , Jayant Madhavan, Reference reconciliation in complex information spaces, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066168]
• 30: Oren Etzioni , Michael Cafarella , Doug Downey , Stanley Kok , Ana-Maria Popescu , Tal Shaked , Stephen Soderland , Daniel S. Weld , Alexander Yates, Web-scale information extraction in knowitall: (preliminary results), Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988687]
• 31: ]]I.P. Fellegi and A.B. Sunter. A theory for record linkage. JASA, 64:1183--1210, 1969.
• 32: ]]A.D. Fuxman and R.J. Miller. First-order query rewriting for inconsistent databases. In ICDT, pages 337--351, 2005.
• 33: ]]R. Gilleron, F. Jousse, I. Tellier, and M. Tommasi. XML document transformation with conditional random fields. In INEX, 2006.
• 34: ]]M.N. Gubanov and P.A. Bernstein. Structural text search and comparison using automatically extracted schema. In WebDB, 2006.
• 35: Ashish Gupta , Iderpal Singh Mumick, Materialized views: techniques, implementations, and applications, MIT Press, Cambridge, MA, 1999
• 36: Rahul Gupta , Sunita Sarawagi, Creating probabilistic databases from information extraction models, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 37: Alon Halevy , Michael Franklin , David Maier, Principles of dataspace systems, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-9, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142352]
• 38: Rob Hall , Charles Sutton , Andrew McCallum, Unsupervised deduplication using cross-field dependencies, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401931]
• 39: Wei Han , David Buttler , Calton Pu, Wrapping web data into XML, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603873]
• 40: Chun-Nan Hsu , Ming-Tzung Dung, Generating finite-state transducers for semi-structured data extraction from the Web, Information Systems, v.23 n.9, p.521-538, Dec. 1998
• 41: ]]A. Jain, D. Kifer, A. Kirpal, S. Merugu, S. Keerthi, P. Bohannon, and R. Ramakrishnan. Concept-centric extraction: using domain knowledge and local learning. In Manuscript, 2008.
• 42: ]]T.S. Jayram, R. Krishnamurthy, S. Raghavan, S. Vaithyanathan, and H. Zhu. Avatar information extraction system. IEEE Data Engineering Bulletin, 29(1):40--48, 2006.
• 43: ]]D.V. Kalashnikov, S. Mehrotra, and Z. Chen. Exploiting relationships for domain-independent data cleaning. In SDM, 2005.
• 44: ]]N. Kushmerick, D.S. Weld, and R.B. Doorenbos. Wrapper induction for information extraction. In IJCAI, pages 729--737, 1997.
• 45: ]]J. Madhavan, L. Afanasiev, L. Antova, and A.Y. Halevy. Harnessing the deep web: Present and future. In CIDR, 2009.
• 46: Andrew McCallum, Information Extraction: Distilling Structured Data from Unstructured Text, Queue, v.3 n.9, November 2005 [doi>10.1145/1105664.1105679]
• 47: ]]A. McCallum and B. Wellner. Conditional models of identity uncertainty with application to noun coreference. In NIPS, 2004.
• 48: Robert McCann , Alexander Kramnik , Warren Shen , Vanitha Varadarajan , Olu Sobulo , AnHai Doan, Integrating Data from Disparate Sources: A Mass Collaboration Approach, Proceedings of the 21st International Conference on Data Engineering, p.487-488, April 05-08, 2005 [doi>10.1109/ICDE.2005.81]
• 49: ]]I. Muslea, S. Minton, and C. Knoblock. STALKER: Learning extraction rules for semistructured. In AAAI: Workshop on AI and Information Integration, 1998.
• 50: ]]J. Myllymaki and J. Jackson. Robust web data extraction with XML path expressions. Technical Report RJ 10245, IBM, 2002.
• 51: Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
• 52: ]]H.B. Newcombe, J.M. Kennedy, S.J. Axford, and A.P. and James. Automatic linkage of vital records. Science, 130:954--959, 1959.
• 53: ]]H. Pasula, B. Marthi, B. Milch, S. Russell, and I. Shpitser. Identity uncertainty and citation matching. In NIPS, 2002.
• 54: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 55: ]]E. Rahm, A. Thor, D. Aumueller, H.H. Do, N. Golovin, and T. Kirsten. iFuice: Information fusion utilizing instance correspondences and peer mappings. In WebDB, pages 7--12, 2005.
• 56: Rajat Raina , Alexis Battle , Honglak Lee , Benjamin Packer , Andrew Y. Ng, Self-taught learning: transfer learning from unlabeled data, Proceedings of the 24th international conference on Machine learning, p.759-766, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273592]
• 57: Raghu Ramakrishnan , Andrew Tomkins, Toward a PeopleWeb, Computer, v.40 n.8, p.63-72, August 2007 [doi>10.1109/MC.2007.294]
• 58: Arnaud Sahuguet , Fabien Azavant, Building Light-Weight Wrappers for Legacy Web Data-Sources Using W4F, Proceedings of the 25th International Conference on Very Large Data Bases, p.738-741, September 07-10, 1999
• 59: Parag Singla , Pedro Domingos, Entity Resolution with Markov Logic, Proceedings of the Sixth International Conference on Data Mining, p.572-582, December 18-22, 2006 [doi>10.1109/ICDM.2006.65]
• 60: ]]S. Sundararajan and S. Keerthi. Graph based classification methods using inaccurate external classifier information. In Manuscript, 2008.
• 61: ]]J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In CIDR, pages 262--276, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

General Terms:
Experimentation, Measurement, Theory

Keywords:
concepts, extraction, ranking, selection