使用数据结构处理搜索查询

摘要

本发明公开了一种生成存储于计算机存储器中用于在互连节点网络中执行搜索查询时使用的数据结构的方法，其中所述方法包括通过以下步骤选择地标节点并且在所述数据结构中示出所选择的地标节点：从所述网络节点对顶点对的第一样本采样；计算用于每个顶点对的最短路径，每个最短路径包括在所述顶点对中的每个顶点之间的顶点集；标识比任何其它顶点更经常出现于更多最短路径中的第一地标节点；从所述网络顶点去除包括所述第一地标节点的最短路径；并且标识比任何其它剩余顶点出现于更多剩余最短路径中的第二地标节点。本发明涉及一种新地标选择策略的改进，该策略通过所选地标最大化所有最短路径的覆盖。

主权项

一种处理搜索查询以提供搜索结果的方法，所述方法包括：在计算机设备处接收数字消息形式的搜索查询，所述查询标识源节点和目标节点；并且在所述计算机设备处执行用于生成搜索结果的应用，所述应用执行以下步骤：访问一种数据结构，其中每个地标已经随其存储了父链接集形式的最短路径树，其中每个父链接标识邻近的顶点节点；对于每个地标，标识所述源节点和所述目标节点在通向所述地标节点的所述最短路径树中的位置；对于每个地标节点，使用所标识的所述目标节点和所述源节点的位置生成所述源节点与所述目标节点之间的距离的度量；确定具有最短距离的所述地标；以及提供与该地标的所述最短路径树有关的搜索结果；其中通过如下步骤生成距离度量：标识在从所述源节点和所述目标节点到所述地标节点的所述最短路径树中的共同祖先节点；标识在所述源节点与所述共同祖先节点之间的第一路径和在所述共同祖先节点与所述目标节点之间的第二路径中的所有节点对；对所述对中的作为边的任何对定位；标识最短距离的所述边；并且使用所述边确定在所述源节点与所述目标节点之间的距离度量。