Archive

Archive for January, 2008

Foaf Groups and Bloom Filters

January 29th, 2008

Bloom filters seem to be popping up in the foaf world quite a bit recently. Henry Story has been posting lots of good thoughts on this (see “My Bloomin’ Friends” from this past August as well as more recent postings on foaf-dev). Henry used an example Bloom Filter vocabulary in his discussion that looked something like this:

[
  a :Bloom ;
  :hashNum 4;
  :length 1000 ;
  :base64String "..."
]

I asked him if he had developed an actual vocabulary for this, or if he knew of any similar work, but didn’t find any published work.

I’d like to flesh this idea out a bit and get a usable vocabulary out of it. I think what Henry came up with looks good, but think it probably needs another predicate to identify the algorithm used to generate the filter. This would allow the vocabulary to be used across languages and environments which might rely on different hashing algorithms and allow systems to determine if they can interact through an arbitrary filter.

Here’s what a simple filter might look like as emitted by the LOAF tools:

[
  a :Bloom ;
  :algorithm <http://loaf.cantbedone.org/#filter> ;
  :hashNum 4;
  :length 1000 ;
  :base64String "..."
]

The idea here is that the value of the :algorithm predicate would indicate what algorithm was used to compute the filter (the value stashed in :base64String). Each :algorithm might imply its own set of parameters or allow for additional algorithm-specific predicates; based on the LOAF example, such additional information would include the underlying hashing algorithm for each hash (such as “sha1;salt=a”, “sha1;salt=b”, …). Of course, the :algorithm value should really be defined by the person who’s actually defining the algorithm (so my defining one for the LOAF algorithm in their namespace is bad form, but hopefully the idea is clear).

Bringing this back to Henry’s example, a FOAF file might then do something like this (modulo the appropriate OpenID login stuff):

<public> rdfs:seeAlso <protected> .
<protected> :readableBy [
  a foaf:Group ;
  bloom:filter [
    a bloom:Bloom ;
    bloom:algorithm <http://blogs.sun.com/bblfish/entry/my_bloomin_friends#applet_filter> ;
    bloom:hashNum 3;
    bloom:length 400 ;
    bloom:base64String "AIhDCURG/nWpcj1Q6OlJ4xV3Xsg9k4IiBgO2zye+PYLhRzwdok9BcTQdKGDCZDpoHgiN"
  ]
] .

Once they login, this would allow anyone in the (hidden) group to retrieve more data from <protected> than was available at <public>. I’m not sure how it would play with TAG guidelines, but this could also be used to provide varying levels of data at <public> depending on whether the client has logged in and what credentials they might have.

Of course, I have my own reasons for playing around with Bloom filters and RDF having to do with SPARQL, but I’ll save that for another post.

