Scalable Social Coordination using Enmeshed Queries

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.