research-article

Learning locality maps from noisy geospatial labels

Authors:

Manjeet Dahiya,

Devendra Samatia,

Kabir RustogiAuthors Info & Claims

SAC '20: Proceedings of the 35th Annual ACM Symposium on Applied Computing

Pages 601 - 608

https://doi.org/10.1145/3341105.3373933

Published: 30 March 2020 Publication History

Abstract

E-commerce and logistics operations produce a vast amount of geospatial data labelled with postal addresses. The data has great potential to mine geospatial knowledge, and we demonstrate that regional maps can be automatically built using the same. We propose an algorithm to construct non-overlapping polygons of the localities at a city level. The algorithm involves non-parametric spatial probability modelling of the localities followed by locality classification of the cells in a hexagonal grid. We show that our algorithm is capable of handling noise, which is significantly high in our setting due to the small scale of localities. A property about the noise and the correct information is presented such that our algorithm infers a correct locality polygon. We quantitatively measure the accuracy of our system by comparing its output with the available ground truth. We also discuss multiple applications of the generated maps in the context of e-commerce and logistics operations.

References

[1]

Colin P.D. Birch, Sander P. Oom, and Jonathan A. Beecham. 2007. Rectangular and hexagonal grids used for observation, experiment and simulation in ecology. Ecological Modelling 206, 3 (2007), 347 -- 359.

[2]

Christopher M. Bishop. 2006. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag, Berlin, Heidelberg.

Digital Library

[3]

David J. Crandall, Lars Backstrom, Daniel Huttenlocher, and Jon Kleinberg. 2009. Mapping the World's Photos. In Proceedings of the 18th International Conference on World Wide Web (WWW '09). ACM, New York, NY, USA, 761--770.

Digital Library

[4]

Ilke Demir and Ramesh Raskar. 2018. Addressing the Invisible: Street Address Generation for Developing Countries with Deep Learning. CoRR abs/1811.07769 (2018). arXiv:1811.07769 http://arxiv.org/abs/1811.07769

[5]

V. A. Epanechnikov. 1969. Non-Parametric Estimation of a Multivariate Probability Density. Theory of Probability & Its Applications 14, 1 (1969), 153--158.

[6]

Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. A Density-based Algorithm for Discovering Clusters a Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD'96). AAAI Press, 226--231. http://dl.acm.org/citation.cfm?id=3001460.3001507

Digital Library

[7]

