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.

Google ScholarTM



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