Two-dimensional database query

A data structure includes a plurality of player entries that associates a player with a respective set of player activity data points having a first value and a second value. In response to a query defining ranges for the first value and second value, a response is generated using the data structure, the response indicating players matching the criteria of the ranges.

TECHNICAL FIELD

Embodiments of the present invention relate to querying a data structure.

DESCRIPTION OF THE RELATED ART

Responding to a query of a database of tracked user activity may be slow if the amount of user activity becomes large or if the query is complex.

DETAILED DESCRIPTION

Described herein are systems and methods for responding to a query of a data structure. The data structure may, for example, comprise data regarding user activity for a plurality of users. The data structure may, for example, comprise a list of user identifiers, each user identifier associated with a set of data points and each of the set of data points indicating a time and an amount of activity associated with time. For example, one element of the list may indicate that a first user played a particular game three times in January, once in March, and once in May. A second element of the list may indicate that a second user played the particular game once in February and once in March. A third element of the list may indicate that a third user played the particular game once in February, twice in April, and three times in August. Such a data structure is both highly scalable and highly responsive.

The query may be a two-dimensional query that specifies a time window and an amount window. The response to the query may include an indication of those users having, within the time window, a total amount of activity within the amount window. For example, a query may request an indication of those users who have played the game at least twice between January and March. Using the example above, the response would indicate the first user and the second user, but not the third user. A second query may request an indication of the users who have played the game at least three times between January and April. Again using the example above, the response would indicate the first user and the third user, but not the second user. Thus, the query may have dynamically quantified predicates, allowing the time window and the amount window to be defined independently from the configuration of the data structure.

FIG. 1is a block diagram of an embodiment of a network architecture100. The network architecture100includes a player relationship management (PRM) system110coupled to a network101. A number of user devices150A-150C are also coupled to the network101and the PRM system110may receive data about user activity from the user devices150A-150C over the network101. An admin device170is also coupled to the network101and the admin device170may submit queries to the PRM system110and receive responses to the queries from the PRM system110over the network101. Although only three user devices150A-150C and a single admin device170are illustrated inFIG. 1, it is to be appreciated that the network architecture100may include any number of user devices or admin devices.

The PRM system110includes a processing device112and a storage device114. The storage device114may store an event manager122. The event manager122may include instructions, executable by the processing device112, for processing event data regarding user activities. The event manager122may include instructions for receiving event data over the network101, processing the event data, and storing the event data in an event data structure124stored in the storage device114. The event manager122may include additional instructions for performing additional functions.

The event manager122may further include instructions for maintaining the event data structure. For example, the event manager122may periodically compress the event data structure to save space in the storage device114. In one embodiment, the event manager122reduces the temporal granularity of event data as it ages. For example, for recent event data, the event data structure114may include event data points specifying an amount of activity that occurred in a single day, week, or month, but, for older event data, include event data points specifying an amount of activity in a month, year, or historically (e.g., all activity before a specified date). The event manager122may reduce the size of the event data structure124in other ways, such as by removing data associated with inactive users or data compression techniques.

The storage device114may also store a query manager126. The query manager126may include instructions, executable by the processing device122, for receiving and responding to queries. The query manager126may include instructions for receiving a query from an admin device170over the network101, searching the event data structure124stored in the storage device114, generating a response to the query based on the search, and sending the response to the admin device170over the network101. The query manager126may include additional instructions for performing additional functions.

FIG. 2is a flow diagram of an embodiment of a method200of responding to a query. The method200may be performed by processing logic that may include hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions run on a processing device, a general purpose computer system, or a dedicated machine), firmware, or a combination thereof. In one embodiment, the method200may be performed, at least in part, by processing logic of the PRM system110described above with respect toFIG. 1. In particular, the method200may be performed by processing logic of the event manager122and the query manager126ofFIG. 1.

