短词散列

摘要

在一个实施方式中，服务器接收搜索查询；服务器基于所接收的搜索查询确定搜索词，每个搜索词包括前缀和后缀；对于搜索词中的每一个，服务器基于每个搜索词的前缀和后缀生成第一二进制数，并且通过散列第一二进制数从数据存储中访问和检索每个搜索词的搜索结果；服务器也聚合各个搜索词的搜索结果。

说明书

技术领域

本公开内容总体涉及社交网络系统。

背景技术

可包括社交网站的社交网络系统能够使其用户(诸如，个人或组织) 与其交互并且通过其彼此交互。随着用户输入，社交网络系统可以在社交 网络系统中创建和储存与用户相关的用户资料。用户资料可包括用户的人 口统计信息、通信信道信息以及个人兴趣信息。随着用户输入，社交网络 系统还可以创建和储存该用户与社交网络系统的其他用户之间的关系记 录，并且为促进两个用户或多个用户之间的社交提供服务(例如，涂鸦墙 (wallpost)、照片共享、活动组织、发消息、游戏或广告)。

社交网络系统可以通过一个或多个网络将与其服务相关的内容或消 息发送至用户的手机或其他计算设备。用户还可以在用户的手机或其他计 算设备上安装软件应用程序，用于访问用户的用户资料以及社交网络系统 内的其他数据。社交网络系统可生成一组个性化的内容对象以显示给用 户，诸如，连接至该用户的其他用户的集合的故事的新闻馈送。

发明内容

具体实施方式描述了基于搜索词的结构为数据库编索引的方法。具体 实施方式可以表示具有二进制数的搜索词以及通过散列二进制数的搜索 词对搜索结果进行索引。代替使用固定长度用于二进制数表示搜索词，具 体实施方式可以通过为每个搜索词确定每个搜索词的前缀和后缀，减小二 进制数的长度，并且至少部分基于每个搜索词的后缀的对象类型确定表示 每个搜索词的二进制数的长度。因而，具体实施方式可以用表示搜索词的 长度较短的二进制数减小为搜索词编索引的散列表的大小。

附图说明

图1示出了与社交网络系统相关联的示例网络环境。

图2示出了示例性社交图谱。

图3示出了基于搜索词的结构为数据库编索引的示例性方法。

图4示出了示例计算机系统。

具体实施方式

图1示出了与社交网络系统相关联的示例网络环境100。网络环境100 包括通过网络110彼此连接的用户101、客户端系统130、社交网络系统 160、及第三方系统170。尽管图1示出了用户101、客户端系统130、社 交网络系统160、第三方系统170以及网络110的具体布置，但是本公开 考虑了用户101、客户端系统130、社交网络系统160、第三方系统170 以及网络110的任何合适的布置。作为实例并非限制性方式，客户端系统 130、社交网络系统160以及第三方系统170中的两个或更多可绕开网络 110直接彼此连接。作为另一实例，客户端系统130、社交网络系统160 以及第三方系统170中的两个或更多可物理地或逻辑地整体或部分共同位 于同一位置。此外，尽管图1示出了用户101、客户端系统130、社交网 络系统160、第三方系统170以及网络110的具体数量，但是本公开考虑 用户101、客户端系统130、社交网络系统160、第三方系统170以及网络 110的任何合适的数量。作为实例并非限制性方式，网络环境100可包括 多个用户101、客户端系统130、社交网络系统160、第三方系统170以及 网络110。

在具体实施方式中，用户101可以是与社交网络系统160或通过社交 网络系统160交互或者通信的个体(个人用户)、实体(例如，企业、商 家或第三方应用)或者(例如，个体的或者实体的)群体。在具体实施方 式中，社交网络系统160可以是承载在线社交网络的网络可寻址计算机系 统。社交网络系统160可生成、存储、接收、以及发送社交网络数据，例 如，用户资料数据、概念资料数据、社交图谱信息、或者与在线社交网络 有关的其他合适数据。社交网络系统160可由网络环境100的其他组件直 接或者经由网络110访问。在具体实施方式中，社交网络系统160可包括 授权服务器(或其他合适的组件)，其允许用户101选择参加还是退出使 他们的动作被社交网络系统160记录或者与其他系统(例如，第三方系统 170)共享，诸如，通过设定适当的隐私设置。用户的隐私设置可以确定 与用户相关的什么信息可被记录，可以如何记录与用户相关的信息，何时 可以记录与用户相关的信息，谁可以记录与用户相关的信息，与用户相关 的信息可以与谁共享，以及记录或分享与用户相关的信息的目的是什么。 在适当的情况下，认证服务器可以用于通过嵌段、数据散列、匿名化、或 其他适用技术强制执行社交网络系统30的用户的一个或多个的隐私设置。 在具体实施方式中，第三方系统170可以是承载网站和应用程序的网络可 寻址计算机系统。第三方系统170可生成、存储、接收、以及发送第三方 系统数据，例如，网页、文本、图像、视频、音频、或应用程序。第三方 系统170可由网络环境100的其他组件直接或者经由网络110访问。在具 体实施方式中，一个或多个用户101可使用一个或多个客户端系统130访 问数据、将数据发送至社交网络系统160或第三方系统170、以及从社交 网络系统160或第三方系统170接收数据。客户端系统130可直接、经由 网络110或经由第三方系统访问社交网络系统160或第三方系统170。作 为实例并非限制性方式，客户端系统130可通过社交网络系统160访问第 三方系统170。客户端系统130可以是任意合适的计算设备，诸如，个人 计算机、便携式计算机、蜂窝电话、智能电话或平板计算机。

本公开内容考虑任意合适的网络110。作为实例并非限制性方式，网 络110的一个或多个部分可以包括自组织网络、内联网、外联网、虚拟专 用网络(VPN)、局域网(LAN)、无线局域网(WLAN)、广域网(WAN)、 无线广域网(WWAN)、城域网(MAN)、因特网的一部分、公共交换电 话网的一部分(PSTN)、蜂窝电话网络、或它们的两个或多个的组合。网 络110可以包括一个或多个网络110。

链路150可将客户端系统130、社交网络系统160以及第三方系统170 连接到通信网络110或者彼此连接。本公开内容考虑任意合适的链路150。 在具体实施方式中，一个或多个链路150包括一个或多个有线线路(诸如， 数字用户线路(DSL)或者有线电缆数据服务发送规范(DOCSIS))、无 线链路(诸如，Wi-Fi或者微波存取全球互通(WiMAX))、或者光学链路 (诸如，同步光学网络(SONET)或者同步数字体系(SDH))。在具体实 施方式中，一个或多个链路150各自包括自组织网络、内联网、外联网、 VPN、LAN、WLAN、WAN、WWAN、MAN、互联网的一部分、PSTN 的一部分、以蜂窝技术为基础的网络、以卫星通信技术为基础的网络、另 一个链路150或者两个或者多个此类链路150的组合。在整个网络环境100 中链路150不必相同。就一方面或者多方面而言，一个或多个第一链路150 可不同于一个或多个第二链路150。

图2示出了示例性社交图谱200。在具体实施方式中，社交网络系统 160可在一个或多个数据存储中储存一个或多个社交图谱200。在具体实 施方式中，社交图谱200可以包括多个结点-其可以包括多个用户结点202 或多个概念节点204-以及连接节点的多个矢线206。为了启发式的目的， 以二维直观图示出了图2中示出的示例性社交图谱200。在具体实施方式 中，社交网络系统160、客户端系统130、或第三方系统170可以访问社 交图谱200和合适应用的相关的社交图谱信息。例如，在数据存储(诸如， 社交图谱数据库)中社交图谱200的节点和矢线可被储存为数据对象。此 类数据存储可包括社交图谱200的节点或矢线的一个或多个可搜索或可查 询的索引。

在具体实施方式中，用户结点202可以对应于社交网络系统160的用 户。作为实例并非限制性方式，用户可以是与社交网络系统160或者通过 社交网络系统160进行交互或者通信的个体(个人用户)、实体(例如， 企业、公司或者第三方应用)或者(例如，个人或者实体的)群体。在具 体实施方式中，当用户使用社交网络系统160注册账号，社交网络系统160 可以创建对应于该用户的用户节点202，并且在一个或多个数据存储中储 存用户节点202。在适当情况下，本文中所描述的用户和用户节点202可 以称为注册用户以及与注册用户相关的用户节点202。此外或者作为可替 换的，在适当情况下，本文中所描述的用户和用户节点202可以称为没有 注册社交网络系统160的用户。在具体实施方式中，用户节点202可以与 用户提供的信息或者各种系统(包括社交网络系统160)收集的信息相关。 作为实例并非限制性方式，用户可以提供他或她的姓名、资料图片、联系 信息、生日、性别、婚姻状况、家庭状况、工作情况、教育背景、偏好、 兴趣或其他人口统计信息。在具体实施方式中，用户节点202可以与对应 于与用户相关的信息的一个或多个数据对象相关。在具体实施方式中，用 户节点202可对应于一个或多个网页。

在具体实施方式中，概念节点204可对应于一个概念。作为实例并非 限制性方式，一个概念可对应于一个地点(诸如，电影院、餐馆、地标或 城市)；网站(诸如，与社交网络系统160相关的网站或者与网络应用服 务器相关的第三方网站)；实体(诸如，个人、公司、群体、运动队或名 人)；位于社交网络系统160中或外部服务器(诸如，网络应用服务器) 上的资源(诸如，音频文件、视频文件、数码相片、文本文件、结构化文 档或应用程序)；不动产或知识产权(诸如，雕塑、绘画、电影、游戏、 歌曲、想法、照片或书面著作)；游戏；活动；想法或理论；另一个合适 的概念；或者两个以上此类概念。概念节点204可以与用户提供的概念信 息或者通过各种系统(包括社交网络系统160)收集的信息相关。作为实 例并非限制性方式，概念信息可包括姓名或题目；一个或多个图像(例如， 书的封面的图像)；位置(例如，地址或地理位置)；网站(其可以与URL 相关)；联系信息(例如，电话号码或电子邮件地址)；其他合适的概念信 息；或者此类信息的任何合适的结合。在具体实施方式中，概念节点204 可以与对应于与概念节点204相关的信息的一个或多个数据对象相关。在 具体实施方式中，概念节点204可对应于一个或多个网页。

