Warning: Undefined variable $PHP_SELF in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 2
Warning: Undefined array key "word" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 5
Warning: Undefined array key "svar" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 6
Warning: Undefined array key "valg" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 7
Spanners

Metric space searching is the problem of finding objects in a d-dimensional space. This section will give an example of this, explain why it is an interresting problem, and how t-spanners can be used to solve it.

Imagine a database of cardboard boxes. In this database each box is registred by its dimensions: height, width and length. The purpose of the database is to aid users in finding the box which best fit their wrapping needs. That is, finding the boxes which resemble a set of parameters. This is called inexact matching.

The naive way of performing such a search would be to first find all boxes within a given height, then find all of those within a given width and so forth. The result could be a mile long list of candidate boxes, or worse that no boxes fitting those dimensions exist. Either way a new search would be needed.

The database as a metric space

The entries in the above database could also be seen as points in a 3-dimensional space, with height, width and length along the axis. In this way boxes with similar properties would be located geometrically close to each other. In fact, the euclidian distance between two entries would be a measure of how much two cardboard boxes resembled each other.

In this scenario it would be possible to create a t-spanner connecting all boxes and a point consisting of the search parameters. Close mathces would be directly connected to the search parameters, and a wider search of the database can be done by traversing the graph from the search parameter by some single-source shortest-path algorithm. This search would have guaranteed results, listed by the degree of resemblence.

The bigger picture

Granted, you may never need to search a cardboard box database. In metric space, however, elements can be stored in a d-dimensional space, allowing a wide range of comparable properties to be registred. This makes it possible to replace cardboard boxes with fingerprints, voice recordings, web pages or DNA strings, and things become interesting.

Building a t-spanner with O(n) edges from n elemets can be done in O(n·log n) time. Solving the single-source shortest-path problem on a graph with O(n) edges can be done with Dijkstras algorithm in O(n · log n) time. This means that finding the closest matches to i.e. a fingerprint can be done in O(n·log n) time, making this an attractive algorithm.