String Matching with Metric Trees
Using an Approximate Distance
Ilaria Bartolini, Paolo Ciaccia, and Marco Patella
DEIS - CSITE-CNR
University of Bologna, Italy{ibartolini, pciaccia, mpatella}@deis.unibo.it

Abstract. Searching in a large data set those strings that are more similar, according to the edit distance, to a given one is a time-consuming
process. In this paper we investigate the performance of metric trees,
namely the M-tree, when they are extended using a cheap approximate
distance function as a ﬁlter to quickly discard irrelevant strings. Using
the bag distance as an approximation of the edit distance, we show an improvement in performance up to 90% with respect to the basic case. This,
along with the fact that our solution is independent on both the distanceused in the pre-test and on the underlying metric index, demonstrates
that metric indices are a powerful solution, not only for many modern
application areas, as multimedia, data mining and pattern recognition,
but also for the string matching problem.

1

Introduction

Many modern real world applications, as text retrieval, computational biology,
and signal processing, require searching in a huge string database for those sequences that are more similar to a given query string. This problem, usuallycalled approximate string matching, can be formally deﬁned as follows: Let Σ bea ﬁnite alphabet of symbols, let O ⊆ Σ ∗ be a database of ﬁnite length strings
over the Σ alphabet, let q ∈ Σ ∗ be a string, and let dedit be the edit distancefunction, ﬁnd the strings in O which are suﬃciently similar to q, up to a given
threshold. The edit distance dedit (X, Y ) between two strings X, Y ∈ Σ ∗ counts
the minimum number of atomic edit operations (insertions, deletions, and substitutions of one symbol) needed to transform X in Y . As an example, the distance
between the strings "spire" and "peer" is 4, dedit ("spire", "peer") = 4, because to transform "spire" in "peer" we need at least 4 edit operations, i.e. 1
substitution (replace i with e), 2 deletions (s and e), and 1 insertion (e).
In the online version of the problem [13], the query string can be preprocessed, but the database cannot, thus the best algorithms are at least linear
in the database size. An alternative approach, ﬁrst proposed in [2], considers
the strings to be searched as points in a metric space: A metric index is thenbuilt on the strings to reduce the number of distance computations needed tosolve a query. Metric indices organize strings using relative distances and areable to consistently improve search performance over the simple sequential scan,since only a fraction of database strings has to be compared against q. In somecases, however, response times are still unsatisfactory, particularly in the caseof long strings, due to the fact that computing dedit (X, Y ) using dynamic programming is O(|X| · |Y |), where |X| (resp. |Y |) is the length of string X (resp.
Y ) [19]. To overcome such limitation, we propose the use of an approximate andcheap distance function to quickly discard objects that cannot be relevant for
the query. We then show how, using a simple “bag distance”, whose complexity is O(|X| + |Y |), performance of metric trees can be improved up to 90%.
Moreover, our results can also be applied to other approximate distances, thus
making metric trees a powerful solution also for the text application domain, afact that only in recent times has been considered [2, 14].
The paper is organized as follows: In Section 2 we give background information on solving similarity queries with metric trees. Section 3 presents ourapproach, and Section 4 contains results obtained from experimentations withreal data sets. Finally, in Section 5 we conclude and discuss about possible extensions for our work.

2

Background