在具体实施方式中，社交图谱200中的节点可以表示网页(其可被称 为“资料页面”)或者由网页表示。资料页面可以由社交网络系统160承 载或者可访问社交网络系统160。资料页面还可以在与第三方服务器170 相关的第三方网站上承载。作为实例并非限制性方式，对应于具体的外部 网页的资料页面可以是具体的外部网页，并且资料页面可以对应于具体的 概念节点204。资料页面可以是所有人或者其他用户的选择子集可见的。 作为实例并非限制性方式，用户节点202可具有对应的用户资料页面，其 中，对应的用户可以添加内容，做出声明或者他或她自己的其他表达。作 为另一个实例并非限制性方式，概念节点204可具有对应的概念资料页面， 其中，一个或多个用户可添加内容，做出声明或者表达他们的想法，具体 地，涉及与对应于概念节点204的概念。

在具体实施方式中，概念节点204可以表示第三方网页或者由第三方 系统170承载的资源。第三方网页或资源可包括，在其他元素、内容、可 选择的或其他图标、或者表示动作或活动的其他中间能实行的对象(例如， 其可以在JavaScript、AJAX或PHP编码中实施)中。作为实例并非限制 性方式，第三方网页可包括可选择的图标，诸如，“喜欢”、“登记”、“吃”、 “推荐”或者另一个合适的动作或活动。浏览第三方网页的用户可以通过 选择一个图标(例如，“吃”)来执行动作，导致客户端系统130将指示用 户动作的消息发送至社交网络系统160。响应于该消息，社交网络系统160 可以在对应于用户的用户节点202与对应于第三方网页或资源的概念节点 204之间创建矢线(例如，“吃”矢线)并且在一个或多个数据存储中储存 矢线206。

在具体实施方式中，社交图谱200中的一对节点可以通过一个或多个 矢线206彼此连接。连接一对节点的矢线206可以表示该对节点之间的关 系。在具体实施方式中，矢线206可包括或表示一个或多个数据对象或者 对应于一对节点之间的关系的属性。作为实例并非限制性方式，第一用户 可以指示第二用户是第一用户的“好友”。响应于该指示，社交网络系统 160可以将“好友请求”发送至第二用户。如果第二用户确认该“好友请 求”，则社交网络系统160可以在社交图谱200中创建将第一用户的用户 节点202连接至第二用户的用户节点202的矢线206，并且在一个或多个 数据存储中储存矢线206作为社交图谱信息。在图2的实例中，社交图谱 200包括指示用户“A”与用户“B”的用户节点202之间的好友关系的矢 线206，以及指示用户“C”与用户“B”的用户节点202之间的好友关系 的矢线。尽管本公开内容描述或示出了具有连接具体用户节点202的具体 属性的具体矢线206，但是本公开内容考虑了具有连接用户节点202的任 何合适属性的任何合适的矢线206。作为实例并非限制性方式，矢线206 可以表示友谊、家庭关系、公司或工作关系、爱好者关系、粉丝关系、访 客关系、客户关系、上级/下属关系、相互关系、非相互关系、另一个类型 合适的关系或者两个以上此类关系。此外，尽管本公开内容总体将节点描 述为被连接的，但是本公开内容还将用户或概念描述为被连接的。在本文 中，在适当情况下，参考连接的用户或概念可以称为对应于通过一个或多 个矢线206在社交图谱200中被连接的这些用户或概念的节点。

在具体实施方式中，用户节点202与概念节点204之间的矢线206可 以表示由与用户节点202相关的用户向与概念节点204相关的概念执行的 具体动作或活动。作为实例并非限制性方式，如图2中所示，用户可以“喜 欢”、“参加”、“播放”、“收听”、“烹饪”、“工作”或“观看”概念，其中 的每个可以对应于矢线的类型或子类型。例如，对应于概念节点204的概 念资料页面可包括可选择的“登记”图标(诸如，可点击的“登记”图标) 或者可选择的“添加到收藏夹”图标。类似地，在用户点击这些图标之后， 响应于对应于各自动作的用户的动作，社交网络系统160可以创建“收藏 夹”矢线或“登记”矢线。作为另一个实例并非限制性方式，用户(用户 “C”)可以使用具体的应用程序(SPOTIFY，它是在线音乐应用程序)收 听具体的歌曲(“RambleOn”)。在该情况下，社交网络系统160可以在对 应于用户的用户节点202与对应于歌曲和应用程序的概念节点204之间创 建“收听”矢线206和“使用”矢线(如图2中所示)，以指示用户听过 该歌曲并且使用过该应用程序。此外，社交网络系统160可以在对应于歌 曲和应用程序的概念节点204之间创建“播放”矢线206(如图2中所示)， 以指示通过具体的应用程序播放了具体的歌曲。在该情况下，“播放”矢 线206对应于在外部音频文件(歌曲“Imagine”)上通过外部应用程序 (SPOTIFY)执行的动作。尽管本公开内容描述了具有连接用户节点202 与概念节点204的具体属性的具体矢线206，但是本公开内容考虑了具有 连接用户节点202和概念节点204的任何合适属性的任何合适的矢线206。 此外，尽管本公开内容描述了表示单一关系的用户节点202与概念节点 204之间的矢线，但是本公开内容考虑了表示一个或多个关系的用户节点 202与概念节点204之间的矢线。作为实例并非限制性方式，矢线206可 以表示用户喜欢并且以具体的概念使用了矢线206。可替换地，另一个矢 线206可以表示用户节点202与概念节点204之间(如图2中示出的用户 “E”的用户节点202与“SPOTIFY”的概念节点204之间)的每个类型 的关系(或者多个单一关系)。