VN:F [1.9.22_1171]
Rating: 5.0/10 (2 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Author: Categories: Semantic Web Tags:

IEEE Intelligent Systems, Ten to Watch – 2008

January 24th, 2008

IEEE Intelligent Systems is pleased to announce the 2008 edition of the “Ten to Watch” list — a list of ten top researchers in the areas of coverage of our publication who have received their PhDs in the past couple of years. We solicited nominees from a number of sources, including the AAAI Fellows, the chairs of major CS departments around the world, a number of mailing lists in this area, and with an open call in our magazine and other public forums. We received a large number of very qualified applicants from around the world. A committee from the Advisory and Editorial Board winnowed this down to the top ten. The 2008 “Ten to Watch” recipients are:

Please join me in congratulating this outstanding group of young scientists.

A feature on these recipients will run in our May/June 2008 issue.

(The “Ten to Watch” was first awarded in 2006 – see the list of 2006 recipients.)

VN:F [1.9.22_1171]
Rating: 10.0/10 (1 vote cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Author: Categories: AI Tags:

OWL 1.1 documents – please review

January 9th, 2008

It is no secret, and in fact is a matter of public record, that although I am a member of the W3C’s OWL Working Group, I am not very happy with the language and its design. I worry that we are adding a lot of complexity to the language for a small amount of functionality gain (if any), that the work is being motivated by theoretical issues rather than user need, and that a small fragment of the growing OWL community is adding significant complexity to the language for very specific representational properties that follow from the Description Logic literature, rather than from a rich exploration of the many different roles a Web ontology language could have in the growing Semantic Web info-ecology (i.e. a world of mixed expressivity with heterogeneity among many different reasoners). The three documents that have been released are somewhat difficult to penetrate – at the end of this blog I have a list of the old and new OWL vocabulary terms and as you can see, despite the claim to a minor version number, the OWL 1.1 design almost doubles the size of the language.

Anyway, here’s your chance to prove me wrong if you think I’m mistaken, or to comment on the overall effort if you think I might have a point. The documents have been released and there is a call for reviews – the easiest way to get there is to follow the links from the W3C news item about the publications. Technical comments are, of course, welcome and needed, but since this is the first release of these documents with this wide of a dissemination, it is useful for us also to know if we appear to be addressing users’ needs and if the language design appears to be going in the right direction.

- Jim Hendler
p.s. Before I get accused of trying to sabotage the groups efforts or anything like that, let me point out that the WG’s mailing list archives are public, the history of my comments, the arguments against them, and the rest of the give and take, is all a matter of public record – and I encourage interested users to explore that literature and see from where the different points of views arise. You’d be just as mistaken to take my word on this as to take anyone else’s.

=== New OWL vocabulary, may be a slight variation from the published one – thanks to Peter Patel-Schneider for this list (which I have edited slightly for clarity from his original email)- see the thread there for details===

ORIGINAL OWL:
owl:AnnotationProperty
owl:Class
owl:DataRange
owl:DatatypeProperty
owl:FunctionalProperty
owl:InverseFunctionalProperty
owl:ObjectProperty
owl:Ontology
owl:Restriction
owl:SymmetricProperty
owl:TransitiveProperty
owl:allValuesFrom
owl:cardinality
owl:complementOf
owl:differentFrom
owl:disjointWith
owl:equivalentClass
owl:equivalentProperty
owl:hasValue
owl:imports
owl:intersectionOf
owl:inverseOf
owl:maxCardinality
owl:minCardinality
owl:onProperty
owl:oneOf
owl:sameAs
owl:someValuesFrom
owl:unionOf

owl:AllDifferent 		Alternative mapping for DifferentIndividuals axiom
owl:distinctMembers

owl:DeprecatedClass		Used in special "annotations"
owl:DeprecatedProperty

owl:OntologyProperty		Used for ontology properties

owl:backwardCompatibleWith	Built-in OWL DL annotation properties - OK
owl:priorVersion
owl:incompatibleWith
owl:versionInfo

owl:Nothing			Built-in OWL Classes - OK
owl:Thing

ADDED IN OWL 1.1

owl11:AsymmetricProperty       Typing triples
owl11:FunctionalDataProperty
owl11:FunctionalObjectProperty
owl11:IrreflexiveProperty
owl11:ReflexiveProperty
owl11:Individual
owl11:declaredAs

owl11:equivalentDataProperty	Disambiguation for EquivalentProperties axiom
owl11:equivalentObjectProperty

owl11:subDataPropertyOf		Disambiguation for SubProperty axiom
owl11:subObjectPropertyOf

owl11:DataRestriction		Disambiguation for restriction construct
owl11:ObjectRestriction

owl11:dataPropertyDomain	Disambiguation for domain construct
owl11:objectPropertyDomain

owl11:dataPropertyRange		Disambiguation for range construct
owl11:objectPropertyRange

owl11:Axiom			Annotations of axioms

owl11:NegativeDataPropertyAssertion	    For new OWL 1.1 constructs
owl11:NegativeObjectPropertyAssertion
owl11:SelfRestriction
owl11:onClass
owl11:onDataRange
owl11:disjointDataProperties
owl11:disjointObjectProperties
owl11:disjointUnionOf
owl11:inverseObjectPropertyExpression
owl11:<XSD facet>
VN:F [1.9.22_1171]
Rating: 0.0/10 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Author: Categories: owl, Semantic Web Tags: