We present an end-user oriented visual query system that combines faceted search with graph queries. Unlike previous systems, the architecture is designed to scale gracefully to both very large datasets and complex queries. This is achieved by setting up an indexing structure for facet values that can easily be scaled out arbitrarily. In return, it compromises some precision in computing sets of available facet values, but it does so in a highly con gurable manner.
Introduction
Faceted search [
Faceted search has also been extended to semantics-based data, e.g. in
SemFacet [
In this demo, we present a system that combines faceted search with graph queries, and that uses an indexing structure for facet values that can easily be scaled out arbitrarily. In return, it compromises some precision in computing sets of available facet values, in a highly con gurable manner. 1 https://lucene.apache.org/ 2 http://sphinxsearch.com/ , s n itoa se l m e a ,trs ten p c ce fa n o c
te se
u fca lav
Faceted Search Index controls s l o r t n o c Index con g. lls n a l q u e r y
We implemented this new functionality as part of OptiqueVQS [
The essence of the index structure is to use one table (that could be stored e.g. in a Lucene index) per concept available in the query interface. In addition to the facet values applicable to that concept, the index can also store information about the existence of object property links to other resources, facet values of such neighbouring resources, links from those to further resources, etc. How much information about neighbouring resources is to be stored in the index can be congured. Independently of the con guration, the index will provide an approximation from above (a superset) of the possible remaining values for each facet. 2
Approximating Facet Value Computation
We therefore approximate this computation, possibly computing a superset of the possible values, by considering only a part of Q, a neighbourhood of the focus variable ?x. In the simplest case, object properties are ignored, and classical faceted search on the data properties for the variable is performed, using only data lters on ?x. To do this e ectively, an index table with one column per facet is created. Standard search engine technology can perform the required ltering and gathering of possible values in a scalable way.
However, usability studies with OptiqueVQS have shown that users react to facet values that they consider to be obviously excluded by some of the object properties in their partial query. To accommodate an object property o, we can add a boolean-valued facet representing the existence of a triple ?x o ?y to some resource ?y in the data. The index data structure remains a simple table of facet values. As an example, consider the following data: :kona a :Drink; :kind "Coffee"; :suppliedBy :americanDrinks . :sencha a :Drink; :kind "Tea"; :suppliedBy :asianDrinks . :orangeJuice a :Drink; :kind "Juice" . :americanDrinks a :Supplier; :basedIn "America" . :asianDrinks a :Supplier; :basedIn "Asia" .
The user builds a query for drinks supplied by companies based in America, see screenshot (a) in Fig. 2. In screenshot (b), the index is con gured not to take the suppliedBy relation into account. Therefore, all three kinds of drinks are available as options for the Kind facet. In (c), the existence of a supplier is added to the index, and the choice Juice is disabled, since there is no product of that kind that has a supplier.
This can be further re ned by adding columns for datatype properties on the resources connected by object properties. These can then be taking into account when ltering for combinations of values permitted by Q. In the example, adding the based in facet of the supplier to the index table for drinks means that only Co ee will be available, as screenshot (d) shows.
Which combinations of object and datatype properties should be added as
columns to the search engine table, depending on the type of ?x, is controlled by
the index con guration. The details of this con guration, how it controls index
generation, and how the index is used to compute sets of possible facet values is
explained in a technical report, together with a more elaborate example [
Independently of the con guration, the index has the shape of a single table that can be scaled out using standard methods to arbitrarily large datasets. If necessary, index storage and processing can be parallelized, which is considerably easier for single tables than for relational or graph databases.
We will demonstrate our tool on an instance of the NPD benchmark [
An interesting remaining question concerns the relationship between perceived usability and index con guration. The larger the neighbourhood considered by the index, the sharper the approximation of possible facet values, but the more space will also be required by the index. We surmise that users expectations of possible choices can be met by considering rather small con gurations. To show this empirically in usability studies, and to get an idea of the trade-o between perceived usability and index size, are future work.
(a) example query (b) without supplier (c) existence of supplier (d) location of supplier
Acknowledgements This work has been funded by the Norwegian Research Council through SIRIUS (NFR 237898).