FastMap Algorithm
C. Faloutsos,
K. Lin, "FastMap: A Fast Algorithm for Indexing, Data-Mining and
Visualization of Traditional and Multimedia Datasets," in Proceedings
of 1995 ACM SIGMOD, SIGMOD RECORD (June 1995), vol.24, no.2, p
163-174.
Visit author's web page: Christos
Faloutsos
In this system, we used FastMap algorithm,
which was introduced by Faloutsos and Lin, to plot document positions
in a document space. A FastMap algorithm is an algorithm to map
objects into points in some k-dimensional space (k is user-defined),
such that the dis-similarities are preserved. The reason we used
this algorithm is because it can calculate plotting position easily
with existing distance calculation methods therefore more convenient
in graphing the document space in any k-dimensional space, and
still can remain the distance differences in the graph.
The design of FastMap as a linear algorithm
fulfills goals such as:
- It solves the general problem ('distance' problem which represents
difficulty in plotting N points in a k-dimensional space such
that the distances are maintained as well as possible.)
- It is linear on the database size, and therefore much faster
than MDS and
- At the same time, it leads to fast indexing, being able to
map a new, arbitrary object into a k-d point in O(k) distance
calculations regardless of the database size N.
The two benefits mentioned by the authors
were: (1) efficient retrieval, and (2) visualization and data-mining,
in terms of having the objects plot as points in 2-D or 3-D space,
which reveals potential clusters and correlations among attributes
and other regularities that data-mining is looking for.
The simple step of FastMap algorithm works
as follows:
- Find the objects which have most long distance each other
among all documents.
- These objects are called the pivot objects.
- Calculate xi by cosine law to project the objects on a line.
- To map objects in k-d space, use Euclidean distance function
D'().
- Do loop depend on the expected dimensional space.
- Eventually it will give 'images' of objects by which mapping
in space is possible.
The FastMap algorithm works in the steps as
below.