Antony Galton and Matt Duckham. 2006. What Is the Region Occupied by a Set of Points?. In Geographic Information Science, Martin Raubal, Harvey J. Miller, Andrew U. Frank, and Michael F. Goodchild (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 81--98.

[8]

Mordechai (Muki) Haklay and Patrick Weber. 2008. OpenStreetMap: User-Generated Street Maps. IEEE Pervasive Computing 7, 4 (Oct. 2008), 12--18.

Digital Library

[9]

Suradej Intagorn and Kristina Lerman. 2011. Learning Boundaries of Vague Places from Noisy Annotations. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '11). ACM, New York, NY, USA, 425--428.

Digital Library

[10]

Suradej Intagorn and Kristina Lerman. 2012. A Probabilistic Approach to Mining Geospatial Knowledge from Social Annotations. SIGSPATIAL Special 4, 3 (Nov. 2012), 2--7.

Digital Library

[11]

Suradej Intagorn and Kristina Lerman. 2012. A Probabilistic Approach to Mining Geospatial Knowledge from Social Annotations. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management (CIKM '12). ACM, New York, NY, USA, 1717--1721.

Digital Library

[12]

Ray A Jarvis. 1973. On the identification of the convex hull of a finite set of points in the plane. Information processing letters 2, 1 (1973), 18--21.

[13]

C. B. Jones, R. S. Purves, P. D. Clough, and H. Joho. 2008. Modelling vague places with knowledge from the Web. International Journal of Geographical Information Science 22, 10 (2008), 1045--1065.

Digital Library

[14]

Adriano Moreira and Maribel Yasmina Santos. 2007. Concave hull: a k-nearest neighbours approach for the computation of the region occupied by a set of points. In Proceedings of the Second International Conference on Computer Graphics Theory and Applications - Volume 1: GRAPP,. INSTICC, SciTePress, 61--68.

[15]

David O'sullivan and David Unwin. 2014. Geographic information analysis. John Wiley & Sons.

[16]

Jin-Seo Park and Se-Jong Oh. 2012. A new concave hull algorithm and concaveness measure for n-dimensional datasets. Journal of Information science and engineering 28, 3 (2012), 587--600.

[17]

Tye Rattenbury, Nathaniel Good, and Mor Naaman. 2007. Towards Automatic Extraction of Event and Place Semantics from Flickr Tags. In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '07). ACM, New York, NY, USA, 103--110.

Digital Library

[18]

Mark Sanderson and Bruce Croft. 1999. Deriving Concept Hierarchies from Text. In Proceedings of the 22Nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '99). ACM, New York, NY, USA, 206--213.

Digital Library

[19]

Patrick Schmitz. 2006. Inducing ontology from flickr tags. In Collaborative Web Tagging Workshop at WWW2006, Edinburgh, Scotland, Vol. 50. 39.

[20]

David W Scott. 2015. Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons.

[21]

Wesley E Snyder, Hairong Qi, and William A Sander. 1999. Coordinate system for hexagonal pixels. In Medical Imaging 1999: Image Processing, Vol. 3661. International Society for Optics and Photonics, 716--727.

Cited By

Ruan SLong CMa ZBao JHe TLi RChen YWu SZheng YZhang ARangwala H(2022)Service Time Prediction for Delivery Tasks via Spatial Meta-LearningProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539027(3829-3837)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539027
Tallamraju RAl Hasan MXiong L(2022)Geographical Address Models in the Indian e-CommerceProceedings of the 31st ACM International Conference on Information & Knowledge Management10.1145/3511808.3557515(5096-5097)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3511808.3557515
Ruan SLong CYang XHe TLi RBao JChen YWu SCui JZheng Y(2022)Discovering Actual Delivery Locations from Mis-Annotated Couriers' Trajectories2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00307(3241-3253)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00307

Index Terms

Learning locality maps from noisy geospatial labels
1. Computing methodologies
  1. Machine learning
2. Information systems
  1. Information systems applications
    1. Data mining
    2. Spatial-temporal systems
      1. Geographic information systems

Recommendations

A dissimilarity function for clustering geospatial polygons
GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

The traditional point-based clustering algorithms when applied to geospatial polygons may produce clusters that are spatially disjoint due to their inability to consider various types of spatial relationships between polygons. In this paper, we propose ...
A dissimilarity function for geospatial polygons

Similarity plays an important role in many data mining tasks and information retrieval processes. Most of the supervised, semi-supervised, and unsupervised learning algorithms depend on using a dissimilarity function that measures the pair-wise ...
Exploiting spatial locality in data caches using spatial footprints
Special Issue: Proceedings of the 25th annual international symposium on Computer architecture (ISCA '98)

Modern cache designs exploit spatial locality by fetching large blocks of data called cache lines on a cache miss. Subsequent references to words within the same cache line result in cache hits. Although this approach benefits from spatial locality, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '20: Proceedings of the 35th Annual ACM Symposium on Applied Computing

March 2020

2348 pages

ISBN:9781450368667

DOI:10.1145/3341105

Conference Chairs:
Chih-Cheng Hung
Kennesaw State University
,
Tomas Cerny
Baylor University
,
Program Chairs:
Dongwan Shin
New Mexico Tech
,
Alessio Bechini
University of Pisa, Italy

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 March 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC '20

Sponsor:

SIGAPP

SAC '20: The 35th ACM/SIGAPP Symposium on Applied Computing

March 30 - April 3, 2020

Brno, Czech Republic

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
117
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ruan SLong CMa ZBao JHe TLi RChen YWu SZheng YZhang ARangwala H(2022)Service Time Prediction for Delivery Tasks via Spatial Meta-LearningProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539027(3829-3837)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539027
Tallamraju RAl Hasan MXiong L(2022)Geographical Address Models in the Indian e-CommerceProceedings of the 31st ACM International Conference on Information & Knowledge Management10.1145/3511808.3557515(5096-5097)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3511808.3557515
Ruan SLong CYang XHe TLi RBao JChen YWu SCui JZheng Y(2022)Discovering Actual Delivery Locations from Mis-Annotated Couriers' Trajectories2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00307(3241-3253)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00307

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents