Processing search queries in a network of interconnected nodes

Abstract

A search query to provide a search result may be received, which identifies source and target nodes and an application for generating the search result. The application accesses a data structure holding landmark nodes, which store a shortest path tree in the form of a set of parent links. Each parent link can identify an adjacent vertex node in a shortest path between each node in the data structure and the landmark node. The location of the source node and the target node in the shortest path trees may be identified to the landmark node. For each landmark node, using the identified locations of the target node and source node, a measure of distance between the source node and the target may be generated. The landmark node with the shortest distance may be determined. A search result related to the shortest path tree of that landmark node may be provided.

Description

technical field [0001] The present invention relates to processing search queries, particularly in a network of interconnected nodes. Background technique [0002] There are many situations in which computer networks typically include a very large number of interconnected nodes. A communication network such as Skype represents a large social network for peer-to-peer communication. Figure 1 is a schematic diagram of a small portion of a typical computer network. The network shown includes a number of nodes Ni. Each node may be associated with one or more physical computer devices as shown, for example in the case of node Ni the node is shown associated with a mobile device 2 , a PC 4 and a tablet 6 . Each node is associated with a single user, who in this case may use any of these computer devices to register or log in to a particular network. The nodes are shown interconnected by connections Ci. In the context of a physical network, the connections Ci can be implemented...

AI Technical Summary

Problems solved by technology

[0006] Although landmark-based algorithms do not provide strong theoretical guarantees about the quality of the approximation, they have been shown to perform well in practice scaling up to graphs with millions or even billions of edges with acceptable accuracy and Response times are under one second per query

Images