English Sentence Retrieval System Based on
Dependency Structure and its Evaluation
Yoshihide Kato
Graduate School of International Development
Nagoya University
Furo-cho, Chikusa-ku, Nagoya,464-8601 Japanyosihide@gsid.nagoya-u.ac.jp

Seiji Egawa
Graduate School of Information Science
Nagoya University
Furo-cho, Chikusa-ku, Nagoya,464-8601 Japan

Shigeki Matsubara
Information Technology Center
Nagoya University
Furo-cho, Chikusa-ku, Nagoya,464-8601 Japan

Yasuyoshi Inagaki
Faculty of Engineering
Toyohashi University of Technology
1-1 Hibarigaoka, Tempaku-cho, Toyohashi, Aichi,
441-8580 Japan

Abstract
This paper proposes a system of retrieving English sentences by utilizing linguistically structural information. The
user’s query consists of a sequence of keywords. The system automatically identifies dependency relations between
occurrences of the keywords in sentences and classifies thesentences according to those dependency relations. The system provides a simple and intuitive keyword-based interface
and realizes linguistically sophisticated sentence retrieval.
We conducted an experiment to evaluate the accuracy of thesystem. The results demonstrate that the system provides
high accuracy.

1. Introduction
Sentence retrieval systems help non-natives to write papers in English. These systems are useful for English learners, translators and so on. Many systems have been presented so far.
Most systems provide keyword-based search functionality (for example, Tonguen[6] and WebCorp1 ). They aresimple and intuitive, but not linguistically sophisticatedenough to utilize language structure.
On the other hand, Corley et al.[2] and Resnik et al.[5]have presented syntax-based search systems, Gsearch and
Linguist’s Search Engine (LSE), respectively. The Gsearch
1 http://www.webcorp.org.uk/

receives a phrase structure pattern and context free grammarfrom the user. The system parses sentences by using the
given grammar, and returns the sentences whose parse trees
match the given pattern. In the LSE, the user first gives anexample of sentences which s/he needs. The system parses
the example sentence by using a parser and returns the parsetree. The user edits the parse tree to specify a structural pattern. Finally, the system returns the sentences whose parsetrees match the pattern.
These systems can retrieve sentences by utilizing syntactic structure. However, the interfaces are not simple. The
user needs to build a grammar or to specify a structural pattern. It is a hard task for naive users.
This paper presents a sentence retrieval system which
provides both a keyword-based interface and syntax-based
search functionality. The user’s query consists of a sequence of keywords. The system automatically identifies
dependency relations (modifier-modifee relations) between
the occurrences of the keywords in sentences, and classifies
the sentences according to the identified dependency relations. The classification assists the user to obtain the sentences which s/he needs. The user needs neither to build agrammar like the Gsearch nor to edit a structural query likethe LSE. We conducted an experiment to evaluate the accuracy of the classification. The results demonstrate that theclassification is performed with high accuracy.
This paper is organized as follows: Section 2 gives an
overview of our system. Section 3 proposes an algorithm ofidentifying dependency structure patterns, which is the basis of our system, and Section 4 describes a sentence clas-

dobj

dobj
det

iobj
det
These
det
1

ncsubjgrammar
noun
2

dobj

parse
verb
3

ncsubj iobj

ncmod ncmod

inasentences
noun preposition det
564

det :determinerncsubj:subject
dobj :object

dobj

psycholinguistically
adverb7

plausible
adjective
8

fashionnoun
9ncmod:modifier
iobj :preposition modifying verb

Figure 1. Dependency structure for “These
grammars parse sentences in a psycholinguistically plausible fashion.”

We beganbyparsingnoun verb preposition verb
1
2
3
4

det
the
det
5

det
ncmod
sentencesinthenoun preposition det
6
7
8

ncmod
multilingual corpus
noun
adjective
10
9

Figure 2. Dependency structure for “We began by parsing the sentences in the multilingual corpus.”(b) We want to map phrase structure trees to parses which
predict the words of the sentences in the multilingual
corpus.

sification based on the algorithm. Section 5 reports experimental results. In Section 6, we concludes this paper.