Metric trees are access methods that are able to eﬃciently solve range and knearest neighbor queries over general metric spaces. A metric space is a pair(U, d), where U is a set of objects and d : U ×U → + is a symmetric binary function that also satisﬁes the triangle inequality: d(Oi , Oj ) ≤ d(Oi , Ok ) + d(Ok , Oj ),∀Oi , Oj , Ok ∈ U. Given a data set O = {O1 , . . . , ON }, an object q ∈ U, and avalue r ∈ + , a range query selects all the objects O in O whose distance dfrom q is not higher than r. A k-nearest neighbor query, k being a natural number, retrieves the k objects in O having the minimum distance d from q. This
general view of the problem is shared by many application domains (e.g. image
databases [15], computational biology [8], and pattern recognition [3]).
To reduce the number of distance evaluations needed to solve a query, anumber of index structures has been recently introduced for the general case of
metric spaces [6, 5, 4, 9]. Among them, metric trees, like the M-tree [9] and the
Slim-tree [17], are secondary memory structures whose goal is to reduce both
CPU and I/O times for solving queries over very large data sets, that cannot ﬁt
into main memory.
A characteristic shared by all metric trees is that they partition the data space
U into regions and assign each region to a node n stored on a disk page, whereas
data objects are stored into leaf nodes [7]. In detail, at index-construction time,a hierarchical subdivision of the space is performed, such that each region of anode in a sub-tree is enclosed within the region associated to the root of the tree
(thus, the root of a sub-tree is a coarser description of its descendant nodes).
Even if metric trees can be used to solve both range and k-nearest neighbors
queries, in the following we will concentrate on the former type, since the lattercan be built over range queries by using a priority search on the tree [9, 7]. At
query time, the index is explored downwards, and distances between the queryobject q and objects in internal nodes are computed in order to prune away subtrees that cannot lead to any qualifying object, since their regions are disjoint
from the query region. At the leaf level, objects that have not been ﬁlteredout, which are called candidate objects, are directly compared to the query tocheck if they should be included in the result (for a candidate object O thishappens if d(q, O) ≤ r). Following the terminology introduced in [7], the cost for
determining the candidate objects is named internal complexity, while the costfor checking all candidates is referred as external complexity (see Figure 1).

