Location-Centric View Selection in a Location-Based Feed-Following System

TY - GEN

T1 - Location-Centric View Selection in a Location-Based Feed-Following System

AU - Chen, Kaiji

AU - Zhou, Yongluan

PY - 2019/6/24

Y1 - 2019/6/24

N2 - Location-based feed-following is a trending service that can provide contextually relevant information to users based on their locations. In this paper, we consider the view selection problem in a location-based feed-following system that continuously provides aggregated query results over feeds that are located within a certain range from users. Previous solutions adopt a user-centric approach and require re-optimizations of the view selection once users move their locations. Such methods limit the system's scalability to the number of users and can be very costly when a substantial number of users move their locations. To solve the problem, we propose the new concept of location-centric query plans. In this approach, we use a grid to partition the space into cells and generate view selection and query processing plans for each cell, and user queries will be evaluated using the query plans associated with the users' current locations. In this way, the problem's complexity and dynamicity is largely determined by the granularity of the grid instead of the number of users. To minimize the query processing cost, we further propose an algorithm to generate an optimized set of materialized views to store the aggregated events of some feeds and a number of location-centric query plans for each grid cell. The algorithm can also efficiently adapt the plans according to the movement of the users. We implement a prototype system by using Redis as the back-end in-memory storage system for the materialized views and conduct extensive experiments over two real datasets to verify the effectiveness and efficiency of our approach.

AB - Location-based feed-following is a trending service that can provide contextually relevant information to users based on their locations. In this paper, we consider the view selection problem in a location-based feed-following system that continuously provides aggregated query results over feeds that are located within a certain range from users. Previous solutions adopt a user-centric approach and require re-optimizations of the view selection once users move their locations. Such methods limit the system's scalability to the number of users and can be very costly when a substantial number of users move their locations. To solve the problem, we propose the new concept of location-centric query plans. In this approach, we use a grid to partition the space into cells and generate view selection and query processing plans for each cell, and user queries will be evaluated using the query plans associated with the users' current locations. In this way, the problem's complexity and dynamicity is largely determined by the granularity of the grid instead of the number of users. To minimize the query processing cost, we further propose an algorithm to generate an optimized set of materialized views to store the aggregated events of some feeds and a number of location-centric query plans for each grid cell. The algorithm can also efficiently adapt the plans according to the movement of the users. We implement a prototype system by using Redis as the back-end in-memory storage system for the materialized views and conduct extensive experiments over two real datasets to verify the effectiveness and efficiency of our approach.

U2 - 10.1145/3328905.3329512

DO - 10.1145/3328905.3329512

M3 - Article in proceedings

SP - 67

EP - 78

BT - Proceedings of the 13th ACM International Conference on Distributed and Event-based Systems, DEBS 2019, Darmstadt, Germany, June 24-28, 2019.

ER -