在具体实施方式中，社交网络系统160可以在社交图谱200中的用户 节点202与概念节点204之间创建矢线206。作为实例并非限制性方式， 观看概念资料页面的用户(诸如，通过使用网页浏览器或通过用户的客户 端系统130承载的专用应用程序)可以指示他或她通过点击或选择“喜欢” 图标喜欢通过概念节点204表示的概念，这可使用户的客户端系统130将 指示用户对与概念资料页面相关的概念的喜欢的消息发送至社交网络系 统160。响应于该消息，社交网络系统160可以在与用户相关的用户节点 202与概念节点204之间创建矢线206，如所示出的，通过用户与概念节 点204之间的“喜欢”矢线206。在具体实施方式中，社交网络系统160 可在一个或多个数据存储中储存矢线206。在具体实施方式中，响应于具 体的用户动作矢线206可以自动地由社交网络系统160形成。作为实例并 非限制性方式，如果第一用户上传图片，观看电影或者听歌，则矢线206 可在对应于第一用户的用户节点202与对应于这些概念的概念节点204之 间形成。尽管本公开内容描述了以具体的方式形成具体矢线206，但是本 公开内容考虑了以任何合适的方式形成任何合适的矢线206。

另外，任何两个节点之间的分离度被定义为从一个节点到另一节点跨 越社交图谱所需的最小跳数(或者矢线)。两个节点之间的分离度可被视 为由社交图谱中的两个节点表示的用户或者概念之间的关联性的测量。

如前所述，社交网络系统可以在一个或多个数据存储中存储社交图谱 信息和涉及信息的其他社交网络系统。在具体实施方式中，可根据具体数 据结构组织数据存储中存储的信息。每个数据存储可以是相关的、直列的、 相关的或者其他适当的数据库。具体实施方式考虑任何合适类型的数据 库。此外，可通过独立服务器或独立物理位置保持每个数据存储(或分区)。 具体实施方式可提供能够使社交网络系统、客户端系统或者第三方系统管 理、检索、修改、添加或者删除存储在数据存储中的信息的接口。

提交至数据库的搜索查询可以包括一个或多个关键字短语，诸如 “Pi”、“唐顿庄园”、“NBA全明星赛”、或“世界上最高的山”。数据库可 以通过散列关键字短语为关键字短语的搜索结果编索引。例如，数据库的 索引服务器可以通过将散列函数应用到所得到的散列值的关键字短语来 存储、修改、检索、或删除关键字短语的搜索结果，并且在与得到的散列 值对应的位置处的数据库中存储或查寻搜索结果。即，数据库的搜索索引 可以包括与散列函数相关的散列表。然而，当关键字短语长度很长时，仅 散列关键字短语就可能产生数据库的非常大的搜索索引，并且在访问存储 在数据库中的数据中会引起较高的成本或较低的性能。具体实施方式描述 了减小搜索索引的大小的方法。具体实施方式可以确定数据库的搜索查询 的一个或多个搜索词，并且基于搜索词的结构为数据库编索引。

图3示出了基于搜索词的结构为数据库编索引的示例性方法300。可 以由社交网络系统或者包括一个或多个数据存储或数据库的任何合适的 系统的一个或多个计算设备(例如，服务器)实现300的方法。该方法300 可从步骤310开始。在具体实施方式中，在步骤310中，社交网络系统的 一个或多个计算设备可以接收搜索查询。例如，接收的搜索查询可以包括 用户通过社交网络系统承载的PHP(超文本预处理器)处理提交的结构化 或基本非结构化的文本串。例如，所接收的搜索查询可以是“谁是John 和Bob共同的朋友？”、“谁在该照片中加标签？”、“寻找SanCarlos，CA 附近有意思的地方”、“我的朋友中谁在该餐馆登记？”、或者“谁喜欢该 张贴？”。

在具体实施方式中，在步骤320中，社交网络系统的一个或多个计算 设备可以基于所接收的搜索查询确定一个或多个搜索词。在具体实施方式 中，每个搜索词可以包括前缀和后缀。

例如，对于所接收的搜索查询“谁是John和Bob共同的朋友？”，计 算设备可以确定“John”的用户标识符<177>以及“Bob”的用户标识符 <213>。计算设备可以确定所接收的搜索查询可由两个搜索词“朋友： <177>”和“朋友：<213>”组成。每一个确定的搜索词包括用户标识符 (<177>或<213>)中的前缀“朋友：”(即，…的朋友)以及后缀。每个 搜索词的预期搜索结果可以包括用户标识符的列表(例如，是用户<177> 的朋友的用户的列表)。计算设备可以通过将与AND算子应用于两个确定 的搜索词而确定所接收的搜索查询的结果：(AND朋友：<177>朋友： <213>)。

例如，计算设备可以确定所接收的搜索查询“谁在这张照片中加标签” 可由具有“这张照片”的照片标识符<65199>中的前缀“tagged_in_photo” (即，在照片中加标签的用户)和后缀的搜索词“tagged_in_photo:<65199>” 组成。搜索词的预期结果可以包括与在照片<65199>中加标签的用户对应 的用户标识符的列表。

