KEYWORD-BASED SEARCH METHODS

Elmurod Kuriyozov

Keyword Search over Structured Data

• Anyone who has used a computer knows how to use keyword search
• No need to understand logic or query languages
• No need to understand (or have) structure in the data
• Database-style queries are more precise, but:
• Are more difficult for users to specify
• Require a schema to query over!
• Constructing a mediated, queriable schema is one of the major challenges in getting a data integration system deployed
• Can we use keyword search to help?

The Foundations

• Keyword search was studied in the database context before being extended to data integration

​

• We’ll start with these foundations before looking at what is different in the integration context
• How we model a database and the keyword search problem
• How we process keyword searches and efficiently return the top-scoring (top-k) results

Outline

• Basic concepts
• Data graph
• Keyword matching and scoring models
• Algorithms for ranked results
• Keyword search for data integration

​

The Data Graph

Captures relationships and their strengths, among data and metadata items

Nodes

• Classes, tables, attributes, field values
• May be weighted – representing authoritativeness, quality, correctness, etc.

Edges

• is-a and has-a relationships, foreign keys, hyperlinks, record links, schema alignments, possible joins, …
• May be weighted – representing strength of the connection, probability of match, etc.

Querying the Data Graph

• Queries are expressed as sets of keywords

​

• We match keywords to nodes, then seek to find a way to “connect” the matches in a tree

​

• The lowest-cost tree connecting a set of nodes is called a Steiner tree
• Formally, we want the top-k Steiner trees
• … However, this is NP-hard in the size of the graph!

Data Graph Example – Gene Terms, Classifications, Publications

• Blue nodes represent tables
• Genetic terms, record link to ontology, record link to publications, etc.
• Pink nodes represent attributes (columns)
• Brown rectangles represent field values
• Edges represent foreign keys, membership, etc.

Querying the Data Graph

membrane

publication

Relational query 1 tree: Term, Term2Ontology, Entry2Pub, Pubs

Relational query 2 tree: Term, Term2Ontology, Entry, Pubs

title

An index to tables,

not part of results

Trees to Ranked Results

Each query Steiner tree becomes a conjunctive query

• Return matching attributes, keys of matching relations
• Nodes 🡺 relation atoms, variables, bound values
• Edges 🡺 join predicates, inclusion, etc.
• Keyword matches to value nodes 🡺 selection predicates

Query tree 1 becomes:

q1(A,P,T) :- Term(A, “plasma membrane”), Term2Ontology(A, E), Entry2Pub(E, P), Pubs(P, T)

Computing and executing this query yields results

• Assign a score to each, based on the weights in the query and similarity scores from approximate joins or matches

Where Do Weights Come from?

Node weights:

• Expert scores
• PageRank and other authoritativeness scores
• Data quality metrics

Edge weights:

• String similarity metrics (edit distance, TF*IDF, etc.)
• Schema matching scores
• Probabilistic matches

​

In some systems the weights are all learned

Scoring Query Results

• The next issue: how to compose the scores in a query tree
• Weights are treated as costs or dissimilarities
• We want the k lowest-cost
• Two common scoring models exist:
• Sum the edge weights in the query tree
• The tree may have a required root (in some models), or not
• If there are node weights, move onto extra edges – see text
• Sum the costs of root-to-leaf edge costs
• This is for trees with required roots
• There may be multiple overlapping root 🡪 leaf paths
• Certain edges get double-counted, but they are independent

Outline

• Basic concepts
• Algorithms for ranked results
• Keyword search for data integration

​

Top-k Answers

• The challenge – efficiently computing the top-k scoring answers, at scale
• Two general classes of algorithms
• Graph expansion -- score is based on edge weights
• Model data + schema as a single graph
• Use a heuristic search strategy to explore from keyword matches to find trees
• Threshold-based merging – score is a function of field values
• Given a scoring function that depends on multiple attributes, how do we merge the results?
• Often combinations of the two are used

Graph Expansion

Basic process:

• Use an inverted index to find matches between keywords and graph nodes
• Iteratively search from the matches until we find trees

Term

Term2�Ontology

Entry2�Pub

Pubs

acc

name

...

go

_

id

entry

_

ac

entry

_

ac

pub

_

id

...

pub

_

id

...

title

GO

:

00059

plasma membrane

...

membrane

title

What Is the Expansion Process?

Assumptions here:

• Query result will be a rooted tree -- root is based on direction of foreign keys
• Scoring model is sum of edge weights (see text for other cases)

Two main heuristics:

• Backwards expansion
• Create a “cluster” for each leaf node
• Expand by following foreign keys backwards: lowest-cost-first
• Repeat until clusters intersect
• Bidirectional expansion
• Also have a “cluster” for the root node
• Expand clusters in prioritized way

Querying the Data Graph

membrane

publication

title

Graph vs. Attribute-Based Scores

• The previous strategy focuses on finding different subgraphs to identify the tuples to return
• Assumes the costs are defined from edge weights
• Uses prioritized exploration to find connections
• But part of the score may be defined in terms of the values of specific attributes in the query

score = … + weight₁ * T₁.attrib₁ + weight₂ * T₂.attrib₂ + …

• Assume we have an index of “partial tuples” by sort order of the attributes
• … and a way of computing the remaining results – e.g., by joining the partial tuples with others

Threshold-based Merging with Random Access

• Given multiple sorted indices L₁, …, L_m over the same “stream of tuples” try to return the k best-cost tuples with the fewest I/Os
• Assume cost function t(x₁,x₂,x₃,…, x_m) is monotone, i.e.,� t(x₁,x₂,x₃,…, x_m) ≤ t(x₁’,x₂’, x₃’, …, x_m’) � whenever x_i’≤ x_i’ for every i
• Assume we can retrieve/compute tuples with each x_i

