Handling crowd requests for large geographic areas

• US 8,321,509 B2
• Filed: 12/23/2009
• Issued: 11/27/2012
• Est. Priority Date: 02/02/2009
• Status: Active Grant

• Current Assignee: Stripe, Inc.
• Original Assignee: Waldeck Technology, LLC (Concert Technology Corporation)
• Inventors: Jennings, Kenneth, Amidon, Christopher M., Katpelly, Ravi Reddy
• Primary Examiner(s): Recek, Jason
• Application Number:
  US12/645,560
• Publication Number:
  US 20100198862A1
• Time in Patent Office: 1,070 Days
• Field of Search: 709/204, 709/220, 707/769
• US Class Current: 709/204
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 67/54 Presence management, e.g. monitoring or registration for receipt of user log-on information, or the connection status of the users
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A system and method are provided for processing a request for crowd data for a large geographic area. In one embodiment, a central system, which includes one or more servers, operates to obtain current locations for users of mobile devices and form crowds of three or more users based on the current locations of the users. In order to provide access to crowd data for crowds for a large geographic area, the central system receives a request for crowd data from a requesting device, establishes a bounding region for the request, and identifies one or more starting points within the bounding region for the request. Crowds are identified, crowd data for the crowds is generated, and the crowd data is returned to the requesting device in an iterative manner for a series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting points.

Claims

1. A method comprising:

obtaining current locations of a plurality of users of a plurality of mobile devices, each of the plurality of users being a user of a corresponding one of the plurality of mobile devices;

receiving a request from a requesting device;

establishing a bounding region for the request;

identifying one or more starting spots within the bounding region for the request; and

iteratively identifying crowds each including three or more of the plurality of users, generating crowd data for the crowds, determining a needed number of follow-up requests based on at least one of a number of starting spots and a size of the bounding region, and returning the crowd data for the crowds and the needed number of follow-up requests to the requesting device for a series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots.

2. The method of claim 1 wherein iteratively identifying the crowds, generating the crowd data for the crowds, and returning the crowd data for the crowds to the requesting device for the series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots comprises:

establishing one or more initial request regions centered at the one or more starting spots such that each of the one or more initial request regions is a geographic region centered at a corresponding one of the one or more starting spots;

identifying one or more crowds relevant to the one or more initial request regions centered at the one or more starting spots;

generating crowd data for the one or more crowds relevant to the initial request regions centered at the one or more starting spots; and

returning, to the requesting device, the crowd data for the one or more crowds relevant to the one or more initial request regions centered at the one or more starting spots.

3. The method of claim 2 wherein iteratively identifying the crowds, generating the crowd data for the crowds, and returning the crowd data for the crowds to the requesting device for the series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots further comprises:

receiving a follow-up request from the requesting device;

establishing one or more request regions for the follow-up request corresponding to next geographic regions in the series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots;

identifying one or more crowds relevant to the one or more request regions for the follow-up request;

generating crowd data for the one or more crowds relevant to the one or more request regions for the follow-up request; and

returning the crowd data for the one or more crowds relevant to the one or more request regions for the follow-up request to the requesting device.

4. The method of claim 3 wherein iteratively identifying the crowds, generating the crowd data for the crowds, and returning the crowd data for the crowds to the requesting device for the series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots further comprises repeating the steps of receiving a follow-up request, establishing one or more request regions for the follow-up request, identifying one or more crowds relevant to the one or more request regions for the follow-up request, generating crowd data for the one or more crowds, and returning the crowd data to the requesting device for one or more additional follow-up requests.

5. The method of claim 4 further comprising:

determining a number of follow-up requests needed to obtain crowd data for a remaining portion of the bounding region for the request that is outside of the one or more initial request regions centered at the one or more starting spots; and

returning a needed number of follow-up requests to the requesting device along with the crowd data for the one or more crowds within the one or more initial request regions centered at the one or more starting spots;

wherein the one or more additional follow-up requests is a number of follow-up requests that is less than or equal to the number of follow-up requests needed to obtain crowd data for the remaining portion of the bounding region for the request that is outside of the one or more initial request regions centered at the one or more starting spots.

6. The method of claim 4 wherein iteratively identifying the crowds, generating the crowd data for the crowds, and returning the crowd data for the crowds to the requesting device for the series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots further comprises filtering crowds to remove redundant crowds among the one or more crowds identified as being relevant to the one or more request regions for the follow-up request and the one or more crowds identified as being relevant to the one or more request regions for each of the one or more additional follow-up requests to remove redundant crowds.

