DEIM Forum 2013 A1-6

A Study on Eﬃcient Similar Sentence Matching
Yanhui GU† , Zhenglu YANG† , Miyuki NAKANO† , and Masaru KITSUREGAWA†† Institute of Industrial Science, the University of Tokyo
4–6–1 Komaba, Meguro–ku, Tokyo 153–8505 Japan
E-mail: †{guyanhui,yangzl,miyuki,kitsure}@tkl.iis.u-tokyo.ac.jp
Abstract Similar sentence matching is an essential issue for many applications, such as text summarization, image
extraction, social media retrieval, question-answer model, and so on. A number of studies have investigated thisissue in recent years. Most of such techniques focus on eﬀectiveness issues but only a few focus on eﬃciency issues.
In this paper, we study the eﬃciency and eﬀectiveness in the sentence similarity matching. For a given sentencecollection, we determine how to eﬀectively and eﬃciently identify the top-k semantically similar sentences to a query.
The experimental evaluation demonstrates the eﬀectiveness of our strategy. Moreover, from the eﬃciency aspect, we
introduce several optimization techniques to improve the performance of the similarity computation. The trade-oﬀ
between the eﬀectiveness and eﬃciency is further explored by conducting extensive experiments on real datasets.
Key words rank aggregation, threshold algorithm, semantic, Top-k

1. Introduction

syntax based strategy [15], [21]; and (4) hybrid strategy[15], [21], [34].

Searching semantic similar sentences is an essential issue

Naively testing every candidate sentence is time consum-

because it is the basis of many applications, such as snip-

ing, especially when the size of the sentence collection is huge.

pet extraction, image retrieval, question-answer model, doc-

To tackle this issue, we introduce eﬃcient strategies to eval-ument retrieval, and so forth [26], [37]. From a given sentenceuate as few candidates as possible. Moreover, we aim tocollection, this kind of queries asks for those sentences which

progressively output the top-k results, i.e., the top-1 result

are most semantically similar to a given one.

should be output almost instantly, then the top-2 and more

The problem can be solved as follows: we ﬁrstly mea-

results will be obtained as the execution time becomes longer.

sure the semantic similarity score between the query andThis satisﬁes the requirement of the real applications [10]. As

each sentence in the data collection using the state-of-the-such, these issues are the challenges of the paper, which have

art techniques [15], [21], [25], [31], [33], then sort them withnot been studied before.

regard to the score and ﬁnally return the top-k ones. Al-

We propsed a propose to tackle the eﬃciency issue formost all the previous studies focus on improving the eﬀec-

searching top-k semantic similar sentences [41], which is dif-

tiveness (i.e., precision) of the problem and the datasets con-ferent from previous works that focus on the eﬀectiveness as-

ducted are small. However, when the size of the data col-pect. Based on the most comprehensive work [15], we intro-

lection increases, the scale of the problem will dramaticallyduce the optimization techniques and improve the eﬃciency.

increase and the state-of-the-art techniques will be imprac-

For each similarity measurement, we introduce a correspond-

tical [7], [8], [12], [13], [16], [27], [29], [40]. As far as we know,

ing strategy to minimize the number of candidates to be eval-this paper is the ﬁrst study that aims to address the eﬃ-

uated. A rank aggregation method is introduced to progres-ciency issue in the literature. Moreover, most of the previous

sively obtain the top-k results when assembling the features.

strategies applied the threshold-based strategy [15], [21], [33],In this paper, we study the most important issues of similarthat a threshold is predeﬁned to ﬁlter out those dissimilarsentence mathcing, i.e., eﬀectiveness and eﬃciency. We alsosequences. However, this threshold is diﬃcult for users to

study the trade-oﬀ between eﬀectiveness and eﬃciency.

determine. For real applications (e.g., Google), users may
prefer the top-k results.
There are mainly four kinds of techniques to measure

2. Eﬃcient Similar Sentence matching
2. 1 Preliminaries

the similarity between sentences: (1) knowledge-based strat-

