There Goes the Neighborhood: Relational Algebra for Spatial Data Search
<|reference_start|>There Goes the Neighborhood: Relational Algebra for Spatial Data Search: 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.<|reference_end|>
@article{gray2004there,
    title={There Goes the Neighborhood: Relational Algebra for Spatial Data Search},
    author={Jim Gray, Alexander S. Szalay, Aniruddha R. Thakar, Gyorgy Fekete,
  William O'Mullane, Maria A. Nieto-Santisteban, Gerd Heber, Arnold H. Rots},
    journal={arXiv preprint arXiv:cs/0408031},
    year={2004},
    number={MSR-TR-2004-32},
    archivePrefix={arXiv},
    eprint={cs/0408031},
    primaryClass={cs.DB}
}