2. An Overview of Our System
Our proposed system has the following three features:
1. keyword-based interface: The user’s query consists ofa sequence of keywords.
2. dependency-based retrieval: The resulting sentences
should include the all keywords and there should be
dependency relations between the occurrences of the
keywords.
3. sentence classification: The system classifies the resulting sentences according to the dependency relations
holding between the occurrences of the keywords.
The first feature realizes an intuitive interface between thesystem and its user. We expect that the second and thirdfeatures make the retrieval effective. In the rest of this section, we describe the basic concept of the second and thirdfeatures.
As an example, let us consider the following query:parse sentence in -n

xcomp

(1)

Our system accepts words or part-of-speech (POS) tags as
keywords. -n means a noun word. For query (1), our system returns sentences such as the following:(a) These grammars parse sentences in a psycholinguistically plausible fashion.
The sentence has the dependency relations between the occurrences of the keywords (see Figure 1).
On the other hand, the system discards from the search
results the following sentence which has no dependency relations between the occurrences of the keywords:

This sentence is probably irrelevant to the user intention.
The second feature means that the system discards this typeof sentence from the search results.
Let us consider another sentence:(c) We began by parsing the sentences in the multilingual
corpus.
This sentence also has dependency relations between theoccurrences of the keywords (see Figure 2). That is, sentence (c) is also included in the search result. However, thedependency relations are different from that in sentence (a).
In order for the user to easily obtain sentences which s/heneeds, the system should display these sentences separately.
This is why our system has the third feature.

3. Identifying Dependency Structure PatternThis section proposes a method of identifying dependency structure patterns. The method is the basis of oursystem. It receives a keyword sequence and a sentence
annotated with dependency structure, and returns a dependency structure pattern which represents dependency relations holding between the occurrences of the keywords inthe sentence. As an example, assume that query (1) and thesentence with the dependency structure shown in Figure 1
are given. For this inputs, the method generates a patternshown in Figure 3.
The method is an extended version of the method proposed in the literature[4]. It is augmented with types of dependency relations.

3.1. A Method of Identifying Dependency Structure
Patterns
Our proposed method identifies dependency structure
patterns which are formed by occurrences of keywords inr(a) h → h'

iobj
dobj
parse
verb
3

dobj

sentencesinnoun preposition
4
5dfashionnoun
9

Figure 3. An example of dependency structure pattern for parse sentence in -n.

r

TL
…

h

DL

r

TL
…

h

DR

T'R
…

h'

D'L

(a)

D'R

r
d

dependency structure: D

combining: Let d = (h, DL , DR , TL , TR ) and d =, DR
, TL , TR ) be dependency structure pat(h , DL
terns for qi · · · qj and qj+1 · · · qk , respectively. Let
rm(d) < lm(d ) where rm(d) and lm(d) are therightmost and leftmost positions in d, respectively.
r= ε, then generate a
If h → h ∈ D and DR, DR, rTL , TR )dependency structure pattern (h , dDLr
for qi · · · qj qj+1 · · · qk (see Figure 4(a)). If h →h ∈ D, then generate a dependency structure
pattern (h, DL , DR d, TL , TR r) for qi · · · qj qj+1 · · · qk
(see Figure 4(b)).

T'L…

Figure 4. Combining.

sentence: s = w1 · · · wn (w1 , . . . , wn are pairs of words
and POS tags)

initialization: For each qi (1 ≤ i ≤ m) and each wj (1 ≤j ≤ n), if qi matches wj , then generate the dependency pattern (j, ε, ε, ε, ε). ε means null list.

d'

TR
…

DL

where D is a set of dependency relations between the words
in s. If wj modifies wk and a relation r holds between wjr
and wk , (j, k, r) is an element of D. We write j → k for(j, k, r).
We define a dependency structure pattern as a 5-tupled = (h, DL , DR , TL , TR ), where h is a word position, DL
and DR are lists of dependency structure patterns and TL
and TR are lists of relations. h is called head of d. The dependency structure pattern d represents that each head of thedependency structure pattern in DL modifies h from left.
Similarly for DR , from right. The i-th element ri in TL
means that the relation ri holds between the head of the i-th
element in DL and the head of d. Similarly for TR .
Our method generates dependency structure patterns
from a query q1 · · · qm by applying the following operations
in a bottom-up fashion.

h'

D'L

r
(b) h' → h
d

T'L
…

DR

a sentence. If the occurrences of the keywords have no dependency relations, the method fails to identify the pattern.
The inputs are as follows:
query: q1 · · · qm (q1 , . . . , qm are keywords)

d'

TR
…

TL
…

TR
…

h

DL

h'*

DR

(b)

r
d
h'*

TL
…

h

DL

TR
…
DR

Figure 5. Interpolation.
By applying the combining operation to the query, all dependency structure patterns that directly connect the occurrences of the keywords in the sentence s can be generated.

3.2. Interpolation
In some cases, the user may not intend that some keywords in the query directly modify the other keywords. To
process such queries robustly, the interpolation operation isused:interpolation: Let d be a dependency structure pattern forqi · · · qj whose head is h. For h and r such thatrh → h ∈ D, if rm(d) < h , then generate a dependency structure pattern (h∗ , d, ε, r, ε) for qi · · · qj (seeFigure 5 (a)). If h < lm(d), then generate a dependency structure pattern (h∗ , ε, d, ε, r) for qi · · · qj . A
symbol ∗ means that h is introduced by interpolation(see Figure5 (b)).

The operation can generate dependency structure patterns
which include words not occuring in the query. However, unrestricted application of the interpolation operation
generates dependency structure patterns for any sentenceswhere all the keywords occur. It is inconsistent with theconcept of our system described in Section 2. To avoid useless application of the operation, we introduce a cost defined by the number of occurrence of ∗ in the dependency
structure pattern. The algorithm generates no dependency
structure patterns whose costs are greater than a threshold.

3.3. Algorithm
Figure 6 illustrates the algorithm of identifying dependency structure patterns. θ is the threshold of cost. Di,j,c
is used for recording the dependency structure patterns withcost c for qi+1 · · · qj .

3.4. Examples
3.4.1

An example of combining operation

As an example, let us consider query (1) and the sentencewith the dependency structure shown in Figure 1.
The first keyword parse matches the third word in thesentence, so the following dependency structure pattern isgenerated by the initialization:(3, ε, ε, ε, ε)(2)

Similarly, the following dependency structure pattern isgenerated for the keyword sentence:(4, ε, ε, ε, ε)(3)(5, ε, ε, ε, ε)(4)

input: query q1 · · · qm ,sentence w1 · · · wn ,dependency structure D
initialization:for i = 1 to m dofor each j s.t. wj = qi dopush (j, ε, ε, ε, ε) to Di−1,i,0 ;for cost = 0 to θ do
combining:for k = 2 to m dofor j = k − 1 down to 1 dofor i = j − 1 down to 0 do
for c = o to cost dofor each d = (h, DL , DR , TL , TR ) ∈ Di,j,cd = (h , DL
, DR
, TL , TR ) ∈ Dj,k,cost−cs.t. rm(d) < lm(d ) dor
if h → h ∈ D ∧ DR
= ε thenpush (h , dDL , DR , rTL , TR ) to Di,k,cost ;r
if h → h ∈ D thenpush (h, DL , DR d , TL , TR r) to Di,k,cost ;interpolation:for j = 1 to m dofor i = j − 1 down to 0 do
if i = 0 ∨ j = m thenfor each d = (h, DL , DR , TL , TR ) ∈ Di,j,cost dor
for h s.t. h → h ∈ D do
if h > rm(d) thenpush (h∗ , d, ε, r, ε) to Di,j,cost+1 ;else if h < lm(d) thenpush (h∗ , ε, d, ε, r) to Di,j,cost+1 ;return D0,m,0 ∪ · · · ∪ D0,m,cost ;Figure 6. An algorithm of identifying dependency structure patterns

For the keyword in ,dobj

Furthermore, since 9 → 5 holds between adjacent patterns(4) and (7), the following pattern is generated for in -n.

is generated. For the keyword -n,(2, ε, ε, ε, ε)(5)(4, ε, ε, ε, ε)(6)(9, ε, ε, ε, ε)(7)

are generated.
For the adjacent patterns (2) and (3), there exists a dependobj

dency relation between their heads, that is, 4 → 3 holds.
Therefore, these patterns are combined and the following
pattern is generated for parse sentence:(3, ε, (4, ε, ε, ε, ε), ε, dobj)(8)(5, ε, (9, ε, ε, ε, ε), ε, dobj)(9)

By applying the combining operation to patterns (8) and (9),(3,ε, (4, ε, ε, ε, ε) · (5, ε, (9, ε, ε, ε, ε), ε, dobj),
ε, dobj · iobj)(10)

is generated.
On the other hand, for the sentences where some occurrences of keywords do not directly modify the other (forinstance, sentence (b) in Section 2), the algorithm generates
no dependency structure patterns.

3.4.2

An example of interpolation operation

dobj

Let us consider another example of query:

parse
verb

parse sentence fashionand the sentence in Figure 1. If we set the threshold of cost
to 0, no dependency structure patterns are generated. If thethreshold is 1, a dependency structure pattern is generated
by the following steps. For the keyword fashion, de-

ncmod

dobj

sentenceinnoun
preposition noun

Figure 7. Another example of dependency
structure pattern for parse sentence in
-n.

dobj

pendency structure pattern (7) is generated. Since 9 → 5
holds, the following dependency structure pattern is generated for fashion by applying the interpolation operation
to pattern (7):5. Implementation and Evaluation

The cost of this pattern is 1. Next, for this pattern and pattern (8), the dependency structure pattern in Figure 3 is generated by the combining operation.
This example shows that the interpolation operation allows the generation of the dependency structure pattern inthe case where some occurrences of keywords do not directly modify the other occurrences.

We developed an English sentence retrieval system basedon the algorithm described in Section 3. The system works
on a web server. It has a collection of English sentences
which were taken from papers in the area of computer science.
To evaluate our system, we conducted an experiment.
We collected queries and judged which sentences are relevant to the queries. By using this test collection, we measured recall and precision of our system.

4. Classifying Sentences

5.1. Building an English Sentence Collection

Given a query, our system identifies dependency structure patterns for sentences in a sentence collection and classifies the sentences according to the identified dependency
structure patterns. If sentences have an identical dependency structure pattern, they are classified as a same class.
As an example, let us consider query (1). For the queryand the following sentences, the identical dependency structure pattern shown in Figure 3 is identified:

We built an English sentence collection by extracting
sentences from PDF formatted papers in the area of computer science. The procedure is as follows:(5∗ , ε, (9, ε, ε, ε, ε), ε, dobj)(11)• These grammars parse sentences in a psycholinguistically plausible fashion. (=sentence (a))• Our method can still parse large sentences in a reasonable amount of time.
These sentences are included in a same class.
On the other hand, for the following sentences, the dependency structure pattern shown in Figure 7 is identified:• We began by parsing the sentences in the multilingual
corpus. (=sentence (c))• We parse all the sentences in the domain document
collection.
These sentences are included in the other class.
This example shows that dependency structure pattern
identification enables the system to classify sentences according to the relation holding between keywords.

1. Convert PDF formatted papers to XML formatted files
by using pdf2html2 . XML formatted files have the information of text and its layout.
2. Extract paragraphs by using the method in the literature [3], which analyzes the layout of a document.
3. Annotate sentences with dependency structures by using the dependency parser RASP [1].
We obtained 185,488 sentences.

5.2. Test Collection
To evaluate our system, we constructed a test collection,
which consists of the following data:
1. Queries
2. Sentences sampled from the sentence collection
3. Relevance judgements
2 http://pdftohtml.sourceforge.net/

Table 1. Distribution of queries.
query length # of queries # of queries for which
relevant sentences(word)
were sampled
1
42
11
128
34
2
95
27
3
26
9
4
11
1
5

Generally speaking, whether a sentence is relevant to aquery depends on the user’s need. So the sentence relevances were assessed by subjective judgement.
The subjects made queries and assessed sentence relevances. The relevances are binary. To motivate the subjects
to make queries, we gave questions about English composition to the subjects. Because it is impractical to assess therelevances for all sentences in the sentence collection, we
sampled about 20 sentences for every query and the subjects
judged the relevances. Sentences were sampled through thefollowing procedure:
1. Extract all sentences which include all keywords in thequery.
2. Classify the extracted sentences by the sentence classification described in Section 4.

Table 2. Precision and recall.
precision(%) recall(%) F-value
baseline1
44.2
100.0
0.613
100.0
45.9
0.629
baseline2
69.0
77.9
0.732
our system

We define recall and precision as the following. Let d1 ,. . ., dl be dependency structure patterns and Sdi be a set ofsentences for which the dependency structure pattern di are
identified. Let C be a set of sentences relevant to the query.
Before giving the definition, let us consider an ideal classification. If the classification is ideal, there exists S ∗ ∈{Sd1 , . . . , Sdl } such that S ∗ = C. By using precision andrecall measures, we judge whether a classification has sucha class.
The definition is as follows:
1. For each Sdi , calculate the precision Pdi and the recall
Rdi of the class Sdi .
2P

Pdi and Rdi are defined as follows:

3. Randomly sample sentences from every class. The total of sampled sentences are about 20.
Sampled sentences are shuffled and shown to the subjects.
The information about dependency structure were removed
from the sentences. This process is automatically executedon a web-based interface. The subjects assess the relevancesof these sentences.
To evaluate the influence of the interpolation operation,
we set the threshold of cost to 0 or 1 for each query.
The subjects are 7 students in computer science. We obtained a total of 302 queries. The average length of thequeries is 2.5 words. Table 1 shows the distribution of thequeries. For 68 queries, no sentences were sampled. For
58 queries, the subjects did not judge the relevances of thesampled sentences. For 94 queries, the subjects judged thatno sentences were relevant. For 82 queries, the subjects
judged that some relevant sentences existed. We measured
precision and recall for 71 queries in these queries whose
lengths are greater than 1.

5.3. Evaluation
By using the test collection described in the previous section, we measured recall and precision of our system.

R

i di
2. Select Sdi which maximizes F -value Pd d+R
. We
di
i
define the precision and the recall of classification{Sd1 , . . . , Sdl } as that of Sdi .

Pdi =|Sdi ∩ C||Sdi |Rdi =|Sdi ∩ C||C|

5.4. Results
Table 2 shows the precision and the recall of our proposed classification. As a baseline for the experiment, weconsider the cases where sentences are not classified (baseline1) and where each sentence is in a class. The F -valueof our system is higher than the baseline. This result showsthe effectiveness of the sentence classification.

5.5. Evaluating the influence of interpolation
We assume that dependency relations exist between theoccurrences of keywords in relevant sentences. If the assumption is true, dependency structure patterns with cost
0 must be generated for relevant sentences. To prove theassumption, we investigated the relation between cost andnumber of relevant sentences. Table 3 shows the result. This
result is for 23 queries where dependency pattern identification with cost threshold 1 were executed. The result showsthat dependency structure pattern with cost 0 are identified

Table 3. Relation between cost and number ofsentences relevant to queries
the cost ofgenerated dependency
structure pattern
0
1

the number of
relevant
sentences
76
51

total

193
353

for many relevant sentences. χ2 -test revealed that there wassignificant difference (p < 0.01) between cost 0 and 1.
On the other hand, for a few of the relevant sentences,
dependency structure patterns with cost 1 were generated.
This means that the interpolation is useful for processing
queries robustly.

6. Conclusion
This paper has presented an English sentence retrieval
system based on dependency structure. The system finds
sentences in which dependency relations hold between theoccurrences of keywords. A subjective experiment demonstrated the effectiveness of the system.
Our proposed dependency structure pattern identification
relies on the parsing results of a dependency parser. Thismeans that a misanalysis of the parser may lead to incorrect
identification. In order to solve this problem, we will investigate a method to identify dependency structure patterns byutilizing only reliable parsing results.

Acknowledgment
This research was partially supported by the Grant-inAid for Scientific Research (B) (No. 20300058) of JSPS.

References[1] T. Briscoe, J. Carroll, and R. Watson. The second releaseof the RASP system. In Proceedings of COLING/ACL 2006
Intaractive Presentation Sessions, pages 77–80, 2006.
[2] S. Corley, M. Corley, F. Keller, M. W. Crocker, and S. Trewin.
Finding syntactic structure in unparsed corpora: The gsearch
corpus query system.
Computers and the Humanities,
35(2):81–94, 2001.
[3] Y. Ishitani. Logical structure analysis of document images
based on emergent computation. IEICE Transactions on Information and Systems, E88–D(8):1831–1842, 2005.
[4] Y. Kato, S. Matsubara, and Y. Inagaki. A corpus search system utilizing lexical dependency structure. In Proceedings of
the 5th International Conference on Language Resources and
Evaluation, pages 2269–2272, 2006.

[5] P. Resnik and A. Elkiss. The linguist’s search engine: An
overview. In Proceedings of the 43rd ACL Interacrive Poseterand Demonstration Sessions, pages 33–36, 2005.
[6] K. Tanaka-Ishii and Y. Ishii. Multilingual phrase-based concordance generation in real-time. Information Retrieval,10(3):275–295, 2007.