It is to be appreciated that the method200may be performed by a PRM system for any number of queries simultaneously, concurrently (partially overlapping in time), or consecutively. However, for ease of reference, the method200is described for a single query.

At block210of method200, the processing logic receives event data regarding a plurality of events. The event data includes, for each of the plurality of events, an indication of a user associated with the event, a time associated with the event, and an amount associated with the event. The event may be indicative of user activity. For example, the event data may indicate that a first user, during the month of July, three times, played a particular game on a user device. As another example, the event data may indicate that a second user, during 2014, spent $314.15 on in-app purchases. As a further example, the event data may indicate that a third user, on a particular date (e.g., Feb. 12, 2012) slept 7.5 hours. As yet another example, the event data may indicate that a fourth user, at a particular time (e.g., Nov. 29, 2013 at 11:30 am), lifted 405 pounds. As another example, the event data may indicate that a fifth user, at a yearly physical, had a resting heart rate of 68 beats per minute. It is to be appreciated that the event data may include other types of activities or include other types of data about a user.

The event data may include any of a number of different data structures. The event data may include one or more event data objects, each associated with a single event.FIG. 3is a block diagram of an embodiment of an event data object300and is described further below. The event data may include one or more event data tables, each associated with a plurality of events.FIG. 4is a block diagram of an embodiment of an event data table400and is also described further below. The event data may include other types of data structures.

The event data object300ofFIG. 3includes a number of different fields. The event data object300includes an object identifier field310that includes a unique identifier of the object that also serves to uniquely identify an event described by the event data object300. The event data object300includes a user field320that includes a user indicator that indicates a user associated with the event. The user indicator may be a user identifier number associated with the user or a username associated with the user.

The event data object300includes a time field330that indicates a time associated with the event. The indicated time may be a year, month, day, hour, minute, second, or any other time or period of time. The event data object300includes an amount field340that indicates an amount associated with the event. The amount may be any number. In one embodiment, the event data object300does not include an amount field340, but implicitly indicates an amount. For example, an event data object300excluding an amount field340may implicitly indicate an amount associated with the event of one. For example, the event data object300may explicitly indicate that event occurred at a particular time and implicitly indicate that the event occurred one time. The event data object300may include additional fields350that include other data. The other data may include, for example, a set of player data comprising one or more of an age indicator indicating an age of the player, a gender indicator indicating a gender of the player, a country indicator indicating a country of the player, or a username indicator indicating a username of the player.

The event data table400ofFIG. 4includes a number of columns411-414and a number of rows421-424indicating a number of events that have occurred. The example event data table400illustrated inFIG. 4indicates a number of times users have played a particular game during particular months. It is to be appreciated that other event data tables may provide data regarding different events.

The event data table400includes a number of rows421-424, each associated with a different user, as indicated in a user column411. In each row421-424in the user column411, the event data table400includes a user indicator indicating a particular user. In each row421-424, in the age column412, the event data table400includes an age indicator indicating an age of the user indicated by the user indicator in the user column411. Similarly, the gender column413includes a gender indicator indicating a gender of the user indicated by the user indicator in the user column411. It is to be appreciated that the event data table400may include additional, not shown, columns including other kinds of data.

The event data table400includes, for each row421-424, a number of played columns414indicating a number of times the user indicated in the user column411has played a particular game during a particular month. For example, in the first row421, the played columns414may indicate that the user associated with the user indicator USER1has played the particular game two times in January (e.g., JAN1=2), zero times in February (e.g., FEB1=0), zero times in March (e.g., MAR1=0), and one time in April (e.g., APR1=1).

Returning toFIG. 2, at block220, the processing logic generates an event data structure based on the event data. Generating the event data structure based on the event data may include modifying an existing event data structure to include the events indicated by the event data. The event data structure associates each of a plurality of user indicators with a respective set of event data points. Each of the event data points comprises a pairing of a time indicator indicating a time associated with an event and an amount indicator indicating an amount associated with the event.