例如，计算设备可以确定所接收的搜索查询“寻找SanCarlos，CA附 近有意思的地方”可由搜索词“places_in:<752039>”组成，该搜索词具有 前缀“places_in”(地图瓦片(maptile)中的位置)，以及与“SanCarlos,CA” 对应的地图瓦片标识符<752039>。在此，地图可以表示地理区域，诸如， 世界、世界的一部分、或任何合适的区域。地图可被分成地图瓦片，其中， 每个地图瓦片表示地图的特定地理区域。例如，与SanCarlos,CA对应的 地图瓦片<752039>可以包括具有地理坐标中的四角(37.52,-122.24)、(37.52, -122.30)、(37.47,-122.30)、以及(37.47,-122.24)的矩形区域。搜索词 “places_in:<752039>”的预期结果可以包括地点(或任何合适的概念)的 标识符的列表，其中，每个地点(或概念)在地图瓦片<752039>的矩形区 域内具有位置。

在具体实施方式中，在步骤330中，为每个搜索词，计算设备可以基 于每个搜索词的前缀和后缀生成第一二进制数。计算设备可以基于前缀生 成第二二进制数并且基于后缀的对象类型生成第三二进制数。计算设备可 以通过连结第二二进制数和第三二进制数生成第一二进制数。

计算设备可以首先基于每个搜索词的前缀生成每个搜索词的第二二 进制数。例如，计算设备可以将搜索词的前缀映射至具有10位的长度的 第二二进制数。第二二进制数的10位的长度可以使第二二进制数表示高 达大约1,000(2¹⁰)个不同的前缀，诸如，先前描述的“朋友：”、 “tagged_in_photo：”以及“places_in：”。前缀的其他的实例可以包括 “posts_of:”(用户的张贴)、“commenters_of”(关于张贴进行评论的用 户)、以及“likers_of”(喜欢张贴、照片、或任何合适的概念的用户)。具 体实施方式考虑搜索词的任何合适的前缀。计算设备可以访问存储在社交 网络系统的数据存储中的映射表并且查寻表示特定前缀的特定10位的二 进制数的映射表。

计算设备可以基于每个搜索词的后缀或每个搜索词的后缀对象类型 生成每个搜索词的第三二进制数。计算设备可以基于每个搜索词的后缀的 对象类型确定第三二进制数的长度。计算设备可以确定特定对象类型的第 三二进制数的长度因此长度足够大以唯一表示存储在社交网络系统中的 特定对象类型的所有合理的对象。第三二进制数的长度也可足够大到两倍 以上以唯一表示特定对象类型的所有的合理对象以避免与散列函数相关 联的冲突。在此，冲突可以表示提供给散列函数的两个不同的输入值(散 列关键字)可能产生相同结果(散列值)。冲突不具有索引期望的一对一 映射特性。例如，计算设备可以生成用户标识符的后缀的37位二进制数。 即，用户标识符可以转换成37位的二进制数。37位二进制数足以唯一表 示社交网络系统的2¹⁵个不同的用户。对于另一实例，计算设备可以生成 概念标识符(例如，地点的标识符)的后缀的64位二进制数。即，概念 标识符可以转换成64位的二进制数。64位二进制数足以唯一表示社交网 络系统的2³⁰个不同的概念节点。对于又一实例，计算设备可以生成地图 瓦片标识符的后缀的32位二进制数。即，地图瓦片标识符可以转换成32 位的二进制数。32位二进制数足以唯一表示存储在社交网络系统中的地图 的2¹⁵个不同的地图瓦片。具体实施方式考虑了任何合适的后缀对象类型。 例如但不限于，后缀对象类型可对应于用户、地点、概念、地图瓦片、张 贴、照片、地点、应用程序、事件、网页、或视频。

在具体实施方式中，计算设备可以通过连结第二二进制数和第三二进 制数生成第一二进制数。例如，搜索词“朋友：<177>”的第一二进制数 可以包括通过表示后缀<177>的37位(第三)二进制数连结的表示前缀“朋 友：”的10位(第二)二进制数。因此，搜索词“朋友：<177>”的第一 二进制数具有47位的长度。对于另一实例，搜索词 “tagged_in_photo:<65199>”的第一二进制数可以包括通过表示后缀 <65199>的64位(第三)二进制数连结的表示前缀“tagged_in_photo:”的 10位(第二)二进制数。因此，搜索词“tagged_in_photo:<65199>”的第 一二进制数具有74位的长度。对于又一实例，搜索词“places_in:<752039>” 的第一二进制数可以包括通过表示后缀<752039>的32位(第三)二进制 数连结的表示前缀“places_in：”的10位(第二)二进制数。因此，搜索 词“places_in:<752039>”的第一二进制数具有42位的长度。

在具体实施方式中，在步骤340中，对于每个搜索词，计算设备可以 通过散列第一二进制数从一个或多个数据存储访问和检索每个搜索词的 一个或多个搜索结果。计算设备可以用合适的散列函数散列第一二进制 数。即，数据存储可以用与散列函数相关联的一个或多个散列表为与每个 搜索词对应的第一二进制数的搜索结果编索引。在一些实施方式中，在用 合适的散列函数散列第一二进制数之前，计算设备可以将可逆变换功能应 用到第一二进制数。在这种情况下，第一二进制数可具有“起伏”特性因 为大多数“1”位在第一二进制数中的位的某个范围内。可逆变换功能可 以将起伏的第一二进制数变换成更均匀分布的形式(例如，“1”位更均匀 分布在第一二进制数的所有位中)，因而避免与散列函数相关联的合理的 冲突。在此，可逆函数F具有x＝F-1(F(x))的行为，其中，F-1是F的 倒数。

