Definitions

A metric space is a pair (S, f) where S is an abritrary (possibly infinite) set of objects and f is a function which returns a "distance" for any two objects x, y in S. This distance is a number used to express the similarity between the two objects. The larger the distance, the more they differ. A distance of zero means they are considered equal.

The function f has to be a "metric", i.e. the following conditions have to be met for all x, y, z in S:

• f(x, y) >= 0

  (positivity)

• f(x, y) == f(y, x)

  (symmetry)

• f(x, z) <= f(x, y) + f(y, z)

  (triangle inequality)

This definition adheres to most people's intuitive understanding of the distance between two points in a Euclidian space (of arbitrary dimensionality). [1] Imagine you have three points in a 2-dimensional space like this:

A-------B
 \     /
  \   /
   \ /
    C

It is evident that the distance between two of these points is necessarily larger than (or equal to) zero, and that the direction you take for measuring (from A to B or vice versa) has no influence on the distance. The third condition, the triangle inequality is easy to grasp, too: if you know the distances between A and B and between B and C, you can be sure that their sum is equal to or larger than the distance between A and C. Voila, there's your metric space.

In many cases, metric distance functions take a long time to compute. Because of this, data structures used to index metric spaces are designed to minimize the number of distance computations necessary for searching the whole space by using the properties of its metric function (most notably the triangle inequality) to discard as many objects as possible after every computation.

Use cases & caveats

Metric distance functions can be defined for objects other than points in Euclidian space, too. One very well known distance function is the Levenshtein distance, which is applicable to arbitrary strings. Since it is quite popular and indexing strings is one of the major use cases for metric spaces, an implementation of this function is included in this module. Other metric distance functions for strings are the Damerau-Levenshtein variant and Hamming distance. These can be used for a variety of tasks, such as spell-checking, record linkage (or "deduplication"), error detection etc.

Please note that indexing a large number of objects usually takes a considerable amount of time and memory. Indexing only pays off if you are going to do a lot of searches in the index. If you just want to search a set of objects for all objects similar to one or a few other objects, you are better off comparing them sequentially by hand with your distance function.

Installation

This file is a stand-alone module for Python 2.4 and later which you only have to save somewhere in your PYTHONPATH. [2] No installation is necessary. The only tight dependencies are the modules sys, random and weakref which are most probably already included in your Python installation.

If you are using this on a 32 Bit i386 machine running Windows or Linux, you probably also want to install Psyco which speeds up execution times quite noticeably (in exchange for only a slightly increased memory usage). Psyco will be used automatically if it is available.

The most current version is always available from this site:

http://well-adjusted.de/mspace.py/

The project is currently kept in SVN and may be obtained from the following URL:

svn://svn.well-adjusted.de/mspace/trunk

Index creation

Say you have a dictionary file containing one or more words per line. You can make an index of all the words in it by doing:

>>> import mspace
>>> mydict = file('dictionary.txt')
>>> words = mspace.tokenizer(mydict)
>>> index = mspace.VPTree(words, mspace.levenshtein)

You can delay the time-comsuming construction phase by creating the index without any parameters and explicitly calling construct at a later time:

>>> index = mspace.VPTree()
>>> index.construct(words, mspace.levenshtein)

Please note that the index' content is dismissed on every call to construct. The index is built from scratch with only the objects and distance function passed as parameters.

Performing range-searches

After you have built the index (and got yourself some coffee if the index is large) you may search it for all objects having distance to a given other object between arbitrary bounds:

>>> index.range_search('WOOD', min_dist=0, max_dist=1)
['GOOD', 'WOOD', 'WOOL', 'MOOD']

In this case, you received four results: the object you searched for (apparently it has been in your dictionary, too) and two other objects "GOOD" and "WOOL", both of which have the requested maximum distance of one to your query object. Result lists are unordered and do not contain information about their contents' distance to the query object. If you need this, you have to calculate it by hand.

Both min_dist and max_dist are optional parameters defaulting to zero. Thus, if you leave them out, a search for objects which are exactly equal (as defined by your distance function) to the query object is performed. For historical reasons, and since range-searching with a minimum distance of zero and a maximum greater than zero is quite common, there is a shortcut to search with min_dist=0:

>>> index.search('WOOD', 1)
['GOOD', 'WOOD', 'WOOL', 'MOOD']

Performing nearest-neighbour-searches

The second type of search you can perform is "k-nearest-neighbour" search. It returns a given number of objects from the index that are closest to the query object. Search results are guaranteed to never contain an object with a distance to the query object that is larger than that of any other object in the tree.

Result lists are composed of (object, distance) tuples, sorted ascendingly by the distance. If you don't specify a maximum number of matches to return, it defaults to one:

>>> index.nn_search('WOOD')
[('WOOD', 0)]
>>> index.nn_search('WOOD', 5)
[('WOOD', 0), ('WOOL', 1), ('GOOD', 1), ('MOOD', 1), ('FOOT', 2)]

