IN A LAYERED LINKED NODE DATABASE

FIELD OF THE INVENTION

[0001] The present invention relates generally to node ranking in a layered linked node database, and more specifically to a system and method for dynamically

determining node relevancy based on proximal weighting within and between layers, in a scalable manner.

DESCRIPTION OF THE BACKGROUND ART

[0002] There is a rapidly accelerating growth in the use of the world wide web and other computer systems to access information about people and places. There is also a rapidly accelerating growth in the use of mobile devices, and in particular, mobile devices that have the ability to derive the current location of the user. There is a further trend for mobile devices to provide functionality to access the full Internet, including, but not limited to, web sites. These trends have combined to create a rapidly growing number of mobile devices supporting full access to the Internet, for mobile device users to increasingly regard the mobile device as the primary device that is used to access information, and for the device they are using to know where the user is at a given point in time.

[0003] As these trends accelerate, they are changing the expectations that mobile device users have. In the past, mobile device users tended to regard mobile devices as largely static convenience devices that allowed them to make telephone calls, or to send text messages, at will. Increasingly, as the devices become more central to the life of the mobile device user, the mobile device is used to store more intimate information about the user. This has the effect of changing the mobile device users' perception of the device, from something static and impersonal, to something dynamic and personal. In other words, as the mobile device user imparts more knowledge about themselves to the device, mobile device users increasingly expect the device to know more about them, and to leverage that information to aide the mobile device user.

[0004] Until the present invention, technologies did not meet all of the expectations of all mobile device users. The greatest mismatch between functionality and expectations is due to the limitations of the mobile devices in dealing with the context in which a mobile device user is operating. As a mobile device user moves through their day, the context in which they are operating continually changes: their location changes, and the people and places with which they are interacting change. Current devices and online services supporting them cannot deal adequately with these continuous context changes.

[0005] As the mobile device user's context changes, so does the relevancy of the things around them. As a simple example, if a mobile device user travels to another city, intuitively, the restaurants around them are likely to be of greater relevance than restaurants many miles away. This may not always be the case: the mobile device user may be doing research about restaurants, in which case, the mobile device context reflects some change of interest, and hence relevancy (by changing into a 'search' context, the system naturally reflects a difference in relevancy). A system needs to be able to dynamically adapt to such changes.

[0006] The notion of proximal relevancy can be found in almost everything mobile device users do. For geospatial distances, the research is clear: for the most part, people do not consider places more than 16 miles away to be of any immediate relevance (Candia2008, Gonzalez2008). A similar pattern is also found in online social networks: studies (Wassermanl995, Zeigler2005, Rocha, Hill, Kumar) have shown that most people have less than 150 online friends, and generally less than 7 close friends that they are constantly in contact with. Other studies have shown that the relevance or 'value' of a relationship decreases rapidly as the number of people between one person and another increases (inverse of the 6 degrees effect). While there are a large number of things in which a mobile device user may be interested, at any given point in time, the true number of relevant items is actually fundamentally limited (Dunbarl992, Dunbarl993,

Murata2007, Sawal990).

[0007] As noted earlier, current mobile devices do not meet mobile device user expectations for contextual relevancy, and neither do current search technologies. While search engines may, or may not, provide a means to restrict search results to within a given geospatial proximity, such restrictions are typically handled as a special case, and not as an intrinsic part of the search engine. A good example is the Google search engine, which uses the well-known PageRank algorithm to statically determine the relevancy of a particular set of pages: proximity restrictions are layered over the underlying ranked link database as a filtering, or sorting based on proximity. Other relevancy restrictions, such as social relevancy, would likewise be layered over the underlying, static weighted node database.

SUMMARY OF INVENTION

[0008] A key factor of the present invention is to look at mobile device users, and their relationship to the world, as a set of weighted connections that are constantly changing, and to realize that proximity in connections is crucial. The problem of making mobile devices more personal then becomes a problem of maintaining, in real time, a set of weighted connections between items and mobile device users. By storing the nodes and connections in a layered linked node database, and then using this database, and user context to determine relevancy of nodes within the database, it is possible to provide a more dynamic, and personal view to mobile device users.

