EUVIMEDEUVIMED entdecken
Crossref

Efficient Geo-Fencing via Hybrid Hashing

Suhua Tang, Yi Yu, Roger Zimmermann, Sadao Obana

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →