Thursday, July 9, 2020

Semantically Diverse Path Search

The Best Paper Award Runner-Up at IEEE MDM 2020 were awarded to the authors of "Semantically Diverse Path Search"! 




Location-Based Services are often used to find proximal Points of Interest (PoI) – e.g., nearby restaurants and museums, police stations, hospitals, etc. – in a plethora of applications. An important recently addressed variant of the problem not only considers the distance/proximity aspect, but also desires semantically diverse locations in the answer-set. For instance, rather than picking several close-by attractions with similar features – e.g., restaurants with similar menus; museums with similar art exhibitions – a tourist may be more interested in a result set that could potentially provide more diverse types of experiences, for as long as they are within an acceptable distance from a given (current) location. Towards that goal, in this work we propose a novel approach to efficiently retrieve a path that will maximize the semantic diversity of the visited PoIs that are within distance limits along a given road network. We introduce a novel indexing structure – the Diversity Aggregated R-tree, based on which we devise efficient algorithms to generate the answer-set – i.e., the recommended locations among a set of given PoIs – relying on a greedy search strategy. Our experimental evaluations conducted on real datasets demonstrate the benefits of proposed methodology over the baseline alternative approaches.

The nice presentation was given by Xu Teng, Iowa State University, at the IEEE MDM 2020.



X. Teng, G. Trajcevski, J.-S. Kim, and A. Züfle, “Semantically Diverse Path Search,” In Proceedings of IEEE International Conference on Mobile Data Management (MDM 2020), July 2020, pp. 69-78

Managing Uncertainty in Evolving Geo-Spatial Data


Andreas Züfle, Goce Trajcevski, Dieter Pfoser, Joon-Seok Kim

Our ability to extract knowledge from evolving spatial phenomena and make it actionable is often impaired by unreliable, erroneous, obsolete, imprecise, sparse, and noisy data. Integrating the impact of this uncertainty is a paramount when estimating the reliability/confidence of any time-varying query result from the underlying input data. The goal of this advanced seminar is to survey solutions for managing, querying and mining uncertain spatial and spatio-temporal data. We survey different models and show examples of how to efficiently enrich query results with reliability information. We discuss both analytical solutions as well as approximate solutions based on geosimulation.

The Advanced Seminar of IEEE MDM 2020 was featured with four parts as follows:

  • Part I: Introduction and Motivation
  • Part II: Uncertainty in Spatial Data
    1. Uncertainty Models and Possible World Semantics
    2. Representative Query Processing using Monte-Carlo Sampling
  • Part III: Uncertainty in Evolving Spatial Data
    1. Sources, Models and Contexts
    2. Non-point Evolving Entities
  • Part IV: Geospatial Simulation 


Among them, I share the video of "Part IV: Geospatial Simulation" that I presented at the conference.




The whole video for the advanced seminar can be found here.

A. Züfle, G. Trajcevski, D. Pfoser, and J.-S. Kim, “Managing Uncertainty in Evolving Geo-Spatial Data,” In Proceedings of IEEE International Conference on Mobile Data Management (MDM 2020), July 2020, pp. 5-8

Friday, July 3, 2020

Location-Based Social Network Data Generation Based on Patterns of Life

Joon-Seok Kim, Hyunjee Jin, Hamdi Kavak, Ovi Chris Rouly, Andrew Crooks, Dieter Pfoser, Carola Wenk, Andreas Züfle

Abstract

Location-based social networks (LBSNs) have been studied extensively in recent years. However, utilizing real-world LBSN data sets yields several weaknesses: sparse and small data sets, privacy concerns, and a lack of authoritative ground-truth. To overcome these weaknesses, we leverage a large-scale LBSN simulation to create a framework to simulate human behavior and to create synthetic but realistic LBSN data based on human patterns of life. Such data not only captures the location of users over time but also their interactions via social networks. Patterns of life are simulated by giving agents (i.e., people) an array of "needs" that they aim to satisfy, e.g., agents go home when they are tired, to restaurants when they are hungry, to work to cover their financial needs, and to recreational sites to meet friends and satisfy their social needs. While existing real-world LBSN data sets are trivially small, the proposed framework provides a source for massive LBSN benchmark data that closely mimics the real-world. As such, it allows us to capture 100% of the (simulated) population without any data uncertainty, privacy-related concerns, or incompleteness. It allows researchers to see the (simulated) world through the lens of an omniscient entity having perfect data. Our framework is made available to the community. In addition, we provide a series of simulated benchmark LBSN data sets using different synthetic towns and real-world urban environments obtained from OpenStreetMap. The simulation software and data sets, which comprise gigabytes of spatio-temporal and temporal social network data, are made available to the research community.

Please check out the video that I presented in the 21st IEEE International Conference on Mobile Data Management (MDM 2020)!




Source code: https://github.com/gmuggs/pol
LSBN Data: https://osf.io/e24th/
Additional materials: https://mdm2020.joonseok.org


J.-S. Kim, H. Jin, H. Kavak, O. Rouly, A. Crooks, D. Pfoser, C. Wenk, and A. Züfle, “Location-Based Social Network Data Generation Based on Patterns of Life,” In Proceedings of IEEE International Conference on Mobile Data Management (MDM 2020), July 2020, pp. 158-167

Thursday, July 2, 2020

Call for Paper GeoSim 2020




The GeoSim 2020 workshop focuses on all aspects of simulation as a general paradigm to model and predict spatial systems and generate spatial data. New simulation methodologies and frameworks, not necessarily coming from the SIGSPATIAL community, are encouraged to participate. Also, this workshop is of interest to everyone who works with spatial data. The simulation methods that will be presented and discussed in the workshop should find a wide application across the community by producing benchmark datasets that can be parameterized and scaled. Simulated data sets will be made available to the community via the website.

The workshop seeks high-quality full (8-10 pages) and short (up to 4 pages) papers that will be peer-reviewed. Once accepted, at least one author is required to register for the workshop and the ACM SIGSPATIAL conference, as well as attend the workshop to present the accepted work which will then appear in the ACM Digital Library.


  • We solicit novel and previously unpublished research on all topics related to geospatial simulation including, but not limited to:
  • Disease Spread Simulation
  • Urban Simulation
  • Agent Based Models for Spatial Simulation
  • Multi-Agent Based Spatial Simulation
  • Big Spatial Data Simulation
  • Spatial Data/Trajectory Generators
  • Road Traffic Simulation
  • Environmental Simulation
  • GIS using Spatial Simulation
  • Modeling and Simulation of COVID-19
  • Interactive Spatial Simulation
  • Spatial Simulation Parallelization and Distribution
  • Geo-Social Simulation and Data Generators
  • Social Unrest and Riot Prediction using Simulation
  • Spatial Analysis based on Simulation
  • Behavioral Simulation
  • Verifying, and Validating Spatial Simulations
  • Applications for Spatial Simulation


Special Topic:

The special topic for GeoSim 2020 brings focus to current trends in disease spread simulations, their practicality in predictive and prescriptive analytics, and the challenges they face in their use.

Paper Format:

Manuscripts should be submitted in PDF format and formatted using the ACM camera-ready templates available at http://www.acm.org/publications/proceedings-template.

Submission Site:

https://easychair.org/my/conference?conf=geosim2020


For more information, please visit our workshop website: at https://www.geosim.org/


Saturday, November 9, 2019

Won the First Place at ACM SIGSPATIAL Cup 2019!


The authors of "Distance-Aware Competitive Spatiotemporal Searching Using Spatiotemporal Resource Matrix Factorization" won the first place ($500) at ACM SIGSPATIAL Cup 2019

Dr. Bo Xu, a contest co-chair and a Principal Research Engineer at HERE Technologies, introduced this year challenge in the Contest Session. ACM SIGSPATIAL Cup 2019 was about optimization of agents’ maneuvers based on the ride-hailing simulation provided by the contest organizers. The main challenge was how smartly the agents (or drivers) seeking customers relocate their cars without any communication with other agents while globally minimizing search time of all agents and wait time of all customers. The results of the top three teams (George Mason University, Ludwig-Maximilians-Universität, Eindhoven University of Technology) were very close to each other. I believe tuning parameters to higher the chance to win was the secret. The certificate was awarded at the banquet on November 7, 2019.



From left to right: Prof. Andreas Züfle, Dr. Joon-Seok Kim, Prof. Goce Trajcevski (ACM SIGSPATIAL Vice-Chair), Prof. Cyrus Shahabi (ACM SIGSPATIAL Chair)



For more information, please visit my project web site: http://giscup19.joonseok.org

Sunday, October 20, 2019

Special Issue "Geo-Enriched Data Modeling & Mining", IJGI

A Special Issue "Geo-Enriched Data Modeling & Mining" of  ISPRS International Journal of Geo-Information (ISSN 2220-9964)


Deadline for manuscript submissions: 31 August 2020.

Special Issue Information

Dear Colleagues,

