Re: Special query type for Spatial DB

"Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message news:<4TzRb.20$9F.242_at_news.oracle.com>...
> "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
>

That's correct.

> 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

Interesting, I'd have to give this some thots ... So, I'm assuming density-maps are pre-computed.

I'm sure if u saw my last post about ...

The other issue is that the universe of discourse may be more ordered/evenly-spaced out than what we were talking about; e.g. honeycomb cells or nuclear-reactor uranium rods.

So, I guess density map will not reveal much since they are all evenly spaced; unless, we use a different property to create the density map, such as free honeycomb cells (i.e. not occupied by eggs or larvae.)

I'd like to hear your thots on this.
Thanks.

>
> 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 Thu Jan 29 2004 - 00:43:57 CET