To measure the similarity sim(Q, P ) between two sen-egy [25], [33]; (2) corpus-based strategy [15], [17], [18], [34]; (3)tences Q and P , we apply state-of-the art strategies by as-sembling multiple similarity metric features [15], [21]. Givena general framework is presented by incorporating all sim-that we cannot evaluate all the similarity measurement

ilarity measurement strategies. To the best of our knowl-

strategies in this paper, we select several representative fea-edge, [15] presented the most comprehensive approach thattures based on the framework presented in [15]. Notably,incorporates representative similarity metrics.

considering that a sentence comprises a set of words, thestruct a similarity matrix and recursively extract representa-

similarity score between two sentences denotes the overall

tive words (maximal-valued element) which are then aggre-

scores of all word pairs, the components of which belong togated to obtain the similarity between two sentence.

They con-each sentence. See [15] for detail on computing sentence sim-

2. 4 Optimization Strategies

ilarity based on word similarity.

We apply the framework of [41] as the evaluation base

2. 2 Similarity Measurement Strategies

which is an optimization strategies on the framework which

2. 2. 1 String Similarity

is proposed in [15]. The original are composed with the following: String (NLCS,NMCLCS1 and NMCLCSn ), Seman-

String similarity measures the diﬀerence in syntax betweentic (corpus-based strategy) and Common word order （注 2）.

strings. An intuitive idea is that two strings are similar to

Actually, they apply string and semantic strategies in theeach other if they have adequate common subsequences (e.g.,framework. Accordingly, [41] proposed eﬃcient similar sen-

LCS [11]). String similarity measurement strategies, includ-

tence matching strategy on string and semantic.

ing edit-distance, hamming distance and so on.

We fo-

cus on three representative string similarity measurement
strategies introduced in [15], namely, NLCS, NMCLCS1 and
NMCLCSn（注 1）.
2. 2. 2 Corpus-based Similarity

3. Experimental Evaluation
To evaluate eﬀectiveness and eﬃciency, we conducted
extensive experiments by using 16-core Intel(R) Xeon(R)E5530 server running Debian 2.6.26-2. All the algorithms
were written in C language and compiled by GNU gcc. The

The corpus-based similarity measurement strategy recog-

baseline algorithm is implemented according to the state-of-nizes the degree of similarity between words using large cor-

the-art work [15].

pora, e.g., BNC, Wikipedia, Web and so on. Corpus-based

In the whole experimental evaluation, we use three dif-similarity measurement strategies are of several types: PMI-

ferent datasets, i.e., the benchmark dataset which was used

IR, LSA, HAL, and so on. In this paper, we apply the Sec-in [15], [21], BNC（注 3） dataset and MSC（注 4） dataset.

ond Order Co-occurrence PMI (SOC-PMI) [14], [15] which
employs PMI-IR to consider important neighbor words in a

3. 1 Evaluation on Eﬀectiveness

context window of the two target words from a large corpus.

In the former experiments, we have demonstrated that our

They use PMI-IR to calculate the similarities between word

proposal outperforms the state-of-the-art technique with re-pairs (including neighbor words). High PMI scores are thengard to the eﬃciency issue. In this section, we evaluate theaggregated to obtain the ﬁnal SOC-PMI score.

eﬀectiveness of our proposal. We conduct experiments on

2. 2. 3 Common Word Order Similarity

two labeled datasets, i.e., the benchmark dataset and MCS
dataset.

Common word order similarity measures how similar the or-

3. 1. 1 Evaluation on Precisely Labeled Dataset

der of the common-words is between two sentences, as either

The benchmark dataset which was used in [15], [21] and it

the same order, almost the same order, or very diﬀerent or-

has been labeled by concrete value, i.e., we can easily un-der. Although [15] indicates that syntactic information is less

derstand the closeness between measured result and labeled

important during the semantic processing of sentences, we in-data. Here, we denote Distance as the metric which mea-

corporate this similarity measurement strategy to test howsures the closeness between two sets of results, e.g., baselinemuch order similarity aﬀects the whole sentence similarity.

