MR-Cubes: On-the-Fly Computation of Location Popularity from Check-in Data Streams

Several applications in urban planning, ride-sharing or marketing, require access to the location popularity of a geographical area (e.g., city block, city, county) in near real-time and at different resolutions. To conceptualize such an access, imagine a visualization tool to view a heatmap of location popularity of a region on-the-fly as a user interacts seamlessly by zooming in and out. The access method required to enable such a seamless visualization must support: 1) updating the heatmap cells frequently as the raw data (e.g., check-ins) arrives at a high rate in a streaming fashion, and 2) splitting and merging the adjacent cells quickly to support zooming in and out, respectively. This is challenging because the most useful metric for location popularity, location entropy, requires counting the number of unique visits per user, and hence: 1) a large data structure should be maintained and updated per cell, and 2) the adjacent cells must be aggregated/disaggregated quickly while the unique visits are not additive. Due to these challenges, the previous techniques for OLAP cubes, streaming sketches and index structures are not effective. In this paper, we propose a new index structure called MR-Cube that approximates the popularity by maintaining sketches of streamed data per cell, supports time-decay for older visits and aggregates the non-additive location popularity quickly and accurately at different resolutions. We evaluate the accuracy and efficiency of MR-Cube using real-world and synthetic datasets and show its utility for our application.

• Publication year

  2019

• Venue

  International Conference on Mobile Data Management

• Publication date

  2019-06-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1109/MDM.2019.00-77
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Optimal assignment and incentive design in the taxi group ride problem

  2017cited by this paper
• Optimal Pick up Point Selection for Effective Ride Sharing

  2017cited by this paper
• Geotagged Twitter posts from the United States: A tweet collection to investigate representativeness

  2016cited by this paper
• A Server-Assigned Spatial Crowdsourcing Framework

  2015cited by this paper
• Mining Human Mobility in Location-Based Social Networks

  2015cited by this paper
• User Category Based Estimation of Location Popularity using the Road GPS Trajectory Databases

  2014cited by this paper
• Scalable top-k spatio-temporal term querying

  2014cited by this paper
• Understanding Twitter data with TweetXplorer

  2013cited by this paper
• Geo-spotting: mining online location-based services for optimal retail store placement

  2013cited by this paper
• Uncovering Patterns of Inter-Urban Trip and Spatial Interaction from Social Media Check-In Data

  2013cited by this paper
• Mergeable summaries

  2012cited by this paper
• A near-optimal algorithm for estimating the entropy of a stream

  2010cited by this paper
• Bridging the gap between physical location and online social networks

  2010cited by this paper
• TwitterMonitor: trend detection over the twitter stream

  2010cited by this paper
• Methods for finding frequent items in data streams

  2010influential reference
• Feeling-based location privacy protection for location-based services

  2009cited by this paper
• Exponentially Decayed Aggregates on Data Streams

  2008cited by this paper
• Data streaming algorithms for estimating entropy of network traffic

  2006influential reference
• Estimating Entropy and Entropy Norm on Data Streams

  2006cited by this paper
• A Mathematical Theory of Communication

  2006cited by this paper
• Efficient Computation of Frequent and Top-k Elements in Data Streams

  2005cited by this paper
• Entropy-based sensor selection heuristic for target localization

  2004cited by this paper
• An improved data stream summary: the count-min sketch and its applications

  2004cited by this paper
• Abstract The

  2002cited by this paper
• IR evaluation methods for retrieving highly relevant documents

  2000cited by this paper
• Relative prefix sums: an efficient approach for querying dynamic OLAP data cubes

  1999cited by this paper
• An overview of data warehousing and OLAP technology

  1997influential reference
• Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals

  1996cited by this paper
• A behavioral theory of timing.

  1988cited by this paper
• Random sampling with a reservoir

  1985cited by this paper
• The Quadtree and Related Hierarchical Data Structures

  1984cited by this paper
• R-trees: a dynamic index structure for spatial searching

  1984influential reference
• A hierarchical data structure for picture processing

  1975cited by this paper

• No citing papers are available for this paper.