RDF molecules and lossless decompositions of RDF graphs

July 31st, 2005

Some RDF graphs can be viewed as making assertions about the world. Suppose you were given a graph, G, and asked to find supporting evidence on the web.

One approach is to search for documents with RDF graphs containing G as a sub-graph, adhering to RDF’s semantics for blank nodes and maybe applying some RDFS and OWL semantics. Even after doing that, few or maybe no RDF documents may contain *all* of G as a subgraph.

Another approach is to decompose G into its constituent triples and for each, use a Swoogle-like system to find documents containing it. But then what? The presence of blank nodes makes it difficult or impossible to assemble the support for G.

We’ve been exploring a third way using the notion of an RDF molecule. We start by computing a lossless decomposition of G into a set of subgraphs M. The decomposition is lossless in that combining the M‘s elements produces the original graph G, even if their blank nodes have been renamed apart. We can then use a Swoogle-like system to search for documents supporting each molecule in M. Find support for all, we have support for G.

We suspect that the RDF molecule concept has other potential uses. For details, see

Tracking RDF Graph Provenance using RDF Molecules, Li Ding, Tim Finin, Yun Peng, Paulo Pinheiro da Silva, and Deborah McGuinness, report TR-CS-05-06, Computer Science and Electrical Engineering, University of Maryland, Baltimore County, April 30, 2005.

The Semantic Web facilitates integrating partial knowledge and finding evidence for hypothesis from web knowledge sources. However, the appropriate level of granularity for tracking provenance of RDF graph remains in debate. RDF document is too coarse since it could contain irrelevant information. RDF triple will fail when two triples share the same blank node. Therefore, this paper investigates lossless decomposition of RDF graph and tracking the provenance of RDF graph using RDF molecule, which is the finest and lossless component of an RDF graph. A sub-graph is lossless if it can be used to restore the original graph without introducing new triples. A sub-graph is finest if it cannot be further decomposed into lossless sub-graphs. The lossless decomposition algorithms and RDF molecule have been formalized and implemented by a prototype RDF graph provenance service in Swoogle project.

DHS to deploy RFID at border crossings

July 31st, 2005

The U.S. Department of Homeland Security will install radio frequency technology at five border posts with Canada and Mexico to track foreigners driving in and out of North America beginning this coming Thursday. As people pass thorough the security check once, they will be given an index card sized document containing the chip. The document is to be placed on the car’s dashboard so that a person’s personal information can be read as they approach a border crossing. The mandatory program will apply to all foreigners with U.S. visas–including those from the 27 countries whose citizens don’t need visas for short U.S. visits–who cross into the United States at those points. Canadians and Mexicans, who fall under special immigration rules, are exempt from needing the chip. (Link )

I found these quotes, from Link), to be misleading:

Kimberly Weissman, spokeswoman for the US-VISIT program at the U.S. Department of Homeland Security told The Whig-Standard yesterday that the new devices can’t be tracked outside the border crossing area. “It has a range of 10 to 15 metres,” she said. “The UHF frequency that we’ve chosen makes it impossible to locate a specific person.”

She must have meant that (1) while the tags were in the border crossing area they couldn’t be read from outside the area; (2) the tags are not designed for localization. Such mistatements, which I assume were due to carelessness, can come back to haunt.

Hierarchy vs. facets vs. tags

July 30th, 2005

Mimi Yin has a nice discussion of three alternatives for organizing things on the Open Source Applications Foundation journal wiki. There are many other interesting entries in their journal.

Bart Simpson learns the first rule of RDF

July 29th, 2005

Adapted from Milinkito

CollaborativeRank for del.icio.us

July 29th, 2005

CollaborativeRank is a project by Amir Michail of the University of New South Wales. See his partial draft of a paper entitled CollaborativeRank — Motivating People to Give Helpful and Timely Ranking Suggestions. He has a new version for tagging, probably a better environment, based on del.icio.us tags:

Users on del.icio.us who give meaningful tags to helpful/timely URLs (as evidenced by others subsequently doing the same)
will be rewarded with higher CollaborativeRank, which means that their tagging will have greater influence on this search engine’s rankings.

Technorati Mobile launched

July 29th, 2005

Technorati launches Technorati Mobile.
Technorati Mobile

(Via The Blog Herald).

America Gasps for Breath in the R&D Marathon

July 27th, 2005

CRA’s computing research policy blog has a long exerpt from Vint Cerf’s op-ed in the Wall Street Journal. See the CRA post for more or the WSJ piece if you are a subscriber.

America will soon find its grip on the levers of international commerce slipping as we turn our backs on a proud tradition of technology innovation. The stewards of our national destiny are busily tightening the tap on the federal R&D budget, the most important source of funding for programs that seek to answer fundamental questions of science and technology.