and our proposal, where xi and yi are two sets of results re-See [15], [21] for detail.

spectively. Smaller value indicates that the two results are

2. 3 General Framework for Measuring Sentence
Similarity
To measure the overall similarity between two sentences,（注 2）：We conducted experiments on benchmark dataset and foundthat common word order similarity has low importance in sentence（注 1）：NLCS: Normalized Longest Common Substring; NMCLCS1 :similarity measurement.

Normalized Maximal Consecutive LCS starting at character 1; NM-（注 3）：http://www.natcorp.ox.ac.uk/

CLCSn: Normalized Maximal Consecutive LCS starting at any char-（注 4）：Microsoft Research Paraphrase Corpus. It contains 5801 pairs

acter n. See [15] for detail.

of sentences.

closer to each other. Distance = n1n−1Threshold Hit Miss Hit Ratio(xi − yi )2i=0

The experimental result conducted on the benchmark
dataset is illustrated in Fig. 1. From this ﬁgure we can seethat the results of both algorithms are close to each other,which indicates that our proposal can obtain the same highprecision as the state-of-the-art technique.
Baseline
Our Proposal

0.7

0

20

0.6

1

19

0%
5%

0.5

9

11

45%

0.4

12

8

60%

0.3

17

3

85%

0.2

15

5

75%

0.1
14
6
70%
Table 2 Diﬀerent hit ratio under diﬀerent selection of τ

Accordingly, we conducted extensive experiments to search
the best τ value. Since we know that the similarity scorecomes from two diﬀerent parts, i.e., string similarity and semantic similarity, and the weight α we apply before is 0.5.
To evaluate the precise hit ratio under diﬀerent τ , we evaluate the whole hit ratio by using MSC dataset under diﬀerent
τ and α value. Table. 3 shows the experimental results.
From the table, we can see, when τ =0.3 under α=0.6, weFig. 1 Evaluation on eﬀectiveness under benchmark dataset

3. 1. 2 Evaluation on Rawly Labeled Dataset
MSC is another labeled dataset which has been extracted
from news sources on the web, along with human annotations
indicating whether each pair captures a paraphrase-semantic
equivalence relationship. They apply the value 1 as similarobtain the best hit ratio as 80.52%. However, the evaluationof each τ is under a ﬁxed α, i.e., we cannot determine the
combination of τ and α which can obtain the best hit ratio.
Therefore, we should extensively train the value of α underdiﬀerent τ .
b ) Training α under diﬀerent τ

while the value 0 as dissimilar. However, such label data is

We apply a k-fold cross-validation（注 5） strategy to check

rather raw and we cannot apply them to judge our measured

α under diﬀerent τ . Firstly, we divide MSC dataset into k

results directly.

parts and apply the part from 1 to k − 1 as the training data.

a ) Raw data preprocessing
Since such dataset has no concrete value while only “1”or “0”, we should distinct each value beforehand. Consider
an example, there are two cases. Case (a): the similarity
score between two sentences is 0.30 while the labeled datais 1. Case (b): the similarity score between two sentences
is 0.60 while the labeled data is 0. From this example we
can see that we cannot judge 0.30 or 0.60, which one represents “closeness”. So, how to measure our experimental
results by using such raw data. To answer this question, weapply a threshold τ as the bound, i.e., if any measured value
is greater than or equal to τ and the labeled data is “1” ,we regard it as “hit”. Similarly, if one measured value is less

Then we get α and τ under the best hit ratio and apply thesetwo parameters to compute the hit ratio on the kth part. In
each step i, we can get the best hit ratio Hi and the hit ratio(test) Hti . For example, in the 1st step, the best hit ratio
occurs when α = 0.6 and τ = 0.3. Then we get the 81.24%
hit ratio in testing part which means there is no distinguishdiﬀerence between training and testing. After k steps ﬁnish,
we get a list of values of α, τ and hit ratios. The ﬁnial α andτ will be the average value. From Table. 4, we can see that τ= 0.56 and α = 0.31 are the best parameters. We show theevaluation on the eﬀectiveness for the MSC dataset in Fig.
2 under these two parameters.

