Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh

Dániel Kondor; László Dobos; István Csabai; András Bodor; Gábor Vattay; Tamás Budavári; Alexander S. Szalay

doi:10.1145/2618243.2618245

Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh

Dániel Kondor, László Dobos, István Csabai, András Bodor, Gábor Vattay, Tamás Budavári, Alexander S. Szalay

Krieger School of Arts and Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 TriangularMesh (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 falsepositive 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.

Original language	English (US)
Title of host publication	SSDBM 2014 - Proceedings of the 26th International Conference on Scientific and Statistical Database Management
Publisher	Association for Computing Machinery
ISBN (Print)	9781450327220
DOIs	https://doi.org/10.1145/2618243.2618245
State	Published - 2014
Event	26th International Conference on Scientific and Statistical Database Management, SSDBM 2014 - Aalborg, Denmark Duration: Jun 30 2014 → Jul 2 2014

Publication series

Name	ACM International Conference Proceeding Series

Conference

Conference	26th International Conference on Scientific and Statistical Database Management, SSDBM 2014
Country/Territory	Denmark
City	Aalborg
Period	6/30/14 → 7/2/14

ASJC Scopus subject areas

Software
Human-Computer Interaction
Computer Vision and Pattern Recognition
Computer Networks and Communications

Access to Document

10.1145/2618243.2618245

Cite this

Kondor, D., Dobos, L., Csabai, I., Bodor, A., Vattay, G., Budavári, T., & Szalay, A. S. (2014). Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh. In SSDBM 2014 - Proceedings of the 26th International Conference on Scientific and Statistical Database Management Article 4 (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/2618243.2618245

Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh. / Kondor, Dániel; Dobos, László; Csabai, István et al.
SSDBM 2014 - Proceedings of the 26th International Conference on Scientific and Statistical Database Management. Association for Computing Machinery, 2014. 4 (ACM International Conference Proceeding Series).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kondor, D, Dobos, L, Csabai, I, Bodor, A, Vattay, G, Budavári, T & Szalay, AS 2014, Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh. in SSDBM 2014 - Proceedings of the 26th International Conference on Scientific and Statistical Database Management., 4, ACM International Conference Proceeding Series, Association for Computing Machinery, 26th International Conference on Scientific and Statistical Database Management, SSDBM 2014, Aalborg, Denmark, 6/30/14. https://doi.org/10.1145/2618243.2618245

Kondor D, Dobos L, Csabai I, Bodor A, Vattay G, Budavári T et al. Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh. In SSDBM 2014 - Proceedings of the 26th International Conference on Scientific and Statistical Database Management. Association for Computing Machinery. 2014. 4. (ACM International Conference Proceeding Series). doi: 10.1145/2618243.2618245

Kondor, Dániel ; Dobos, László ; Csabai, István et al. / Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh. SSDBM 2014 - Proceedings of the 26th International Conference on Scientific and Statistical Database Management. Association for Computing Machinery, 2014. (ACM International Conference Proceeding Series).

@inproceedings{8e492b2d942841a2b597e2f554d43525,

title = "Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh",

abstract = "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 TriangularMesh (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 falsepositive 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.",

author = "D{\'a}niel Kondor and L{\'a}szl{\'o} Dobos and Istv{\'a}n Csabai and Andr{\'a}s Bodor and G{\'a}bor Vattay and Tam{\'a}s Budav{\'a}ri and Szalay, {Alexander S.}",

year = "2014",

doi = "10.1145/2618243.2618245",

language = "English (US)",

isbn = "9781450327220",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery",

booktitle = "SSDBM 2014 - Proceedings of the 26th International Conference on Scientific and Statistical Database Management",

note = "26th International Conference on Scientific and Statistical Database Management, SSDBM 2014 ; Conference date: 30-06-2014 Through 02-07-2014",

}

TY - GEN

T1 - Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh

AU - Kondor, Dániel

AU - Dobos, László

AU - Csabai, István

AU - Bodor, András

AU - Vattay, Gábor

AU - Budavári, Tamás

AU - Szalay, Alexander S.

PY - 2014

Y1 - 2014

N2 - 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 TriangularMesh (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 falsepositive 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.

AB - 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 TriangularMesh (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 falsepositive 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.

UR - http://www.scopus.com/inward/record.url?scp=84904438106&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904438106&partnerID=8YFLogxK

U2 - 10.1145/2618243.2618245

DO - 10.1145/2618243.2618245

M3 - Conference contribution

AN - SCOPUS:84904438106

SN - 9781450327220

T3 - ACM International Conference Proceeding Series

BT - SSDBM 2014 - Proceedings of the 26th International Conference on Scientific and Statistical Database Management

PB - Association for Computing Machinery

T2 - 26th International Conference on Scientific and Statistical Database Management, SSDBM 2014

Y2 - 30 June 2014 through 2 July 2014

ER -

Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this