Both of the current trends in technology such as smartphones, general mobile devices, stationary sensors and satellites as well as a new user mentality of utilizing this technology to voluntarily share information produce a huge flood of geospatial data. This data is enriched by multiple additional sources or contexts such as social information, text, multimedia data, and scientific measurements, called geo-enriched data. This data flood provides a tremendous potential of discovering new and possibly useful knowledge. The novel research challenge is to model, share, search, and mine this wealth of geo-enriched data. The focus of this Special Issue is to analyze what has been achieved so far and how to further exploit the enormous potential of this data flood. The ultimate goal of this Special Issue is to develop a general framework of methods for modeling, searching and mining enriched geospatial data in order to fuel an advanced analysis of big data applications beyond the current research frontiers. Furthermore, this Special Issue intends to compile an interdisciplinary research collection in the fields of databases, data science, and geoinformation science.

This Special Issue is dedicated to giving an overview of state-of-the-art solutions, techniques and applications on modeling, managing, searching and mining geo‐enriched data, such spatio-textual, spatio-temporal, spatio-social, geo-social network, mobile and wireless data.

We call for original papers from researchers around the world that focus on topics including, but not limited to, the following:

Dr. Andreas Züfle
Dr. Joon-Seok Kim
Guest Editors

Keywords


  • Big Spatial Data
  • Crowdsourcing Computing Resources
  • Data Extraction Techniques including NLP
  • Data Mining on Geo-Enriched data
  • Geo-Multimedia DataM Geo-Social Data
  • Geo-Textual Data
  • Indexing Geo-Enriched data
  • Location-Based Social Networks
  • Spatial Data Models and Representation
  • Spatial Privacy and Confidentiality
  • Spatial Reasoning and Analysis
  • Spatial Recommendation Systems
  • Temporal Geo-Enriched Data
  • Uncertainty in Spatial and Spatio-Temporal Data
  • Visualization of Geo-Enriched Data


Special Issue Editors


  • Dr. Andreas Züfle (Guest Editor)
  • Dr. Joon-Seok Kim (Co-Guest Editor)



Tuesday, October 8, 2019

Distance-Aware Competitive Spatiotemporal Searching Using Spatiotemporal Resource Matrix Factorization

GIS Cup is an annual contest of SIGSPATIAL. ACM SIGSPATIAL Cup 2019 was about optimization of agents’ maneuvers based on the ride-hailing simulation provided by the contest organizers. The main challenge was how smartly the agents (or drivers) seeking customers relocate their cars without any communication with other agents while globally minimizing search time of all agents and wait time of all customers. My approach is to learn a spatiotemporal resource model using non-negative matrix factorization. Then, our SmartAgents strive to avoid both oversupply and undersupply, considering balance of greed for travel-distance and resource distribution.


Our paper was accepted as one of four finalists who achieved the best results. The final result of the contest will be revealed at ACM SIGSPATIAL'19, November 7, 2019. For more information, please visit my project web site http://giscup19.joonseok.org

Abstract

Congested traffic wastes billions of liters of fuel and is a significant contributor to Green House Gas (GHG) emissions. Although convenient, ride sharing services such as Uber and Lyft are becoming a significant contributor to these emissions not only because of added traffic but by spending time on the road while waiting for passengers. To help improve the impact of ride sharing, we propose an algorithm to optimize the efficiency of drivers searching for customers. In our model, the main goal is to direct drivers represented as idle agents, i.e., not currently assigned a customer or resource, to locations where we predict new resources to appear. Our approach uses non-negative matrix factorization (NMF) to model and predict the spatio-temporal distributions of resources. To choose destinations for idle agents, we employ a greedy heuristic that strikes a balance between distance greed, i.e., to avoid long trips without resources and resource greed, i.e., to move to a location where resources are expected to appear following the NMF model. To ensure that agents do not oversupply areas for which resources are predicted and under supply other areas, we randomize the destinations of agents using the predicted resource distribution within the local neighborhood of an agent. Our experimental evaluation shows that our approach reduces the search time of agents and the wait time of resources using real-world data from Manhattan, New York, USA.


Smart Agent vs. Random Destination





Our contributions:


  • Generalization: Assuming that resources vary between days, the algorithm should adapt to random deviations in resource distributions, rather than overfitting to the resource distribution in the training data set.
  • Balancing Utility and Distance: Agents should find a balance between exploration (moving to more useful locations) and exploitation (remaining in the current location). The algorithm must find a balance between these two aspects.
  • Fairness: Without allowing agents to communicate with each other, the algorithm should evade flocking towards the same destination, to avoid oversupplying some regions while causing starvation in others.
  • Timing: Agents should move towards regions where their is a maximal chance of finding a resource at the time of arrival.



J.-S. Kim, D. Pfoser, and A. Züfle, Distance-Aware Competitive Spatiotemporal Searching Using Spatiotemporal Resource Matrix Factorization (GIS Cup), In Proceedings of ACM SIGSPATIAL GIS ’19, November 5-8, 2019. Chicago, IL, USA (to appear)