Please use this identifier to cite or link to this item:
Title: Edge-based locality sensitive hashing for efficient geo-fencing application
Authors: Yu, Y.
Tang, S.
Zimmermann, R. 
Keywords: geo-fencing
geographic information systems
locality sensitive hashing
Issue Date: 2013
Citation: Yu, Y.,Tang, S.,Zimmermann, R. (2013). Edge-based locality sensitive hashing for efficient geo-fencing application. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems : 566-569. ScholarBank@NUS Repository.
Abstract: Geo-fencing is a promising technique for emerging location-based services. Its two basic spatial predicates, INSIDE and WITHIN pairings between points and polygons, can be addressed by state-of-the-art methods such as the crossing number algorithm. In the era of big-data, however, geo-fencing has to process millions of points and hundreds of polygons or even more in real-time. In this paper, we propose an efficient algorithm to improve the scalability of geo-fencing, which consists of two main stages. At the first stage, an R-tree is used to quickly detect whether a point is inside the minimum bounding rectangle of a polygon. In the second stage, instead of an exhaustive search, we design an edge-based locality sensitive hashing scheme adapted to the crossing number algorithm. As for the case of WITHIN detection, a probing scheme is suggested to locate adjacent buckets so as to check all edges near to a target point. By further exploiting batch processing and multi-threading programming, our algorithm can achieve a fast speed while retaining 100% accuracy over all training datasets provided by the GIS Cup 2013 organizers. © 2013 Authors.
Source Title: GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
ISBN: 9781450325219
DOI: 10.1145/2525314.2527264
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 10, 2018

Page view(s)

checked on Nov 23, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.