W3C home > Mailing lists > Public > semantic-web@w3.org > January 2013

indexing and ordered searches

From: Jeremy J Carroll <jjc@syapse.com>
Date: Mon, 21 Jan 2013 16:11:46 -0800
Message-Id: <BD4751A5-5799-4941-84BA-326821F3BD61@syapse.com>
To: "semantic-web@w3.org" <semantic-web@w3.org>

What triple stores offer any optimization for integer or other numeric queries, e.g. with the following query

SELECT  ?a
WHERE { ?a  eg:prop ?i .
        FILTER ( 10 < ?i && ?i < 15 ) }

a naive approach would be to find all eg:prop triples and compute the filter for each one (O(N) complexity); if the store only has say integers as objects of eg:prop then a Predicate/Object index could achieve the same result in O(log(N)) by a numeric binary chop on the Object part of the index.

I looked at the TDB code and got the impression that the indices do in fact preserve ordering of at least some types, but could not see FILTERs being treated in the way indicated here  then I thought I would ask here.

Jeremy
Received on Tuesday, 22 January 2013 00:12:16 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 21:45:53 GMT