Note that the index may contain other objects with a distance of two to the query object 'WOOD' (e.g. 'FOOL'). They have just been cut off because a maximum of five objects has been requested. You have no influence on the choice of representatives that is made.

Note that you must not expect this method to always return a list of length num because you might ask for more objects than are currently in the index.

Indexing complex objects

If you have "complex" objects which you want to index by only one specific attribute, you can write a simple wrapper around levenshtein (or some other function applicable to the attribute) which extracts this attribute from your objects and returns the distance between their attributes' value. This way you can search for and retrieve complex objects from the index while comparing only a single attribute

>>> import mspace
>>>
>>> class Record(object):
...     def __init__(self, firstname, surname):
...         self._firstname, self._surname = firstname, surname
...
>>> def firstnameLev(r1, r2):
...     return mspace.levenshtein(r1._firstname, r2._firstname)
...
>>> index = mspace.VPTree(listOfRecords, firstnameLev)
>>> rec = Record("Paul", "Brady")
>>> index.search(rec, 2)
[<Record: 'Paula Bean'>, <Record: 'Raoul Perky'>, <Record: 'Paul Simon'>]

Of course you can also use more advanced techniques like writing a function factory which returns a function that extracts arbitrary attributes from your objects and applies a metric function to it:

>>> def metric_using_attr(metric, attr):
...     def f(one, other, attr=attr):
...         attr1, attr2 = getattr(one, attr), getattr(other, attr)
...         return metric(attr1, attr2)
...     return f
...
>>> metric = metric_using_attr(mspace.levenshtein, "_firstname")
>>> metric( Record("Paul", "Brady"), Record("Paul", "Simon") )
0

(Note that the inner function f in this example deviates from the standard protocol by accepting an optional third parameter. This is done here only to pull the name attr into the inner function's namespace to save some time when looking up its associated value. No index structure in this module will ever call its distance function with more than two parameters anyway, so that whatever you passed as attr to metric_using_attr when creating your function will be used when this function gets called by an index. Got it?)

Reverse indexes

Of course you can use a similar technique to avoid full indexes and instead create an index which only contains references to your data (in a database, text file, somewhere on the net etc.). Your distance function would then use the supplied values to fetch the objects to compare from your data source. But, I cannot stress this enough, your distance function's performance is absolutely crucial to efficient indexing and searching. Therefore you should make sure that your way of accessing the data is really fast.

Capabilities

The algorithms implemented in this module have different capabilities which are displayed in the table below:

The first row is about the value returned by the distance function the index uses. BKTrees are not prepared to handle non-discrete distances (for example floats) and will most probably perform really bad when they occur.

The other two rows describe what you can do with the indexes after they have been constructed. Please note that neither of them may shrink over time. Only BKTrees are able to handle insertion efficiently.

Performance

[In short: you are probably better off using BKTrees unless you need a non-discrete metric. When in doubt, test both options.]

Obviously, the whole point of this module is to speed up the process of finding objects similar to one another. And, as you can imagine, the different algorithms perform differently when exposed to a specific problem.

Here's an example: I took the file american-english-large from the Debian package wamerican-large and did some time measurements of indexing and searching a random subset of it. The machine I used is an 1.1GHz Pentium3 running Python 2.4 from Debian stable with Psyco enabled. Please note that the following numbers have been determined completely unscientifical. I only show them to give you an idea of what to expect. For serious benchmarking, I should have used the timeit module. Nevertheless, this is it:

This table shows construction times (total and per node in seconds) for data sets of a given size. Additionally, you can see the height [3] of the trees. Apparently, BKTrees can be constructed a lot faster than VPTrees. Both of them need an increasing time per node with growing data sets. This is expected since construction complexity is O(n log(n)) in both cases.

This table shows the runtime of searches done in the trees (in seconds), the number of distance calculations done and the number of results for growing error tolerance. All values are given as average over 100 random searches (from the same file, but not necessarily from the set of indexed objects). As you can see, search runtime (tightly connected to the number of distance calculations) literally explodes for larger values of k. This growth only fades when an increased part of the complete search space is examined (the number of distance calculations equals the number of nodes compared with the query object).

As you can see, too, long search runtimes for large values of k don't actually hurt usability very much since you only get a usable number of results for small k anyway. This is of course due to the nature of the data set and the distance function used in this example. Your application may vary greatly.

You also have to keep in mind that the dictionary I used contains almost no duplicates. If you used the words of a real document as your data set, your tree would have significantly less nodes than the number of words in your document since you typically repeat a lot of words very often. A quick test with my diploma thesis revealed only 4400 distinct words in a document with 14,000 words (including LaTeX commands). This makes searching much faster because equal objects (as defined by the distance function) are only evaluated once.