[boost] spatial and metric containers

From: conrado_at_[hidden]
Date: 2003-07-24 08:58:56

Dear Boost members,

This post is to ask for potential interest for a new library. We
(G. Marpons and me) have developed a prototype library 
called SMTL (Spatial and Metric Template
Library) whose basic functionality is to provide STL-like containers
and iterators for spatial and metric data. If there is interest for
such a library we would make the necessary changes to conform to Boost
standards and submit it for a formal review. 

SMTL aims to efficiently solve queries like:

a) Which books where written by authors whose last name begins with
   "B" between 1986 and 1994?
b) How many cities with population above 10,000 are located between
   such and such latitude and such and such longitude?
c) Which is the closest gas station to this point?
d) Which are the 10 most similar objects to this complex object?

Besides providing more efficient solutions, the SMTL allows the
programmer to express the solution in terms closer to
the problem s/he is actually trying to solve.

An spatial container template accepts a dimension d, a key type 
and a mapped type. The key type can be anything as long
as it behaves as a d-dimensional tuple where for each attribute there
is some total order. The necessary flexibility is achieved through a
key_traits parameter which defaults to the expected behavior when
key_type is for instance vector<T>, T[], T*.
Spatial maps support usual associative container operations and 
range queries. A range query specifies a lower
and upper bound (possibly -infinity or infinity) for each coordinate
and returns a pair of STL-compatible iterators that can be used to retrieve the
elements inthe container that satisfy the query. The cost of the query
is proportional to the number of retrieved elements plus some
sublinear overhead (O(sqrt(N)) for a collection of N elements).

A metric container template accepts a key type T, a mapped type and a
metric functor. A metric functor for type T 
must provide double operator()(const T&, const T&), to measure the
distance between two T's. As a metric the distance function d must satisfy d(x,x)=0,
d(x,y) = d(y,x), d(x,y)>0 if x!=y, and d(x,y) <= d(x,z)+d(z,y)
(triangular inequality). The
metric container efficiently supports nearest neighbor queries (NN
queries). A NN query specifies some x of type T and returns a pair of
STL-compatible iterators
that can be used to retrieve all the data points of the collection
from the closest element to x to increasingly far away points. The
points are retrieved incrementally; for instance, if only the closest point is needed
then the cost of the query is small (O(log N) under some mild assumptions). 

There are more things in SMTL, but I think this is enough for the
moment. I'll be happy to give more details to anyone interested.

I'll appreciate a lot comments and suggestions about SMTL. I think
this library can be interesting for a lot of people and it is suitable
for inclusion in the boost collection, but I'm too novice in this
bussiness and maybe too enthusiastic.

Conrado Martinez