XML Full-Text Search and Scoring
Sihem Amer-Yahia
AT&T Labs Research - USA
Database Department
Talk at the University of Tsukuba
May 10th, 2005

AT&T Labs
• 5,500 scientists and engineers
Middletown, NJ• AT&T’s patent portfolio includes
1,580 granted patents• Over 80% of our scientists &technologists hold a PhD or otheradvanced degree

Menlo Park, CA• Currently involved withapproximately 90 U.S. &international universities
Florham Park, NJ
05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research2Research Priorities for 2005
Speech Access
 Security
 Information Management


{
{



Enabling Infrastructure{{

05/10/2005

Network Management
Information Systems
Network
Software
Sihem Amer-Yahia -- AT&T Labs Research3Internet and Network Systems Research
{
{
{
{
{
{

{
{
{

Optical Systems
Access and Metro Network
Access Technology and Applications
Network Analysis and Optimization
Network Theory
Network Measurement, Monitoring, andManagement
IP Managed Services
Network Security
Internet and Network Incubation
05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

4

Information & Software Systems{ Statistics{ Information Mining{ Customer Information{ Information Visualization{ Data Management{ Communication Software – Artificial Intelligence{ Dependable, Distributed Computing andCommunication{ Software Systems - Scale{ Information Mining & Software Systems
Incubation{ Information Mining Services
05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

5Voice & IP Services{ Speech Algorithms & Engines{ Natural Language Understanding & Dialog{ Knowledge Discovery from Speech & Data
{ Multimedia Services{ IP Services{ Speech Services

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

6

Database Research at AT&T
 Researchers{ Sihem Amer-Yahia, Mary Fernandez, Rick Greer, Ted Johnson , Flip

Korn, Yannis Kotidis, Misha Rabinovich, Divesh Srivastava, Yannis
Velegrakis
 Research{ Large Scale Storage Systems{ XML Query Processing{ Data Stream Processing{ Network Monitoring{ Information Hosting{ Data Integration

 Systems{ Daytona, Silkroute, Galax, ShreX, GalaTex, Gigascope, Spider,

Bellman, RaDar.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research7Motivation

XML is able to represent a mix of structured andunstructured (text) information.



Examples of XML repositories are: IEEE INEX datacollection, Shakespeare's plays, DBLP, the Libraryof Congress collection.



Existing query languages for XML (XPath and
XQuery) are very limited when querying text.

Two main activities: W3C, INEX (TREC for XML).

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research8Outline

Extending XPath/XQuery to support
full-text search{Scoring on both content and structure{syntax, data model and semantics.
approximate matching on structure.

Open Issues.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research9Extending XPath/XQuery

Full-text Search in XML{

TeXQuery and XQuery Full-Text{definition and requirements.
syntax, data model and semantics.

GalaTex{architecture and implementation.

Joint work with Chavdar Botev and Jayavel Shanmugasundaram(Cornell U.), Emiran Curtmola (UC San Diego)

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

10

FT Search Queries<book id="1000"><author>Elina Rose</author><content><p> The usability of software measures how
well the software provides support for
quickly achieving specified goals.
</p><p> The users must be and feel well-served. </p></content></book>return book paragraphs containing the keyword “software” andstemmed forms of “usability” and do not contain “Rose”
return elements containing "usability" and ("software" or "goals") within
12 words
return ranked results

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

11

FT Search Definition
Context expression: XML nodes where the searchoccurs: e.g., book chapters.
{

Use XPath and XQuery to identify nodes in the search context

Return expression: document fragments that are returned tousers: e.g., book title and authors.
{

Use XPath and XQuery to build returned answers

Search expression: FT search conditions:e.g., Boolean, proximity, stemming.



{



Need for new language primitives

Score expression: a scoring function for threshold or top-K queries.
{

05/10/2005

Need for scoring framework

Sihem Amer-Yahia -- AT&T Labs Research

12

FT Search RequirementsComposable FT search conditions{

keyword, proximity order, times, stemming, stop words,
thesaurus, wildcards, …

Integrate FT search with XPath/XQuery.
{

Non-trivial since structured XML queries operate on XML
nodes, while FT queries operate on keywords and theirpositions within XML nodes.

No extension to XPath/XQuery data model.

Enable answer scoring and top-K queries.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research13

Prior Work







SQL/MM extends SQL with primitives on
text, images and spatial data.
Keyword similarity: Elixir, XXL, XIRQL.
Proximity distance: InQuery, SQL/MM.
Relevance ranking: XQueryIR, XIRQL, XXL,
JuruXML.
Dynamic context: XRank, TIX, XSearch.
All explore only a few FT search primitives
at a time and none of them develops a fully
compositional model for FT search.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

14

Prior Work

Current XML query languages provide very
rudimentary text/IR support:
{
{
{



Composability and extensibility not supported.
Data Model not formalized.
Hard to optimize across structured andunstructured queries.

Sophisticated scoring and ranking algorithms
interleaved with query processing.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

15

XQuery in a Nutshell
Functional language. Compositional.
 Input/Output: sequence of items
{

atomic types, elements, attributes, processing instructions,comments,...

XPath core navigation language.
 Variable binding.
 Element construction.


05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

16

XQuery FLWOR Expression
Find books on usability sorted on price:for $item in //books/book
let $pval := $item/metadata/pricewhere fn:contains($item//content,”usability”)
order by $pval ascending
return <result>{$item/title}<price> {$pval} </price></result>Limited sub-string operations: fn:start-with(), fn:end-with()
No scoring or ranking

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

17

Alternative XQuery Extensions
One function per FT primitive:
distance(
contains ($n, "usability"),contains ($n, "software") or contains ($n,"analysis), 10 )returned type not sufficient to compute keyword distance.



Sublanguage:
contains($n, "usability and (software or analysis)
distance 10")
FT search specified in an uninterpreted string that is opaque tothe rest of the XQuery language.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

18

TeXQuery[Amer-Yahia, Botev, Shanmugasundaram WWW’04]

Fully composable FT search primitives
called FTSelections.
 Composable with XPath/XQuery.
 Formal data model called FullMatch.
 Scoring and ranking.
 Basis for XQuery Full-Text.


05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

19

XQuery/TeXQuery Composability
Nest TeXQuery Expressions
in XQuery Expressions

Evaluate to a
Sequence of
items

XQueryExpression

FTSelections

Evaluate toa FullMatch

Nest XQuery Expressions
in TeXQuery Expressions

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

20

XQuery Full-TextFull-Text Task Force (FTTF) started in Fall 2002 to
extend XQuery with full-text search capabilities.



Members:{

AT&T, IBM, Microsoft, Oracle, the US Library of Congress.



Adopted TeXQuery in June 2004.



FTTF documents (public comments are welcome!):{{{05/10/2005

http://www.w3.org/TR/xmlquery-full-text-use-cases/
http://www.w3.org/TR/xmlquery-full-text-requirements/
http://www.w3.org/TR/xquery-full-text/

Sihem Amer-Yahia -- AT&T Labs Research

21

XQuery Full-Text Syntax


FTContainsExpr ::= RangeExpr ( "ftcontains"
FTSelection FTIgnoreOption? )?
returns true if at least one node in ContextExpr
satisfies FTSelection.

FTScoreClause ::= "score" "$" VarName "as" Expr
provides access to fine-grained ranking (e.g.,
threshold and top-k.)

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

22

FT Search: FTSelections


FTWord | FTAnd | FTOr | FTNot | FTMildNot | FTOrder | FTWindow| FTDistance | FTScope | FTTimes | FTSelection (FTMatchOptions)*{

books//title [. ftcontains “usability” ]{books//abstract [. ftcontains (“usability” || “web-testing”) ]{books//content [. ftcontains (“usability” && “software”)
ordered window at most 3 ]{books//abstract [. ftcontains (“usability” && “web”) samesentence]{books//title [. ftcontains “usability” 4 occurrences ]{books//book/section [. ftcontains books/book/title ]05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

23

FT Search: FTMatchoptions
FTCaseOption | FTDiacriticsOption| FTStemOption | FTThesaurusOption| FTStopwordOption | FTLanguageOption | FTWildCardOption

{books//title [ . ftcontains (“usability”) case sensitive withthesaurus “synonyms” ]{books//content [ . ftcontains (“usability” && “software”) withstopwords window at most 3 ]{books//title ftcontains (“Utilisation” language “French” withstemming && “.?site” with wildcards ){books//abstract [ . ftcontains “usability” || “web-testing”
with special characters ]05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

24

XQuery Full-Text Semantics
FullMatch∨
SimpleMatch∧

SimpleMatch

StringInclude StringExclude
Position

Position

Propositional formula over word positions in DNF

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

25

FullMatch (AllMatch) Data Model






FullMatch has a hierarchical structure
represented as XML.
Semantics of FTSelections specified astransformation of input FullMatches to an
output XML FullMatch.
Semantics of FTSelections specified in
XQuery itself!
FT search and structural search represented
in same framework:{

Enables joint optimization

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

26

Sample Document and Query<book(1) id(2)=``1000(3)''><author(4)>Elina(5) Rose(6)</author(7)><content(8)><p(9)> The(10) usability(11) of(12) software(13)measures(14) how(15) well(16) the(17)software(18) provides(19) support(20) for(21)quickly(22) achieving(23) specified(24)goals(25). </p(26)><p(27)>The(28) users(29) must(30) not(31) only(32)be(33) well-served(34), but(35) must(36)feel(37) well-served(38).</p(39)></content(40)></book(41)>books//book ftcontains(“usability” with stemming && “Rose”) window at most 10
05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research27

Query Evaluation Plan
Context
expression

Filteredcontext
expression

Scoring
FM4

Tranform
FullMatch

5

FTDistanceAtMost(at most 10 words)
FM3
FM1

Build
FullMatch

FTWordToken: “usability”

FTAnd

FM2

FTWordToken: “Rose”

getPositions() on the inverted lists

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research28

Positions of “usability” with stemming ,“Rose”<book(1) id(2)=``1000(3)''><author (4)>Elina(5) Rose(6)</author(7)><content(8)><p(9)> The(10) usability(11) of(12) software(13)measures(14) how(15) well(16) the(17)software(18) provides(19) support(20) for(21)quickly(22) achieving(23) specified(24)goals(25). </p(26)><p(27)>The(28) users(29) must(30) not(31) only(32)be(33) well-served(34), but(35) must(36)feel(37) well-served(38).</p(39)></content(40)></book(41)>05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research29

“usability” with stemming , “Rose”“usability” with stemming

05/10/2005“Rose”

Sihem Amer-Yahia -- AT&T Labs Research

30

FTWord Semantics
declare function fts:FTSingleSearchToken($evalCtx as element()*,$searchToken as schema-element(fts:TokenInfo),$matchOptions as xs:string,$queryPos as xs:string ) as schema-element (fts:FullMatch){ validate{ <fts:FullMatch>{ for $position in fts:getPositions($evalCtx, $searchToken, "")return<fts:SimpleMatch><fts:StringInclude queryString="{$searchToken/@word}“
queryPos="{$queryPos}">{ $position }</fts:StringInclude></fts:SimpleMatch>}</fts:fullMatches>}};
05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research31

“usability” with stemming && “Rose”

×“usability” with stemming“Rose”

function fts:FTAnd ($fullMatch1 as element(fullMatch, fts:FullMatch),$fullMatch2 as element(fullMatch, fts:FullMatch))as element(fullMatch, fts:FullMatch){<fullMatch> {for $sm1 in $fullMatch1/simpleMatch
for $sm2 in $fullMatch2/simpleMatch
return <simpleMatch> {$sm1/* $sm2/*} <simpleMatch></fullMatch>}
05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research32

“usability” with stemming && “Rose”

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research33

“usability” with stemming && “Rose” window at most 10

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

34

Scoring Requirements

Ranking answers on their relevance to FTquery is an inherent part of FT search.
Score value should reflect relevance ofanswer to FT expression.
Score value depends on scoring algorithm
but must satisfy:{{{

05/10/2005

Score is of type xs:float in the range [0, 1].
For score values greater than 0, a higher scoremust imply a higher degree of relevance.
If the Boolean evaluation of the FT expression isfalse then score value must be 0.
Sihem Amer-Yahia -- AT&T Labs Research

35

Scoring Examples
Query returning scores:
for $b in /books/bookscore $s as $b/content ftcontains "web site" && "usability" and$b//chapter/title ftcontains "testing"return $s

Top-K query example:
for $result at $pos infor $p in //books/book/paragraphscore $s as $p ftcontains “users“ && “software“ with
distance at most 13 words
order by $s
return $p
where $pos <= 10
return $result

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

36

New Scoring Desiderata






FT expression true implies score > 0.
score = 0 implies ftcontains false.
FT expression false should not imply
anything for score.
Answers satisfying query approximately may
be returned.
Scoring answers needs to consider scoring
FT, scalar and structural predicates.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research37

GalaTex overview








First complete conformant implementationof W3C XQuery Full-Text language.
Web demo includes W3C XQuery Full-Text
Use Cases:
http://www.galaxquery.com/galatex
Poster presentation at WWW’05.
Built on top of the Galax XQuery engine.
Soon (in a few weeks) available as open
source non-commercial software.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research38

GalaTex Architecture
<xml>
<xml>
<doc>
<doc>
Text Text
Text Text
Text Text
Text Text</doc></doc></xml</xml

Preprocessing& Inverted Lists
Generation

.xml

)
ns(
o
i
t
osi Pos() )Ptge tains nce(acon dDistrwo

Full-Text Primitives(FTWord,FTWindow, FTTimes
etc.)

inverted lists
Galax
XQuery Engine

Full-Text
Full-Text
Query
Query

05/10/2005

GalaTex
Parser4

Equivalent
Equivalent
XQueryXQueryQuery
Query

Sihem Amer-Yahia -- AT&T Labs Researchevaluation

<doc>
<doc>
Text Text
Text Text
Text Text
Text Text</doc></doc>.xml

39

GalaTex Demo Snapshot

6(: Q2: 2.2.2 Find all book subjects containing the phrase "usability testing" :)<results>{$xmlfile/books/book/metadata/subjects/subject[ . ftcontains "Usability testing" ]}</results><results>{ $xmlfile/books/book/metadata/subjects/subject[( let $ec_1 := ( . ) return
fts:FTContains( $ec_1,
fts:FTWordsSelectionAny( $ec_1, "Usability testing", validate{<fts:FTMatchOptions/>}, "1")))]} </results><results xmlns:fts="http://www.w3.org/xquery-fulltext"><subject >Usability testing</subject><subject >Usability testing</subject><subject >Usability testing</subject></results>
05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

40

Scoring XML

Joint work with Nick Koudas, (U. of Toronto) , Amélie Marian (Columbia
University), Divesh Srivastava (AT&T Labs Research), David Toman(University of Waterloo)

MotivationQueries on XML data combine conditions on structure withconditions on values.

Computing the relevance of an answer to a query should relyon:{{

Evaluating conditions on values and on structure approximately.
Combining scores.

Only a few recent contributions to approximate XML queries
on structure [Schlieder’02, Delobel and Rousset’02, AmerYahia et al’02].



Goal: Study query approximation on structure in XML anddefine a family of scoring methods.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research42

Outline
Examples of Query Approximation on
Structure.
 XML Query Relaxation.
 Scoring Functions for XML.


05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

43Query and Data Examples
book

book
info
authorCharles
Dickens

info

editionpaperbacktitle… Great
Expectations ..

author
C. Dickens

title
Great
Expectations

book
info
editionpaperbackauthor
Dickens
title
Great
Expectations

 Heterogeneous XML Data about booksbook Query:
book [./info/author ftcontains “Dickens”] and[./info/title ftcontains “Expectations”] and[./edition ftcontains “paperback”]

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

info

editionpaperbackauthor
Dickens

title
Great
Expectations
44

XML Query Relaxation[Amer-Yahia, Cho and Srivastava EDBT’02][Amer-Yahia, Lakshmanan and Pandit SIGMOD’04]
Query



book

Tree pattern relaxations:Leaf node deletion{ Edge generalization{ Subtree promotion

info

{

info
authorCharles
Dickens
05/10/2005

info

edition(paperback)
title
Great
Expectations

title
Great
Expectations
book

book

book

Data

author
Dickens

editionpaperbackauthor
C. Dickens

edition?

title
Great
Expectations

Sihem Amer-Yahia -- AT&T Labs Research

info
editionpaperbackauthor
Dickens
title
Great
Expectations
45

XML Query Relaxation[Amer-Yahia, Cho, Srivastava EDBT’02]
Query plan

Encode relaxations in asingle join plan:

X



X

More efficient than rewriting-based
techniques.
{ Static threshold for top-K pruning.
{ Batch mode processing.

title

{

Challenge: Maximize answer
scores to enable early pruning Traditional join ordering notapplicableX

author

X p( book,edition) infoor d( book,edition)book

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

edition46

Scoring Functions Critical for
Top-k Query ProcessingTop-k answer quality depends on scoring
function.
Efficient top-k query processing requires
scoring function:{{

Monotonic.
Fast to compute.

Little attention given to scoring functions forstructured and semi-structured data
Extensively studied over text data (e.g., tf.idf)
Æ Proposed scoring function inspired by tf.idf for XML
data{

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

47Adaptation of tf.idf to XML[Marian, Amer-Yahia, Koudas, Srivastava ICDE’05]

Document Collection(Information Retrieval)

XML Document

Document

XML Node (result is a subtree
rooted at a distinguished node, i.e.,a node with a given label andstructural properties)

Keyword(s)Query Pattern

idf (inverse document frequency) is a idf is a function of the fraction offunction of the fraction of documents distinguished nodes that match thethat contain the keyword(s)query patterntf (term frequency) is a function of
the number of occurrences of the
keyword in the document
05/10/2005

tf is a function of the number ofways the query pattern matches thedistinguished node

Sihem Amer-Yahia -- AT&T Labs Research48

Scoring Function for XML
Approximate MatchesbookRequired properties:

book

book

book

Exact matches should be
info
editioneditionscored higher than relaxed
info
info
edition infoedition(paperback)(paperback)matches (idf)(paperback) (paperback)author{ Returned elements withauthortitle
title title(Dickens)
several matches should be(Dickens) (Great(Great(Greatranked higher than those Expectations)Expectations)
Expectations)with fewer matches (tf){How to combine tf and idf?
tf.idf, as used by IR,
violates above properties{ Ranking based on idf, thenbreaking ties using tf
satisfies the properties

(a)

(b)

{

05/10/2005

score(a) <=>= score(b)Sihem Amer-Yahia -- AT&T Labs Research

49

A Family of Scoring Methods for
XML Path Queries

Twig predicate
High quality{ Expensive computation
{




info

Path predicates
Binary predicates
Low quality{ Fast computation

info

edition(paperback)authortitle(Dickens) (Great
Expectations)
05/10/2005

book + book + bookinfo

edition(paperback)authortitle(Dickens) (Great
Expectations)

{

book

book

Query

info

edition(paperback)title
author(Dickens) (Great
Expectations)book + book + book + bookauthorinfo
editiontitle(Dickens) (Great(paperback)Expectations)

Sihem Amer-Yahia -- AT&T Labs Research

50Representing Relaxed Query Patterns:
DAG Structure
a
b






Each child is more relaxed(has more matches) than its
parents
idf of a child is lower than
the idf of its parents
idf scores are accessible inconstant time for any match(complete or partial) usinghash function

Exhaustive algorithm to build the DAG

c
a

a

b
c

b
c
a

a

b
c

b c
a

a

b c

b

a

a

c

b
a

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

51

Query Processing using the DAG
 Benefits:{ Score computation done in a preprocessing

phase (using exact or approximate information){ Score access during query processing done inconstant time
{ Additional information needed for query
processing precomputed and accessed inconstant time (e.g., score upper bound) tf estimated at runtime based on available

information
05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research52Summary of Contributions


A family of scoring methods for XML queries
{
{




Structure and content
Structural relaxations

Evaluation of the scoring methods tradeoffs.
Efficient data structures to compute andaccess scores during top-k query
processing.

05/10/2005

Sihem Amer-Yahia -- AT&T Labs Research

53

Open Issues
Extensive experimental evaluation of scoring functions and ranking
algorithms for XML:{{Define a score-aware algebra for XQuery Full-Text for the joint
optimizations of queries on both structure and text:
{
{
{
{



INEX topics and datasets.
In collaboration with K. Hatano (NAIST).

Consistent scoring: equivalent query expressions should result in same
scores.
Consistent ranking: equivalent query expressions should result in thesame topK results for any given document fragment.
Optimize individual FTSelections: e.g. FTAnd.
In collaboration with E. Curtmola and A. Deutsch (UCSD).

Refine XQuery Full-Text language syntax and semantics:{{

05/10/2005

A syntax for specifying structural relaxations?
Semantics of structural relaxations when combined with query
approximation on content?

Sihem Amer-Yahia -- AT&T Labs Research54