Re: Special query type for Spatial DB

"Arthur Yeo" <ayeo_at_acm.org> wrote in message news:a79bf3a3.0401271032.4601af2f_at_posting.google.com...
> "Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message
news:<BXUNb.8$KI3.136_at_news.oracle.com>...
> > 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?
>
> It can be metric-space (with some additional work added to support
> it).
> Closeness = shortest distance
> i.e. For every point in a given neighborhood of points, its distance
> to every other point is the shortest.

Do you mean minimal diameter of the cluster A?

diam(A) = max(||x-y||), for any x and y from A

Note that

sqrt(sum(||x-y||^2)), for any x and y from A

is a natural clustering factor metrics as well.

> Approximate is fine.

Given that we routinely operate floating point numbers, how can it be otherwise:-)

> > 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.
>
> Density map sounds very interesting.
> However, I see a problem in adding more to the WHERE-clause if my
> query is slightly modified so that it becomes:
> Find me 5 fire-stations in California that are closest to each other
> and everyone of them must have, at least, 2 free fire-engines.
>
> Is there an easy way to augment a density-map with other properties,
> like the free fire-engines example so that it can support more complex
> queries?

Suppose you know the minimal diameter of 5 point set that includes a given point from your set:

relation densityMap5 (

     x location,      -- fire station's location
     diameter real  -- diameter of 5 point set cluster that includes x

Then, your query might look like this:

select * from densityMap5, fireStations
where distance(fireStations.x, densityMap5.x) < densityMap5.diameter and fireStations.#freeFireEngines >= 2
order by densityMap.diameter

Anyway, the idea is to start with very approximate but fast query that returns you a superset of solutions, which is later postprocessed with more refined filters. This wouldn't always work always, of course. For example we ranked clusters by density and start iterating through them based upon the diameter ordering, and none of the clusters meet your postfilter condition. Then you'll have to iterate through the whole set.

I would suggest that the topic is really more complicated than a usenet message can possibly acomodate;-) Received on Tue Jan 27 2004 - 21:20:52 CET