In the 1960s and ’70s, a collection of academics and private-sector technologists, including a co-author of this piece, used findings funded by the Pentagon’s Advanced Research Projects Agency (now DARPA), to participate in implementation of the first wide-area packet switched network (the ARPANET) and the subsequent integrated collection of packet-switched networks (the Internet).

Now DARPA officials have revealed a shift in focus away from its history of open-ended long-range research, which typically has been performed in universities and nonprofit institutions. According to recent news reports, DARPA funding for university researchers in computer science has fallen from $214 million to $123 million from 2001 to 2004. Moreover, the focus of DARPA R&D is more near-term and more immediately defense-oriented than before. While this is defensible in some ways, the largest impacts of long-term research funded in the past by DARPA have been in areas that have wider or dual application to defense and the civilian sector.

The U.S. is already lagging behind in R&D funding. Our total national spending on R&D is 2.7% of our GDP, and now ranks sixth in the world, in relative terms, behind Israel (4.4%), Sweden (3.8%), Finland (3.4%), Japan (3.0%) and Iceland (2.9%). The federal government’s share of total national R&D spending has fallen from 66% in 1964 to 25%.

AOL Unveils New Mobile Search Services

July 27th, 2005

source( Gary Price’s blog at Search Engine Watch)
AOL just announced a search service(beta version) for PDA users. Gary Price pointed out some of its interesting features:

  • A new mobile web search tool (beta) that will automatically optimizes non-mobile friendly pages for mobile phones and devices. Google and Yahoo also offer this feature. AOL’s "transcoding" technology comes from InfoGin, an Israeli company.
  • The new AOL Mobile Search site also allows the user to access the AOL PinPoint Shopping and AOL Yellow Pages.
  • Even if you don’t have mobile web access, you can view the site on a regular browser here and see a mobile search results page
  • I ran a mobile "web" search for "Search Engine Watch" and spotted paid listings at the top of each results page (Results page one has paid listings, results page two shows paid listings and so on) Presently, neither Yahoo nor Google show paid listings on mobile search results pages.

AOL web search also identifies different sections in a web page. When I ran into the first result “http://www.umbc.edu/~finin/” using keyword “finin”, Tim’s photo was displayed at the very beginning, and the navigation bar has been detected and put on the second page. This beta version still has some limitations, e.g. it does not support JavaScript very well. Below is a table that compares three mobile search providers.

  Yahoo Google AOL search
web search (WAP) local, image, web local, image, web, mobile-web web, AOL services
SMS (text messaging) local, weather, stock, dictionary, area code … local, weather, stock, glossary, area code, movies, Q/A, phone book, driving direction, Froogle N/A
online demo WAP,   SMS SMS WEB

First FIPA IEEE meetings

July 26th, 2005

The Foundation for Intelligent Physical Agents (FIPA) was established some ten years ago to develop software standards for heterogeneous and interacting agents and agent-based systems. It successfully developed and published a very good set of standards for agent communication and agent infrastructure. Earlier this year FIPA became an IEEE sponsored standards committee.

FIPA will meet for the first time under this new banner this week in Utrecht on Friday 29 July from 10:30h to 12:30h, during AAMAS 2005.

The first technical FIPA/IEEE meeting to be held 13-14 September in Budapest just before CEEMAS 2005. Participation is free and open also to FIPA members and non-members alike, though participatns are aksed to register online.

New IST project on Ambient Intelligence Agents

July 26th, 2005

ASK-IT (Ambient Intelligence System of Agents for Knowledge-based and Integrated Services for Mobility Impaired users) Integrated Project (IST-2003-511298) aims to establish Ambient Intelligence (Ami) in semantic web enabled services, to support and promote the mobility of the Mobility Impaired (MI) people, enabling the provision of personalised, self-configurable, intuitive and context-related applications and services and facilitating knowledge and content organisation and processing. The project involves 42 partners from 13 different European countries and will last until September 2008.

EBB tide

July 22nd, 2005

We’ve upgraded EBB to WordPress The posting interface is similar, but there are some changes. If you encounter any problems, email finin@umbc.edu. We’ve added text ads in an attempt to get rich. Or at least make enough money to keep the ebiquity lab’s coffee fund solvent. If anyone’s moral sense is greatly offended let me know. Coffee drinkers get two votes, btw.

Fujitsu’s semantic web search tool

July 22nd, 2005

Fujitsu has demonstrated a “search tool for the Semantic Web” called the Business Information Navigator that use embedded metadata to identify relationships between documents spread throughout an organization and improve search results. The system was demonstrated at the Fujitsu Forum 2005, a company technology showcase that took place in Tokyo in mid July. The application visualizes search results using position and size for importance and different links reflecting the strength of the relationships between them. Information on the relevance of the documents to company divisions or individuals can be accessed via the graph. Fujitsu is said to be testing the system with an un-named domestic financial institution. I’ve been unable to find any additional information on this other than this story and related ones. It will be interesting to see if they use RDFS or OWL and if they do any inferencing.