FIG. 5is a block diagram of an embodiment of an event data structure500. The event data structure500ofFIG. 5includes a number of rows521-524and a number of columns511-514, including an event data points column514that includes, for each row521-524, a set of event data points. The example event data structure500illustrated inFIG. 5(like the event data table400ofFIG. 4) indicates a number of times users have played a particular game during particular months. It is to be appreciated that other event data tables may provide data regarding different events. Further, although illustrated as a two-dimensional structure, it is to be appreciated that the event data structure500may take other shapes and forms in which user indicators are associated with sets of event data points.

The event data structure500includes a number of rows521-524, each associated with a different user, as indicated in a user column511. In each row521-524in the user column511, the event data structure500includes a user indicator indicating a particular user. In each row521-524, in the age column512, the event data table500includes an age indicator indicating an age of the user indicated by the user indicator in the user column511. Similarly, the gender column513includes a gender indicator indicating a gender of the user indicated by the user indicator in the user column511. It is to be appreciated that the event data structure500may include additional columns including other kinds of data.

The event data structure500includes, for each row521-524, an event data points column514including a set of event data points. The set of event data points may be a null set including zero event data points (as illustrated in the second row522). The set of event data points may include a single event data point (as illustrated in the third row523). The set of event data points may include a plurality of event data points (as illustrated in the first row521and the fourth row524).

Each of the event data points includes a pairing of a time indicator and an amount indicator. Thus, if USER1has played the particular game two times in January, zero times in February, zero times in March, and one time in April, the set of event data points may include a first point indicating (January, 2) and a second point indicating (April, 1).

It is to be appreciated that the event data structure500ofFIG. 5is different from the event data table400ofFIG. 4. Whereas the event data table400ofFIG. 4includes a number of played columns414for a particular game, the event data structure500ofFIG. 5includes a single event data points column514for a particular game.

Thus, if USER1has played the particular game two times in January, zero times in February, zero times in March, and one time in April, the event data table400ofFIG. 4may include four played columns indicating (2, 0, 0, 1), whereas the event data structure500ofFIG. 5may include a set of event data points indicating (January, 2) and (April, 1).

Similarly, if USER2has not played the particular game in January, February, March, or April, the event data table400ofFIG. 4may include four played columns indicating (0, 0, 0, 0), whereas the event data structure500ofFIG. 5may associate USER2with a null set.

Because the event data structure500only includes event data points with particular events that have occurred, the event data structure500ofFIG. 5is more data space efficient than the event data table400ofFIG. 4. For example, if a user had no activity over a particular time period, no memory or disk space is allocated to store this information.

The event data structure500may include additional space saving features. In one embodiment, time values are encoded with a time offset value instead of an absolute time value in order to save space. In another embodiment, different time ranges have different temporal granularity. For example, a set of event data points may indicate that a user played a game seven times in 2011, six times in 2012, once in March 2013, twice in April 2013, and once in August 2013. Thus, in earlier years, the temporal granularity is a full year, whereas in more recent years, the temporal granularity is monthly.

Returning toFIG. 2, at block230, the processing logic receives a query defining a time window and an amount window. The time window may include both a start time and a stop time. The time window may include only one of a start time or a stop time. The time window may indicate a time period, e.g., a day, month, or year. The amount window may include both a minimum amount and a maximum amount. The amount window may include only one of a minimum amount and a maximum amount. The time window and amount window may be indicated in other ways.

The query may request a list of user indicators of users matching the criteria specified by the time window and amount window. For example, the query may request a list of user indicators indicating users that have played a particular game at least a threshold number of times within the time window. For example, the query may request a list of user indicators indicating users that have played a particular game at least five times in January. Thus, the time window is between January 1 and January 31 and the amount window is 5 and above (e.g., between 5 and infinity). As another example, the query may request a list of user indicators indicating users that have spent more than a threshold amount of money within the time window.

