Social activity planning system and method

A social activity planning system, comprising:

• a database storing a plurality of candidate invitees, geographical locations of the candidate invitees, interest scores towards a topic of the candidate invitees, and a social graph (G={V,E}) comprising vertices (vi ε V) representing the candidate invitees, and edges (ei,j ε E) connecting vertex (vi) and vertex (vj) representing mutual acquaintance of the candidate invitees represented by the vertex (vi)and the vertex (vj);
• and
• a social activity planning device connected to the database, comprising a processing unit and an input unit, wherein the input unit receives a social activity request comprising an invitation number (P), information about a social activity, and a familiarity condition for the social activity request, and the processing unit finds a feasible solution, wherein the feasible solution comprises (p) candidate invitees and meets the familiarity condition, and
• wherein the information about a social activity request comprises a rally point location (q), the familiarity condition comprises a familiarity constraint number (k), and the processing unit finds the feasible solution by performing the following operations:
• (a) packing the candidate invitees in an R-tree data structure with tree nodes in the R-tree data structure representing the candidate invitees or minimum bounding rectangles (MBRs) of the candidate invitees if the R-tree data structure has not been constructed;
• (b) generating a priority queue according to the tree data structure with the priority queue in ascending order based on the distance of the geographical locations of the candidate invitees to the rally point location (q);
• (c) running backtracking algorithm with a branch-and-bound tree to move candidate invitees from a first set (SR) to a second set (SI) according to the priority queue, wherein the first set (SR) comprises all the candidate invitees at initialization, the candidate invitees moved to the second set (SI) are intermediate candidate invitees, and tree nodes in the branch-and-bound tree representing the second set (SI) comprising different intermediate candidate invitees;
• and
• (d) generating the feasible solution wherein the feasible solution is obtained when the backtracking algorithm first expands the branch-and-bound tree to the second set (SI) comprising (p) intermediate candidate invitees, and meeting the familiarity condition, which means an average number of unknown intermediate candidate invitees of the intermediate candidate invitees in the second set (SI) does not exceed the familiarity constraint number (k).