Shortest Path (was Re: Loading model into memory)

[Stephen Allen <sa...@apache.org>]

On Thu, Mar 8, 2012 at 7:50 AM, Andy Seaborne <an...@apache.org> wrote:
> On 08/03/12 15:03, Chris Dollin wrote:
>>
>> Mena said:
>>
>>> I want to apply the OnTools .FindShortestPath function on Yago.
>>> I am using the following code to load the model:
>>>
>>> Model model = TDBFactory.createModel(FullYagoDirectory);
>>>
>>> The FindShortestPath function taking too much time to return a result.
>>> I wonder if it is possible to load the model into main memory to make it
>>> faster or if there is any other way to make FindShortestPath much faster.
>>
>>
>>     Model model = ModelFactory.createDefaultModel().add(
>> TDBFactory.createModel(FullYagoDirectory) );
>>
>> Of course you may then run out of memory if the model is big.
>>
>> Chris
>>
>> ("Default" models are in-memory models.)
>
>
> IIRC YAGO(2) is a bit big.  The core is something like 30 million triples
> and full 80 million triples, I think.
>
> Bit big for memory unless you have a big server.
>
> Do you need "shortest path" or is just connectivity of entities acceptable?
>
> ARQ now has DISTINCT for paths and executes it (more) efficiently:
>
> { :x DISTINCT(path) ?y }
>
> in the ARQ language.
>
> (more to come here ... "soon")
>
>
> If you do want "shortest path", you may need to simplify the problem.
>
> Jena's OntTools shortest path is quite general - can you work with, say, the
> path being a fixed property?
>
> If so, maybe extract all the occurrences of that property and make a
> subgraph, hopefully smaller.


I'm currently working on a shortest path problem that does have a
fixed property.  In my application, icons can optionally be associated
with types and I'd like entities to use the "closest" icon(s) (i.e.
direct type(s), then parent(s), then grandparent(s), etc.).  Assuming
no RDFS inferencing were performed, to get the icon(s) for particular
instance you'd do something like:

PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX ex: <http://example.org/>
select ?icon
where {
    ex:Entity1 rdf:type/SHORTEST(rdfs:subClassOf*/ex:hasIcon) ?icon .
}

I saw some discussion of path lengths at [1][2], and I understand why
general path length is difficult because of the introduction of a new
datatype, but the shortest path operator here doesn't require
reporting the actual length to the user.

Do you think it's feasible to implement such an operator that utilizes
a breadth-first search in order to match the shortest paths?  I have
to admit I'm not as familiar with the property path code as I'd like
to be.

Alternatively, is there some way I'm missing to do this with sub-queries?

Thanks,
Stephen

[1] http://www.w3.org/2009/sparql/meeting/2009-03-17#path_lengths___26___20_path__2d_matching_variables
[2] http://www.w3.org/2009/sparql/wiki/Feature%3aPathLength

Property paths - upcoming changes.

[Andy Seaborne <an...@apache.org>]

The SPARQL-WG is seriously considering making some changes to property 
paths for the arbitrary length operators * (zero or more), + (one of 
more).  The results of some queries may change.

There is no formal decision yet so it is not definite it will happen.

The changes affect cardinality.  Currently, * and + match all possible 
so if there are multiple ways to get from A to B, there will be one rows 
in the each possible path.

Where paths included common elements, duplicates occur.  In highly 
connected graphs, it can be a lot of duplicates.  For example in a 
clique of 6 nodes, :p* has 326 solutions, while it has 6 if unique.  It 
gets worse for larger N.

