[0042] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0043] 应当理解，当在本说明书和所附权利要求书中使用时，术语“包括”指示所描述特征、整体、步骤、操作、元素和/或组件的存在，但并不排除一个或多个其它特征、整体、步骤、操作、元素、组件和/或其集合的存在或添加。
[0044] 还应当理解，在此本发明说明书中所使用的术语仅仅是出于描述特定实施例的目的而并不意在限制本发明。如在本发明说明书和所附权利要求书中所使用的那样，除非上下文清楚地指明其它情况，否则单数形式的“一”、“一个”及“该”意在包括复数形式。
[0045] 还应当进一步理解，在本发明说明书和所附权利要求书中使用的术语“和/或”是指相关联列出的项中的一个或多个的任何组合以及所有可能组合，并且包括这些组合。
[0046] 如在本说明书和所附权利要求书中所使用的那样，术语“若”、“如果”可以依据上下文被解释为“当...时”或“一旦”或“响应于确定”或“响应于检测到”。类似地，短语“如果确定”或“如果检测到[所描述条件或事件]”可以依据上下文被解释为意指“一旦确定”或“响应于确定”或“一旦检测到[所描述条件或事件]”或“响应于检测到[所描述条件或事件]”。
[0047] 为了说明本发明所述的技术方案，下面通过具体实施例来进行说明。
[0048] 在本发明实施例中，为便于说明，将搜索用户的邻近区域的形状设置为矩形区域，在实际应用中，搜索用户的邻近区域的形状可以为任意形状。
[0049] 实施例一
[0050] 参照图1，图1是本发明实施例一提供的用户位置隐私的保护方法的实现流程图，如图所示，该方法包括以下步骤：
[0051] 步骤S101，待发现用户终端接收待发现用户输入的位置隐私需求。
[0052] 在本发明实施例中，所述待发现用户在终端中设置位置隐私需求。
[0053] 步骤S102，待发现用户终端获取搜索用户终端的邻近区域。
[0054] 在本发明实施例中，每一个搜索用户对应一个邻近区域，所述邻近区域是指所述搜索用户终端的位置范围区域，例如，如图2所述所述搜索用户终端u1的邻近区域为矩形区域201，所述搜索用户终端的真实位置位于所述矩形区域中。
[0055] 可选的，步骤S102具体实现过程可以为：服务器将搜索用户的信息生成索引，待发现用户终端每隔预设时间间隔从所述索引下载所述搜索用户的信息，所述搜索用户的信息包括所述搜索用户终端的邻近区域信息。
[0056] 在本发明实施例中，预设时间是待发现用户终端预先设置的时间，例如，待发现用户终端将预设时间设置为1分钟，则待发现用户终端每隔1分钟从所述索引下载所述搜索用户的信息。
[0057] 进一步地，所述索引包括HGrid索引，所述HGrid索引包括网格结构和哈希表，所述网格结构用于存储所述搜索用户的身份信息，所述哈希表用于存储所述搜索用户终端所处位置的邻近区域信息。
[0058] 在本发明实施例中，HGrid包括网格结构和哈希表，所述网格结构用于存储所述搜索用户的身份信息，有助于待发现用户终端找到邻近区域覆盖其真实位置的搜索用户。网格中的每个单元格有两个链表，分别为：pl，用于记录邻近区域部分覆盖该单元格的用户；fl，用于存储邻近区域完全覆盖整个单元格的用户。所述哈希表用于存储搜索用户的邻近区域信息，哈希表中包含用户id和邻近区域的位置。例如，假设搜索用户邻近区域为矩形，哈希表中存储的搜索用户的邻近区域信息为(u1，x1，y1，x2，y2)，其中，u1为搜索用户的id，(x1，y1)为矩形左下角坐标，(x2，y2)为矩形右上角坐标。
[0059] 可选的，所述待发用户终端每隔预设时间间隔从所述索引下载部分或者全部搜索用户的信息。
[0060] 在本发明实施例中，通过将搜索用户的邻近区域组织成一个索引，待发现用户终端可以从索引下载搜索用户的信息，能够高效的找到覆盖待发现用户终端真实位置的搜索用户的邻近区域。
[0061] 步骤S103，待发现用户终端寻找满足所述位置隐私需求的搜索用户列表。
[0062] 在本发明实施例中，所述搜索用户列表包括所述搜索用户的身份信息，若所述搜索用户终端满足所述位置隐私需求，则获取所述搜索用户的身份信息作为所述搜索用户列表。
[0063] 可选的，待发现用户终端计算所有所述搜索用户终端邻近区域的交集，得到所述待发现用户终端的模糊位置信息；若所述模糊位置信息满足所述位置隐私需求，则生成搜索用户列表。
[0064] 在本发明实施例中，所有邻近区域的交集即为所述待发现用户终端的模糊位置，所述模糊位置是根据所述搜索用户终端的邻近区域确定的所述待发现用户终端所处的位置区域，即所述待发现用户终端的真实位置位于所述模糊位置中。所述位置隐私需求指所述待发现用户可接受的模糊位置信息的最小范围，所述模糊位置信息包括所述模糊位置的面积信息，具体的，所述位置隐私需求是指所述待发现用户可接受的所述模糊位置的最小面积。所述模糊位置的面积大于所述待发现用户可接受的模糊位置的最小面积，即为所述模糊位置信息满足所述位置隐私需求。若所述模糊位置信息满足所述位置隐私需求，则获取所述搜索用户的身份信息作为搜索用户列表。
[0065] 在本发明实施例中，设用户u1，u2，u3，…，un通过社交发现软件，例如，微信，可以搜索到用户u，将用户u称为待发现用户，u1，u2，u3，…，un称为搜索用户，即待发现用户u的搜索用户为u1，u2，u3，…，un。定义搜索用户u1，u2，u3，…，un为待发现用户u的足迹集FSu，记为FSu＝{u1,u2,u3,...,un}。每一个搜索用户对应一个邻近区域，计算所有所述邻近区域的交集，得到所述待发现用户终端的模糊位置信息，待发现用户u关于FSu的模糊位置为搜索用户邻近区域的交集，记为 待发现用户u的隐私需求即为待发现用户可接受的模糊位置的最小范围，例如，待发现用户u的隐私需求设置为minu，即待发现用户u可接受的最小模糊位置范围为minu，模糊位置范围大于minu为满足待发现用户u的隐私需求，模糊位置范围不大于minu为不满足待发现用户u的隐私需求。模糊位置和位置隐私需求minu可以为面积值。若所述模糊位置信息满足所述位置隐私需求，则获取所述搜索用户的身份信息作为搜索用户列表。
[0066] 例如，如图2所示，为简便起见，将搜索用户的邻近区域的形状设置为矩形。待发现用户u的搜索用户为u1、u2和u3，终端u的位置包含在搜索用户u1，u2，u3的邻近区域内，则用户u的足迹集为FSu＝{u1,u2,u3}。搜索用户u1、u2和u3的邻近区域分别为图2中的矩形201、202和203，邻近区域201、202和203的交集为区域204，则待发现用户u关于FSu＝{u1,u2,u3}的模糊位置为图中的区域204，即根据搜索用户u1、u2和u3确定的待发送用户u的位置区域为204。设待发现用户设置的隐私需求为minu，若区域204的面积大于minu，则说明模糊位置满足待发现用户u的位置隐私需求，则搜索用户列表中的搜索用户为u1、u2和u3，即u的真实位置在搜索用户u1、u2和u3的邻近区域中。
[0067] 在本发明实施例中，模糊位置信息不满足待发现用户的隐私需求，称待发现用户u存在过度共享攻击，即搜索用户确定的待发现用户的位置区域的面积不大于用户可接受的最小模糊位置面积。为了防止过度共享攻击，需要为待发现用户u找到一个足迹集FSu，使得根据足迹集FSu中的搜索用户的邻近区域计算得到的模糊位置满足隐私需求。
[0068] 在本发明实施例中，需要找到满足待发现用户隐私需求的最大足迹集，即安全的最大足迹集。可选的，通过四栈方法(FBuck)计算满足所述隐私需求的搜索用户，即安全的最大足迹集。所述四栈方法具体包括：
[0069] 获取所述搜索用户的信息，所述搜索用户的信息包括所述搜索用户的身份信息和邻近区域信息，所述邻近区域信息是指所述邻近区域的坐标信息；
[0070] 将所述搜索用户的身份信息和邻近区域信息放入四个栈中；
[0071] 将所述搜索用户的信息按照预设顺序排列；
[0072] 若栈不为空，则访问所述栈中的栈顶元素；
[0073] 根据栈中的元素计算所述邻近区域的交集得到模糊位置信息；
[0074] 若所述模糊位置信息满足所述隐私需求，则生成搜索用户列表；
[0075] 若所述模糊位置信息不满足所述位置隐私需求，则从四个栈中选择删除用户，将所述删除用户从栈中删除；
[0076] 将剩余搜索用户的信息按照预设顺序排列，执行步骤若栈不为空，则访问所述栈中的栈顶元素。
[0077] 例如，假设待发现用户u的真实位置信息用坐标表示，坐标为(x，y)，利用HGrid索引，可以得到覆盖待发现用户真实位置(x，y)的邻近区域所属的搜索用户足迹集FSu，通过四个栈计算FSu中用户组合的相交区域。
[0078] 为了便于理解，首先介绍栈的结构。在本发明实施例中，假设搜索用户的邻近区域为矩形，将矩形的四个边界分别称作左(l)、右(r)、下(b)和上(t)，一个栈代表一种邻近区域边界，分别记为l-buk，r-buk，b-buk和t-buk。每个栈中都分别包含一个搜索用户的ID和一个邻近区域的边界坐标，例如，在l-buk和r-buk中记录的是邻近区域的左下角坐标和右上角坐标中的x值，在b-buk和t-buk中记录的是邻近区域的左下角坐标和右上角坐标中的y值。以邻近区域的边界坐标为关键词，将l-buk和b-buk中的用户ID做非降序排列，将r-buk和t-buk中的用户ID做非升序排列。四个栈顶元素组成的矩形是当前搜索用户组成的最小相交矩形，为待发现用户u的模糊位置信息，如果矩形的面积小于待发现用户的隐私需求minu，则从四个栈顶中选择一个删除用户，将其从每个栈中删除，新的顶部元素将形成一个新的相交矩形，如果新矩形的面积仍然小于minu，则重复上述步骤，直到每个栈均为空或者相交区域的面积不小于minu。
[0079] 参考图3，图3是一个由三个搜索用户u1、u2和u3的邻近区域构成的四个栈的示意图。待发现用户u的三个搜索用户为u1、u2和u3，搜索用户为u1、u2和u3的邻近区域分别为301、302和303，三个搜索用户的邻近区域信息分别为(u1,2,0,6,4,)、(u2,1,1,5,5)和(u3,3,3,
7,7)，四个栈元素如图3所示，四个栈顶元素组成的矩形304是当前搜索用户u1、u2和u3组成的最小相交矩形，为待发现用户u的模糊位置信息，如果矩形304的面积小于待发现用户的隐私需求minu，则从四个栈顶中选择一个删除用户，将其从每个桶中删除，如删除u3，新的顶部元素将形成一个新的相交矩形305，如图4所示，图4是本发明实施例一提供的图3中删除一个搜索用户后的的邻近区域构成的四个栈的示意图，如果新矩形的面积不小于minu，则{u1，u2}是待发现用户u的最大安全足迹集。
[0080] 下面，以邻近区域为矩形为例说明四栈方法FBuck。
[0081] 1.从HGrid索引中获取待发现用户u的足迹集FSu；
[0082] 2.针对FSu中的每一个用户的邻近区域，初始化l-buk，r-buk，b-buk和t-buk；
[0083] 3.将l-buk和b-buk中的元素按非升序排序；
[0084] 4.将r-buk和t-buk中的元素按非降序排序；
[0085] 5.当l-buk不为空时，则
[0086] 6.访问每一个栈中的栈顶元素；
[0087] 7.用每一个栈顶元素组成矩形ur；
[0088] 8.若矩形ur的面积不大于minu，则
[0089] 9.选择一个搜索用户作为待删除搜索用户du；
[0090] 10.从四个桶中和FSu中删除待删除搜索用户du；
[0091] 11.将l-buk,r-buk,b-buk和t-buk中的元素重排序，继续执行步骤5，直至矩形ur的面积小于minu；
[0092] 12.返回FSu中的剩余用户作为安全的最大足迹集合。
[0093] 在本发明实施例中，选择删除用户的基本原则是：选择删除邻近区域边界限制或者将会限制待发现用户模糊位置的搜索用户。在提出选择策略之前，首先定义待发现用户和搜索用户之间的内部距离和外部距离。
[0094] 设待发现用户的足迹集为FSu，FSu中搜索用户的邻近区域相交的矩形为pt，设pt中的边界搜索用户组成的集合为 其中 待发现用户的真实位置在pt中，则对于 内部距离可表示为
[0095] 其中， 是从待发现用户u到搜索用户ui邻近区域边界的最小垂直距离。
[0096] 若待发现用户u在集合 中，则待发现用户u与搜索用户ui的内部距离为从待发现用户u到搜索用户ui邻近区域边界的最小垂直距离，若待发现用户u不在集合 中，则待发现用户u与搜索用户ui的内部距离为无穷。
[0097] 设待发现用户的足迹集为FSu， 是搜索用户ui的邻近区域的四个角，分别为左下角，右下角，左上角，右上角，外部距离可以表示为[0098] 其中，distpu是待发现用户u的真实位
置和邻近区域的角p之间的距离。
[0099] 参照图4，以图4中u和u1为例，u与u1的内部距离为d1，u与u1的外部距离为d2。
[0100] indist(u,ui)值越小表示ui的邻近区域边界限制了模糊位置的大小，因此拥有较小内部距离的用户应早移除。outdist(u,ui)值越小表示ui的邻近区域边界限制了模糊位置的大小，因此拥有较小外部距离的用户应早移除。
[0101] 步骤S104，待发现用户终端获取邻近记录，所述邻近记录是指所述待发现用户终端位于所述搜索用户列表中的搜索用户终端的邻近区域中。
[0102] 在本发明实施例中，设搜索用户列表中的搜索用户为u1，u2，u3，…，un，将待发现用户u终端的邻近记录形式化的定义为{，，，…，}，其中，表示u在u i的邻近 区域内 ，即ui的 邻近区 域包含 u的真 实位置 信息 ，记 为其中，locu是u的真实位置， 是ui的邻近区域。
[0103] 步骤S105，待发现用户终端将所述邻近记录发送到服务器。
[0104] 步骤S106，服务器根据接收到的所述邻近记录，将所述待发现用户终端的标识信息发送至所述邻近记录中的搜索用户终端。
[0105] 在本发明实施例中，待发现用户终端将邻近记录发送到服务器，服务器再将待发现用户终端的标识信息发送到邻近记录中的搜索用户终端。所述待发现用户终端的标识信息指能表明待发现用户身份的信息，并不包括待发现用户的位置信息或者与搜索用户的距离信息，即只在搜索用户的搜索列表中显示搜索到的待发现用户的标识信息，例如，注册账号、用户名、头像和个性签名等信息。
[0106] 可选的，所述邻近区域的获取方式为：服务器根据接收的所述待发现用户终端的邻近记录，计算所述待发现用户终端的模糊位置信息，所述模糊位置信息为所述邻近记录中的所述搜索用户邻近区域的交集；当所述待发现用户作为搜索用户时，基于所述模糊位置信息得到邻近区域。
[0107] 在本发明实施例中，在初始阶段，会存在冷启动的问题，即初始阶段所有用户都没有邻近记录，无法计算模糊位置，也无法得到邻近区域。在这种情况下，可以通过传统签到服务中的签到记录开始首次搜索，或者通过先验保护的方法获得用户的模糊位置。所述先验保护即在查询处理前将用户的真实位置用模糊位置代替，可以通过泛化(例如，空间匿名化)、加密(例如，PIR技术)差分或者加入噪声的方法模糊位置。
[0108] 可选的，当待发现用户在预设时间间隔内没有操作时，服务器使所述待发现用户的登录信息过期。
[0109] 在本发明实施例中，预设时间是待发现用户在待发现用户终端预先设置的时间，例如5分钟，当待发现用户在5分钟内没有在待发现用户终端有任何操作时，则服务器使所述待发现用户终端的登录信息过期，即使待发现用户终端退出登录。
[0110] 在本发明实施例中，通过待发现用户在待发现用户终端中设置位置隐私需求，当搜索用户满足位置隐私需求使，则将待发现用户的标识信息发送至搜索用户终端，当搜索用户不满足待发现用户的位置隐私需求时，则不发送待发现用户的标识信息，能够避免待发现用户终端的真实位置信息泄露。
[0111] 实施例二
[0112] 如图5所示，所述方法还包括：
[0113] 步骤S501，待发现用户从所述搜索用户列表中选择待发送搜索用户作为待发送搜索用户列表。
[0114] 步骤S502，待发现用户终端将所述待发送邻近记录发送到服务器。
[0115] 步骤S503，服务器将所述待发现用户终端的标识信息发送至所述待发送邻近记录中的待发送搜索用户终端。
[0116] 在本发明实施例中，待发送搜索用户是待发现用户选择的分享其标识信息的搜索用户。待发送用户终端显示所述邻近记录，所述邻近记录包括满足所述位置隐私需求的搜索用户的身份信息，待发送用户选择分享其标识信息的搜索用户作为待发送搜索用户，获取待发送搜索用户的身份信息作为待发送邻近记录。例如，待发现用户u的邻近记录包含搜索用户u1、u2和u3，即所述待发现用户的真实位置在所述搜索用户u1、u2和u3中，并且搜索用户u1、u2和u3的邻近区域计算得到的模糊位置满足所述位置隐私需求，待发现用户u可以选择u1和u2作为待发送搜索用户，服务器将待发现用户的标识信息发送给u1和u2，而不会发送给u3。本发明实施例中，待发现用户可以主动选择分享其信息的搜索用户。
[0117] 应理解，上述实施例中各步骤的序号的大小并不意味着执行顺序的先后，各过程的执行顺序应以其功能和内在逻辑确定，而不应对本发明实施例的实施过程构成任何限定。
[0118] 所属领域的技术人员可以清楚地了解到，为了描述的方便和简洁，仅以上述各功能单元、模块的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同的功能单元、模块完成，即将所述装置的内部结构划分成不同的功能单元或模块，以完成以上描述的全部或者部分功能。实施例中的各功能单元、模块可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中，上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。另外，各功能单元、模块的具体名称也只是为了便于相互区分，并不用于限制本申请的保护范围。上述系统中单元、模块的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。
[0119] 本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。
[0120] 在本发明所提供的实施例中，应该理解到，所揭露的装置和方法，可以通过其它的方式实现。例如，以上所描述的系统实施例仅仅是示意性的，例如，所述模块或单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通讯连接可以是通过一些接口，装置或单元的间接耦合或通讯连接，可以是电性，机械或其它的形式。
[0121] 所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。
[0122] 另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。
[0123] 所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明实施例的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)或处理器(processor)执行本发明实施例各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。
[0124] 以上所述实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围，均应包含在本发明的保护范围之内。
