Efficient Geo-Fencing via Hybrid Hashing
ACM Transactions on Spatial Algorithms and Systems · 2015
DOI: 10.1145/2774219 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Spatial Algorithms and Systems, 2015. Verfasst von Suhua Tang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 36 Literaturangaben. Gefördert von: Singapore National Research Foundation under its International Research Centre @ Singapore Funding Initiative, IDM Programme Office through the Centre of Social Media Innovations for Communities.
Abstract (Originalsprache)
Geo-fencing, as a spatial join between points (moving objects) and polygons (spatial range), is widely used in emerging location-based services to trigger context-aware events. It faces the challenge of real-time processing a large number of time-variant complex polygons, when points are constantly moving. Following the filter-and-refine policy, in our previous work, we proposed to organize edges per polygon in hash tables to improve the performance of the refining stage. The number of edges, however, is uneven among buckets. As a result, some points that happen to match big buckets with many edges will have much longer responses than usual. In this article, we solve this problem from two aspects: (i) Constructing multiple parallel hash tables and dynamically selecting the bucket with fewest edges and (ii) sorting edges in a bucket so as to realize the crossing number algorithm by binary search. We further combine the two to suggest a hybrid hashing scheme that takes a better tradeoff between real-time pairing points with polygons and system overhead of building hash tables. Extensive analyses and evaluations on two real-world datasets confirm that the proposed scheme can effectively reduce the pairing time in terms of both the average and distribution.
Förderung
- Singapore National Research Foundation under its International Research Centre @ Singapore Funding Initiative
- IDM Programme Office through the Centre of Social Media Innovations for Communities
Zitieren
APA
Tang, S., Yu, Y., Zimmermann, R., & Obana, S. (2015). Efficient Geo-Fencing via Hybrid Hashing. ACM Transactions on Spatial Algorithms and Systems. https://doi.org/10.1145/2774219
Vancouver
Tang S, Yu Y, Zimmermann R, Obana S. Efficient Geo-Fencing via Hybrid Hashing. ACM Transactions on Spatial Algorithms and Systems. 2015. doi:10.1145/2774219
BibTeX
@article{Tang2015,
author = {Tang, Suhua and Yu, Yi and Zimmermann, Roger and Obana, Sadao},
title = {Efficient Geo-Fencing via Hybrid Hashing},
journal = {ACM Transactions on Spatial Algorithms and Systems},
year = {2015},
doi = {10.1145/2774219}
}
EUVIMED