Re: R-tree indexing

[Chris Albertson <chrisalbertson90278@yahoo.com>]

--- Doug Welch <welch@physics.mcmaster.ca> wrote:
> 
> Two questions:
> 
> 1) Is R-tree indexing being used on coordinate boxes of type box?
> If not, this would be a superb idea since R-tree indexed coordinate
> box queries (overlap, contained-within, etc) are viciously efficient
> and postgresql implements this index.

R-tree seems like a good idea.  It certainly works well for
rectangular (x,y) systems but there is some problems and
special case when you apply it to a spherical or polar system.
There are singularities at the poles and problems with selection
boxes that include the zero degrees.  You can get around these
but I don't know how well the Database system's built-in
R-tree index would work.  I do intend to try it.

One more thing.  In our case one, I think, always wants
to querry by great circle distance not with a bounding box.
So even if the R-tree is use you still need to screen the
results with a great circle calculation

One word of advice about testing:  Use a large dataset.  On
a modern PC with lots of RAM that means a hundred million row
database.  On a thousand point or maybe even a million row
test data the whole thing will cache in RAM and everything
will look fast.  I've used random number generators to 
create test data.

One index scheem that is known to work well in sperical data is
the P-Code.  Basically you divide the sky into areas of equal
size, Maybe a million such areas then you tag each ra,dec pair
with the "area code" and then maintain a standard B-Tree index
on the area code.  Stars within their error circle of an area
code boundry need to be tagges with both codes.

Still you need to de-select the result with a great circle
calculation.

te PostgreSQL DBMS allows us to refine operators and functions
that can be used in SQL queries using a kind of "plug in"
to the server.  So it's not hard to implement any of these
methods.  What's better is that the users don't have to know
how you were able to find a few stars out of 100,000,000 in
two or three seconds.  

> 
> 2) Is anyone considering implementing an "alert" query which would
> be triggered by a object being added outside previous object
> positions
> (if they exist for that part of the sky) and/or not in the Tycho
> list?
> This would be a way of detecting moving objects, flare stars, novae,
> etc.

If a database were built and public access were allowed to it
Users could define their own triggers as "triggers" are stanadrd
featur in most database systems.

Going back to my proposel about cross referenced catalogs.  I think
"triggers" are a good way to populate a costom catalog.  You'd
want to think it through well so as not to be flooded with
false positives.

The thing to remember is that while a database might phyicaly like
on some far any computer, today's Internet is fast enough that
it shouldn't matter.  The litle bits of data like "All stars with
in 30 arcsec of star_number_X that have at least 50 data points"
travels over the INternet almost as fast as over a local connection.

> 
> Cheers,
> Doug
> 
> 


=====
Chris Albertson
  Home:   310-376-1029  chrisalbertson90278@yahoo.com
  Cell:   310-990-7550
  Office: 310-336-5189  Christopher.J.Albertson@aero.org
  KG6OMK

__________________________________
Do you Yahoo!?
Yahoo! Calendar - Free online calendar with sync to Outlook(TM).
http://calendar.yahoo.com