spatial-index


Namespatial-index JSON
Version 1.0.2 PyPI version JSON
download
home_pagehttps://github.com/Caltech-IPAC/SpatialIndex
SummaryLibrary for generating DBMS spatial index constraints.
upload_time2020-06-30 14:59:44
maintainer
docs_urlNone
authorJohn Good
requires_python
licenseLICENSE.txt
keywords astronomy database spatial-index
VCS
bugtrack_url
requirements No requirements were recorded.
Travis-CI No Travis.
coveralls test coverage No coveralls.
            # SpatialIndex
Spatial Indexing Library for Astronomy

One of the most common database searches in astronomy involves finding all the 
objects in a region of the sky.  Basic DBMS engines provide efficient indexed 
searches only for single column (i.e. something that can be sorted linearly).
Some servers are starting to support true multidimensional indexing (e.g.,
R-Trees) but this is neither universal nor uniform.

It is, however, possible to leverage the standard internal database indexing
(B-Tree) to support impressively efficient 2D indexing.  If one tesselates the
sky into a heirarchical, Z-ordered space (using a scheme like a Heirarchical
Triangular Mesh (HTM)  or Hierarchical Equal Area isoLatitude Pixelization
(HEALPix)), then any "object" (sky coordinate) belongs to a specific 
tesselation cell and each cell has a unique ID (number).  This number can
be stored in an integer column in the database table.

Then when one wants to perform a spatial search, the region can be converted
to a range (actually set of ranges) of spatial index cell numbers and, 
because of the Z-ordering) these ranges tend to be co-located and can be
accessed efficiently.  For large tables, this can speed up queries by orders
of magnitude.

The resultant records are actually a superset of those desired, but a simple
geometric filtering (also part of the database query) can remove the extraneous
records.

All this requires that the DBMS table be augmented with four extra columns:
a spatial index column at some pre-chosen HTM/HEALPix level and the three-vector
(x,y,z) coordinate of the point on the sky.

This library converts a geometric constraint into a pair of constraints that
can be added to otherwise-generic SQL to turn it into a spatially-indexed
region query.  For instance, if the DBMS table has been indexed at HTM level
7, a cone on the sky at latitude 43.7, longitude 129.4 with radius 0.5 degrees
gets turned into the following SQL constraints 

   WHERE (   (htm7 = 245093) 
          OR (htm7 = 245098) 
          OR (htm7 = 245100)
          OR (htm7 = 245105) 
          OR (htm7 = 245110)
          OR (htm7 = 245118))

     AND (-0.45888930755155893*x)+(0.55866098617988125*y)+(0.69088241107685844*z)
         >=9.99975630705394747e-01


Fragments like this get inserted into the SQL statement as appropriate.




Building the Python library:

The spatial index code need to be wrapped for Python use.  This is taken care
of the Makefile but consists of using Cython to compile the spatial-index.pyx
code (Python with Cython directives) into "spatial_index.c", then building 
a LINUX library from the this plus our C libraries (our C code plus tinyhtm).
This results in "spatial_index.cpython-37m-x86_64-linux-gnu.so". which has the
right content to be loadable by the Python runtime and accessed by Python
calls.

The last step is to turn this into a Wheel file that can be pip-install in
our Python distribution and/or uploaded to PyPI.  This file is
(dist/spatial_index-0.9-cp37-cp37m-linux_x86_64.whl).  There is bookkeepping
as well, but the primary files in this sequence are again

  spatial_index.c
  spatial_index.cpython-37m-x86_64-linux-gnu.so
  dist/spatial_index-0.9-cp37-cp37m-linux_x86_64.whl



            