(A clique is a graph in which every node is connection to every other - 
it's the most extreme for of highly connected).

In a FOAF graph, you usually want to know if A and B are connection, not 
how many times (and if you did want that you'd probably want the length 
as well and SPARQL 1.1 doesn't give you that).

rdfs:subclassOf* is example:

{ :thing rdf:type/rdfs:subclassOf* ?class } is the class and all 
superclasses of :thing.  An RDFS schema isn't a tree - it can have 
acyclic shapes in it as well (directed cycles really would not make 
sense!).  The app probably wants the classes once.

But sometimes duplicates do matter.

See for example:
http://people.apache.org/~andy/property-paths.html

which is adding up a purchase order to get the total cost.  Just because 
items have the same price (same literal or same structured node in the 
graph) doesn't mean they can be considered the same.

The current plan is to have two sets of operators, one counting 
(duplicates), one distinct matches.

There are:
   counting: {*} and {+}
   distinct: * and +

as being the common usage on way round and anyway {...} can generate 
duplicates in other forms.

But that is a change in semantics to * and + from the current SPARQL 1.1 
where * and + are counting.

For some (many?) uses of * and + this makes no difference. For example, 
accessing lists:

    { ?list rdf:rest*/rdf:first ?member }

Also, SPARQL 1.1 would have a general path operator DISTINCT(..path..) 
to turn duplicates into distinct results for that path segment.

path* == DISTINCT(path{*})
path+ == DISTINCT(path{+})

If you have any comments, please make them soon.

The development ARQ (2.9.1-SNAPSHOT) will have these changes in it very 
soon.

	Andy

Re: Shortest Path (was Re: Loading model into memory)

[Andy Seaborne <an...@apache.org>]

On 09/03/12 18:59, Andy Seaborne wrote:
>
>> I'm currently working on a shortest path problem that does have a
>> fixed property. In my application, icons can optionally be associated
>> with types and I'd like entities to use the "closest" icon(s) (i.e.
>> direct type(s), then parent(s), then grandparent(s), etc.). Assuming
>> no RDFS inferencing were performed, to get the icon(s) for particular
>> instance you'd do something like:
>>
>> PREFIX rdf:<http://www.w3.org/1999/02/22-rdf-syntax-ns#>
>> PREFIX rdfs:<http://www.w3.org/2000/01/rdf-schema#>
>> PREFIX ex:<http://example.org/>
>> select ?icon
>> where {
>> ex:Entity1 rdf:type/SHORTEST(rdfs:subClassOf*/ex:hasIcon) ?icon .
>> }
>>

Thought: the length is well defines and not a multiple value.  The 
operator could return the length: e.g.:

SHORTEST(:path, ?length)

	Andy

Re: Shortest Path (was Re: Loading model into memory)

[Andy Seaborne <an...@apache.org>]

> I'm currently working on a shortest path problem that does have a
> fixed property.  In my application, icons can optionally be associated
> with types and I'd like entities to use the "closest" icon(s) (i.e.
> direct type(s), then parent(s), then grandparent(s), etc.).  Assuming
> no RDFS inferencing were performed, to get the icon(s) for particular
> instance you'd do something like:
>
> PREFIX rdf:<http://www.w3.org/1999/02/22-rdf-syntax-ns#>
> PREFIX rdfs:<http://www.w3.org/2000/01/rdf-schema#>
> PREFIX ex:<http://example.org/>
> select ?icon
> where {
>      ex:Entity1 rdf:type/SHORTEST(rdfs:subClassOf*/ex:hasIcon) ?icon .
> }
>
> I saw some discussion of path lengths at [1][2], and I understand why
> general path length is difficult because of the introduction of a new
> datatype, but the shortest path operator here doesn't require
> reporting the actual length to the user.
>
> Do you think it's feasible to implement such an operator that utilizes
> a breadth-first search in order to match the shortest paths?  I have
> to admit I'm not as familiar with the property path code as I'd like
> to be.

Yes and I think it's a good idea to have it.

SPARQL isn't a graph analysis language but access to some common 
operators so mixed purpose queries can be done is going to be helpful.

I am doing some work on property paths at the moment to add the features 
that SPARQL-WG is likely to adopt.  Even if they don't having them in 
ARQ/extended-SPARQL  will be good so I'm doing them anyway. [*]

As I have the parser and syntax support to update, I'll add SHORTEST at 
the same time.  It'll parse ... and throw "unimplemented" if touched at 
execution time. ARQ/extended-SPARQL experimental feature.

>
> Alternatively, is there some way I'm missing to do this with sub-queries?

As the path can be arbitrary length, and * and + give you no control on 
outcome, there isn't a way to use a sub-query (that I can think of!).

Floyd-Warshall grows the shortest path from each end of the path and 
terminates when it meets in the middle.  That's an arbitrary loop.

	Andy

>
> Thanks,
> Stephen
>
> [1] http://www.w3.org/2009/sparql/meeting/2009-03-17#path_lengths___26___20_path__2d_matching_variables
> [2] http://www.w3.org/2009/sparql/wiki/Feature%3aPathLength

	Andy