Scalable Social Coordination with Group Constraints using Enmeshed Queries
© 2013 Conference on Innovative Data Systems Research (CIDR). All rights reserved. While specific 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 differ from entangled queries, publish-subscribe systems, dating services and nested transactions. While even offline group coordination using enmeshed queries is NP-hard, we introduce efficient 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.