在具体实施方式中，数据存储可以保留多个散列表。每个散列表可以 为特定后缀对象类型的搜索词的搜索结果编索引。即，数据存储可以基于 搜索词的后缀的对象类型为搜索结果编索引。例如，数据存储可以保留具 有用户对象类型的后缀的搜索词(例如，“朋友：<177>”，其中，后缀<177> 是用户标识符)的散列表。数据存储可以维护具有概念对象类型的后缀的 搜索词(例如，“tagged_in_photo:<65199>”，其中，<65199>是概念标识符) 的另一散列表。数据存储可以维护具有地图瓦片对象类型的后缀的搜索词 (例如，“places_in:<752039>”，其中，<752039>是地图瓦片标识符)的 又一散列表。此外，每个散列表可以包括可以为搜索词的前缀编索引的一 个或多个前缀映射。在一个实施方式中，每一个数据存储可被配置为储存 单个对象类型的对象。例如，数据存储可被配置为储存用户对象(和与每 个存储的用户对象相关联的信息)。另一数据存储可被配置为储存概念对 象(和与每个存储的概念对象相关联的信息)。第三数据存储可被配置为 储存地图瓦片对象(和与每个存储的地图瓦片对象相关联的信息)。每一 个数据存储可以包括上述一个或多个散列表。

与之相比，在没有基于上述每个搜索词的后缀对象类型使用不同长度 的二进制数来表示搜索词的情况下，长的二进制数可以用于表示任意后缀 (或缺少后缀)对象类型的任意搜索词。例如，96位的二进制数可用于唯 一表示社交网络系统的任意搜索词。然而，用于为96位的二进制数表示 的搜索词编索引的相应的单个散列表会比用于用先前描述的较短的二进 制数为搜索词编索引的散列表大很多。即，具体实施方式可以确定搜索词 的前缀和后缀中的搜索词的结构，并且基于后缀的对象类型表示具有较短 的二进制数的搜索词，因而减小了散列表的大小。例如，具体实施方式可 以为社交网络系统将散列表的总大小减小20％以上。

在一个实施方式中，计算设备可以生成第一二进制数而不生成之前所 描述的第二二进制数和第三二进制数。例如，如果计算设备不能确定搜索 词的前缀或后缀，计算设备可以生成表示搜索词的64位的二进制数。计 算设备可以通过散列64位的二进制数访问数据存储并且从数据存储检索 搜索词的一个或多个搜索结果。

在具体实施方式中，在步骤350中，计算设备可以聚合各个搜索词的 搜索结果。例如，对于先前所描述的所接收的搜索查询“谁是John和Bob 共同的朋友”，计算设备可以从搜索词“朋友：<177>”的数据存储中检索 第一组结果(例如，用户<1>、<3>、<11>)。计算设备可以从搜索词“朋 友：<213>”的数据存储检索第二组结果(例如，用户<1>、<11>、<17>、 <28>)。计算设备可以通过将与操作应用于第一组和第二组结果聚合搜索 结果，从而产生聚合搜索结果(例如，用户<1>、<11>)。

在适当情况下，具体实施方式可重复图3中的方法的一个或多个步骤。 尽管本公开内容描述并示出了图3的方法的具体步骤以具体顺序发生，但 是本公开内容考虑图3的方法的任何合适的步骤以任何合适的顺序发生。 此外，虽然本公开内容描述并且示出了执行图3中的方法的具体步骤的具 体部件、装置或者系统，但是本公开内容考虑了执行图3中的方法的任何 合适步骤的任何合适部件、装置或者系统的任何合适的组合。

图4示出了示例性计算机系统400。在具体实施方式中，一个或多个 计算机系统400执行本文描述或示出的一种或多种方法的一个或多个步 骤。在具体实施方式中，一个或多个计算机系统400提供本文描述或示出 的功能。在具体实施方式中，运行在一个或多个计算机系统400上的软件 执行本文描述或示出的一种或多种方法的一个或多个步骤或者提供本文 描述或示出的功能。具体实施方式包括一个或多个计算机系统400的一个 或多个部分。在本文中，在适当情况下，参考计算机系统可包含计算设备。 此外，在适当情况下，参考计算机系统可包含一个或多个计算机系统。

本公开内容考虑了任何合适数量的计算机系统400。本公开内容考虑 了采用任何合适的物理形式的计算机系统400。作为实例并非限制性方式， 计算机系统400可以是嵌入式计算机系统、片上系统(SOC)、单板计算 机系统(SBC)(诸如，电脑模组(COM)或系统模组(SOM))、台式计 算机系统、便携式或笔记本计算机系统、互动平台、主机、计算机系统网 格、移动手机、个人数字助理(PDA)、服务器、平板计算机系统、或者 这些的两个或更多的组合。在适当情况下，计算机系统400可包括一个或 者多个计算机系统400、为整体式或者分布式、跨多个地点、跨多台机器、 跨多个数据中心或者驻留在可包括一个或者多个网络中的一个或者多个 云部件的云中。在适当情况下，一个或者多个计算机系统400可执行本文 所描述或者示出的一种或者多种方法的一个或者多个步骤，而基本没有空 间和时间限制。作为实例并非限制性方式，一个或者多个计算机系统400 可实时地或以批量模式执行本文所描述或者示出的一种或者多种方法的 一个或者多个步骤。在适当情况下，一个或者多个计算机系统400可在不 同时间或者在不同地点执行本文所描述或者示出的一种或者多种方法的 一个或者多个步骤。

