Alan Dix > 2010

Spreading Activation Over Ontology-Based Resources:
From Personal Context To Web Scale Reasoning

Alan Dix1 , Akrivi Katifori2, Giorgos Lepouras3, Costas Vassilakis3, Nadeem Shabir4

1 Computing Department, Lancaster University, Lancaster, UK
2 Department of Informatics & Telecommunications, University of Athens, Athens, Hellas (Greece)
3 Dept. of Computer Science and Technology, University of Peloponnese, Tripolis, Hellas (Greece)
4 Talis, Birmingham, UK

Accepted for publication in the Internatonal Journal of Semantic Computing, Special Issue on Web Scale Reasoning: scalable, tolerant and dynamic

Full paper text at DOI: 10.1142/S1793351X10000973
Download draft paper (PDF, 880K)

Abstract

This paper describes methods to allow spreading activation to be used on web-scale information resources.  Existing work has shown that spreading activation can be used to model context over small personal ontologies, which can be used to assist in various user activities, for example, in auto-completing web forms.  This previous work is extended and methods are developed by which large external repositories, including corporate information and the web, can be linked to the user’s personal ontology and thus allow automated assistance that is able to draw on the entire web of data.  The basic idea is augment the personal ontology with cached data from external repositories, where the choice of what data to fetch or discard is related to the level of activation of entities already in the personal ontology or cached data.  This relies on the assumption that the working set of highly active entities is relatively small; empirical results are presented, which suggest these assumptions are likely to hold.  Implications of the techniques are discussed for user interaction and for the social web.  In addition, warm world reasoning is proposed, applying rule-based reasoning over activate entities, potentially merging symbolic and sub-symbolic reasoning over web-scale knowledge bases.

keywords: personal ontology; spreading activation; web-scale reasoning; context modelling intelligent user interface; personal information management, warm-world assumption
Full reference:
A. Dix, A. Katifori, G. Lepouras, C. Vassilakis and N. Shabir (2010). Spreading Activation Over Ontology-Based Resources: From Personal Context To Web Scale Reasoning. Internatonal Journal of Semantic Computing, Special Issue on Web Scale Reasoning: scalable, tolerant and dynamic. 4(1) pp.59-102.
http://www.hcibook.com/alan/papers/
web-scale-reasoning-2010/
more:
TIM Project web page
play with Snip!t