than τ and the labeled data is “0”, we also regard it as “hit”,
otherwise “miss”. Table. 1 illustrates the strategy.
Labeled value
1

>
=τ
hit

<τ
miss

0
miss
hit
Table 1 The selection of τ

Randomly selecting 20 sentence pairs from MSC and set
diﬀerent τ value, we can obtain the result which is presented
in Table. 2. Here we set hit ratio be the number of hits divided by total results. With these diﬀerent threshold τ , weselect the optimal one that obtains the maximal hit ratio,i.e., τ =0.3 in this example.

Fig. 2 Evaluation on eﬀectiveness under MSC

020.55% 21.20% 36.25% 41.29% 36.06% 34.18% 18.86% 16.89% 16.43%

0.1

17.74% 24.67% 41.29% 41.39% 33.24% 28.44% 18.74% 15.14% 12.27%

0.2

56.73% 55.25% 53.51% 51.44% 46.13% 34.80% 30.32% 26.62% 22.76%

0.3

69.28% 72.33% 68.70% 63.39% 55.34% 49.53% 34.67% 22.51% 18.69%

0.4

77.71% 78.57% 68.85% 57.32% 51.46% 47.66% 36.36% 28.44% 22.31%

0.5

77.81% 79.16% 77.59% 74.37% 63.37% 51.27% 40.41% 32.77% 32.77%

0.6

71.02% 76.87% 80.52% 71.70% 63.21% 53.28% 39.05% 33.86% 22.29%

0.7

66.30% 71.07% 72.32% 63.06% 61.42% 39.91% 36.05% 30.01% 18.82%

0.8

34.84% 67.63% 69.92% 57.30% 50.99% 36.29% 34.22% 30.10% 21.32%

0.9

29.62% 36.32% 61.92% 53.28% 46.18% 41.13% 36.29% 30.81% 17.95%

1.0

20.84% 22.44% 21.34% 18.86% 16.95% 15.14% 12.72% 11.58% 10.36%
Table 3 Hit ratio under diﬀerent τ and α
Hit RatioHi

parameter α threshold τ

Hit-Ratio(test)Hti

1st

81.25%

0.6

0.3

81.24%

2nd

84.48%

0.7

0.3

81.58%

3rd

78.72%

0.7

0.4

82.79%

4th

80.46%

0.5

0.3

80.03%

5th

80.67%

0.4

0.3

84.51%

6th

84.18%

0.4

0.4

71.26%

7th

79.10%

0.5

0.3

79.35%

8th

82.16%

0.6

0.3

77.28%

9th

82.07%

0.6

0.2

75.39%

10th

80.42%

0.6

0.3

79.00%

Avg.
0.56
0.31
Table 4 10-fold cross-validation on τ under diﬀerent α

NLCSStringBaseline

NLCS

NMCLCS1NMCLCSn

StringBaseline

Semantic

NMCLCSn

Semantic
NLCS

Our Proposal

String

NMCLCS1NMCLCSn

Semantic(a) Single vs. Combination

Our Proposal

StringTo evaluate the eﬀectiveness, we apply single strategy
in baseline and combination strategy（注 6） in our proposal.

NLCS

NMCLCS1

3. 2. 1 Single Strategy in the Baseline vs. Our Proposal

Firstly, we compare the eﬀectiveness between each strategy

NMCLCS1NMCLCSnin baseline and combination strategy in our proposal. We

Semantic(b) Single vs. Single

Fig. 3 Two diﬀerent evaluation strategies on trade-oﬀ between
eﬃciency and eﬀectiveness3. 2 Evaluation on Trade-oﬀ between Eﬃciency
and EﬀectivenessBecause the introduced framework is built based on thealso evaluate the execution time and index time of each pairunder such strategy. The experimental result is illustrated
in Fig. 4. We report three diﬀerent single string strategy in
Fig. 4(a), 4(c) and 4(e). String strategy and semantic strategy results are listed in Fig. 4(g) and Fig. 4(i), respectively.
From the ﬁgure we can see that, single strategy beats ouraggregation of diﬀerent features, i.e., string similarity andproposal in execution time while not in the eﬀectiveness.