Raw data

            {
    "_id": null,
    "home_page": "https://github.com/Caltech-IPAC/SpatialIndex",
    "name": "spatial-index",
    "maintainer": "",
    "docs_url": null,
    "requires_python": "",
    "maintainer_email": "",
    "keywords": "astronomy database spatial-index",
    "author": "John Good",
    "author_email": "jcg@ipac.caltech.edu",
    "download_url": "",
    "platform": "",
    "description": "# SpatialIndex\nSpatial Indexing Library for Astronomy\n\nOne of the most common database searches in astronomy involves finding all the \nobjects in a region of the sky.  Basic DBMS engines provide efficient indexed \nsearches only for single column (i.e. something that can be sorted linearly).\nSome servers are starting to support true multidimensional indexing (e.g.,\nR-Trees) but this is neither universal nor uniform.\n\nIt is, however, possible to leverage the standard internal database indexing\n(B-Tree) to support impressively efficient 2D indexing.  If one tesselates the\nsky into a heirarchical, Z-ordered space (using a scheme like a Heirarchical\nTriangular Mesh (HTM)  or Hierarchical Equal Area isoLatitude Pixelization\n(HEALPix)), then any \"object\" (sky coordinate) belongs to a specific \ntesselation cell and each cell has a unique ID (number).  This number can\nbe stored in an integer column in the database table.\n\nThen when one wants to perform a spatial search, the region can be converted\nto a range (actually set of ranges) of spatial index cell numbers and, \nbecause of the Z-ordering) these ranges tend to be co-located and can be\naccessed efficiently.  For large tables, this can speed up queries by orders\nof magnitude.\n\nThe resultant records are actually a superset of those desired, but a simple\ngeometric filtering (also part of the database query) can remove the extraneous\nrecords.\n\nAll this requires that the DBMS table be augmented with four extra columns:\na spatial index column at some pre-chosen HTM/HEALPix level and the three-vector\n(x,y,z) coordinate of the point on the sky.\n\nThis library converts a geometric constraint into a pair of constraints that\ncan be added to otherwise-generic SQL to turn it into a spatially-indexed\nregion query.  For instance, if the DBMS table has been indexed at HTM level\n7, a cone on the sky at latitude 43.7, longitude 129.4 with radius 0.5 degrees\ngets turned into the following SQL constraints \n\n   WHERE (   (htm7 = 245093) \n          OR (htm7 = 245098) \n          OR (htm7 = 245100)\n          OR (htm7 = 245105) \n          OR (htm7 = 245110)\n          OR (htm7 = 245118))\n\n     AND (-0.45888930755155893*x)+(0.55866098617988125*y)+(0.69088241107685844*z)\n         >=9.99975630705394747e-01\n\n\nFragments like this get inserted into the SQL statement as appropriate.\n\n\n\n\nBuilding the Python library:\n\nThe spatial index code need to be wrapped for Python use.  This is taken care\nof the Makefile but consists of using Cython to compile the spatial-index.pyx\ncode (Python with Cython directives) into \"spatial_index.c\", then building \na LINUX library from the this plus our C libraries (our C code plus tinyhtm).\nThis results in \"spatial_index.cpython-37m-x86_64-linux-gnu.so\". which has the\nright content to be loadable by the Python runtime and accessed by Python\ncalls.\n\nThe last step is to turn this into a Wheel file that can be pip-install in\nour Python distribution and/or uploaded to PyPI.  This file is\n(dist/spatial_index-0.9-cp37-cp37m-linux_x86_64.whl).  There is bookkeepping\nas well, but the primary files in this sequence are again\n\n  spatial_index.c\n  spatial_index.cpython-37m-x86_64-linux-gnu.so\n  dist/spatial_index-0.9-cp37-cp37m-linux_x86_64.whl\n\n\n",
    "bugtrack_url": null,
    "license": "LICENSE.txt",
    "summary": "Library for generating DBMS spatial index constraints.",
    "version": "1.0.2",
    "split_keywords": [
        "astronomy",
        "database",
        "spatial-index"
    ],
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "682d9d2eee62629c300d3f6563f17730",
                "sha256": "72a6515c7d4c1c426cde6b282dadc485736eec157469b1409fdf404198b77ecf"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp27-cp27m-macosx_10_6_x86_64.whl",
            "has_sig": false,
            "md5_digest": "682d9d2eee62629c300d3f6563f17730",
            "packagetype": "bdist_wheel",
            "python_version": "cp27",
            "requires_python": null,
            "size": 69534,
            "upload_time": "2020-06-30T14:59:44",
            "upload_time_iso_8601": "2020-06-30T14:59:44.425784Z",
            "url": "https://files.pythonhosted.org/packages/61/e2/e00b9acca07df5d35d9352540639f0533b63ae64a1c34f1af25e8c24ea2d/spatial_index-1.0.2-cp27-cp27m-macosx_10_6_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "3198a152086ac4c10ce1db3a105289e2",
                "sha256": "73660e72470992ad533a3e2cde034d504aa065981f0596db633b073c8d5414c4"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp27-cp27m-manylinux1_x86_64.whl",
            "has_sig": false,
            "md5_digest": "3198a152086ac4c10ce1db3a105289e2",
            "packagetype": "bdist_wheel",
            "python_version": "cp27",
            "requires_python": null,
            "size": 178078,
            "upload_time": "2020-06-30T14:59:52",
            "upload_time_iso_8601": "2020-06-30T14:59:52.786457Z",
            "url": "https://files.pythonhosted.org/packages/2d/32/d264d0f5117c157033a3c39482324718b1a1d9b40dd85bcb57c10053ba48/spatial_index-1.0.2-cp27-cp27m-manylinux1_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "9223fd949d434409c27362691bc290cb",
                "sha256": "7103897effd6c4c26511c901a7750457f948e45012408ccaf745cc3a1024c2bb"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp27-cp27m-manylinux2010_x86_64.whl",
            "has_sig": false,
            "md5_digest": "9223fd949d434409c27362691bc290cb",
            "packagetype": "bdist_wheel",
            "python_version": "cp27",
            "requires_python": null,
            "size": 178082,
            "upload_time": "2020-06-30T14:59:53",
            "upload_time_iso_8601": "2020-06-30T14:59:53.908790Z",
            "url": "https://files.pythonhosted.org/packages/4e/90/e28f040ff4401a313071717335fa7d512a68410145fa0c68525a14222565/spatial_index-1.0.2-cp27-cp27m-manylinux2010_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "b476a04d9f708f67202f057f90a90041",
                "sha256": "9f0a4cd43295c01910c0867f4d51bf1985cce87f42209babe4d0136e9de8e61f"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp36-cp36m-macosx_10_7_x86_64.whl",
            "has_sig": false,
            "md5_digest": "b476a04d9f708f67202f057f90a90041",
            "packagetype": "bdist_wheel",
            "python_version": "cp36",
            "requires_python": null,
            "size": 69665,
            "upload_time": "2020-06-30T14:59:48",
            "upload_time_iso_8601": "2020-06-30T14:59:48.824058Z",
            "url": "https://files.pythonhosted.org/packages/66/ea/aefe91a6cdf9d7094087ce4190c375d7dcbf12023f0fd7e02177337249ca/spatial_index-1.0.2-cp36-cp36m-macosx_10_7_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "dcf45f3861a9a8320b5c6ca7555bfb65",
                "sha256": "34fae3be054e363675db7b214f0e599f2a4900d308a97e8fb84fcb4831274b34"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp36-cp36m-manylinux1_x86_64.whl",
            "has_sig": false,
            "md5_digest": "dcf45f3861a9a8320b5c6ca7555bfb65",
            "packagetype": "bdist_wheel",
            "python_version": "cp36",
            "requires_python": null,
            "size": 185539,
            "upload_time": "2020-06-30T14:59:55",
            "upload_time_iso_8601": "2020-06-30T14:59:55.377683Z",
            "url": "https://files.pythonhosted.org/packages/ce/a7/e12399134cc1f912191e47a94308144ee77d5df49f9745910da941c05072/spatial_index-1.0.2-cp36-cp36m-manylinux1_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "bb1eef0ea82c7f84d6661ce90ff732f6",
                "sha256": "72dd12250032b33028c4a002d966b5f8d76b7eafb9ff5834278bda0a4eee19ea"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp36-cp36m-manylinux2010_x86_64.whl",
            "has_sig": false,
            "md5_digest": "bb1eef0ea82c7f84d6661ce90ff732f6",
            "packagetype": "bdist_wheel",
            "python_version": "cp36",
            "requires_python": null,
            "size": 185545,
            "upload_time": "2020-06-30T14:59:56",
            "upload_time_iso_8601": "2020-06-30T14:59:56.809529Z",
            "url": "https://files.pythonhosted.org/packages/0f/a6/1380009f28f205319f798a805f73602de2e4f1192269528c5687689b2676/spatial_index-1.0.2-cp36-cp36m-manylinux2010_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "009ad4c0b542910df4922a945f61cdc2",
                "sha256": "c4266cf336fd2140e33d179323200f4b4699b1808c56d62376f146b149138cbf"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp37-cp37m-macosx_10_7_x86_64.whl",
            "has_sig": false,
            "md5_digest": "009ad4c0b542910df4922a945f61cdc2",
            "packagetype": "bdist_wheel",
            "python_version": "cp37",
            "requires_python": null,
            "size": 71021,
            "upload_time": "2020-06-30T14:59:50",
            "upload_time_iso_8601": "2020-06-30T14:59:50.202775Z",
            "url": "https://files.pythonhosted.org/packages/fc/dc/b4746cf47b6a6cc284528a953d5deb77db14145f9c47c372ec3429c17620/spatial_index-1.0.2-cp37-cp37m-macosx_10_7_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "640e3b985071658e0a7410ce80132956",
                "sha256": "67ae6fb18c2e8b73e9b74c7e1408f31c241db8b7087f1ee97f06397db24bc8ce"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp37-cp37m-manylinux1_x86_64.whl",
            "has_sig": false,
            "md5_digest": "640e3b985071658e0a7410ce80132956",
            "packagetype": "bdist_wheel",
            "python_version": "cp37",
            "requires_python": null,
            "size": 187540,
            "upload_time": "2020-06-30T14:59:58",
            "upload_time_iso_8601": "2020-06-30T14:59:58.011903Z",
            "url": "https://files.pythonhosted.org/packages/bc/97/b54b6a8a1d121d09382695adf70c81d310abd2799d714bcc0750fc9c0e0d/spatial_index-1.0.2-cp37-cp37m-manylinux1_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "03e8e675c0d195f41dc9f1cbac03a7bd",
                "sha256": "aed9f92873a47fa7f70cb754623968be268038da25ef71f00c21ac239f036f39"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp37-cp37m-manylinux2010_x86_64.whl",
            "has_sig": false,
            "md5_digest": "03e8e675c0d195f41dc9f1cbac03a7bd",
            "packagetype": "bdist_wheel",
            "python_version": "cp37",
            "requires_python": null,
            "size": 187542,
            "upload_time": "2020-06-30T14:59:59",
            "upload_time_iso_8601": "2020-06-30T14:59:59.570826Z",
            "url": "https://files.pythonhosted.org/packages/81/d1/5315670bdd2c212d1381a663c486bfb7ee80bdbe6d1803a8da618920eca8/spatial_index-1.0.2-cp37-cp37m-manylinux2010_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "47cf852abea4153c3355bf282b985224",
                "sha256": "ba57560604ca7a9ffc758625bb7ddae448a8479fa8b66ce3df2e145f52aefc0a"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp38-cp38-macosx_10_9_x86_64.whl",
            "has_sig": false,
            "md5_digest": "47cf852abea4153c3355bf282b985224",
            "packagetype": "bdist_wheel",
            "python_version": "cp38",
            "requires_python": null,
            "size": 71503,
            "upload_time": "2020-06-30T14:59:51",
            "upload_time_iso_8601": "2020-06-30T14:59:51.275841Z",
            "url": "https://files.pythonhosted.org/packages/d7/55/1a93a815b322e4cd04d93e097aba13020fa75454115962aac6c562eef9be/spatial_index-1.0.2-cp38-cp38-macosx_10_9_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "f4425e9a3f54bf938b828a7232877b78",
                "sha256": "68477a2bab9dc74b5fb762227fc4c0acc5ea00b30d0b7931ea933b87ca2e5d0d"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp38-cp38-manylinux1_x86_64.whl",
            "has_sig": false,
            "md5_digest": "f4425e9a3f54bf938b828a7232877b78",
            "packagetype": "bdist_wheel",
            "python_version": "cp38",
            "requires_python": null,
            "size": 213459,
            "upload_time": "2020-06-30T15:00:01",
            "upload_time_iso_8601": "2020-06-30T15:00:01.228038Z",
            "url": "https://files.pythonhosted.org/packages/64/2a/708ba59d29a8df41493e3ae2109f68e344e130a489edd58e2d8dafc5229f/spatial_index-1.0.2-cp38-cp38-manylinux1_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "309cbf0de13aa119b444271d32033833",
                "sha256": "94bc58593eecab64cdfc66f6d8e6a60eef46bf0d7442041f9d022072db0c820a"
            },
            "downloads": -1,
            "filename": "spatial_index-1.0.2-cp38-cp38-manylinux2010_x86_64.whl",
            "has_sig": false,
            "md5_digest": "309cbf0de13aa119b444271d32033833",
            "packagetype": "bdist_wheel",
            "python_version": "cp38",
            "requires_python": null,
            "size": 213462,
            "upload_time": "2020-06-30T15:00:02",
            "upload_time_iso_8601": "2020-06-30T15:00:02.942655Z",
            "url": "https://files.pythonhosted.org/packages/53/1b/00cf1314200f0392e991d336731dc764064d3896c35e91be7633be718e4d/spatial_index-1.0.2-cp38-cp38-manylinux2010_x86_64.whl",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2020-06-30 14:59:44",
    "github": true,
    "gitlab": false,
    "bitbucket": false,
    "github_user": null,
    "github_project": "Caltech-IPAC",
    "error": "Could not fetch GitHub repository",
    "lcname": "spatial-index"
}
        
Elapsed time: 0.11362s