Java Marker-Passing Search Service

JMaPSS is the Java Marker-Passing Search Service, a relevance search engine employing a family of marker-passing algorithms.


Internet search tools respond to information queries representing a user's information need. Typically page ranking algorithms that use clustering or other heuristic techniques to respond to user queries are applied to a large collection of indexed documents. Heuristics are applied on both the index side (e.g. "stop tags") and the query side (e.g. query syntax languages, synonym-generators) to improve the chances that returned results meet users' information needs.

While this is certainly an over-simplification of today's search technology, it does capture the essence of how modern search engines respond to queries. This is generally a good and sound approach; yet even though search engines push the envelope to become more responsive to users, there exists room for alternative search approaches that focus more on user (and group) intent. One such approach is associative retrieval, which applies cognitive psychology theory of semantic memory organization to the task of retrieving relevant knowledge from a reasoning agent's cognitive store based on the current information need. JMaPSS is an enterprise web-enabled search system based on associative retrieval.

There are several applications we can see JMaPSS supporting:

  1. Personalized or group-based search - stateful search, where the system returns results influenced by the most recent queries from a user or group.
  2. Semantic web search - JMaPSS is a platform for implementing marker-passing variations. One variation types nodes according to semantic web meta-information. Using ontologies, we can incorporate rich semantic information to better direct the search.
  3. Search agents - proactive search applications that integrate what you are currently working on and actively find relevant information on the web or your desktop.

Recent projects in JMaPSS

  • Initial implementation of JMaPSS (Brad Szabo and Braden Chapman)
  • A semantic web customization of JMaPSS (Livanya Vijayan)
  • Exposing JMaPSS to an enterprise portal using web services (Krishna Krovi)
  • GATE- A visualization tool for JMaPSS administration (Jayavarshini Radhadkrishnan)
  • Machine learning applied to JMaPSS (Aishwarya Sivaraman)
  • A browser plugin for performing personalized relevance search (Aishwarya Sivaraman)

A (very) Brief Background on Marker-passing
Marker-passing algorithms are based on spreading activation theories of knowledge processing from cognitive psychology; in such theories, nodes in semantic memory are excitedwhen stimulated, this excitement spreads to neighboring nodes until it fades out over a distance, much like ripples in pond when you throw a stone. Marker-passing adaptations of spreading activation theories work over a classic AI semantic network structure. Nodes typically corresponding to symbolic knowledge (concepts), while links represent a connection between such knowledge. Markers are tokens that propagate throughout the network, representing the excitement initiated by the external stimulus. When multiple markers propgate through the semantic network, they cause some nodes to activate more than others, and may also find nodes that intersect (visited by more than one marker). These intersecting nodes represent relevant concepts.

Spreading activation theories were popular in cognitive psychology in the late 1960s and early 1970s. Early computer simulation models such as Anderson's ACT system appeared in the early 1970s. AI researchers picked up on the concepts shortly thereafter, and several research implementations of marker-passing came about in the late 1970s through mid-1980s. Typical implementations were geared toward either word-sense diambiguation or parallel inferencing. It is hard to say concretely why worked stopped on marker-passing systems, though I could speculate that it was a combination of multiple things - a general decline in AI ''buzz'' in the early 90s, the lack of affordable parallel hardware on which to adapt implementations, and the lack of formal provability of results or even a solid empirical foundation for characterizing marker-passing performance. I'd like to get Hendler or Charniak's opinion.

Spreading activation implementations began popping back up in 1993 or so as the Web powered into existence. I say spreading activation because these researchers, who typically came from an information processing background, did not use the term marker-passing, nor do they even seem aware of the wealth of work in the area given discussions in Related Work sections. But, the basic premise of applying spreading activation to problems of search is sound. The perceived potential benefits are:

  1. Scalability
  2. Ability to define and utilize richer semantic structures (such as using the Semantic Web)
  3. Relevance, a concept very well-suited to search
  4. Suitability of search problems to empirical study