View article

Relational, XML and HTML data can be represented as graphs with entities as nodes and relationships as edges. The common representation enables novel data integration applications. An important building block is schemafree keyword search on such graphs, with text associated with nodes and possibly edges. Answers to keyword queries are usually modeled as trees connecting nodes matching the keywords.

In this paper we first extend the keyword search model by proposing a class of proximity queries that search for nodes most closely/densely connected to a set of keywords, possibly by multiple paths. We illustrate several applications for such queries, and define a model for scoring proximity based on spreading activation. Our keyword query model is further enhanced by allowing the user to specify approximate twig patterns that answers edges should match.