Multi-Example Search in Rich Information Graphs

Matteo Lissandrini, Davide Mottin, Themis Palpanas, Yannis Velegrakis

Abstract :

In rich information spaces, it is often hard for users to formally specify the characteristics of the desired answers, either due to the complexity of the schema or of the query language, or even because they do not know exactly what they are looking for. Exemplar queries constitute a query paradigm that overcomes those problems, by allowing users to provide examples of the elements of interest in place of the query specification. In this paper, we propose a general approach where the user-provided example can comprise several partial specification fragments, where each fragment describes only one part of the desired result. We provide a formal definition of the problem, which generalizes existing formulations for both the relational and the graph model. We then describe exact algorithms for its solution for the case of information graphs, as well as top-k algorithms. Experiments on large real datasets demonstrate the effectiveness and efficiency of the proposed approach.


Multi-Example Search in Rich Information Graphs.”
Proceedings of the 34rd IEEE International Conference on Data Engineering, ICDE 2018 (pp. 809-820).

  author    = {Lissandrini, Matteo and Mottin, Davide and Velegrakis, Yannis and Palpanas, Themis},
  title     = {{Multi-Example Search in Rich Information Graphs}},
  booktitle = {34rd {IEEE} International Conference on Data Engineering, {ICDE} 2018, Paris, France, April 16-19, 2018},
  pages     = {809--820},
  year      = {2018},
  url       = {},
  doi       = {10.1109/ICDE.2018.00078}