[0009] Aspects of the present invention provide a system and method for assigning a relevance ranking to nodes in a layered linked node database. Aspects of the present invention have a number of benefits over previous systems and methods, including, but not limited to, a means to use the link structure within a layered linked node database to determine relevancy, a more natural derivation of relevancy, especially from the viewpoint of a human user, a means to dynamically determine relevancy, taking into account the most recent changes to the layered linked node database, a system that can scale to extremely large databases, and a structure allowing the relevancy to be updated in near real time.

[0010] Aspects of the present invention use a layered linked node database to determine relevancy. A layered linked node database consists of a number of layers, an example of which is shown in Figure 1 , where there are a plurality of layers, Geospatial, Place, and Space. Each layer has a set of nodes with connections between them such that each layer forms a graph. Connections may also exist between layers, forming another graph. This structure is more complex than typical node databases used for determining node ranking, and provides opportunities to more accurately determine a true relevancy ranking for a node.

[0011] Aspects of the present invention use the link structure of a layered linked node database to derive a relevancy ranking for nodes based on proximal weighting. There may be a plurality of layers, each with its own connection structure and weighting factors. It should be clear to those skilled in the relevant art that there are any number of possible layers and connection patterns within and between them. The ranking of a particular node is determined by propagating a value between and within layers in the layered linked node database.

[0012] In the context of Figure 1, which shows three layers, Geospatial (physical location), Place (virtual location) and Space (social network), intuitively, direct social connections are generally of more relevance to a given person, than indirect connections. Likewise, Place data (virtual location) created by a user is generally of more relevance than Place data created by unknown people. Further, geospatial locations that are referenced by, or related to, direct social connections, or Place data created by them, is generally of more relevance than arbitrary geospatial locations. As such, in the context of Figure 1 a layered linked node database is created to reflect the connections, and a node ranking is determined from this layered linked node database, which more naturally reflects the relevance to mobile device users.

[0013] Note that in general, relevancy is determined using a per-layer and inter-layer weighting scheme, and that by altering the starting node set and the damping scheme different effects can be achieved. For example, in the context of Figure 1, if the inter- layer weighting were set to 0, then relevancy ranking would occur only within a particular layer. This can be used to determine, for example, only 'nearby places' at the Geospatial layer, or 'close friends' at the Space layer. As a further example, assuming the connection between 2 users was set to 0, the effect in terms of determining the most relevant geospatial locations for a given user would immediately reflect the change in relevance of locations with direct connections to one of the two users. This flexibility in retrieval is significant to aspects of the present invention.

[0014] Those skilled in the relevant art will also understand that extant relevancy ranking schemes, such as PageRank, determine relevancy for all nodes based on link structures and do so statically by performing an analysis of all nodes and arcs at once, thereby producing a static 'snapshot' of node relevancy. While aspects of the present invention may be used to determine relevancy in a static manner, for all nodes, it is neither necessary nor sufficient for processing the dynamic changes to relevancy that occur naturally. As such, aspects of the present invention emphasize, but are not limited to, a dynamic determination of relevancy that immediately takes updates to the layered linked node database into account.

[0015] Some aspects of the present invention further require only local updates to the layered linked node database in order to dynamically alter the relevancy ranking of nodes. As noted earlier, setting the inter-layer connection weight to 0 will result in no nodes from other layers being included in the ranking. Due to the emphasis on dynamic determination of node relevancy in the present invention, local changes such as this have an immediate impact. By only requiring local updates, aspects of the present invention are far more scalable and dynamic than comparable systems.

[0016] Some aspects of the present invention further provide a structure that can be updated in close to real time, even for large graphs, thereby providing a level of dynamic behavior hereto unavailable in large linked databases. With only local updates being required, literally thousands of updates to the layered linked node database could occur per second, with effects of updates being immediately apparent.

[0017] One embodiment of the present invention can be used in a system that statically assigns a node ranking to all nodes in layered linked node database, thereby providing a global node ranking mechanism. The global ranking may be used to determine, in the absence of restrictions or context, the most highly valued nodes within the database. This is similar to extant node ranking mechanisms, such as PageRank in that it produces global static weightings, though the present invention uses a somewhat different mechanism for determining the weights.

[0018] A further embodiment of the present invention can be used in a system to dynamically determine relevance for a particular set of nodes, or a particular context. For example, the system may be used to determine the most relevant restaurants for a mobile device user when they are at a given location at a given point in time. Such a system will dynamically take into account past preferences and current location in the determination of relevancy.

[0019] A further embodiment of the present invention can be used in a system for categorization based on relevancy, such as clustering of news articles. For example, each news article can be taken as a node, with links between nodes and node features. The weighting mechanism described herein will cluster the nodes based on distance metrics. Higher level features, such as 'category,' and lower-level features, such as term frequency and term proximity weightings can also be incorporated. With such a system, the clustering would 'evolve' over time, possibly incorporating feedback from users to indicate 'true' relevance clusterings.

[0020] Yet another embodiment of the present invention can be used in a system that will learn relevance, and dynamically take temporal affinity into account. For example, if a mobile device user has searched for restaurants, and historically has had a preference for Japanese food, but most recently, has always expressed interest in Chinese food, the system would automatically weight Chinese restaurants higher.

[0021] Yet another embodiment of the present invention can be used in a system that can determine node relevancy based on geospatial filtering or other forms of proximal filtering. For example, a system might provide a means to rank nearer restaurants higher than restaurants further away.

[0022] Other embodiments and systems that are compatible with the description and claims of the present invention are possible. Those skilled in the relevant art will appreciate the flexibility and large number of potential applications of the present invention.

BRIEF DESCRIPTION OF DRAWINGS

[0023] Figure 1 shows an example of a set of nodes and connections that might be stored in a layered linked node database.

[0024] Figure 2 shows another example of a set of nodes and connections that might be stored in a layered linked node database.

[0025] Figure 3 shows an example of a connection set with connections and weights associated with them.

[0026] Figure 4 shows an example of a connection set within a given layer with nodes (A thru E) and connections between nodes (CI thru C4) along with a propagated value.

[0027] Figure 5 shows a more detailed graph, including weight values before the application of the techniques from the present invention.

[0028] Figure 6 shows a more detailed graph, including weight values and node rankings, after application of techniques from the present invention. [0029] Figure 7 outlines the basic mechanism used to perform node rankings.

[0030] Figure 8 shows the main conceptual parts of the present invention.

DETAILED DESCRIPTION

[0031] In the following description the present invention will be described using specifics for illustrative purposes. Those with skill in the relevant art will immediately appreciate that there are large number of variations possible that still lie within the purview of the present invention. In particular, the present invention is described in the context of a particular layered linked node database, while being generally applicable to linked node databases of arbitrary structure. Furthermore, the following description focuses on use in the context of mobile devices, but as those skilled in the relevant art will appreciate, the present invention is applicable to other domains.

[0032] The problem of determining what is relevant to a user of a mobile device at a given point in time can be broken into two major parts: naturally modeling the items a mobile device user interacts with, and naturally modeling and manipulating the relationship between these items. The term 'item' is used to refer to an arbitrary, identifiable entity, such as, but not limited to a contact, an establishment such as a bar, restaurant, or museum, a geospatial location or virtual items representing abstract concepts, such as Japanese food, skiing or education. Being able to naturally and consistent manage relationships to both physical and virtual items is significant to aspects of the present invention.

[0033] One way to naturally represent items and the relationship between them, is as a graph G={V,E}, wherein each node (vertices, or V) represents an item, and arcs (edges, arcs or E) between nodes represent a relationship. For the purposes of determining relevancy, many systems associate a weight to the edge indicating some strength of connection. By altering the topology and semantics of the arcs connecting the vertices, it is possible to created a layered structure, thereby creating a layered linked node structure, or layered linked node database. There may be a plurality of layers, each with its own connection structure within and between layers.

[0034] A typical layered linked node database is shown in Figure 1. In this particular case the database is comprised of 3 layers: Geospatial 101, Place 102 and Space 103. The Geospatial layer 101 represents physical locations 107. The Place layer 102 represents a virtual node structure that describes geophysical locations as indicated by the arcs 106 between nodes 108 in the Place layer and nodes 107 in the Geospatial layer. The Space layer 103 represents social network nodes 109, connections 105 between nodes in the same layer, and connections 104 between nodes in different layers. It should be clear to those skilled in the relevant art that there are any number of possible layers and connection patterns within and between them.

