  Social coordination allows users to move beyond awareness of their friends to
efficiently coordinating physical activities with others. While specific forms
of social coordination can be seen in tools such as Evite, Meetup and Groupon,
we introduce a more general model using what we call enmeshed queries. An
enmeshed query allows users to declaratively specify an intent to coordinate by
specifying social attributes such as the desired group size and who/what/when,
and the database returns matching queries. Enmeshed queries are continuous, but
new queries (and not data) answer older queries; the variable group size also
makes enmeshed queries different from entangled queries, publish-subscribe
systems, and dating services.
  We show that even offline group coordination using enmeshed queries is
NP-hard. We then introduce efficient heuristics that use selective indices such
as location and time to reduce the space of possible matches; we also add
refinements such as delayed evaluation and using the relative matchability of
users to determine search order. We describe a centralized implementation and
evaluate its performance against an optimal algorithm. We show that the
combination of not stopping prematurely (after finding a match) and delayed
evaluation results in an algorithm that finds 86% of the matches found by an
optimal algorithm, and takes an average of 40 usec per query using 1 core of a
2.5 Ghz server machine. Further, the algorithm has good latency, is reasonably
fair to large group size requests, and can be scaled to global workloads using
multiple cores and multiple servers. We conclude by describing potential
generalizations that add prices, recommendations, and data mining to basic
enmeshed queries.