semantic similarity, the execution time is related to the num-

The former evaluation on eﬀectiveness tells us that the com-

ber of features used. Therefore, if we apply only one feature,bination strategy can obtain more precise results. Fig. 4(b),the execution time is shorter yet such strategy may aﬀect

Fig. 4(d), Fig. 4(f), Fig. 4(h) and Fig. 4(j) present the experi-

the whole eﬀectiveness. So we conduct a set of experiments

mental results of execution time of single strategy in baseline(illustrated in Fig. 3(a)) to study the trade-oﬀ between eﬃ-

and execution time of our proposal. Since the strategies inciency and eﬀectiveness. In this set of experiments, we ﬁrst

baseline do not need to index, we report the index time ofevaluate the performance of single feature in the baseline

combination strategy in our proposal. Note that in all thestrategy vs. our whole framework, as illustrated in Fig. 3(a).

evaluation, we show the performance of extracting the top-

Then we explore the performance of single feature in the

5 results with 10 randomly selected queries. Here we takebaseline strategy vs. single feature in our framework as il-

NLCS vs. combination strategy pair as an example. Fig.

lustrated in Fig. 3(b).

4(b) illustrates the execution time and the index time for
NLCS (i.e., the left bar) and our proposal (i.e., the right（注 5）：We apply 10-fold cross-validation in this paper.

（注 6）：Combination strategy means the whole framework strategies.

framework (i.e., Fig. 3(b)). Firstly, we compare the eﬀectiveness between the two situations, as illustrated in Fig. 5. From
the ﬁgure we can see that the execution time of each single
strategy in baseline is longer than that of in our proposal(i.e., including the execution time and index time). These
results demonstrate that the optimizations of our proposal(a) NLCS vs. Our Proposal(b) NLCS vs. Our Proposal(c) NMCLCS1 vs.OurProposal(d) NMCLCS1 vs.OurProposal(e) NMCLCSn vs.OurProposal(f) NMCLCSn vs. OurProposal(g) String vs. Our Proposal

are eﬃcient and make eﬀect on each feature.

(a) NLCS vs. Our NLCS(b) NMCLCS1 vs. NMCLCS1(c) NMCLCSn vs. NMCLCSn(d) String vs. String(h) String vs. Our Proposal(e) Semantic vs. Semantic

Fig. 5 Eﬃciency and index cost between single strategy in baseline and combination strategy in our proposal

4. Conclusion and Future WorkIn this paper, we study the eﬀectiveness and eﬃciency on(i) Semantic vs. Our Proposal(j) Semantic vs. Our Proposal

Fig. 4 Evaluation on trade-oﬀ between eﬃciency and eﬀectivenessbar). We can easily see that the execution time of NLCS
is very fast while the combination strategy consumes moretime. The similar results can be seen in Fig. 4(d), Fig. 4(f)and Fig. 4(h). In Fig. 4(j), the execution time of single
semantic strategy is longer than that of combination strategy. Such result tells us that the optimization on semantic
similarity is crucial among all the optimization strategies.
3. 2. 2 Single Strategy vs. Single Strategy
Evaluation on single strategy vs. combination strategy
demonstrates the trade-oﬀ between eﬀectiveness and eﬃciency. In this section, we study the performance of single feature in the baseline strategy vs. single feature in oursimilar sentence matching. Eﬃcient searching top-k similar sentences is very important especially when the data islarge. Several eﬃcient strategies are introduced to test as
few candidates as possible during the searching process. The
comprehensive experimental evaluation demonstrates the efﬁciency of the proposed techniques while keeping the samehigh eﬀectiveness as the state-of-the-art techniques. For further understand how optimization strategy works, we conducted extensive experiments on diﬀerent types of datasets.
To evaluate the eﬀectiveness, we conducted on two diﬀerent
types of labeled datasets and trained two parameters for theeﬃciency evaluation. To understand the trade-oﬀ between
eﬀectiveness and eﬃciency, we evaluated diﬀerent combination of features between the baseline and our proposal. In
the future, we will incorporate more similarity strategies toevaluate the eﬃciency and eﬀectiveness of the framework.