The query may further define additional criteria to be matched by the users. For example, the query may define user data criteria such as an age of the user, a gender of the user, a country of the user, or a username of the user. For example, the query may request a list of user indicators indicating users that are under twenty, female, and who have played a particular game at least once within the last forty days.

At block240, the processing logic uses the event data structure generated in block220to determine one or more matching user indicators based on the time window and amount window specified in the query. The processing logic may further determine the matching user indicators based on additional criteria specified by the query.

In one embodiment, the matching user indicators are determined such that each of the matching user indicators is associated by the event data structure with a respective set of event data points having a subset of data points wherein each of the subset of data points comprises a time indicator indicating a time within the time window and wherein the subset of data points comprises a set of amount indicators indicating a set of amounts having a sum within the amount window.

At block250, the processing logic sends a response to the query comprising the matching user indicators.

FIG. 6is a block diagram of an embodiment of a player relationship management (PRM) module600. The PRM module600may be executed by the processing device112of the PRM system110ofFIG. 1. The PRM module600takes, as input, event data601and, based on the event data601, generates or modifies an event data structure605stored in a database, memory, or other storage device. The PRM module600also takes, as input, a query692and provides, as output, a response694to the query692based on information in the event data structure605.

The PRM module600includes an event data management module610that parses received event data601and generates or modifies the event data structure605to include the information of the received event data. The PRM module600includes a query management module620that receives the query692and provides the response694.

FIG. 7is a flow diagram of an embodiment of a method700of searching a data structure. The method700may be performed by processing logic that may include hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions run on a processing device, a general purpose computer system, or a dedicated machine), firmware, or a combination thereof. In one embodiment, the method700may be performed, at least in part, by processing logic of the PRM system110described above with respect toFIG. 1. In particular, the method700may be performed by processing logic of the event manager122and the query manager126ofFIG. 1.

It is to be appreciated that the method700may be performed by a PRM system for any number of queries simultaneously, concurrently (partially overlapping in time), or consecutively. However, for ease of reference, the method700is described for a single query.

At block710of method700, the processing logic receives player activity data. The player activity data may be similar to the event data described above. The player activity data may include, for each of a number of player activities, an indication of a player associated with the activity, a first value associated with the activity, and a second value associated with the activity. In one embodiment, the first value is a time and the second value is an amount.

For example, the player activity data may indicate that a first player, during the month of July, three times, played a particular game on a user device. As another example, the player activity data may indicate that a second user, during 2014, spent $314.15 on in-app purchases. It is to be appreciated that the player activity data may include other types of activities or include other types of data about a player.

At block720, the processing logic compiles the player activity data into a data structure. Compiling the player activity data into a data structure may include modifying an existing data structure to include the player activity indicated by the player activity data. The data structure comprises a plurality of player entries associating a player with a set of activity data points. Each of the activity data points comprises a pairing of a first value associated with an activity and a corresponding second value associated with the activity. In one embodiment, the first value indicates a time a player has played a particular game and the second value indicates an amount the player has played the particular game during the time.

In one embodiment, the data structure is the event data structure500ofFIG. 5. Thus, the data structure may associate players with a set of player data comprising one or more of an age indicator indicating an age of the player, a gender indicator indicating a gender of the player, a country indicator indicating a country of the player, or a username indicator indicating a username of the player.

It is to be appreciated, as described above and illustrated in the event data structure500ofFIG. 5, that the set of activity data points may include zero, one, or a plurality of data points. In particular, the set of activity data points may be the null set. Thus, the data structure may include a first player entry associating a first player with a first set of activity data points comprising zero activity data points, a second player entry associating a second player with a second set of activity data points comprising only a single activity data point, and a third player entry associating a third player with a third set of activity data points comprising a plurality of activity data points.

At block730, the processing logic receives a query. The query may be received after the player activity data is compiled into the data structure. The query may specify a first range for the first value and a second range for the second value. For example, the first range may be a time window and the second range may be threshold.

