Seagate ST9100823A Uživatelský manuál stáhnout pdf

The Zones Algorithm for

Finding Points-Near-a-Point or Cross-Matching Spatial Datasets

Jim Gray, María A. Nieto-Santisteban, Alexander S. Szalay

Microsoft, Johns Hopkins University

MSR TR 2006 52

April 2006

Abstract:

Zones index an N-dimensional Euclidian or metric space to efficiently support points-near-a-

point queries either within a dataset or between two datasets. The approach uses relational algebra and the

B-Tree mechanism found in almost all relational database systems. Hence, the Zones Algorithm gives a

portable-relational implementation of points-near-point, spatial cross-match, and self-match queries. This

article corrects some mistakes in an earlier article we wrote on the Zones Algorithm and describes some

algorithmic improvements. The Appendix includes an implementation of point-near-point, self-match, and

cross-match using the USGS city and stream gauge database.

1. Introduction

The article “There Goes the Neighborhood: Relational Algebra for Spatial Data Search” [1] introduced

three spatial indexing methods for points and regions on a sphere: (1) Hierarchical Triangular Mesh

(HTM) that is good for point-near-point and point-in-region queries with high dynamic range in region

sizes, (2) Zones which is good for point-near-point queries with know radius, and also batch-oriented

spatial join queries, and (3) Regions which is an algebraic approach to representing regions and doing

Boolean operations on them, and answering point-in-region queries.

We have used all three methods extensively since that article was written [2], [4], [5], [6], [7]. The Zone

Algorithm is particularly well suited to point-near-point queries with a search radius known in advance.

However, when the radius is more than ten times larger than the zone height, the Zone Algorithm is less

efficient. This high dynamic range is common in adaptive mesh simulations and many other spatial

applications. In those cases, the HTM approach or perhaps DLS [3] is a better scheme. But, for many

Astronomy and cartographic applications there is a natural scale (arcminute or mile) that covers many

cases. For those applications, the Zone approach has some

real advantages. First it works entirely within SQL, not

requiring any extensions. So it is portable to any SQL

database system. Second, it is efficient for batch-oriented

spatial join queries – from 20 to 40 times faster than the

object-at-a-time approach. The batch efficiency has given

Zones a prominent place in building and using

SkyServer.sdss.org and OpenSkyQuery.net. In particular,

we use it to build the Neighbors table and to do batch-

oriented cross match queries [4], [6], and [7].

This article corrects some subtle mistakes in the Zone

algorithm described in [1], and presents some extensions.

The basic changes are:

• The radius-inflation was wrong (θ‘= θ /cos(abs(dec)) is

wrong.) The correct computation affects both margin

widths and search widths.

• The zone margin logic can be simplified.

• Self-match can do ½ the work by adding the symmetric

pairs as a second step. Cross-match between different

datasets doesn’t have this symmetric option.

• A Zone table can eliminate the loop in multi-zone

searches and matches.

Terrestrial and Celestial Coordinates,

A Rosetta Stone:

Celestial coordinates are often expressed

as Equatorial right ascension and

declination (ra, dec) expressed in

degrees. On the terrestrial sphere,

people often use latitude and longitude

(in degrees). This article uses (ra, dec)

degrees, which geo-spatial readers will

want to interpret as lon/lat (not lat/lon) –

i.e. lat ~ dec and lon ~ ra. The code in

the appendix uses (lat, lon) since the

sample datasets are USGS places and

stream gauges.

We also find it useful to represent

(ra,dec) by their Cartesian coordinates –

the unit vector u = (x,y,z) where x points

at the prime meridian equator, z points

to the north pole, and y is normal to x

and z.

x = cos(dec)*cos(ra)

y = cos(dec)*sin(ra)

z = sin(dec)

1 2 3 4 5 6 ... 17 18

Shrnutí obsahu

Strany 1 - 1. Introduction

1 The Zones Algorithm for Finding Points-Near-a-Point or Cross-Matching Spatial Datasets Jim Gray, María A. Nieto-Santisteban, Alexander S. Szalay M

Strany 2 - 2. Zone idea

10 3. Summary Zones partition an N-Dimensional Euclidian or metric space to efficiently support points-near-a-point queries, either within a dataset

Strany 3

11 A. Appendix A.1. Defining and Populating The Sample Database ------------------------------------------------------------------------------- -- Sa

Strany 4

12 A.2. Define and Populate the Zone Indices ------------------------------------------------------------------------------- -- Create an populate th

Strany 5 - end

13 ------------------------------------------------------------------------------- -- Procedure to populate the zone index. -- If you want to change

Strany 6

14 ----------------------------------------------------------------------- -- ZoneZone table maps each zone to zones which may have a cross m

Strany 7 - 2.3. Cross-Match

15 A.3. Define And Use Points-Near-Point Function ------------------------------------------------------------------------------- -- GetNearbyObjects

Strany 8

16 go ------------------------------------------------------------------ -- Three test cases: declare @lat float , @lon float, @theta float s

Strany 9

17 A.4. Cross Match Places with Stations and Places with Places ------------------------------------------------------------------------------- -- CR

Strany 10 - 4. References

18 ------------------------------------------------------------------------------- -- SELF-MATCH EXAMPLE -------------------------------------------

Strany 11 - A. Appendix

2 2. Zone idea All index mechanisms use a coarse index to produce candidate objects which are then filtered by some predicate (see Figure 1.) Zon

Strany 12 - in the band

3 If looking for all objects within a certain radius (θ) of point (ra, dec) then one need only look in certain zones, and only in certain parts of e

Strany 13

4 Figure 3: The search range of a zone expands near the poles. The diagram shows the need for α =180° if the pole is included and α ~90° very near

Strany 14

5 Equation (13) can be used to find the maximum value for tan α in equation (8). First refractor (8) to isolate the φ terms by dividing the nominato

Strany 15

6 2.2. Handling margins if there is wrap-around Given a zone table for all cities, if we ask for places within 10 arc minutes of Greenwich, UK (lat,

Strany 16

7 With margins added to the ZoneIndex table, the original query works correctly near the prime meridian. select objID

Strany 17

8 So, cross-match of a zone with itself is: select Z1.objID as ObjID1, Z2.objID as ObjID2 -- get object pairs into #answer

Strany 18 - -- 27 seconds

9 Unfortunately, the SQL Server optimizer is not smart enough to recognize that it can optimize this plan – it scans all objects in all qualifying zo

Další dokumenty pro ne Seagate ST9100823A

Zobrazit dokument Seagate ST9100823A Uživatelský manuál

Seagate ST9100823A Uživatelský manuál (3 stránky)

Komentáře k této Příručce

Žádné komentáře

Seagate ST9100823A Uživatelský manuál

Procházejte online nebo si stáhněte Uživatelský manuál pro ne Seagate ST9100823A. 1. Introduction - Microsoft Research Uživatelská příručka

Shrnutí obsahu

Další dokumenty pro ne Seagate ST9100823A

Komentáře k této Příručce

Související produkty a manuály pro ne Seagate ST9100823A