References

  1. A. Katifori, C. Vassilakis and A. Dix, Ontologies and the Brain: Using Spreading Activation through Ontologies to Support Personal Interaction. Cognitive Systems Research (in press) (2009).
    http://www.hcibook.com/alan/papers/Ontologies-and-the-Brain-2009/
  2. Linked Data - Connect Distributed Data across the Web, linkeddata.org administered by Tom Heath on behalf of the Linked Data community, http://linkeddata.org/
  3. C. Bizer, T. Heath, T. Berners-Lee, Linked Data – The Story So Far. International Journal on Semantic Web and Information Systems (in press) (2009).
  4. D. Fensel, F. van Harmelen (2007). Unifying Reasoning and Search to Web Scale, IEEE Internet Computing 11(2) (2007) 94–96.
  5. G. Anadiotis, S. Kotoulas, and R. Siebes, An architecture for peer-to-peer reasoning, in Proc. of the First Int. Workshop "New forms of reasoning for the Semantic Web: scalable, tolerant and dynamic", co-located with ISWC 2007 and ASWC 2007, Vol-291, Busan, Korea, 2007, http://CEUR-WS.org/Vol-291/
  6. A. Qasem, D. A. Dimitrov, and J. Heflin. ISENS: A Multi-ontology Query System for the Semantic Deep Web, in Proc. of Workshop on The Semantic Web meets the Deep Web, IEEE CEC'08 and EEE'08, Washington DC, 2008.
  7. R. T. Gruber, A Translation Approach to Portable Ontology Specifications, Knowledge Acquisition, Special issue: Current issues in knowledge modeling 5(2) (1993) 199-220
  8. J. Trajkova, S. Gauch, Improving Ontology-based User Profiles, in Proc. of RIAO 2004, University of Avignon (Vaucluse), France, 2004, 380-389
  9. S. Gauch, J. Chaffee, and A. Pretschner, Ontology-Based User Profiles for Search and Browsing, Web Intelligence and Agent Systems, Vol. 1, No. 3-4. (2003), pp. 219-234.
  10. V. Katifori, A. Poggi,. M. Scannapieco, T. Catarci, Y. Ioannidis, Y. OntoPIM: how to rely on a personal ontology for Personal Information Management, in Proc. of the 1st Workshop on The Semantic Desktop, Galway, Ireland, 2005.
  11. L. Sauermann, The Gnowsis Semantic Desktop for Information Integration, in Proc. of the 3rd Conference Professional Knowledge Management, Kaiserslautern, Germany,2005.
  12. P.-A. Chirita, R. Gavriloai, S. Ghita, W. Nejdl, R. Paiu, Activity Based Metadata for Semantic Desktop Search, in Proc. of the 2nd European Semantic Web Conference, Heraklion, Greece, 2005.
  13. M. Golemati, A. Katifori, C. Vassilakis, G. Lepouras, C. Halatsis, Creating an Ontology for the User Profile: Method and Applications, in Proc. Of the First RCIS Conference, Ouarzazate, Morocco, 2007.
  14. A. Katifori, C. Vassilakis, I. Daradimos, G. Lepouras, Y. Ioannidis, A. Dix, A. Poggi, T. Catarci, Personal Ontology Creation and Visualization for a Personal Interaction Management System, in Proc. of PIM Workshop, CHI 2008, Florence, Italy, 2008. http://www.hcibook.com/alan/papers/PIM2008-personal-ontology/
  15. A. Katifori, C. Vassilakis, A. Dix, I. Daradimos, G. Lepouras, Spreading activation user profile ontology, University of Athens, Technical Report, http://oceanis.mm.di.uoa.gr/pened/?category=pub#ontos
  16. A. Dix, Tasks = data + action + context: automated task assistance through data-oriented analysis, in Proc. of Engineering Interactive Systems 2008: Second Conference on Human-Centered Software Engineering, HCSE 2008 and 7th International Workshop on Task Models and Diagrams, TAMODIA 2008, Pisa, Italy, 2008. http://www.hcibook.com/alan/papers/EIS-Tamodia2008/
  17. E. Rukzio, A. Schmidt, H. Hussmann, Privacy-enhanced Intelligent Automatic Form Filling for Context-aware Services on Mobile Devices, in Proc. of workshop on Artificial Intelligence in Mobile Systems 2004 (AIMS 2004), in conjunction with UbiComp 2004, Nottingham, UK, 2004.
  18. W3C draft, Client Side Automated Form Entry, W3C Working Draft WD-form-filling-960416, http://www.w3.org/TR/WD-form-filling.html
  19. A. Dix, A. Katifori, A. Poggi, T. Catarci, Y. Ioannidis, G. Lepouras and M. Mora, From Information to Interaction: in Pursuit of Task-centred Information Management, in Proc. of DELOS Conference 2007, Pisa, Italy, 2007. http://www.hcibook.com/alan/papers/DELOS-TIM2-2007/
  20. J. R. Anderson, A Spreading Activation Theory of Memory, Journal of Verbal Learning and Verbal Behaviour, 22 (1983) 261-295.
  21. F. Crestani, Application of spreading activation techniques in information retrieval, Artificial Intelligence Review 11(6) (1997) 453–482.
  22. F. Crestani, Retrieving documents by constrained spreading activation on automatically constructed hypertexts, in Proc. of EU- FIT 97- Fifth International Congress on Intelligent Techniques and Soft Computing, Aachen, Germany, 1997, pp. 1210-1214.
  23. W. Liu, A. Weichselbraun, A. Scharl, and E. Chang, Semi-Automatic Ontology Extension Using Spreading Activation, Journal of Universal Knowledge Management, 0(1) (2005), 50 – 58.
  24. R. G. Xue, J. H. Zeng, Z. Chen, Y. W. Ma, W. Xi, W. Fan and Y. Yu, (2004). Optimizing Web Search Using Web Click-through Data. in Proc. of ACM Thirteenth Conference on Information and Knowledge Management (CIKM), Washington D.C., U.S.A., 2004, pp. 118-126
  25. M. Hasan, A Spreading Activation Framework for Ontology-enhanced Adaptive Information Access within Organisations. in Proc. of the Spring Symposium on Agent Mediated Knowledge Management (AMKM 2003), Stanford University, California, USA, 2003.
  26. J. J. Hopfield, Neural networks and physical systems with emergent collective computational properties, in Proc. of the National Academy of Sciences of the USA, 79 (1982), pp. 2554 - 2588.
  27. A. Katifori, C. Vassilakis and A. Dix, Using Spreading Activation through Ontologies to Support Personal Information Management, in Proc. of Common Sense Knowledge and Goal-Oriented Interfaces, held in conjunction with the 2008 International Conference on Intelligent User Interfaces (IUI 2008), Canary Islands, Spain, 2008. http://www.hcibook.com/alan/papers/CSKGOI2008-speading-act/
  28. T. Berners-Lee, J. Hendler and O. Lassila, The Semantic Web, Scientific American, May 2001.
  29. About Freebase, MetaWeb Technologies, http://www.metaweb.com/about/
  30. Google Spreadsheets APIs and Tools, http://code.google.com/apis/spreadsheets/overview.html
  31. G. Price, C. Sherman, The Invisible Web: Uncovering Information Sources Search Engines Can't See, (CyberAge Books, 2001).
  32. B. He, M. Patel, Z. Zhang, and C. K. Chang, Accessing the Deep Web: A Survey, Communications of the ACM (CACM) 50(2) (2007) 94–101.
  33. G. P. Ipeirotis, L. Gravano and M. Sahami, Probe, count, and classify: categorizing hidden web databases, SIGMOD Rec. 30(2) (2001) 67-78.
  34. J. P. Bigham, A. C. Cavender, R. S. Kaminsky, C. M. Prince and T. S. Robison, Transcendence: Enabling a Personal View of the Deep Web, in Proceedings of the 11th International Conference on Intelligent User Interfaces (IUI 2008), Canary Islands, Spain, 2008.
  35. D. Gibson, K. Punera, and A. Tomkins, 2005. The volume and evolution of web page templates, in Special interest Tracks and Posters of the 14th ACM Int. Conference on World Wide Web (WWW '05), Chiba, Japan, 2005.
  36. S. Dill, N. Eiron, D. Gibson, D. Gruhl, R. Guha, A. Jhingran, T. Kanungo, S. Rajagopalan, A. Tomkins, A. J. Tomlin, and Y. J. Zien, SemTag and seeker: bootstrapping the semantic web via automated semantic annotation, in Proc. of the 12th ACM Int. Conference on World Wide Web (WWW ’03), Budapest, Hungary, 2003.
  37. Google Sets, http://labs.google.com/sets
  38. LarKC: The Large Knowledge Collider, http://www.larkc.eu/
  39. D. Fensel, F. van Harmelen, B. Andersson, P. Brennan, H. Cunningham, E. Della Valle, F. Fischer, Z. Huang, A. Kiryakov, T. Kyung-il Lee, L. Schooler, V. Tresp, S. Wesner, M. Witbrock and N. Zhong (2008). Towards LarKC: A Platform for Web-Scale Reasoning, in Proc. of IEEE second Int. Conference on Semantic Computing (ICSC 2008), Santa Clara, CA, USA, 2008, pp.524–529
  40. H. Simon, Models of Man, (Wiley, 1957).
  41. R. Motwani, and P. Raghavan, 1996. Randomized algorithms, ACM Comput. Surv. 28(1) (1996), 33-37.
  42. C. Gomes, J. Hoffmann, A. Sabharwal, and B. Selman. From sampling to model counting. In Proc. of International Joint Conferences on Artificial Intelligence (IJCAI ’07), Hyderabad, India, 2007, p.p. 2293–2299.
  43. C. Morbidoni , A. Polleres , and G. Tummarello, Who the FOAF knows Alice? A needed step towards Semantic Web Pipes, in Proc. of the First Int. Workshop "New forms of reasoning for the Semantic Web: scalable, tolerant and dynamic", co-located with ISWC 2007 and ASWC 2007, Vol-291, Busan, Korea, 2007, http://CEUR-WS.org/Vol-291/
  44. S. Ceri, E. Della Valle, D. Fensel, F. van Harmelen. R. Studer, 1st Int. Workshop on Stream Reasoning, Heraklion, Greece, 2009, http://streamreasoning.org/
  45. R. Wallis, Bigfoot - An initial tour, Talis Platform User Guide, 2007 http://www.talis.com/tdn/platform/user/bigfoot/tour
  46. J. Dean and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, in Proc. of Sixth Symposium on Operating System Design and Implementation (OSDI '04), San Francisco, CA, U.S.A., 2004, http://labs.google.com/papers/mapreduce.html
  47. A. Hogan, A. Harth, and A. Polleres. Scalable authoritative OWL reasoning for the web. International Journal on Semantic Web and Information Systems, 5(2), April-June 2009.
  48. A. Qasem , D. Dimitrov, and J. Heflin, Efficient Selection and Integration of Data Sources for Answering Semantic Web Queries, in Proc. of the First Int. Workshop "New forms of reasoning for the Semantic Web: scalable, tolerant and dynamic", co-located with ISWC 2007 and ASWC 2007, Vol-291, Busan, Korea, 2007, http://CEUR-WS.org/Vol-291/
  49. S. Brin, and L. Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, in Proc. of Seventh ACM International World-Wide Web Conference (WWW ‘98), Brisbane, Australia, 1998.
  50. C. R. Atkinson, M. R. Shiffrin, Human memory: A proposed system and its control processes. in The psychology of learning and motivation, ed. K.W. Spence and J.T. Spence, vol. 8. (Academic Press, 1968).
  51. G. A. Miller, The Magical Number Seven, Plus or Minus Two: Some Limits on Our Capacity for Processing Information, The Psychological Review, 63(2) (1956) 81-97.
  52. A. K. Ericsson and W. Kintsch, Long-term working memory, The Psychological Review, 102(2) 1995 211-245.
  53. A. Dix, The brain and the web: intelligent interactions from the desktop to the world. In Proceedings of VII Brazilian Symposium on Human Factors in Computing Systems, IHC'06, vol. 323. (2006) 142. ACM DOI=10.1145/1298023.1298080 http://www.hcibook.com/alan/papers/brazil2006/
  54. The Protégé Ontology Editor and Knowledge Acquisition System. http://protege.stanford.edu/
    M. T. Mitchell, Machine Learning, (McGraw-Hill, 1997).
  55. T. Lømo, The discovery of long-term potentiation. Philosophical Transactions: Biological Sciences. 358(1432) (2003) 617-620.
  56. A. Katifori. Preliminary Evaluation Example of the Spreading Activation Algorithm. University of Athens, Technical Report, http://oceanis.mm.di.uoa.gr/pened/?category=pub#ontos
  57. G. Salton and M.J. Mc Gill, Introduction to modern information retrieval. Mc-Graw-Hill, Singapore (1987).
  58. A. Cheyer, Ja. Park, R. Giuli, IRIS: Integrate. Relate. Infer. Share, in Proc. Workshop on the Semantic Desktop: Next Generation Personal Information Management and Collaboration Infrastructure (ICSC 2005), Galway, Ireland, 2005.
  59. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins and J. Wiener, Graph structure in the Web, Computer Networks 33(1-6) (2000) 309-320.
  60. DESCRIBE Query, SPARQL Query Language for RDF. W3C Recommendation (2008) http://www.w3.org/TR/rdf-sparql-query/#describe
  61. A. S. Tanenbaum, Modern Operating Systems (3rd edition). (Prentice Hall, 2007)
  62. A. Harth, A. Hogan, J. Umbrich, S. Decker, Building a Semantic Web Search Engine: Challenges and Solutions, in Proc. of XTech 2008: “The Web on the Move”, Dublin, Ireland, 2008, http://2008.xtech.org/public/schedule/detail/477
  63. Swoogle Statistics.  No longer available, but as cited in [4]. Originally at http://swoogle.umbc.edu/2005/modules/Swoogle Statistics/images/figure5-2004-09.png
  64. L. Ding, L. Zhou, T. Finin, and A. Joshi, How the Semantic Web is Being Used: An Analysis of FOAF, in Proc. of the 38th International Conference on System Sciences, Hawaii, U.S.A., 2005.
  65. J.M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, January 1998, pp. 668–677.
  66. H. Stuckenschmidt and M. Klein, Structure-Based Partitioning of Large Concept Hierarchies}, International Semantic Web Conference, LNCS 3298, pp. 289-303, http://www.informatik.uni-trier.de/~ley/db/conf/semweb/iswc2004.html#StuckenschmidtK04
  67. BBC Backstage. British Broadcasting Corporation, dated 2004-2005, Accessed 6/7/2009. http://backstage.bbc.co.uk/
  68. L. Dodds, Understanding the Big BBC Graph, dated 11th June 2009. Accessed 10/08/2009. http://blogs.talis.com/n2/archives/569
  69. Y. Raimond, P. Sinclair, N. Humfrey, M. Smeturst, Programmes ontology, British Broadcasting Corporation, dated 17th April 2009. Accessed 6/7/2009.  http://purl.org/ontology/po/2009-04-17.shtml
  70. F. Giasson, Y. Raimond, Music Ontology Specification, British Broadcasting Corporation, dated 5th February 2007. Accessed 6/7/2009.  http://purl.org/ontology/mo/
  71. Talis Platform. Talis. Accessed 6/7/2009.  http://www.talis.com/platform/
  72. I. Davis.  Moriarty, n2 Wiki.   Iand 09:00, dated 2 October 2007.  accessed 6/7/2009. http://n2.talis.com/wiki/Moriarty
  73. B. Nowack, ARC2: Easy RDF and SPARQL for LAMP systems. Semsol.  accessed 6/7/2009. http://arc.semsol.org/
  74. Kalfoglou, Y., Alani, H., Schorlemmer, M. and Walton, C. (2004) On the emergent Semantic Web and overlooked issues. In: 3rd International Semantic Web Conference, November 2004, Hiroshima, Japan.
  75. K. Golden, O. Etzioni, and D. Weld. Omnipresence without omnipresence. In Proc. of 12th Nat. Conf. on Artificial Intelligence(AAAI’94), 1994.
  76. V. Tanasescu, Differences + Triple Spaces = Active Triple Spaces, in Proc. of the First Int. Workshop "New forms of reasoning for the Semantic Web: scalable, tolerant and dynamic", co-located with ISWC 2007 and ASWC 2007, Vol-291, Busan, Korea, 2007, http://CEUR-WS.org/Vol-291/
  77. A. Dix, J. Finlay and J. Hassell, Environments for cooperating agents: Designing the interface as medium, in CSCW and Artificial Intelligence, eds. J. Connolly and E. Edmonds, (Springer Verlag, 1994) pp. 9-26.
  78. L. Sauermann and D. Heim, Evaluating Long-Term Use of the Gnowsis Semantic Desktop for PIM, in Proc. of the 7th international Conference on the Semantic Web, Karlsruhe, Germany, 2008, 467-482.
  79. P. Resnick and H. R. Varian (Eds.), Special Issue on Recommender Systems, Communications of the ACM, 40(3) (1997) 56–89
  80. T. O'Reilly, What Is Web 2.0 - Design Patterns and Business Models for the Next Generation of Software, (2005) http://www.oreillynet.com/pub/a/oreilly/tim/news/2005/09/30/what-is-web-20.html
  81. A. Dix, The web sharer vision. Working Paper. aqtive limited, (1999) http://www.hiraeth.com/alan/ebulletin/websharer/vision-web-sharer.html
  82. G. Mayer-Kress and C. Barczys, The global brain as an emergent structure from the worldwide computing network, The information society 11(1) (1995) 1-28.
  83. K. Lerman , The Web-Brain Hypothesis, University of Southern California  (1998)  http://www.isi.edu/~lerman/etc/brain.html
  84. N. Zhong, Towards Human Level Web Intelligence: A Brain Informatics Perspective, Pattern Recognition and Machine Intelligence, LNCS 4815 (2007) p. 311, DOI: 10.1007/978-3-540-77046-6_38

http://www.hcibook.com/alan/papers/web-scale-reasoning-2010/

Alan Dix 19/8/2009