2004/08/14 by Jim Gray, Gray, Jim, Alexander S. Szalay +17 · 7 citations
Computer Science · #Advanced Database Systems and Queries #C.4 #Data Management and Algorithms #Data Mining Algorithms and Applications #Databases (cs.DB) #FOS: Computer and information sciences #cs.DB
paper · pdf · doi:10.48550/arxiv.cs/0408031
Original at http://research.microsoft.com/research/pubs/view.aspx?tr_id=736
arxiv created 2004/08/14 · openalex publication_date 2004/08/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We explored ways of doing spatial search within a relational database: (1) hierarchical triangular mesh (a tessellation of the sphere), (2) a zoned bucketing system, and (3) representing areas as disjunctive-normal form constraints. Each of these approaches has merits. They all allow efficient point-in-region queries. A relational representation for regions allows Boolean operations among them and allows quick tests for point-in-region, regions-containing-point, and region-overlap. The speed of these algorithms is much improved by a zone and multi-scale zone-pyramid scheme. The approach has the virtue that the zone mechanism works well on B-Trees native to all SQL systems and integrates naturally with current query optimizers - rather than requiring a new spatial access method and concomitant query optimizer extensions. Over the last 5 years, we have used these techniques extensively in our work on SkyServer.sdss.org, and SkyQuery.net.