7. The method of claim 4 wherein iteratively identifying the crowds, generating the crowd data for the crowds, and returning the crowd data for the crowds to the requesting device for the series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots further comprises filtering crowd data to remove redundant crowd data among the crowd data generated for the one or more crowds identified as being relevant to the one or more request regions for the follow-up request and the crowd data generated for the one or more crowds identified as being relevant to the one or more request regions for each of the one or more additional follow-up requests to remove redundant crowds.

8. The method of claim 4 wherein the one or more request regions for the follow-up request and the one or more request regions for each of the one or more additional follow-up requests do not overlap.

9. The method of claim 4 wherein identifying the one or more crowds relevant to the one or more request regions comprises querying a datastore for crowds relevant to a mathematical union of the one or more request regions for the follow-up request.

10. The method of claim 2 wherein identifying the one or more crowds relevant to the one or more initial request regions comprises forming the one or more crowds relevant to the one or more initial request regions in response to the request.

11. The method of claim 2 wherein a plurality of crowds each including three or more users of the plurality of users are proactively formed, and identifying the one or more crowds relevant to the one or more initial request regions comprises identifying one or more of the plurality of crowds as being relevant to the one or more initial request regions.

12. The method of claim 2 wherein a size of each of the one or more initial request regions is an optimal size for identifying one or more crowds relevant to the one or more initial request regions.

13. The method of claim 1 further comprising:

determining whether a size of the bounding region is greater than a predefined maximum size;

wherein iteratively identifying the crowds, generating the crowd data for the crowds, and returning the crowd data for the crowds to the requesting device comprises iteratively identifying crowds, generating crowd data for the crowds, and returning the crowd data for the crowds to the requesting device for the series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots if the size of the bounding region is greater than the predefined maximum size.

14. The method of claim 13 further comprising, if the bounding region for the request is not greater than the predefined maximum size:

identifying one or more crowds relevant to the bounding region for the request;

generating crowd data for the one or more crowds; and

returning the crowd data to the requesting device.

15. The method of claim 1 further comprising:

maintaining a list of hotspots including a plurality of hotspots that are locations at which a substantial number of crowds have historically been located;

wherein identifying the one or more starting spots comprises identifying one or more hotspots within the bounding region from the list of hotspots as the one or more starting spots.

16. The method of claim 1 further comprising:

maintaining a list of hotspots including a plurality of hotspots that are locations selected as hotspots by at least a subset of the plurality of users via a collaborative process;

wherein identifying the one or more starting spots comprises identifying one or more hotspots within the bounding region from the list of hotspots as the one or more starting spots.

17. The method of claim 1 further comprising:

maintaining a list of hotspots including a plurality of hotspots that are locations registered by entities as hotspots via a subscription process;

wherein identifying the one or more starting spots comprises identifying one or more hotspots within the bounding region from the list of hotspots as the one or more starting spots.

18. The method of claim 1 wherein identifying the one or more starting spots comprises identifying current locations of one or more friends of a user of the requesting device that are currently located within the bounding region as the one or more starting spots.

19. A server comprising:

a communication interface communicatively coupling the server to a plurality of mobile devices of a plurality of users via a network, each of the plurality of users being a user of a corresponding one of the plurality of mobile devices; and

a control system associated with the communication interface and adapted to;

obtain current locations of the plurality of users of the plurality of mobile devices;

receive a request from a requesting device;

establish a bounding region for the request;

identify one or more starting spots within the bounding region for the request; and

iteratively identify crowds each including three or more of the plurality of users, generate crowd data for the crowds, determine a needed number of follow-up requests based on at least one of a number of starting spots and a size of the bounding region, and return the crowd data for the crowds and the needed number of follow-up requests to the requesting device for a series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots.

20. A non-transitory computer readable medium storing software for instructing a controller of a server to:

obtain current locations of a plurality of users of a plurality of mobile devices, each of the plurality of users being a user of a corresponding one of the plurality of mobile devices;

receive a request from a requesting device;

establish a bounding region for the request;

identify one or more starting spots within the bounding region for the request; and

iteratively identify crowds each including three or more of the plurality of users, generate crowd data for the crowds, determine a needed number of follow-up requests based on at least one of a number of starting spots and a size of the bounding region, and return the crowd data for the crowds and the needed number of follow-up requests to the requesting device for a series of two or more outwardly radiating, concentric geographic regions centered at the one or more starting spots.