At block740, the processing logic searches the compiled data structure based on the first range and second range. In particular, the processing logic searches the compiled data structure to determine a player (or more than one player) associated by the data structure with a subset of activity data points having first values in the first range and having second values with a sum or other function (e.g., a dynamically computed result) in the second range. For example, where the first range is a time window and the second range is a threshold, searching may determine a player having at least the threshold amount of activity within the time window. As a further example, the threshold amount of activity may be at least once and the time window may be a recent time period to determine a player that performed the activity recently (e.g., within the last few days, within the last couple of months, within the current year, etc.).

The processing logic searches the compiled data structure to find player entries associated with a set of activity data points matching criteria specified by the query. For each set of activity data points, there exists a first-range-matching subset of activity data points (which may include zero, one, or a plurality of activity data points) having first values within the first range. The first-range-matching subset may include each of the activity data points having first values in the first range. If the sum of the second values of the first-range-matching subset is within the second range, it may be determined that the player entry matches the criteria specified by the query.

At block750, the processing logic sends a response to the query. The response may indicate one or more players that match the criteria specified by the query.

FIG. 8illustrates a diagrammatic representation of a machine in the example form of a computer system800within which a set of instructions, for causing the machine to perform any one or more of the methodologies discussed herein, may be executed. The computer system800may represent at least one of the PRM system110, user devices150A-150C, or admin device170ofFIG. 1. In alternative embodiments, the machine may be connected (e.g., networked) to other machines in a LAN, an intranet, an extranet, or the Internet. The machine may operate in the capacity of a server or a client device in a client-server network environment, or as a peer machine in a peer-to-peer (or distributed) network environment. The machine may be a personal computer (PC), a tablet PC, a set-top box (STB), a Personal Digital Assistant (PDA), a cellular telephone, a smartphone, a web appliance, a server, a network router, switch or bridge, or any machine capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that machine. Further, while only a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein. In one embodiment, the PRM module600(as discussed in conjunction withFIG. 6) may be included in the execution block processing device802.

Processing device802represents one or more general-purpose processing devices such as a microprocessor, central processing unit, or the like. More particularly, the processing device may be complex instruction set computing (CISC) microprocessor, reduced instruction set computer (RISC) microprocessor, very long instruction word (VLIW) microprocessor, or processor implementing other instruction sets, or processors implementing a combination of instruction sets. Processing device802may also be one or more special-purpose processing devices such as an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), a digital signal processor (DSP), network processor, or the like. In one embodiment, processing device802may include one or processing cores. The processing device802is configured to execute the instructions of processing logic for performing the operations discussed herein, such as instructions for executing the PRM module600ofFIG. 6.

The computer system800may further include a network interface device808communicably coupled to a network820. The computer system800also may include a video display unit810(e.g., a liquid crystal display (LCD) or a cathode ray tube (CRT)), an alphanumeric input device812(e.g., a keyboard), a cursor control device814(e.g., a mouse), a signal generation device816(e.g., a speaker), or other peripheral devices. Furthermore, computer system800may include a graphics processing unit822, a video processing unit828, and an audio processing unit832. In another embodiment, the computer system800may include a chipset (not illustrated), which refers to a group of integrated circuits, or chips, that are designed to work with the processing device802and controls communications between the processing device802and external devices. For example, the chipset may be a set of chips on a motherboard that links the processing device802to very high-speed devices, such as main memory804and graphic controllers, as well as linking the processing device802to lower-speed peripheral buses of peripherals, such as USB, PCI or ISA buses.

The data storage device818may include a computer-readable storage medium824on which is stored instructions embodying any one or more of the methodologies of functions described herein, including but not limited to the method200ofFIG. 2, the method700ofFIG. 7, or the functions performed by the PRM module600ofFIG. 6. The instructions may also reside, completely or at least partially, within the main memory804and/or within the processing device802during execution thereof by the computer system800; the main memory804and the processing device802also constituting computer-readable storage media.