L₁: Index �on x₁

L₂: Index �on x₂

L_m: Index �on x_m

…

Threshold-based Merge

k best ranked results

cost = t(x₁,x₂,x₃,…, x_m)

The Basic Thresholding Algorithm with Random Access (Sketch)

In parallel, read each of the indices L_i

• For each x_i retrieved from L_i retrieve the tuple R
• Obtain the full set of tuples R containing R
• this may involve computing a join query with R
• Compute the score t(R’) for each tuple R’ ∈ R
• If t(R’) is one of the k-best scores, remember R’ and t(R’)
• break ties arbitrarily
• For each index L_i let x_i be the lowest value of x_i read from the index
• Set a threshold value τ = t(x₁, x₂, …, x_m)
• Once we have seen k objects whose score is at least equal to τ, halt and return the k highest-scoring tuples that have been remembered

An Example: Tables & Indices

Full data:

L_rating: Index by ratings

L_price: Index by (5 - price)

Reading and Merging Results

L_ratings

L_price

t_alma = 0.5*4 + 0.5*2 = 3

Cost formula: t(rating,price) = rating * 0.5 + (5 - price) * 0.5

t_mcgillins = 0.5*4 + 0.5*3 = 3.5

τ = 0.5*4 + 0.5*3 = 3.5

no tuples above τ!

Reading and Merging Results

t_moshulu = 0.5*4 + 0.5*1 = 2.5

t_dinardo’s = 0.5*3 + 0.5*3 = 2.5

L_ratings

L_price

t_alma = 0.5*4 + 0.5*2 = 3

Cost formula: t(rating,price) = rating * 0.5 + (5 - price) * 0.5

t_mcgillins = 0.5*4 + 0.5*3 = 3.5

τ = 0.5*4 + 0.5*3 = 3.5

no tuples above τ!

Reading and Merging Results

t_moshulu = 0.5*4 + 0.5*1 = 2.5

t_dinardo’s = 0.5*3 + 0.5*3 = 2.5

L_ratings

L_price

t_alma = 0.5*4 + 0.5*2 = 3

Cost formula: t(rating,price) = rating * 0.5 + (5 - price) * 0.5

t_mcgillins = 0.5*4 + 0.5*3 = 3.5

these have already been read!

Reading and Merging Results

t_sotto = 0.5*3.5 + 0.5*2 = 2.75

t_moshulu = 0.5*4 + 0.5*1 = 2.5

t_dinardo’s = 0.5*3 + 0.5*3 = 2.5

L_ratings

L_price

t_alma = 0.5*4 + 0.5*2 = 3

Cost formula: t(rating,price) = rating * 0.5 + (5 - price) * 0.5

t_mcgillins = 0.5*4 + 0.5*3 = 3.5

τ = 0.5*3.5 + 0.5*2 = 2.75

Reading and Merging Results

t_sotto = 0.5*3.5 + 0.5*2 = 2.75

t_moshulu = 0.5*4 + 0.5*1 = 2.5

t_dinardo’s = 0.5*3 + 0.5*3 = 2.5

L_ratings

L_price

t_alma = 0.5*4 + 0.5*2 = 3

Cost formula: t(rating,price) = rating * 0.5 + (5 - price) * 0.5

t_mcgillins = 0.5*4 + 0.5*3 = 3.5

τ = 0.5*3.5 + 0.5*2 = 2.75

3 are above threshold

Summary of Top-k Algorithms

• Algorithms for producing top-k results seek to minimize the amount of computation and I/O
• Graph-based methods start with leaf and root nodes, do a prioritized search
• Threshold-based algorithms seek to minimize the amount of full computation that needs to happen
• Require a way of accessing subresults by each score component, in decreasing order of the score component
• These are the main building blocks to keyword search over databases, and sometimes used in combination

Outline

• Basic concepts
• Algorithms for ranked results
• Keyword search for data integration

​

Extending Keyword Search from�Databases to Data Integration

Integration poses several new challenges:

• Data is distributed
• This requires techniques such as those from Chapter 8 and from earlier in this section
• We cannot assume the edges in the data graph are already known and encoded as foreign keys, etc.
• In the integration setting we may need to automatically infer them, using schema matching (Chapter 5) and record linking (Chapter 4)
• Relations from different sources may represent different viewpoints and may not be mutually consistent
• Query answers should reflect the user’s assessment of the sources
• We may need to use learning on this

✓

🡺

🡺

Scalable Automatic Edge Inference

In a scalable way, we may need to:

• Discover data values that might be useful to join
• Can look at value overlap
• An “embarassingly parallel” task – easily computable on a cluster
• Discover semantically compatible relationships
• Essentially a schema matching problem
• Combine evidence from the above two
• Roughly the same problem as within a modern schema matching tool
• Use standard techniques from Chapters 4-5, but consider interactions with the query cost model and the learning model

Learning to Adjust Weights

• We may want to learn which sources are most relevant, which edges in the graph are valid or invalid
• Basic idea: introduce a loop:

Example Query Results & User Feedback

How Do We Learn about Edge and Node Weights from Feedback on Data?

• We need data provenance (Chapter 14) to “explain” the relationship between each output tuple and the queries that generated it

​

• The score components (e.g., schema matcher values) need to be represented as features for a machine learning algorithm

​

• We need an online learning algorithm that can take the feedback and adjust weights
• Typically based on perceptrons or support vector machines

Keyword Search Wrap-up

• Keyword search represents an interesting point between Web search and conventional data integration
• Can pose queries with little or no administrator work (mediated schemas, mappings, etc.)
• Trade-offs: ranked results only, results may have heterogeneous schemas, quality will be more variable
• Based on a model and techniques used for keyword search in databases
• But needs support for automatic inference of edges, plus learning of where mistakes were made!