LQWHUQDOFRPSOH[LW\
WUHH
H[WHUQDOFRPSOH[LW\

REMHFWVαÂ1Fig. 1. Internal and external complexity when querying a tree.

Usually, the internal complexity is (much) lower than the external complexity.
For a given range query, with query object q and radius r, let αq (r) · N be
the number of candidate objects, N being the cardinality of the data set andαq (r) ∈ [0, 1] being the selectivity factor of the tree with respect to the query.
Although the deﬁnition of αq (r) depends on both q and r, we can eliminate
the dependency on q by simply averaging αq (r) over a sample of query objects.
Moreover, let costd be the average cost of computing d.1 The external complexity
needed to solve a range query is therefore:α(r) · N · costd(1)

The goal of metric trees, therefore, is to (consistently) reduce the external
complexity, i.e. access only the objects relevant to the query, by (slightly) increasing the internal complexity (for the sequential scan, the internal complexity
is 0 and the external complexity is N · costd ).
2.1

The M-tree

The M-tree is a paged, dynamic, and balanced metric tree. Each node n corresponds to a region of the indexed metric space (U, d), deﬁned as Reg(n) =1Note that this is a simpliﬁcation, since, in the general case, the cost of a single
distance does depend on the objects for which it is computed, e.g. this is the casefor the edit distance.

{O ∈ U|d(O[n] , O) ≤ r[n] }, where O[n] is called the routing object of node n andr[n] is its covering radius. All the objects in the sub-tree rooted at n are thenguaranteed to belong to Reg(n), thus their distance from O[n] does not exceed
r[n] . Both O[n] and r[n] are stored, together with a pointer to node n, ptr(n), in
an entry of the parent node of n. In order to save distance computations, theM-tree also stores pre-computed distances between each object and its parent.
Thus, if np is the parent node of n, the entry for n in node np also includes thevalue of d(O[np ] , O[n] ).
When the metric space is the space of strings over an alphabet Σ equippedwith dedit , each object corresponds to a string. Figure 2 shows an example of (apart of) an M-tree indexing strings: Strings in each node are connected to therouting string of that node with a line whose length is proportional to the edit
distance between them.
U 
U 

U 


IDUH

WLHU

SHHU





SLSHU



SLH



VSLUH

SLHU  VSLHU





VSDUH

SDUVH



SDULV



VSRUH

Q
VSDUH  VKDNHVSHDUH «

Q

U 

VKDNHVSHDUHQ
SLHU  SDUVH «

Q

«

Q
SLHU  WLHU  VSLHU
SLH  SLSHU  SHHU

SDUVH  VSRUH  IDUH 
VSLUH  SDULV

Fig. 2. An example of an M-tree and regions associated to each node. For each entry
in an internal node, the routing object, the covering radius, and the distance from theparent object are shown, whereas entries in leaf nodes only contain a data string andits distance to the routing object.

Given a query string q and a search radius r, the M-tree is recursively descended and sub-trees are accessed iﬀ the region associated with their root node
overlaps the query region (see Figure 3). For a given node n with routing object
O[n] and covering radius r[n] , this amounts to check if d(q, O[n] ) ≤ r + r[n] holds,
since from the triangle inequality it follows:d(q, O[n] ) > r + r[n] =⇒ d(q, O) > r∀O ∈ Reg(n)(2)

In the example of Figure 3, where q = "spire" and r = 1, node n3 can bepruned since it is dedit ("spire", "pier") = 3 > r + r[n3 ] = 1 + 1 = 2. The distance d(O[np ] , O[n] ) can be used to prune out nodes without actually computingd(q, O[n] ), since the triangle inequality guarantees that:|d(q, O[np ] ) − d(O[np ] , O[n] )| > r + r[n] =⇒ d(q, O) > r∀O ∈ Reg(n)(3)

Note that, since the tree is recursively descended, d(q, O[np ] ) has been alreadycalculated, thus in Equation 3 no new distance is computed. In the example of Figure 3, we can avoid to compute dedit ("spire", "pier"), since it is|dedit ("spire", "spare") − dedit ("spare", "pier")| = |1 − 4| = 3 > 1 + 1 =2. Thus, the internal complexity for solving the query with the given tree is
3 · costdedit , since we have to compare "spire" with the routing strings "spare","shakespeare", and "parse", whereas the external complexity is 4 · costdedit ,since candidate strings are those contained in node n4 , except for "parse"
which can again be eliminated using Equation 3. Result strings are "spire"and "spore".2

U 
U 

U 
WLHU

UT 

SLHU  VSLHU

VSLUH

SHHU







SLSHU



SLH



IDUH





VSDUH

SDUVH



SDULV



VSRUH

Q
VSDUH  VKDNHVSHDUH «

Q

U 

VKDNHVSHDUHQ
SLHU  SDUVH «

Q

«

Q
SLHU  WLHU  VSLHU
SLH  SLSHU  SHHU

SDUVH  VSRUH  IDUH 
VSLUH  SDULV

Fig. 3. Solving a range query with an M-tree: Highlighted nodes are those accessed
during the search. Nodes n2 and n3 are pruned since their regions do not overlap thequery region.

2

Note that routing objects do not necessarily belong to the data set [9], as it is thecase for "spare" in Figure 2.

3

Proposed Solution

The internal complexity for solving range queries with metric indices is usually
very low. On the other hand, when using the edit distance, the external complexity, expressed by Equation 1, can be too high due to costdedit . Thus, to reduce
the external complexity, we need a way to decrease the number of strings forwhich dedit has to be computed. The solution we propose here is to use anotherdistance dc , which approximates dedit , to quickly ﬁlter out candidates. All thestrings remaining after this ﬁltering phase are then checked, using dedit , against
q to see if they qualify for the result. The test to ﬁlter out a candidate string X
is:(4)
dc (q, X) > r
All the strings satisfying Equation 4 are discarded without further processing.
In order to guarantee that no string which should be included in the result is
ﬁltered out (no false dismissals are allowed), we need a constraint over dc :dc (X, Y ) ≤ dedit (X, Y )∀X, Y ∈ Σ ∗(5)i.e. dc should be a lower bound for dedit . If this is not the case, in fact, it could
be dedit (q, X) ≤ r, thus X satisﬁes the query, yet dc (q, X) > r, thus X is ﬁlteredout by dc .
In order to keep costs low, dc should be also very cheap to compute. A goodcandidate for approximating dedit is the “bag distance” (also called “counting
ﬁlter” in [12]), which is deﬁned as follows.
Deﬁnition 1 (Bag Distance). Given a string X over an alphabet Σ, let x =ms(X) denote the multiset (bag) of symbols in X. For instance, ms("peer") ={{e, e, p, r}}. The following can be easily proved to be a metric on multisets:
dbag (x, y) = max{|x − y|, |y − x|}
where the diﬀerence has a bag semantics (e.g. {{a, a, a, b}} − {{a, a, b, c, c}} ={{a}}), and | · | counts the number of elements in a multiset (e.g. |{{a, a}}| = 2).
In practice, dbag (x, y) ﬁrst “drops” common elements, then takes the maximum
considering the number of “residual” elements. For instance:
dbag ({{a, a, a, b}} − {{a, a, b, c, c}}) = max{|{{a}}|, |{{c, c}}|} = 2
It is immediate to observe that dbag (X, Y ) ≤ dedit (X, Y ), ∀X, Y ∈ Σ ∗ .3
Further, since computing dbag (X, Y ) is O(|X| + |Y |), dbag can indeed be effectively used to quickly ﬁlter out candidate strings.4 In the example of Figure 3, the ﬁltering step would exclude the candidate string "fare" since it is3

For the sake of brevity, here and in the following, we will replace the bag ms(X) of
symbols in a string with the string X itself, with a slight abuse of notation.
4
Other distances can be used to approximate dedit [11]; dbag has, however, the advantage that it does not require further processing of strings and is very fast tocompute.

dbag ("spire", "fare") = 3, whereas the string "paris" cannot be excluded
since dbag ("spire", "paris") = 1. Thus, dedit ("spire", "paris") = 4 has to becomputed to exclude the string from the result. The external complexity now is
4 · costdbag + 3 · costdedit .
3.1

How Much Do we Save?

In order to compute the reduction in the external complexity obtained by using
dbag , we need to know the probability that the ﬁlter condition of Equation 4
succeeds for a string X. To this end, we use the distance distribution of objects,
which has been proﬁtably adopted several times to predict performance of metricstructures [10, 16, 7, 17]. Formally, for a generic distance d over a domain U, wedenote with Fd (·) the distance distribution of d, that is:
Fd (x) = Pr{d(Oi , Oj ) ≤ x} = Pr{d ≤ x}x ∈ [0, d+ ]where Oi and Oj are randomly chosen objects of U, d+ is a ﬁnite upper bound on
distance values, and d = d(Oi , Oj ) is a random variable with distribution Fd (·).
Figure 4 shows two sample distance distributions. Of course, since dbag (X, Y ) ≤dedit (X, Y ), ∀X, Y ∈ Σ ∗ , it is also Fdbag (x) ≥ Fdedit (x), ∀x ∈ [0, d+ ].

1

Fd
bag
Fd
edit

Fd

bag

(r)

Fd

edit

(r)

0
0

r

+

d

Fig. 4. Distance distributions for dbag and dedit .

The probability that a random string X is not ﬁltered away by dbag can be,
therefore, computed as:
Pr {dbag (q, X) ≤ r} = Fdbag (r)(6)

We are now ready to compute the overall cost for solving a query. For eachcandidate string X, dbag (q, X) has to be computed, with a cost of costdbag . Only if
the test of Equation 4 fails, which happens with probability given by Equation 6,

we have to compute dedit (q, X), paying costdedit . The overall external complexity
is therefore given as:α(r) · N · costdbag + Fdbag (r) · α(r) · N · costdedit(7)Comparing Equation 7 with Equation 1, we obtain a saving in search time whenever it is:α(r) · N costdbag + Fdbag (r) · costdedit ≤ α(r) · N · costdeditthat is when:
Fdbag (r) ≤ 1 −costdbagcostdedit(8)

The saving S in search time can be computed as:α(r) · N · costdedit − α(r) · N · costdbag + Fdbag (r) · α(r) · N · costdeditS≈=α(r) · N · costdedit
costdbag= 1 − Fdbag (r) −costdedit(9)
where the approximation is due to the fact that, in Equation 9, the internal
complexity is ignored.5 Finally, if Fdbag is invertible, we can obtain the maximum
search radius rmax for which it is convenient to use dbag :
costdbag−1
rmax = Fdbag 1 −(10)
costdedit
3.2

Generalizing the Approach

In the previous Section we showed how we can reduce the external complexity
for solving a query by ﬁltering out objects using an approximate distance. In lineof principle, nothing would prevent to use not only a single distance, but several
ones. However, one should consider the fact that each ﬁltering step requires thecomputation of some distances. As an example, consider the case where two
approximate distances, dc1 and dc2 , are present, with dc1 (X, Y ) ≤ dc2 (X, Y ) ≤dedit (X, Y ). We can ﬁrst use dc1 to prune out some candidate strings, and thenuse dc2 to discard some of the remaining ones. Finally, dedit (q, X) is computed
for strings not ﬁltered out by the second step. The external complexity for thissolution can be computed as (see Figure 5):(11)α(r) · N costdc1 + Fdc1 (r) · costdc2 + Fdc2 (r) · costdedit
Now, one can compare the cost obtained from Equation 11 with that given
by Equation 7 (by replacing dbag with either dc1 or dc2 ) to choose whether it
is convenient to use both distances or only one of them. Of course, it can be
expected that costdc1 < costdc2 , since dc2 is a better approximation of dedit .
5

We will experimentally validate this assumption in Section 4.

1
Fd (r)
c1

Fd
c1
Fd
c2
Fd

edit

Fd (r)
c2

0
0

r

+

d

Fig. 5. Distance distributions for dc1 , dc2 , and edit.

It is now easy to generalize the above discussion to the case where m distances, dc1 , . . . , dcm , each lower-bounding dedit , are present. Possible relations
existing among the dci s allow for a variety of scenarios:– If it is dci (X, Y ) ≤ dci+1 (X, Y ) (i = 1, . . . , m − 1), then each distance can beused to ﬁlter out a fraction of candidate objects. Equation 11 can be easily
extended to deal with m diﬀerent distances, obtaining:(12)α(r) · N costdc1 + Fdc1 (r) · costdc2 + . . . + Fdcm (r) · costdedit– A second scenario is obtained whenever it is dci (X, Y ) ≤ dci+1 (X, Y ), yet
dci+1 (X, Y ) can be incrementally obtained from dci (X, Y ). As an example,
this is the case we get considering the bag distance as computed only on theﬁrst i symbols of the Σ alphabet: This can be easily obtained starting fromthe distance computed considering only the ﬁrst i − 1 symbols. Of course, incomputing costdci+1 , we should not take into account the cost already payedfor computing costdci .
– The more general case is obtained when it is dci (X, Y ) ≤ dedit (X, Y ), yet
dci (X, Y )  dcj (X, Y ), i = j. In this case, the external complexity can still
be computed from Equation 12, but now an important optimization issue
regards the order in which the m distances should be considered.
It has to be noted that, even if in this paper we only use dbag to approximate
the edit distance, any function that lower bounds dedit can do the job, since it
is not required that dc is a metric, but only that Equation 5 holds.

4

Experimental Results

In this Section we experimentally evaluate the solution proposed in Section 3.
To this purpose, we provide results obtained from the following real data sets:

BibleWords: This data set consists of all the 12,569 distinct words occurringin the English King James version of the Holy Bible (as provided by [1]).
BibleLines: The 74,645 variable-length lines of the Holy Bible.
BibleLines20: We took the Holy Bible and segmented it into lines of length
20, which resulted in a total of 161,212 lines.
For each data set, we used a sample of the data (approximately 1% of thewhole data set in size) as query objects and built the tree using the remaining
strings. In order to predict the time saving when using dbag , in Figure 6 distance
distributions for the three data sets are shown, whereas Table 1 presents theaverage time needed to compute dbag and dedit for the three data sets.

1

1
Fd
Fd bag1
Fd
Fd bag

0.8

0.6

0.6
0.4

0.4

0.2

0.2

0.2

0

0
2

4

6

8

10

12

14

16

edit

0.6

0.4

0

Fd
Fd bag

0.8

edit

F(d)

edit

F(d)

F(d)

0.8

0
0

5

10

15

20

0

10

20

30

d

d

d

(a)

(b)

(c)

40

50

60

Fig. 6. Distributions of dedit and dbag for the BibleWords (a), BibleLines20 (b), andBibleLines (c) data sets.

Data set
costdbag (s) costdedit (s)BibleWords 7.78 × 10−6 26.1 × 10−6
BibleLines20 17.7 × 10−6 231.6 × 10−6
BibleLines 66.1 × 10−6 1300 × 10−6
Table 1. Distance computation times for data sets used in the experiments.

We ran all the experiments on a Linux PC with a Pentium III 450 MHz
processor, 256 MB of main memory, and a 9 GB disk. The node size of the Mtree was set to 8 Kbytes. In Figure 7, we show average search times for solving a
range query as a function of the query radius r. The graphs indeed demonstratethat search times rapidly increase for long strings (see Figures 7 (b) and (c)),
but also that, for a suﬃciently wide interval of query radius values, the use of
an approximate distance is very eﬀective in reducing search costs. In particular,
for the BibleLines data set, when r = 10 (0.1% of the data set is retrieved),
the average search time when dbag is not used is 64 seconds, which obviously
makes this solution unaﬀordable, whereas the cost can be reduced to less than
8 seconds by using dbag .

0.4

40
No dbagWith dbag

No dbagWith dbag

0.3

30

0.25

25

0.2
0.15
0.1

time (s)35time (s)time (s)

0.35

20
15
10

0.05

5

0

0
0

1

2

3

4

5

6

7

8

0

2

4

6

r

(a)

8

10

12

14

100
No dbag
90
With dbag
80
70
60
50
40
30
20
10
0
0 5 10 15 20 25 30 35 40 45

r

r

(b)

(c)

Fig. 7. Search times when dbag is used or not for the BibleWords (a), BibleLines20(b), and BibleLines (c) data sets.

In Figure 8 we compare the saving in search time obtained through the experiments with the value predicted using Equation 9. As the graphs show, the actual
searching performance can be very well estimated. The accuracy of Equation 9
is only slightly reduced for low values of the query radius, i.e. when the internal complexity for searching in the M-tree cannot be neglected wrt the external
complexity. In Figure 8 the maximum search radius for which is convenient touse dbag , obtained through Equation 10, is also shown. In particular, using values for distance computation times in Table 1 and the corresponding distance
distributions (Figure 6), we obtain:

Experimental
Predicted

rmax

0

1

2

3

4

5

6

7

8

100
90
80
70
60
50
40
30
20
10
0
-10

Experimental
Predicted
saving (%)

80
70
60
50
40
30
20
10
0
-10
-20

saving (%)

saving (%)(1 − 7.78/26.1) ≈ Fd−1
(0.703) ≈ 6,
– rmax (BibleWords) = Fd−1
bag
bag
−1
−1
– rmax (BibleLines20) = Fdbag (1 − 17.7/232) ≈ Fdbag (0.924) ≈ 11, and– rmax (BibleLines) = Fd−1
(1 − 66.1/1300) ≈ Fd−1
(0.949) ≈ 39.
bag
bag

rmax

0

2

4

6

8

10

12

14

100
90
80
70
60
50
40
30
20
10
0
-10

Experimental
Predicted

rmax
0

5

10 15 20 25 30 35 40 45

r

r

r

(a)

(b)

(c)

Fig. 8. Real and predicted time saving for the BibleWords (a), BibleLines20 (b), andBibleLines (c) data sets. Also shown are the rmax values which limit the usefulnessof using dbag .

The graphs indeed demonstrate the accuracy of Equation 10 that can, therefore, be used to reliably predict whether, for a given query, it is worth using
an approximate distance or not. The values of rmax are high enough to allow
eﬃcient search performance over a wide interval of values of the query radius.

It is also worth noting that even if, for the BibleLines20 and the BibleLines
data sets, dedit is not very well approximated by dbag (see Figure 6), we can stillobtain signiﬁcant performance improvements (see Figure 8). This is due to thefact that, in such cases, dbag is very cheap to compute compared to dedit , becauseof the increased strings length (see Table 1), and this indeed allows to reducesearch times, as also demonstrated by Equation 9.

5

Conclusions

In this paper we considered the problem of searching in a string database forthose strings which are similar, according to the edit distance, to a given one.
Metric trees, as the M-tree [9], can be used to eﬃciently reduce the time needed
to solve such queries. However, metric trees do not always succeed in consistently
reducing the number of strings that have to be directly compared to the query, afact that can indeed abate search performance, particularly when long strings areused. To solve this problem we proposed the use of the approximate and cheapbag distance, to quickly get rid of irrelevant strings. We also used the distributionof distances to predict the eﬀectiveness of this pre-ﬁltering step, showing how
the saving in search times can be analytically computed, thus one can decide inadvance if it is worth to use an approximate distance. Experimental results withlarge real data sets demonstrate that our approach achieves savings up to 90%
with respect to the case when the approximate distance is not used, and thatanalytical predictions are very accurate.
Even if in this paper we concentrated on the M-tree, our solution and results
apply to any other metric index, e.g. the recent Slim-tree [17] or the main memory
structures considered in [2]. Moreover, we would also point out that our approachallows diﬀerent functions to be used for approximating the edit distance, since
we only require the former to lower bound the latter. Together, these two facts
indeed broaden the applicability of our approach.
An issue not covered in this work is that of local string alignment, where thelongest common substrings between a query and a database string are searched[11]. Since, however, such problem can be reduced to that of string matching,
we believe that the use of a cheap function to approximate the edit distance canbe eﬀective also in this case. We leave this research topic as future work.
Finally, we would like to point out that in this paper we did not consider
other techniques that are commonly used to reduce the complexity of the online
problem, e.g. cutoﬀ heuristics that can reduce the complexity of computing theedit distance to O(r·|X|) [18], where r is the query radius and |X| is the length ofa string in the data set. We plan to investigate in the future how such techniques
can be embedded in our approach to further improve its eﬃciency. Moreover,
we also plan to compare our approach with other state-of-the-art main memory
solutions [13].

References
1. Project Gutenberg oﬃcial home site. http://www.gutenberg.net/.

2. R. Baeza-Yates and G. Navarro. Fast approximate string matching in a dictionary.
In Proceedings of the 5th String Processing and Information Retrieval Symposium(SPIRE’98), Santa Cruz, Bolivia, Sept. 1998.
3. S. Berretti, A. Del Bimbo, and P. Pala. Retrieval by shape similarity with perceptual distance and eﬀective indexing. IEEE Transaction on Multimedia, 2(4):225–
239, Dec. 2000.
4. T. Bozkaya and M. Özsoyoglu. Indexing large metric spaces for similarity search
queries. ACM Transactions on Database Systems, 24(3):361–404, Sept. 1999.
5. S. Brin. Near neighbor search in large metric spaces. In Proceedings of the 21stInternational Conference on Very Large Data Bases (VLDB’95), pages 574–584,
Zurich, Switzerland, Sept. 1995.
6. W. A. Burkhard and R. M. Keller. Some approaches to best-match ﬁle searching.
Communications of the ACM, 16(4):230–236, Apr. 1973.
7. E. Chávez, G. Navarro, R. Baeza-Yates, and J. L. Marroquı́n. Proximity searchingin metric spaces. ACM Computing Surveys, 33(3):273–321, Sept. 2001.
8. W. Chen and K. Aberer. Eﬃcient querying on genomic databases by using metricspace indexing techniques. In 1st International Workshop on Query Processing andMultimedia Issues in Distributed Systems (QPMIDS’97), Toulouse, France, Sept.
1997.
9. P. Ciaccia, M. Patella, and P. Zezula. M-tree: An eﬃcient access method for similarity search in metric spaces. In Proceedings of the 23rd International Conference
on Very Large Data Bases (VLDB’97), pages 426–435, Athens, Greece, Aug. 1997.
10. P. Ciaccia, M. Patella, and P. Zezula. A cost model for similarity queries in metricspaces. In Proceedings of the 16th ACM SIGACT-SIGMOD-SIGART Symposiumon Principles of Database Systems (PODS’98), pages 59–68, Seattle, WA, June
1998.
11. T. Kahveci and A. K. Singh. An eﬃcient index structure for string databases.
In Proceedings of the 27th International Conference on Very Large Data Bases(VLDB 2001), pages 351–360, Rome, Italy, Sept. 2001.
12. G. Navarro. Multiple approximate string matching by counting. In Proceedings ofthe 4th South American Workshop on String Processing (WSP’97), pages 125–139,
Valparaiso, Chile, Nov. 1997.
13. G. Navarro. A guided tour to approximate string matching. ACM Computing
Surveys, 33(1):31–88, Mar. 2001.
14. G. Navarro, R. Baeza-Yates, E. Sutinen, and J. Tarhio. Indexing methods forapproximate string matching. IEEE Data Engineering Bulletin, 24(4):19–27, Dec.
2001. Special Issue on Text and Databases.
15. S. Santini. Exploratory Image Databases: Content-Based Retrieval. Series in Communications, Networking, and Multimedia. Academic Press, 2001.
16. C. Traina Jr., A. J. M. Traina, and C. Faloutsos. Distance exponent: A new concept
for selectivity estimation in metric trees. In Proceedings of the 16th International
Conference on Data Engineering (ICDE 2000), page 195, San Diego, CA, Mar.
2000.
17. C. Traina Jr., A. J. M. Traina, C. Faloutsos, and B. Seeger. Fast indexing andvisualization of metric data sets using Slim-trees. IEEE Transactions on Knowledge
and Data Engineering, 14(2):244–260, Mar. 2002.
18. E. Ukkonen. Finding approximate patterns in strings. Journal of Algorithms,
6(1):132–137, Mar. 1985.
19. R. A. Wagner and M. J. Fischer. The string-to-string correction problem. Journalof the ACM, 21(1):168–173, Jan. 1974.