Department of Physics of Complex Systems, Eötvös Loránd University,
Pf. 32, H-1518 Budapest, Hungary
Department of Physics & Astronomy, The Johns Hopkins University, Baltimore, MD 21218, USA
We present a case study about the spatial indexing and regional classification of billions of geographic coordinates from geo-tagged social network data using Hierarchical Triangular Mesh (HTM) implemented for Microsoft SQL Server. Due to the lack of certain features of the HTM library, we use it in conjunction with the GIS functions of SQL Server to significantly increase the efficiency of pre-filtering of spatial filter and join queries. For example, we implemented a new algorithm to compute the HTM tessellation of complex geographic regions and precomputed the intersections of HTM triangles and geographic regions for faster false-positive filtering. With full control over the index structure, HTM-based pre-filtering of simple containment searches outperforms SQL Server spatial indices by a factor of ten and HTM-based spatial joins run about a hundred times faster.
Paper acceptod to SSDBM 2014.
Source code and scripts
Slides for the conference presentation
E-mail: dobos at complex dot elte dot hu