[0035] In an embodiment of the present invention, the nodes and connections would be stored in a database, such as a relational database management system (RDBMS), where each node and connection would be associated with a unique identifier used for identification and retrieval, and could have one or more associated properties, such as name, or in the case of connections, weights. In the preferred embodiment of the present invention a single RDBMS may not be used as the primary data store because, as those skilled in the relevant art will recognize, this will face scalability issues with large graphs. In the preferred embodiment of the present invention, as shown in Figure 8, the graph will instead be partitioned, or 'sharded', across one or more Data Storage units 806, and the graph will be kept largely in a distributed virtual database 803.

[0036] Aspects of the present invention use the link structure of a layered linked node database to derive a relevancy ranking for nodes based on proximal weighting. The node ranking is determined by a simple sum of values propagated through weighted

connections. An example of the summation is shown in Figure 4, where (A) is regarded as the 'starting point'. As the value of (A) is propagated through the graph, the value of the next node is taken as the product of the current node and the weight of the connection between it and the next node, hence node (B) has a value of 0.75, and D has a value of 0.5625. This has the effect of producing rank weightings that are a factor of proximity.

[0037] The graph may be directed, or undirected, the primary difference being that in an undirected graph, there will be a bidirectional connection between vertices, so that the undirected graph would be equivalent to a directed graph with an arc in both directions with the same weight.