在具体实施方式中，计算机系统400包括处理器402、存储器404、 存储介质406、输入/输出(I/O)接口408、通信接口410和总线412。尽 管本公开内容描述和示出了具有按照特定布置的特定数量的特定组件的 特定计算机系统，但是本公开内容考虑了具有按照任何合适布置的任何合 适数量的任何合适组件的任何合适的计算机系统。

在具体实施方式中，处理器402包括用于执行诸如装配计算机程序的 指令的硬件。作为实例并非限制性方式，为了执行指令，处理器402可以 从内部寄存器、内部缓存、存储器404或者存储介质406检索(或者取来) 指令；解码和执行它们；然后将一个或多个结果写入内部寄存器、内部缓 存、存储器404或者存储介质406。在具体实施方式中，处理器402可包 括用于数据、指令或地址的一个或多个内部缓存。在适当情况下，本公开 内容考虑了包括任意合适数量的任意合适的内部缓存的处理器402。作为 实例并非限制性方式，处理器402可包括一个或多个指令缓存、一个或多 个数据缓存以及一个或多个转换后备缓冲器(TLB)。指令缓存中的指令 可以是存储器404或者存储介质406中的指令的副本，并且指令缓存可加 速处理器402检索那些指令。在数据缓存中的数据可以是在用于在处理器 402中执行指令操作的存储器404或存储介质406中数据的副本；用于由 在处理器402中执行的后续指令访问或用于写入存储器404或存储介质 406的在处理器402中执行的先前指令的结果；或者其他合适的数据。数 据缓存可加速处理器402读取或者写入操作。TLB可以加速处理器402的 虚拟地址转换。在具体实施方式中，处理器402可包括用于数据、指令或 地址的一个或多个内部寄存器。在适当情况下，本公开内容考虑了包括任 何合适数量的任何合适的内部寄存器的处理器402。在适当情况下，处理 器402可包括一个或多个算术逻辑单元(ALU)；多核处理器；或者包括 一个或多个处理器402。尽管本公开内容描述和说明了特定的处理器，但 是本公开内容考虑了任何合适的处理器。

在具体实施方式中，存储器404包括用于储存处理器402执行的指令 或处理器402操作的数据的主存储器。作为实例并非限制性方式，计算机 系统400可将指令从存储介质406或另一源(诸如，另一计算机系统400) 加载至存储器404。然后，处理器402可将指令从存储器404加载至内部 寄存器或内部缓存。为了执行该指令，处理器402可从内部寄存器或者内 部缓存检索指令并且将它们进行解码。在指令的执行之中或之后，处理器 402可将一个或多个结果(其可以是中间结果或最终结果)写入到内部寄 存器或内部缓存。然后，处理器402可将那些结果中的一个或多个写入到 存储器404。在具体实施方式中，处理器402仅在一个或多个内部寄存器 或内部缓存或存储器404(与存储介质406相反的位置或其他位置)中执 行指令，并且仅在一个或多个内部寄存器或内部缓存或存储器404(与存 储介质406相反的位置或其他位置)中操作数据。一个或多个存储器总线 (每个可包括地址总线和数据总线)可将处理器402耦接至存储器404。 如下所述，总线412可包括一个或多个存储器总线。在具体实施方式中， 一个或多个存储器管理单元(MMU)位于处理器402与存储器404之间， 并且促进由处理器402要求的对存储器404的访问。在具体实施方式中， 存储器404包括随机存取存储器(RAM)。在适当情况下，该RAM可以 是易失性存储器。在适当情况下，该RAM可以是动态RAM(DRAM) 或静态RAM(SRAM)。此外，在适当情况下，该RAM可以是单端口或 多端口的RAM。本公开内容考虑了任何合适的RAM。在适当情况下，存 储器404可包括一个或多个存储器404。尽管本公开内容描述和说明了具 体的存储器，但是本公开内容考虑了任何合适的存储器。

在具体实施方式中，存储介质406包括用于数据或指令的大容量存储 器。作为实例并非限制性方式，存储介质406可包括硬盘驱动(HDD)、 软盘驱动、闪存、光盘、磁光盘、磁带、或通用串行总线(USB)驱动或 者它们的两种或多种的组合。在适当情况下，存储介质406可包括可移除 的或者不可移除的(或固定的)介质。在适当情况下，存储介质406可以 是计算机系统400的内部或外部。在具体实施方式中，存储介质406是非 易失性的固态存储器。在具体实施方式中，存储介质406包括只读存储器 (ROM)。在适当情况下，该ROM可以是掩码编程ROM、可编程ROM (PROM)、可擦PROM(EPROM)、电可擦PROM(EEPROM)、电可改 写ROM(EAROM)或闪存或这些的两个或更多的组合。本公开内容考虑 了采用任何合适物理形式的大容量存储介质406。在适当情况下，存储介 质406可包括促进处理器402与存储介质406之间通信的一个或多存储器 控制单元。在适当情况下，存储介质406可包括一个或多个存储介质406。 尽管本公开内容描述和说明了具体的存储器，但是本公开内容考虑了任何 合适的存储器。

在具体实施方式中，I/O接口408包括提供用于在计算机系统400与 一个或者多个I/O设备之间进行通信的一个或者多个接口的硬件、软件、 或者硬件和软件。在适当情况下，计算机系统400可包括一个或者多个这 种I/O设备。这些I/O设备的一个或多个可使人员和计算机系统400之间 能够通信。作为实例并非限制性方式，I/O设备可包括键盘、按键、麦克 风、监控器、鼠标、打印机、扫描仪、扬声器、照相机、触控笔、平板、 触摸屏、追踪球、摄影机、其他合适的I/O设备或它们中两个或更多的组 合。I/O设备可包括一个或多个传感器。本公开内容考虑了任何合适的I/O 设备和它们的任何合适的I/O接口408。在适当情况下，I/O接口408可包 括使处理器402能够驱动这些I/O设备中的一个或多个的一个或多个设备 或软件驱动器。在适当情况下，I/O接口408可包括一个或多个I/O接口 408。尽管本公开内容描述和示出了具体的I/O接口，但是本公开内容考 虑了任何合适的I/O接口。

在具体实施方式中，通信接口410包括提供用于在计算机系统400与 一个或者多个其他计算机系统400或者一个或多个网络之间进行通信(诸 如，基于数据包的通信)的一个或者多个接口的硬件、软件、或者硬件和 软件。作为实例并非限制性方式，通信接口410可包括用于与以太网或其 他基于有线网络通信的网络接口控制器(NIC)或网络适配器，或用于与 无线网络(诸如WI-FI网络)通信的无线NIC(WNIC)或无线适配器。 本公开内容考虑了任何合适的网络和它的任何合适的通信接口410。作为 实例而非限制性方式，计算机系统400可与自组织网络、个人区域网 (PAN)、局域网(LAN)、广域网(WAN)、城域网(MAN)或互联网的 一个或多个部分或它们的两个或更多的组合通信。一个或多个这些网络的 一个或多个部分可以是有线的或无线的。作为示例，计算机系统400可与 无线PAN(WPAN)(诸如，BLUETOOTHWPAN)、WI-FI网络、WI-MAX 网络、蜂窝电话网络(诸如，全球移动通信系统(GSM)网络)或其他合 适的无线网络或者这些的两个以上的组合通信。在适当情况下，计算机系 统400可包括用于这些网络中的任何一个的任何合适的通信接口410。在 适当情况下，通信接口410可包括一个或多个通信接口410。尽管本公开 描述和示出了具体的通信接口，但是本公开内容考虑了任何合适的通信接 口。

在具体实施方式中，总线412包括将计算机系统400的部件彼此耦接 的硬件、软件或者硬件和软件。作为实例并非限制性方式，总线412可包 括图形加速端口(AGP)或其他图形总线、增强工业标准架构(EISA)总 线、前端总线(FSB)、HYPERTRANSPORT(HT)互连、工业标准架构 (ISA)总线、INFINIBAND互连、低接脚数(LPC)总线、存储器总线、 微通道结构(MCA)总线、外部设备互连(PCI)总线、PCI快递(PCIe) 总线、串行高级技术附件(SATA)总线、视频电子标准协会局部(VLB) 总线或其他合适的总线或者这些中的两个以上的结合。在适当情况下，总 线412可包括一个或多个总线412。尽管本公开内容描述和示出了具体的 总线，然而本公开内容考虑了任何合适的总线或者互连。

在本文中，在适当情况下，计算机可读非暂时性存储媒体或媒介可包 括一个或多个以半导体为基础的或其他集成电路(IC)(诸如，场可编程 门阵列(FPGA)或应用专用IC(ASIC))、硬盘驱动器(HDD)、混合硬 盘(HHD)、光盘、光盘驱动器(ODD)、磁光盘、磁光盘驱动器、软盘、 软磁盘(FDD)、磁带、固态驱动器(SSD)、RAM驱动器、SECUREDIGITAL 卡或驱动器、任何其他合适的计算机可读非暂时性存储媒体或这些中的两 个以上任何合适的组合。在适当情况下，计算机可读非暂时性存储媒体可 以是易失的、非易失的，或易失和非易失的结合。

在本文中，除非另有明确表示或通过上下文另有表示，否则“或”是 包括性的而不是排除性的。因此，在本文中，除非另有明确表示或通过上 下文的其他表示，否则“A或B”意味着“A、B、或这两者”。此外，除 非另有其他明确表示或通过上下文的其他表示，否则“和”是两者结合及 多个。因此，在本文中，除非另有其他明确表示或通过上下文的其他表示， 否则“A和B”意味着“结合地或分别地A和B”。

本公开内容的范围包括本领域技术人员应当理解的对本文中描述或 示出的示例性实施方式的所有改变、替代、变化、变更以及变形。本公开 内容的范围并不限于本文中描述或示出的示例性实施方式。此外，尽管本 公开内容将本文中各个实施方式描述并且示出为包括具体部件、元件、功 能、操作或步骤，但是本领域普通技术人员应当理解的是，这些实施方式 中的任何一个可包括本文中任何地方描述或示出的任何部件、元件、功能、 操作或步骤的任何组合或排列。此外，所附权利要求中参考的适配于、布 置为、能够、配置为、使能够做、可操作为或有效的执行具体功能的设备 或系统或者设备或系统的部件包括设备、系统、部件，不管是否它或者具 体功能被激活、接通或解锁，只要该设备、系统或部件被如此适配、布置、 能够、配置、能够做、可操作或有效的。