Multi-Resolution Data Structures for Spherically Mapped Point Data

摘要

Data describing entities or objects whose locations may be treated as points on the surface of a sphere are said to be spherically mapped. A number of data structures specifically designed to store and access spherically mapped data have been developed. One of them, Hierarchical Equal Area iso-Latitude Pixelization (HEALPix), has been successfully used for numerous applications, notably including organizing and analyzing cosmic microwave background data. However, for applications involving relatively sparse spherically mapped point datasets, HEALPix has some drawbacks, including inefficient memory requirements due to fixed resolution, overwriting of data for closely proximate points, and return of spurious points in response to certain queries.;A multi-resolution variant of the HEALPix data structure optimized for point data was developed to address these issues. The new data structure is multi-resolution in that different portions of the sphere may be subdivided at different levels of resolution in the same data structure, depending on the data to be stored. It combines the best aspects of HEALPix with the advantages of multi-resolution, including reduced memory requirements, improved query efficiency, and flexible handling of proximate points. The new Multi-resolution HEALPix (MRH) data structure uses multiple quadtrees and the Morton cell addressing scheme.;An implementation of the MRH data structure was tested using four sets of spherically mapped point data from different scientific applications (warhead fragmentation trajectories, weather station locations, redshifted galaxy locations, and synthetic locations). A large set of randomly generated range queries of four different types (disc, polygon, latitude strip, and neighbor) was applied to each data structure for each dataset. MRH used from two to four orders of magnitude less memory than HEALPix to store the same data, and on average MRH queries executed 72% faster.;Additional effort to develop a three dimensional variant of MRH was explored. The new data structure, Multi-MRH, adds an additional degree of freedom (temporal or spatial) into an entirely new data and applications. In Multi-MRH, multiple instances of MRH are utilized to store either temporal, same data point locations at different times, or spatial, data points with spherical coordinates including radius, spherical data.;The Multi-MRH data structure consists of a sorted list of MRH maps. An implementation of the Multi-MRH data structure was tested using three sets of spherically mapped point data from different scientific applications (synthetic locations, warhead fragmentation trajectories, and NEXRAD wind velocity data). A large set of randomly generated range queries of four different types (cone, prism, band, and ray) was applied to each data structure for each data set. The average Multi-MRH query execution time was less than 7% greater than the average MRH query execution time.