[0038] Taking the definition of the graph earlier (G={V,E}), the graph comprises a set of vertices V, and a set of arcs E. Another way to look at this is that there is a list of vertices Vi thru V _n and that the arcs are an n x n matrix of weights, such that E _ljD would be the weight of the arc from Vi to V _n . If the graph is undirected, the weights would be symmetrical (E _ljn would equal E _nj ), but whether the graph is directed or undirected, a lack of a connection would be represented by the value 0. Given such a representation, the value for a given node N is given as the sum of values feeding into N, or by the equation N _{ = ^E^N _j where E is the weight matrix. As noted earlier, layers in the

j

layered linked node database are defined through the graph topology.

[0039] Note that there may be other more or less specific derivative equations that can be used to determine node relevancy. For example, assuming the layered linked node database structure as shown in Figures 1 and 2, a more specific equation that explicitly takes layers into account could be given as N. = G x P,E _; , + S Έ.. where G is a

j

weighting factor based on the geospatial distance and P and S represent nodes in the Place 102 and Space 103 layers with an assumed starting value of 1.0. Those skilled in the relevant art will appreciate that there a large number of possible derivative, but equivalent equations.

[0040] The general update mechanism is shown in Figure 7. At the opening stage 701 the nodes in the graph are all assumed to have a value of 0. Starting with a particular set of one or more nodes, the nodes are given an initial starting value in 702. Then, in the update step 703 the values are propagated throughout the graph by taking the summed product of the value and the weights of connections from one node to another as a derived value for the node. The process is repeated a number of times in order to allow the values to fully propagate throughout the graph and for the values to 'settle'. At the end of the process 704 the nodes most tightly linked to the starting nodes will have the highest values. Figures 5 and 6 represent a typical graph before and after application of the update mechanism.

[0041] A further normalization step may be applied to the nodes whereby each node value is calculated to fall within some range or otherwise transformed. A typical function to be applied to the node value is the logistic function / (N) =— - which will produce

\ - e

a sigmoid curve with the values falling between 0 and 1. This is especially useful if the update mechanism is used to determine the ranking for all nodes in the layered linked node database as it prevents node rankings from increasing or decreasing arbitrarily because of cycles in the graph, or overly represented weightings. [0042] In the context of Figure 8, the preferred embodiment will use multiple instances of the Ranking Analysis Engine 802 running concurrently over the distributed virtual database 803, one for each set of rankings being calculated, where each ranking has a different set of start nodes and different values assigned to the start nodes. In the preferred embodiment, each Ranking Analysis Engine 802 acts as a client of the virtual database 803, pulling node and link sets from the virtual database on an as-needed basis. Each of these Ranking Analysis Engines 802 will maintain the state of the rankings locally, thereby removing the necessity for managing global state.

[0043] A slight variant of the update mechanism may prioritize intra-layer updates over inter-layer updates. Figure 2 shows a typical 3 layer database, with the Geospatial 204, Place 203 and Space 202 layers. The current location of user Fl is illustrated as physical location 201. The figure shows the inter-layer arcs 205 and intra-layer arcs 207. Some of the arcs are more highly weighted than others: for example, the user-created arcs 206 are more highly weighted than the user-visited arcs 205. For example, the arc between a user and a user-created item, such as a photograph taken by the user, is more highly weighted than an arc between the user and a user- visited item, such as a museum. Using an alternate update mechanism, each update cycle would first propagate the node values within a given layer, and then propagate the values between layers. For example, the nodes Fl thru F4 in Space layer 202 might be updated first, applying a slightly different summation mechanism, or applying a different threshold function. Variants such as this allow the update mechanism to be modified to provide a more natural order of updates, and to tailor the individual node updates to more accurately reflect the relevance within a given layer, though again, such variants are derivatives of the more general underlying mechanism.

[0044] Unlike other ranking schemes, the ranking of a particular node is determined by propagating a value through the graph, rather than performing a global ranking based on some fitness function, such as the random surfer model, which assigns a ranking based on the probability of access to each node in the graph. This is because, rather than determining a global value, aspects of the present invention rank nodes according to their relation to a particular node or set of nodes. A global ranking can, however, be calculated for all nodes in the graph by assigning an initial value to all nodes in the layered linked node database, and executing the update mechanism, though this is an atypical usage because of the large processing cost associated with such updates, especially in larger layered linked node databases, because of combinatorial explosion and iterative propagation of the values. Indeed, it is precisely these limitations of extant systems that the present invention provides an alternative to.

[0045] In a typical usage of the present invention, rankings are determined by taking only a small set of initial nodes, assigning a value to them, and then propagating those values based on the arcs between those nodes and other nodes in the layered linked node database. This makes the ranking mechanism more scalable than comparable ranking mechanisms, even for very large graphs, because the cost of calculating the node ranking is not a function of the order of the graph, but rather a function of the connectivity of the nodes within and between layers of the graph. In typical graphs associated with typical envisaged usage in determining the relevance based on social network graphs, the number of arcs will generally be below 150, though in extreme cases, the number might grow to 800 or more arcs per node (Krautl998). This is because, in typical social networks, the number of outbound connections from any particular node, be it a user, or a shared photograph, is small. So in even very large graphs, this allows node relevancy to be determined quickly and efficiently.

[0046] A further optimization may be applied: that of proximal weighting and pruning. Figure 3 shows an ideal representation of the concept of proximity in this mechanism, namely, that weights can be looked at as being inversely proportional to the distance. In Figure 3, each node A thru E is assumed to be floating in space, and each node repels other nodes with equal intensity, and is connected to other nodes with a coil spring, acting as an attractive force countering the force repelling the nodes. In this ideal case, the relative strength of the spring determines the distance between nodes, and conversely, the spring strength is derivable from the distance, determining the strength of the connection. Proximal weighting can be used to determine relevance: closer nodes are considered to be of more direct relevance than nodes further away. Note that in the general case, the distance metric can be any metric that allows distance to be determined in an n-dimensional Euclidean space. For example, a distance can be calculated between individuals based on the similarity of interests, where each interest would be assigned a value, and the set of interests would form a point in an n-dimension space, where n is the number of interests. Note also that this provides a means to integrate both physical proximity and virtual proximity: physical proximity can be directly expressed as a set of weights in the node structure of the layered linked node database. A sorting using proximal weighting can be applied to a collected list of nodes and connections such that those things 'nearest' reflect also those that are most 'relevant'. This mechanism is applied to virtual nodes in the layered linked node database. The above-described distance between nodes is a representation of virtual distance between virtual nodes, the virtual distance being representative of the strength of the connection between two virtual nodes.

[0047] Proximal pruning can be used in large graphs with a large fan-out to restrict the ranking to a particular sub-graph, while still remaining compatible with aspects of the present invention. The update mechanism is a slight variant of that outlined earlier, where the value is propagated within a layer, and a list of top ranked nodes is collected. This list of top ranked nodes is then used to propagate the value within the layered linked node database, rather than propagating rankings for all nodes. This has the effect of restricting the total number of nodes visited during the application of the update mechanism with the added risk of potentially missing some highly relevant nodes because the nodes have a large number of arcs, or highly weighted arcs in the pruned sub-graph. A further variant may also use only the strongest weighted connections to propagate node rankings, thereby even further pruning the graph. Proximal pruning may be applied within arbitrary layers, rather than to all layers.

[0048] Node rankings can be calculated relative to one or more nodes in the graph rather than globally. Further, these rankings can occur dynamically, rather than performing a static relevancy ranking. As noted earlier, this is possible because the number of nodes actually visited during the ranking process is typically constrained to a small local sub-graph, rather than the entire graph. By performing the ranking

dynamically, changes can have an immediate effect on node rankings. For example, if the value of CI in Figure 4 were changed to a value of 0.5, the next ranking would assign a rank value of 0.5 to node B rather than the value of 0.75. Values can change, for example, based on machine learning; things that are 'close' have a higher weight, and as they move 'closer,' the weight will be increased. By dynamically calculating the ranking, the ranking system responds to local changes immediately, without the cost of global re- ranking, which makes aspects of the present invention not only more responsive, but also more scalable. This last point is particularly important for extremely large graphs: a large number of changes to graphs are possible because each change is local, and effects only a local sub-graph.

[0049] The dynamic nature of the node ranking calculation can be used to provide the system with a means to determine temporal relevancy of a node, or a degree of machine learning capability. The concept is best described by referring to Figure 3, but where the springs, instead of having an ideal structure, with a fixed weight, are imperfect and subject to fatigue. This means that over time, the strength of the spring will decrease, eventually falling to some minimal value, and the distance between the nodes will increase. In the proximal weighting and pruning model, these nodes would, over time, become steadily less relevant and may even be eliminated altogether. This can be accomplished by degrading the values of the weights in a particular set of arcs every time a weight is updated. The derivative equation for determining a node ranking then becomes N. = ^E^N _j dt where d is the decay factor, and t is time. This decay can be j

thought of as introducing to the system the ability to slowly 'forget' a relationship, and naturally models the mobile device users' own patterns.

[0050] Note that in addition to the decay factor, some updates may increase the weights of a given arc. For example, in Figure 2, a general update rule might be that every time user (F4) visits a given place (PI), the weight of the connection is increased by 0.05, up to a maximum value. This has the effect of increasing the weight of the spring in Figure 3, thereby decreasing the distance between nodes, and thereby increasing relevance. This capability can be exploited to dynamically learn and react to updates to actions by a mobile device user. For example, continual searches for Japanese restaurants may increase the strength of the weight on the arc from the user to the set of Japanese restaurants in the layered linked node database, or to the term 'Japanese'. In the first case, it would result in Japanese restaurants being ranked higher, in terms of relevance, than other restaurants; in the later case, it might affect rankings for all things Japanese: it is reasonable to assume that someone who is interested in Japanese food may also be interested in Japanese movies. These are not mutually exclusive.

[0051] Referring to Figure 8, the present invention, in a preferred embodiment, using multiple Data Storage units 806, a large in-memory virtual database 803, multiple nodes 804, multiple arcs 805, and multiple Ranking Analysis Engines 802, is a scalable, dynamic, temporally sensitive mechanism for determining relevancy of nodes in a layered linked node database. Unlike extant mechanisms, the system may be used with extremely large layered linked node databases with little impact on performance. Those skilled in the relevant art will note that the combination of strengthening and decaying connections allows the system to directly and naturally mirror the interests of the mobile device users 801. The strengthening and decay factors provide a degree of machine learning that automatically adjusts the relevancy of nodes according to local updates to the virtual database 803 that are immediately visible and usable by the Ranking Analysis Engine instances 802. In the context of mobile device users, those skilled in the relevant art will appreciate that the present invention represents a significant improvement over existing mechanisms by taking advantage of the ability for modern mobile devices to continually interact with the layered linked node database, and by taking advantage of the ability to determine the current location of the mobile device user. The system is sensitive to social, geospatial and temporal relevance.

[0052] Those skilled in the relevant art will further appreciate that the present invention is not constrained to use within the context of mobile devices. The mechanism is a generally applicable node ranking mechanism for large layered linked node databases with a significant number of variant applications. For example, the present invention is directly applicable to domains such as recommending relevant news articles,

recommending products, or targeting advertisements. In all cases, the ability to represent the global aggregate ranking in a dynamic way improves upon the state of the art.

[0053] What is claimed: