Re: Special query type for Spatial DB

"Arthur Yeo" <ayeo_at_acm.org> wrote in message news:1103_1074129738_at_news.mw.cray.com...
> In particular, I'm looking for support for queries like:
> given a bounded region (3D may be), find me n points in a neighborhood
that are the closest to each other.
> Note that there's no base reference point given, except for a bounded
region.
>
> Concrete application queries may look like these:
> a)Given a bounded region in space, find me a cluster of 50 pulsars that
are closest to each other.
> b)Given the state of California, find me a group of 10 fire-stations that
are closest to each other.

Your question has many interpretation. What is the universe of discourse? Is it a metric space, or graph? How do you define "closeness" metric for a set of points? Do you want the exact answer, or approximate one?

Assuming that you can get away with approximate answer, could I suggest density map? Density is a function that associates a number with every point in your metric space, or graph. Density map is an incremental evaluation structure on your universe of discourse. Every time you modify your universe -- add a pulsar point into 3D space, or add a fire station node into network of existing firestation -- you have to update your density map. Quering density map is easy: just fimd me the maximum.

The natural question might be: "Do we need a separate density map for each possible number of points?" Yes, but assuming once again that you can tolerate an approximate answer, you can get away with logarithmic reduction. Just keep density maps for N=2,4,8,16, ... and when asked for N=10, for example, then just invoke the map with closest N. Received on Fri Jan 16 2004 - 18:03:13 CET