References[1] C. Burgess, K. Livesay, and K. Lund. Explorations in context space: words, sentences, discourse. Discourse Processes, 1998.
[2] Diego Ceccarelli, Claudio Lucchese, Salvatore Orlando, Raffaele Perego, and Fabrizio Silvestri. Caching query-biased
snippets for eﬃcient retrieval. In Anastasia Ailamaki, Sihem
Amer-Yahia, Jignesh M. Patel, Tore Risch, Pierre Senellart,
and Julia Stoyanovich, editors, EDBT. ACM, 2011.
[3] Gobinda G. Chowdhury. Introduction to modern information retrieval. Facet, 3. ed. edition, 2010.
[4] Hang Cui, Renxu Sun, Keya Li, Min-Yen Kan, and Tat-Seng
Chua. Question answering passage retrieval using dependency relations. In Ricardo A. Baeza-Yates, Nivio Ziviani,
Gary Marchionini, Alistair Moﬀat, and John Tait, editors,
SIGIR. ACM, 2005.
[5] Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal
aggregation algorithms for middleware. In PODS, 2001.
[6] P. W. Foltz, W. Kintsch, and T. K. Landauer. The measurement of textual coherence with latent semantic analysis.
Discourse Processes, 1998.
[7] Amit Goyal and Hal Daumè III. Approximate scalable
bounded space sketch for large data nlp. In EMNLP, 2011.
[8] Amit Goyal, Hal Daumè III, and Suresh Venkatasubramanian. Streaming for large scale nlp: Language modeling. In
HLT-NAACL, 2009.
[9] Vaseleios Hatzivassiloglou, Judith L. Klavans, and Eleazar
Eskin. Detecting text similarity over short passages: Exploring linguistic feature combinations via machine learning. In EMNLP/VLC, 1999.
[10] Joseph M. Hellerstein, Ron Avnur, Andy Chou, Christian Hidber, Chris Olston, Vijayshankar Raman, Tali Roth,and Peter J. Haas. Interactive data analysis: The control
project. Computer, 32, aug 1999.
[11] D. S. Hirschberg. A linear space algorithm for computing
maximal common subsequences. Commun. ACM, 1975.
[12] Ming Hua, Jian Pei, Ada Wai-Chee Fu, Xuemin Lin, andHo fung Leung. Eﬃciently answering top-k typicality
queries on large databases. In VLDB, 2007.
[13] Ming Hua, Jian Pei, Ada Wai-Chee Fu, Xuemin Lin, and
Ho-Fung Leung. Top-k typicality queries and eﬃcient queryanswering methods on large databases. VLDB J., 18, 2009.
[14] Aminul Islam and Diana Inkpen.
Second order cooccurrence pmi for determining the semantic similarity ofwords. In LREC, 2006.
[15] Aminul Islam and Diana Inkpen. Semantic text similarity using corpus-based word similarity and string similarity. ACM Transactions on Knowledge Discovery from Data,
2008.
[16] Jong Wook Kim, Ashwin Kashyap, Dekai Li, and Sandilya
Bhamidipati. Eﬃcient wikipedia-based semantic interpreterby exploiting top-k processing. In CIKM, 2010.
[17] T. Landauer and S. Dumais. A solution to plato’s problem:
The latent semantic analysis theory of acquisition, induction and representation of knowledge. Psychological Review,
1997.
[18] T. K. Landauer, P. W. Foltz, and D. Laham. An introduction to latent semantic analysis. Discourse Processes,
1998.
[19] Thomas K Landauer and Susan T. Dutnais. A solution toplatos problem: The latent semantic analysis theory of acquisition, induction, and representation of knowledge. Psy-

