Hi, sorry for possibly stupid question but I am looking for a database which would support an indexed* range query between two (even better between multiple) elements in Cartesian space.

[size=11](* by indexed, I mean implementing any feature (index, tree, bitmapping…) that would speed up the search comparing to exhaustive search)[/size]

I.e., I need to SELECT all pairs with specific mutual distance (specified as a range, ideally including uncertainty, but I guess that this would be too much to ask).

Problem:

I have a table of ~x billion points in a Cartesian space and a norm (can be simply L2 norm --> distance) and need to find all pairs that have the norm between <x1, x2>.

Obviously, exhaustive search will need to go through x^2/2 comparisons - practically not feasible. Linear index is not feasible either (too many entries). R/R*-tree derivative will help (limiting the comparisons), but still involve quite too many comparisons.

I have noticed that SciDB “Optical Astronomy (relational)” use-case (scidb.org/UseCases/Astronomy%20in%20ArrayDB.pdf) has the following example:

```
Find stars with stellar neighbor within distance x where at least one of the stellar neighbors has the colors of a white dwarf
SELECT S1.objectId AS s1, S2.objectId AS s2
FROM Star S1 -- S1 is the white dwarf
JOIN Star S2 -- S2 is the second star
WHERE SPH_DIST(S1.raDecl, S2.raDecl) < 5 -- arcseconds
AND S1.ugColor < 0.4 -- and S1 meets Paul Szkody's color cut
AND S1.grColor < 0.7 -- for white dwarfs
AND S1.riColor > 0.4
AND S1.izColor > 0.4;
```

… but I am not sure how this SELECT is evaluated.

As far as I am aware, databases I have looked at do not support this type of query directly, only querying by a distance to a specific fixed point (e.g. postGIS), but maybe I’ve overlooked something.

Questions:

- Could you please briefly explain (or point me towards the appropriate documentation), how will SciDB evaluate such query?
- Do you have any idea how to quickly perform the query I am describing(pairwise distance query)?
- In general - can SciDB help me with this?

Thank you!

Regards,

Ondrej