Scalable Social Coordination using Enmeshed Queries

J. Chen, A. Machanavajjhala, and G. Varghese

Abstract

While some forms of social coordination appear in tools such as Meetup and in game platforms such as XBox LIVE, we introduce a more general model using what we call enmeshed queries. An enmeshed query allows users to declaratively specify an intent to coordinate with other users (who they may not know a priori) by specifying constraints on who/what/when as well as on the composition of the group, such as the desired group size. The database returns a group of users who have registered queries with matching intents. Enmeshed queries are continuous, but new queries (and not data) answer older queries; the group constraints and the ability to coordinate with unknown partners make enmeshed queries different from entangled queries, publish-subscribe systems, dating services and nested transactions. While even onliine group coordination using enmeshed queries is NP-hard, we introduce effifficient heuristic algorithms that can scale to millions of queries, and find 86% of the matches found by an optimal algorithm using 40 microseconds per query on a 2.5 GHz server machine. We conclude by describing potential generalizations that add prices, recommendations, and data mining to basic enmeshed queries.

Details

Publication typeInproceedings
Published inCIDR (Conference on Innovative Data Research)
> Publications > Scalable Social Coordination using Enmeshed Queries