chological review, 1997.
[20] C. Leacock and M. Chodorow. Combining local context
and WordNet similarity for word sense identification, pages
305–332. In C. Fellbaum (Ed.), MIT Press, 1998.
[21] Yuhua Li, David McLean, Zuhair A. Bandar, James D.
O’Shea, and Keeley Crockett. Sentence similarity based on
semantic nets and corpus statistics. IEEE Trans. on Knowl.
and Data Eng., 2006.
[22] Ana Gabriela Maguitman, Filippo Menczer, Heather
Roinestad, and Alessandro Vespignani. Algorithmic detection of semantic similarity. In WWW, 2005.
[23] Charles T. Meadow. Text information retrieval systems.
Academic Press, 1992.
[24] Donald Metzler, Susan T. Dumais, and Christopher Meek.
Similarity measures for short segments of text. In ECIR,
2007.
[25] Rada Mihalcea, Courtney Corley, and Carlo Strapparava.
Corpus-based and knowledge-based measures of text semantic similarity. In AAAI, 2006.
[26] Rada Mihalcea and Paul Tarau. Textrank: Bringing order
into text. In EMNLP, 2004.
[27] Patrick Pantel, Eric Crestan, Arkady Borkovsky, Ana-Maria
Popescu, and Vishnu Vyas. Web-scale distributional similarity and entity set expansion. In EMNLP, 2009.
[28] Filip Radlinski, Andrei Broder, Peter Ciccolo, Evgeniy
Gabrilovich, Vanja Josifovski, and Lance Riedel. Optimizing relevance and revenue in ad search: a query substitution
approach. In SIGIR, 2008.
[29] Christopher Re, Nilesh N. Dalvi, and Dan Suciu. Eﬃcient
top-k query evaluation on probabilistic data. In ICDE, 2007.
[30] Norvald H. Ryeng, Akrivi Vlachou, Christos Doulkeridis,
and Kjetil Nørvåg. Eﬃcient distributed top-k query processing with caching. In DASFAA, 2011.
[31] Mehran Sahami and Timothy D. Heilman. A web-based
kernel function for measuring the similarity of short text
snippets. In WWW, 2006.
[32] Gerard M. Salton, Andrew K. C. Wong, and Chung-Shu
Yang. A Vector Space Model for Automatic Indexing. Communications of the ACM, 1975.
[33] George Tsatsaronis, Iraklis Varlamis, and Michalis Vazirgiannis. Text relatedness based on a word thesaurus. J.
Artif. Intell. Res. (JAIR), 2010.
[34] Peter D. Turney. Mining the web for synonyms: Pmi-ir
versus lsa on toeﬂ. In EMCL, 2001.
[35] Esko Ukkonen. Approximate string-matching with q-grams
and maximal matches. Theoretical Computer Science,92(1), 1992.
[36] Akrivi Vlachou, Christos Doulkeridis, Kjetil Nørvåg, andMichalis Vazirgiannis. On eﬃcient top-k query processing
in highly distributed environments. In SIGMOD, 2008.
[37] Kai Wang, Zhaoyan Ming, Xia Hu, and Tat-Seng Chua.
Segmentation of multi-sentence questions: towards eﬀective
question retrieval in cqa services. In SIGIR, 2010.
[38] Furu Wei, Wenjie Li, Qin Lu, and Yanxiang He. Querysensitive mutual reinforcement chain and its application inquery-oriented multi-document summarization. In SIGIR,
2008.
[39] Zhenglu Yang and Masaru Kitsuregawa. Eﬃcient searching
top-k semantic similar words. In IJCAI, 2011.
[40] Xi Zhang and Jan Chomicki. Semantics and evaluation of
top-k queries in probabilistic databases. Distrib. Parallel
Databases, 2009.
[41] Yanhui Gu, Zhenglu Yang, Miyuki Nakano and Masaru Kitsuregawa. Towards eﬃcient similar sentences extraction.
IDEAL, 2012.