轨迹查询方法、电子设备及存储介质

摘要

本发明提供一种轨迹查询方法，所述方法包括：获取包括每个查询点的描述的查询集；将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布；基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集的候选轨迹集；基于所述查询集的候选轨迹集，计算所述查询集与所述查询集的候选轨迹集中每个候选轨迹的距离，按照距离大小，对所述查询集的候选轨迹集中每个候选轨迹进行排序；根据排序后的候选轨迹集，输出结果给用户。本发明还提供一种电子设备及存储介质。本发明能提高检索精度。

权利要求

1.一种轨迹查询方法，其特征在于，所述方法包括：

获取包括每个查询点的描述的查询集；

将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布；

基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找每个查询点的候选轨迹，将每个查询点的候选轨迹确定为所述查询集的候选轨迹集，其中，查询一个查询点q的候选轨迹包括：基于查询点q对应的主题概率分布，递归遍历四叉树的叶子结点，得到优先队列，所述优先队列按照mdist(q,N)的升序进行排序，所述mdist(q,N)表示查询点q与叶子结点N表示多个轨迹点的最小距离，依次遍历所述优先队列中的每个叶子结点，利用多探针LSH索引技术遍历每个叶子结点对应的LSH索引结构，得到所述查询点的候选轨迹点，将包含所述查询点的候选轨迹点的轨迹作为所述查询点的候选轨迹，并将所述查询点的候选轨迹作为所述查询集的候选轨迹的一部分；

基于所述查询集的候选轨迹集，计算所述查询集与所述查询集的候选轨迹集中每个候选轨迹的距离，按照距离大小，对所述查询集的候选轨迹集中每个候选轨迹进行排序；

根据排序后的候选轨迹集，输出结果给用户。

2.如权利要求1所述的轨迹查询方法，其特征在于，所述语义轨迹数据集中每个轨迹点包含位置坐标和主题分布信息，基于每个轨迹点包含位置坐标和主题分布信息建立包括空间层和主题层的分层索引结构，其中空间层利用四叉树建立索引结构，针对每个叶子结点表示的多个轨迹点，在主题层建立基于位置敏感哈希的每个叶子结点对应的LSH索引结构。

3.如权利要求1所述的轨迹查询方法，其特征在于，所述mdist(q,N)的计算公式如下：mdist(q,N)＝λ·Ds(q,N)+(1-λ)·DT(q,N)；

其中DS(q,N)是基于叶子结点N的最小边界矩阵N.rect，从查询点q到该叶子结点N的最小的空间距离，DT(q,N)从q到所述叶子结点N表示的多个轨迹点的最小主题距离，λ∈[0,1]为权重参数。

4.如权利要求1所述的轨迹查询方法，其特征在于，在计算所述查询集Q与所述查询集Q的候选轨迹集中一个候选轨迹的距离时，包括：计算每个查询点与所述候选轨迹Tr中每个轨迹点的距离；

根据每个查询点与所述候选轨迹Tr中每个轨迹点的距离，计算每个查询点与所述候选轨迹Tr的距离；

根据每个查询点与所述候选轨迹Tr的距离，计算所述查询集与所述候选轨迹Tr的距离。

5.如权利要求4所述的轨迹查询方法，其特征在于，所述计算每个查询点与所述候选轨迹Tr中每个轨迹点的距离包括：给定一个含有文本记录q.W和地理位置q.l的查询点q，从一个轨迹点p到查询点q的距离可根据轨迹点p到查询点q之间的空间接近度和主题相关性度量，计算公式如下：d(q,p)＝λ·DS(q,p)+(1-λ)·DT(q,p)，其中，λ∈[0,1]为用户指定参数被用来调节空间接近度与主题相似性的权重；DS(q,p)是空间欧式距离；DT(q,p)代表q和p文本记录间的主题距离。

6.如权利要求4所述的轨迹查询方法，其特征在于，所述根据每个查询点与候选轨迹中每个轨迹点的距离，计算每个查询点与所述候选轨迹Tr的距离包括：给定一个查询点q和一条轨迹Tr，其中一个轨迹点p∈Tr，对于该轨迹中其它任何一个轨迹点p'而言，有d(q,p)≤d(q,p')，则轨迹点p表示成该轨迹中与查询点q最相关的轨迹点Tr.MRP(q)，则从最相关的轨迹点Tr.MRP(q)到轨迹点q之间的距离就表示为该查询点到轨迹的距离。

7.如权利要求4所述的轨迹查询方法，其特征在于，所述根据每个查询点与所述候选轨迹的距离，计算所述查询集与所述候选轨迹Tr的距离包括：给定包含m个查询点集的查询Q＝{q1,q2,…qm}和一条轨迹Tr，查询Q到轨迹Tr的距离DQ(Tr)为每个查询点qi(i∈[1,m])到轨迹Tr的距离之和，计算如下：查询中每个查询点的最相关点集MRPs就形成了该查询的最相关点集Tr.MRPs(Q)。

8.一种电子设备，其特征在于，所述电子设备包括存储器及处理器，所述存储器用于存储至少一个指令，所述处理器用于执行所述至少一个指令以实现如权利要求1至7中任一项所述轨迹查询方法。

9.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有至少一个指令，所述至少一个指令被处理器执行时实现如权利要求1至7中任一项所述轨迹查询方法。

说明书

轨迹查询方法、电子设备及存储介质

技术领域

[0001] 本发明涉及数据查询领域，尤其涉及一种轨迹查询方法、电子设备及存储介质。

背景技术

[0002] 与传统的移动对象时空轨迹(Spatio-temporal Trajectory)不同，语义轨迹数据不光含有时间、空间信息，还蕴含着丰富的用户行为信息：人们所做所想的、感受到的，通过不同媒体手段在不同位置的表达，例如通过文本、图片、视频等方式，构成一系列行为的轨迹。因此，语义轨迹相关的技术与研究不仅有助于解决道路拥堵问题、提高出行效率、保障交通安全，而且对节省能源、优化交通质量与资源配置有着重要的社会及经济价值，现有技术中的语义轨迹表示通常用户基于文本相似性的检索，注重文本之间“形”的差别，例如通过现有技术中的语义轨迹查询，“喝咖啡”与轨迹点描述“星巴克”被认为毫不相关，无法检索到，这样主题相关的轨迹也就无法检索到，降低了查询准确度。

发明内容

[0003] 鉴于以上内容，有必要提供一种轨迹查询方法、电子设备及存储介质，能提高检索精度。

[0004] 一种轨迹查询方法，所述方法包括：

[0005] 获取包括每个查询点的描述的查询集；

[0006] 将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布；

[0007] 基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集的候选轨迹集；

[0008] 基于所述查询集的候选轨迹集，计算所述查询集与所述查询集的候选轨迹集中每个候选轨迹的距离，按照距离大小，对所述查询集的候选轨迹集中每个候选轨迹进行排序；

[0009] 根据排序后的候选轨迹集，输出结果给用户。

[0010] 根据本发明优选实施例，所述语义轨迹数据集中每个轨迹点包含位置坐标和主题分布信息，基于每个轨迹点包含位置坐标和主题分布信息建立包括空间层和主题层的分层索引结构，其中空间层利用四叉树建立索引结构，针对每个叶子结点表示的多个轨迹点，在主题层建立基于位置敏感哈希的每个叶子结点对应的LSH索引结构。

[0011] 根据本发明优选实施例，所述基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集的候选轨迹集包括：

[0012] 基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配,查找每个查询点的候选轨迹,将每个查询点的候选轨迹确定为所述查询集的候选轨迹集；

[0013] 其中基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配,查询一个查询点q的候选轨迹包括：

[0014] 基于查询点q对应的主题概率分布，递归遍历所述四叉树的叶子结点，得到优先队列，所述优先队列按照mdist(q,N)的升序进行排序，所述mdist(q,N)表示查询点q与叶子结点N表示的多个轨迹点的最小距离；

[0015] 依次遍历所述优先队列中的每个叶子结点，利用多探针LSH索引技术遍历每个叶子结点对应的LSH索引结构，得到所述查询点的候选轨迹点，将包含所述查询点的候选轨迹点的轨迹作为所述查询点的候选轨迹，并将所述查询点的候选轨迹作为所述查询集的候选轨迹的一部分。

[0016] 根据本发明优选实施例，所述mdist(q,N)的计算公式如下：

[0017] mdist(q,N)＝λ·Ds(q,N)+(1-λ)·DT(q,N)；

[0018] 其中DS(q,N)是基于叶子结点N的最小边界矩阵N.rect，从查询点q到该叶子结点N的最小的空间距离，DT(q,N)从q到所述叶子结点N表示的多个轨迹点的最小主题距离。

[0019] 根据本发明优选实施例，在计算所述查询集Q与所述查询集Q的候选轨迹集中一个候选轨迹的距离时，包括：

[0020] 计算每个查询点与所述候选轨迹Tr中每个轨迹点的距离；

[0021] 根据每个查询点与所述候选轨迹Tr中每个轨迹点的距离，计算每个查询点与所述候选轨迹Tr的距离；

[0022] 根据每个查询点与所述候选轨迹Tr的距离，计算所述查询集与所述候选轨迹Tr的距离。

[0023] 根据本发明优选实施例，所述计算每个查询点与所述候选轨迹Tr中每个轨迹点的距离包括：

[0024] 给定一个含有文本记录q.W和地理位置q.l的查询点q，从一个轨迹点p到查询点q的距离可根据轨迹点p到查询点q之间的空间接近度和主题相关性度量，计算公式如下：

[0025] d(q,p)＝λ·DS(q,p)+(1-λ)·DT(q,p)，其中，λ∈[0,1]为用户指定参数被用来调节空间接近度与主题相似性的权重；DS(q,p)是空间欧式距离；DT(q,p)代表q和p文本记录间的主题距离。

[0026] 根据本发明优选实施例，所述根据每个查询点与候选轨迹中每个轨迹点的距离，计算每个查询点与所述候选轨迹Tr的距离包括：

[0027] 给定一个查询点q和一条轨迹Tr，其中一个轨迹点p∈Tr，对于该轨迹中其它任何一个轨迹点p'而言，有d(q,p)≤d(q,p')，则轨迹点p表示成该轨迹中与查询点q最相关的轨迹点Tr.MRP(q)，则从最相关的轨迹点Tr.MRP(q)到轨迹点q之间的距离就表示为该查询点到轨迹的距离。

[0028] 根据本发明优选实施例，所述根据每个查询点与所述候选轨迹的距离，计算所述查询集与所述候选轨迹Tr的距离包括：

[0029] 给定包含m个查询点集的查询Q＝{q1,q2,Λ,qm}和一条轨迹Tr，查询Q到轨迹Tr的距离DQ(Tr)为每个查询点qi(i∈[1,m])到轨迹Tr的距离之和，计算如下：

[0030]

[0031] 查询中每个查询点的最相关点集MRPs就形成了该查询的最相关点集Tr.MRPs(Q)。

[0032] 一种电子设备，所述电子设备包括存储器及处理器，所述存储器用于存储至少一个指令，所述处理器用于执行所述至少一个指令以实现任意实施例中任一项所述轨迹查询方法。

[0033] 一种计算机可读存储介质，所述计算机可读存储介质存储有至少一个指令，所述至少一个指令被处理器执行时实现任意实施例中任一项所述轨迹查询方法。

[0034] 由以上技术方案可以看出，本发明获取包括每个查询点的描述的查询集；通过基于主题分布的相似性度量函数，将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布；基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集的候选轨迹集；基于所述查询集的候选轨迹集，计算所述查询集与所述查询集的候选轨迹集中每个候选轨迹的距离，按照距离大小，对所述查询集的候选轨迹集进行排序；根据排序后的候选轨迹集，输出结果给用户。本发明利用语义轨迹表示模型表示查询点及数据库中的轨迹点，将轨迹点和查询点的文本描述转换为主题概率分布，即一系列的附有位置和时间标签的主题概率分布，使得能够更好地理解文本描述的内在意义，并通过基于主题分布的相似性度来表征它们的语义关联，从而提高检索精度。因此,本发明能基于主题相关的轨迹进行查询,从而提高检索精度。

附图说明

[0035] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。

[0036] 图1是本发明轨迹查询方法的较佳实施例的流程图。

[0037] 图2是本发明轨迹查询装置的较佳实施例的功能模块图。

[0038] 图3是本发明至少一个实例中电子设备的较佳实施例的结构示意图。

具体实施方式

[0039] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0040] 为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

[0041] 为了使本技术领域的人员更好地理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分的实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本发明保护的范围。

[0042] 本发明的说明书和权利要求书及上述附图中的术语“第一”、“第二”和“第三”等是用于区别不同对象，而非用于描述特定顺序。此外，术语“包括”以及它们任何变形，意图在于覆盖不排他的包含。例如包含了一系列步骤或单元的过程、方法、系统、产品或设备没有限定于已列出的步骤或单元，而是可选地还包括没有列出的步骤或单元，或可选地还包括对于这些过程、方法、产品或设备固有的其它步骤或单元。

[0043] 如图1所示，是本发明轨迹查询方法的第一较佳实施例的流程图。根据不同的需求，该流程图中步骤的顺序可以改变，某些步骤可以省略。

[0044] S10、获取包括每个查询点的描述的查询集Q。

[0045] 在本发明的可选实施例中，所述查询集Q包括至少一个查询点。例如，用户在用户界面上输入的带有多个位置的描述，需要查询所述多个位置的描述匹配的数据，其中一个位置的描述为一个查询点，例如平安科技公司下的B公司的金融产品，则所述查询集Q中可以包括两个查询点，查询点一：对平安科技公司的描述、查询点二：对B公司的描述。

[0046] S11、将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布。

[0047] 优选地，每个查询点是由文本描述组成。所述文本描述包括位置和时间标签。利用语义轨迹表示模型表示每个查询点对应的附有位置和时间标签的主题概率分布。

[0048] 具体地，所述语义轨迹表示模型如下：每个查询点是一个由n个空间关键字组成的文本W，Z＝{z1,z2,…,zm}为主题集，所述主题集用于表示n个空间关键字所属的主题，则W对应的概率主题分布TDW中对应每个主题TDW[zi]的计算公式如下：

[0049]

[0050] 其中Nw∈(WIWz)表示W中关键字的个数，α表示对称边界，通常设置为0.1，|W|表示W中关键词的个数，|Z|表示总共的主题个数。

[0051] S12、基于每个查询点的对应的主题概率分布,将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集Q的候选轨迹集。

[0052] 优选地，所述语义轨迹数据集中每个轨迹点包含位置坐标和主题分布信息，基于每个轨迹点包含位置坐标和主题分布信息建立包括空间层和主题层的分层索引结构。其中空间层利用四叉树建立索引结构，从而达到在空间层快速收敛的目的，而在空间层的四叉树的每个叶子结点表示多个轨迹点，针对每个叶子结点表示的多个轨迹点，在主题层建立基于位置敏感哈希的每个叶子结点对应的LSH索引结构，这样通过使用哈希函数将每个叶子节点表示的多个轨迹点中相似的轨迹点映射到同一哈希桶。

[0053] 具体地，四叉树索引是将位置信息递归划分为不同层次的树结构。将已知范围的空间等分成四个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单，并且当空间数据对象分布比较均匀时，具有比较高的空间数据插入和查询效率。轨迹点都存储在叶子结点上，中间结点以及根结点不存储轨迹点。

[0054] 优选地，基于每个查询点对应的主题概率分布与语义轨迹数据集进行搜索匹配，得到每个查询点的候选轨迹点，将包含每个查询点的候选轨迹点的轨迹作为每个查询点的候选轨迹，将每个查询点的候选轨迹作为所述查询集Q的候选轨迹。这样基于每个查询点对应的主题概率分布,计算每个查询点与语义轨迹数据集中轨迹点的相似度,基于主题分布的相似度来表征查询点与语义轨迹数据集中轨迹点间的语义关联，使得能够更好地理解文本描述的内在意义。

[0055] 优选地，查找一个查询点q(所述查询点q为任意一个查询点)的候选轨迹包括以下步骤：

[0056] (1)、基于查询点q对应的主题概率分布，递归遍历所述四叉树的叶子结点，得到优先队列，所述优先队列按照mdist(q,N)的升序进行排序，所述mdist(q,N)表示查询点q与叶子结点N表示的多个轨迹点的最小距离，mdist(q,N)越小，查询点q与叶子结点N表示的多个轨迹点的相似度越高。

[0057] 优选地，所述mdist(q,N)的计算公式如下：

[0058] mdist(q,N)＝λ·Ds(q,N)+(1-λ)·DT(q,N)，

[0059] 其中λ∈[0,1]为权重参数，DT(q,N)的具体计算公式为：

[0060] 其中DS(q,N)是基于叶子结点N的最小边界矩阵N.rect，从查询点q到该叶子结点N的最小的空间距离；DT(q,N)是从q到所述叶子结点N表示的多个轨迹点的最小主题距离。

[0061] ||TDq,N.o||为主题空间中查询点q到锚点N.o的主题分布之间的欧氏距离。

[0062] (2)、依次遍历所述优先队列中的每个叶子结点，利用多探针LSH索引(Multi-Probe LSH Indexing)技术遍历每个叶子结点对应的LSH索引结构，得到所述查询点的候选轨迹点，将包含所述查询点的候选轨迹点的轨迹作为所述查询点的候选轨迹，并将所述查询点的候选轨迹作为所述查询集Q的候选轨迹的一部分。

[0063] 例如，有两个叶子结点，第一结点及第二结点，在优先队列中的顺序为：第二结点、第一结点。先利用多探针LSH索引技术遍历所述第二结点下的轨迹点，再查找第一结点下的轨迹点。

[0064] 具体地，所述多探针LSH索引技术利用探测序列(carefully derived probing sequence)，得到和查询点近似的多个哈希桶。根据LSH的性质，我们可知如果与查询点q相近的数据没有和查询点q被映射到同一个桶中，它很有可能被映射到周围的桶中(即两个桶的哈希值只有些许差别),所以该方法的目标是定位这些临近的桶，以便增加查找近邻数据的机会。

[0065] 按照上述步骤(1)、(2)对每个查询点进行查询，得到所述查询集Q中每个查询点的候选轨迹。

[0066] 通过上述实施，基于每个查询点对应的主题概率分布,计算每个查询点与语义轨迹数据集中轨迹点的相似度,基于主题分布的相似度来表征查询点与语义轨迹数据集中轨迹点间的语义关联，使得能够更好地理解文本描述的内在意义。这样例如查询描述“喝咖啡”与轨迹点描述“星巴克”将因其相似的主题分布而被认为相关。这样能使查询更准确。例如查询描述“喝咖啡”与轨迹点描述“星巴克”将因其相似的主题分布而被认为相关。这样能使查询更准确。

[0067] S13、基于所述查询集Q的候选轨迹集，计算所述查询集Q与所述查询集Q的候选轨迹集中每个轨迹的距离，按照距离大小，对所述查询集Q的候选轨迹集中每个候选轨迹进行排序。

[0068] 具体地，给定一个语义轨迹数据集τ，一个有限的主题集Z，包含一系列查询点的查询集Q，一个用户指定的整形变量k(k＜|τ|)，则一个面向用户意图的语义轨迹相似查询(User-oriented Trajectory Similarity Query，UTSQ)，从τ中返回独立的k条轨迹，而这k条轨迹距离查询集Q有top-k最小的距离DQ(Tr)。

[0069] 优选地，所述计算所述查询集Q与所述查询集Q的候选轨迹集中任意一个候选轨迹Tr的距离包括：

[0070] (1)计算每个查询点与所述候选轨迹Tr中每个轨迹点的距离。

[0071] 具体地，给定一个含有文本记录q.W和地理位置q.l的查询点q，从一个轨迹点p到它的距离可根据它们之间的空间接近度和主题相关性度量，具体计算公式如下：

[0072] d(q,p)＝λ·DS(q,p)+(1-λ)·DT(q,p)，

[0073] 其中，λ∈[0,1]为用户指定参数被用来调节空间接近度与主题相似性的权重；DS(q,p)是空间欧式距离，本文同样采用sigmoid函数规范该距离在区间[0,1]之间；DT(q,p)，是DT(q.W,p.W)的简化，代表q和p文本记录间的主题距离。

[0074] (2)根据每个查询点与所述候选轨迹Tr中每个轨迹点的距离，计算每个查询点与所述候选轨迹的距离。

[0075] 具体地，给定一个查询点q和一条轨迹Tr，如果其中一个轨迹点p∈Tr，对于该轨迹中其它任何一个轨迹点p'而言，我们有d(q,p)≤d(q,p')，则轨迹点p就可表示成该轨迹中与查询点q最相关的轨迹点(Most Relevant Point,MRP)，定义为Tr.MRP(q)。则从最相关点Tr.MRP(q)到轨迹点q之间的距离就表示为该查询点到轨迹的距离，具体可定义下：

[0076] Dmrp(q,Tr)＝minp∈Trd(q,p)，

[0077] (3)根据每个查询点与所述候选轨迹Tr的距离，计算所述查询集与所述候选轨迹Tr的距离。

[0078] 具体地，给定包含m个查询点的查询集Q＝{q1,q2,…qm}和一条轨迹Tr，我们定义查询集Q到轨迹Tr的距离DQ(Tr)为每个查询点qi(i∈[1,m])到轨迹Tr的距离之和，计算如下：

[0079]

[0080] 由此可见，查询中每个查询点的最相关点集MRPs就形成了该查询的最相关点集，Tr.MRPs(Q)，因此寻找一个查询集Q的最相关点集MRPs可被分解为查找该查询中每个查询点的最相关点MRP。

[0081] S14，根据排序后的候选轨迹集，输出结果给用户。

[0082] 优选地,在用户界面上显示排序后的候选轨迹集,所述排序后的候选轨迹集是按照距离从小到大进行排序的。这样就能将最相关的结果显示在最前面以供用户直观地看到最相关的查询结果。

[0083] 本发明通过基于主题分布的相似性度量函数，将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布，基于每个查询点的对应的主题概率分布,将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集Q的候选轨迹集，基于所述查询集Q的候选轨迹集，计算所述查询集Q与所述查询集Q的候选轨迹集中每个轨迹的距离，按照距离大小，对所述查询集Q的候选轨迹集进行排序，根据排序后的候选轨迹集，输出结果给用户。本发明利用语义轨迹表示模型表示查询点及数据库中的轨迹点，将轨迹点和查询点的文本描述转换为主题概率分布，即一系列的附有位置和时间标签的主题概率分布，使得能够更好地理解文本描述的内在意义，并通过基于主题分布的相似度来表征它们的语义关联，从而提高检索精度。

[0084] 如图2所示，本发明轨迹查询装置的第一较佳实施例的功能模块图。所述轨迹查询装置2包括，但不限于以下一个或者多个模块：获取模块20、转换模块21、查找模块22、排序模块23及输出模块24。本发明所称的单元是指一种能够被轨迹查询装置2的处理器所执行并且能够完成固定功能的一系列计算机程序段，其存储在存储器中。关于各单元的功能将在后续的实施例中详述。

[0085] 所述获取模块20获取包括每个查询点的描述的查询集Q。

[0086] 在本发明的可选实施例中，所述查询集Q包括至少一个查询点。例如，用户在用户界面上输入的带有多个位置的描述，需要查询所述多个位置的描述匹配的数据，其中一个位置的描述为一个查询点，例如平安科技公司下的B公司的金融产品，则所述查询集Q中可以包括两个查询点，查询点一：对平安科技公司的描述、查询点二：对B公司的描述。

[0087] 所述转换模块21将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布。

[0088] 优选地，每个查询点是由文本描述组成。所述文本描述包括位置和时间标签。利用语义轨迹表示模型表示每个查询点对应的附有位置和时间标签的主题概率分布。

[0089] 具体地，所述语义轨迹表示模型如下：每个查询点是一个由n个空间关键字组成的文本W，Z＝{z1,z2,…,zm}为主题集，所述主题集用于表示n个空间关键字所属的主题，则W对应的概率主题分布TDW中对应每个主题TDW[zi]的计算公式如下：

[0090]

[0091] 其中Nw∈(WIWz)表示W中关键字的个数，α表示对称边界，通常设置为0.1，|W|表示W中关键词的个数，|Z|表示总共的主题个数。

[0092] 所述查找模块22基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集Q的候选轨迹集。

[0093] 优选地，所述语义轨迹数据集中每个轨迹点包含位置坐标和主题分布信息，基于每个轨迹点包含位置坐标和主题分布信息建立包括空间层和主题层的分层索引结构。其中空间层利用四叉树建立索引结构，从而达到在空间层快速收敛的目的，而在空间层的四叉树的每个叶子结点表示多个轨迹点，针对每个叶子结点表示的多个轨迹点，在主题层建立基于位置敏感哈希的每个叶子结点对应的LSH索引结构，这样通过使用哈希函数将每个叶子节点表示的多个轨迹点中相似的轨迹点映射到同一哈希桶。

[0094] 具体地，四叉树索引是将位置信息递归划分为不同层次的树结构。将已知范围的空间等分成四个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单，并且当空间数据对象分布比较均匀时，具有比较高的空间数据插入和查询效率。轨迹点都存储在叶子结点上，中间结点以及根结点不存储轨迹点。

[0095] 优选地，基于每个查询点对应的主题概率分布与语义轨迹数据集进行搜索匹配，得到每个查询点的候选轨迹点，将包含每个查询点的候选轨迹点的轨迹作为每个查询点的候选轨迹，将每个查询点的候选轨迹作为所述查询集Q的候选轨迹。这样基于每个查询点对应的主题概率分布,计算每个查询点与语义轨迹数据集中轨迹点的相似度,基于主题分布的相似度来表征查询点与语义轨迹数据集中轨迹点间的语义关联，使得能够更好地理解文本描述的内在意义。

[0096] 优选地，所述查找模块22查找一个查询点q(所述查询q点为任意一个查询点)的候选轨迹包括以下步骤：

[0097] (1)、基于查询点q对应的主题概率分布，递归遍历所述四叉树的叶子结点，得到优先队列，所述优先队列按照mdist(q,N)的升序进行排序，所述mdist(q,N)表示查询点q与叶子结点N表示的多个轨迹点的最小距离，mdist(q,N)越小，查询点q与叶子结点N表示的多个轨迹点的相似度越高。

[0098] 优选地，所述mdist(q,N)的计算公式如下：

[0099] mdist(q,N)＝λ·Ds(q,N)+(1-λ)·DT(q,N)，

[0100] 其中DS(q,N)是基于叶子结点N的最小边界矩阵N.rect，从查询点q到该叶子结点N的最小的空间距离；DT(q,N)是从q到所述叶子结点N表示的多个轨迹点的最小主题距离。

[0101] 其中λ∈[0,1]为权重参数，DT(q,N)的具体计算公式为：

[0102] ||TDq,N.o||为主题空间中查询点q到锚点N.o的主题分布之间的欧氏距离。

[0103] (2)、依次遍历所述优先队列中的每个叶子结点，利用多探针LSH索引(Multi-Probe LSH Indexing)技术遍历每个叶子结点对应的LSH索引结构，得到所述查询点的候选轨迹点，将包含所述查询点的候选轨迹点的轨迹作为所述查询点的候选轨迹，并将所述查询点的候选轨迹作为所述查询集Q的候选轨迹的一部分。

[0104] 例如，有两个叶子结点，第一结点及第二结点，在优先队列中的顺序为：第二结点、第一结点。先利用多探针LSH索引技术遍历所述第二结点下的轨迹点，再查找第一结点下的轨迹点。

[0105] 具体地，所述多探针LSH索引技术利用探测序列(carefully derived probing sequence)，得到和查询点近似的多个哈希桶。根据LSH的性质，我们可知如果与查询点q相近的数据没有和查询点q被映射到同一个桶中，它很有可能被映射到周围的桶中(即两个桶的哈希值只有些许差别),所以该方法的目标是定位这些临近的桶，以便增加查找近邻数据的机会。

[0106] 按照上述步骤(1)、(2)对每个查询点进行查询，得到所述查询集Q中每个查询点的候选轨迹。

[0107] 通过上述实施，基于每个查询点对应的主题概率分布,计算每个查询点与语义轨迹数据集中轨迹点的相似度,基于主题分布的相似度来表征查询点与语义轨迹数据集中轨迹点间的语义关联，使得能够更好地理解文本描述的内在意义。这样例如查询描述“喝咖啡”与轨迹点描述“星巴克”将因其相似的主题分布而被认为相关。这样能使查询更准确。

[0108] 所述排序模块23基于所述查询集Q的候选轨迹集，计算所述查询集Q与所述查询集Q的候选轨迹集中每个轨迹的距离，按照距离大小，对所述查询集Q的候选轨迹集中每个候选轨迹进行排序。

[0109] 具体地，给定一个语义轨迹数据集τ，一个有限的主题集Z，包含一系列查询点的查询集Q，一个用户指定的整形变量k(k＜|τ|)，则一个面向用户意图的语义轨迹相似查询(User-oriented Trajectory Similarity Query，UTSQ)，从τ中返回独立的k条轨迹，而这k条轨迹距离查询集Q有top-k最小的距离DQ(Tr)。

[0110] 优选地，所述排序模块23计算所述查询集Q与所述查询集Q的候选轨迹集中任意一个候选轨迹Tr的距离包括：

[0111] (1)计算每个查询点与所述候选轨迹Tr中每个轨迹点的距离。

[0112] 具体地，给定一个含有文本记录q.W和地理位置q.l的查询点q，从一个轨迹点p到它的距离可根据它们之间的空间接近度和主题相关性度量，具体计算公式如下：

[0113] d(q,p)＝λ·DS(q,p)+(1-λ)·DT(q,p)，

[0114] 其中，λ∈[0,1]为用户指定参数被用来调节空间接近度与主题相似性的权重；DS(q,p)是空间欧式距离，本文同样采用sigmoid函数规范该距离在区间[0,1]之间；DT(q,p)，是DT(q.W,p.W)的简化，代表q和p文本记录间的主题距离。

[0115] (2)根据每个查询点与所述候选轨迹Tr中每个轨迹点的距离，计算每个查询点与所述候选轨迹的距离。

[0116] 具体地，给定一个查询点q和一条轨迹Tr，如果其中一个轨迹点p∈Tr，对于该轨迹中其它任何一个轨迹点p'而言，我们有d(q,p)≤d(q,p')，则轨迹点p就可表示成该轨迹中与查询点q最相关的轨迹点(Most Relevant Point,MRP)，定义为Tr.MRP(q)。则从最相关点Tr.MRP(q)到轨迹点q之间的距离就表示为该查询点到轨迹的距离，具体可定义下：

[0117] Dmrp(q,Tr)＝minp∈Trd(q,p)，

[0118] (3)根据每个查询点与所述候选轨迹Tr的距离，计算所述查询集与所述候选轨迹Tr的距离。

[0119] 具体地，给定包含m个查询点的查询集Q＝{q1,q2,…qm}和一条轨迹Tr，我们定义查询集Q到轨迹Tr的距离DQ(Tr)为每个查询点qi(i∈[1,m])到轨迹Tr的距离之和，计算如下：

[0120]

[0121] 由此可见，查询中每个查询点的最相关点集MRPs就形成了该查询的最相关点集，Tr.MRPs(Q)，因此寻找一个查询集Q的最相关点集MRPs可被分解为查找该查询中每个查询点的最相关点MRP。

[0122] 输出模块24根据排序后的候选轨迹集，输出结果给用户。

[0123] 优选地,所述输出模块24在用户界面上显示排序后的候选轨迹集,所述排序后的候选轨迹集是按照距离从小到大进行排序的。这样就能将最相关的结果显示在最前面以供用户直观地看到最相关的查询结果。

[0124] 本发明通过基于主题分布的相似性度量函数，将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布，基于每个查询点的对应的主题概率分布,将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集Q的候选轨迹集，基于所述查询集Q的候选轨迹集，计算所述查询集Q与所述查询集Q的候选轨迹集中每个轨迹的距离，按照距离大小，对所述查询集Q的候选轨迹集进行排序，根据排序后的候选轨迹集，输出结果给用户。本发明利用语义轨迹表示模型表示查询点及数据库中的轨迹点，将轨迹点和查询点的文本描述转换为主题概率分布，即一系列的附有位置和时间标签的主题概率分布，使得能够更好地理解文本描述的内在意义，并通过基于主题分布的相似度来表征它们的语义关联，从而提高检索精度。

[0125] 上述以软件功能模块的形式实现的集成的单元，可以存储在一个计算机可读取存储介质中。上述软件功能模块存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)或处理器(processor)执行本发明每个实施例所述方法的部分步骤。

[0126] 如图3所示，所述电子设备3包括至少一个发送装置31、至少一个存储器32、至少一个处理器33、至少一个接收装置34以及至少一个通信总线。其中，所述通信总线用于实现这些组件之间的连接通信。

[0127] 所述电子设备3是一种能够按照事先设定或存储的指令，自动进行数值计算和/或信息处理的设备，其硬件包括但不限于微处理器、专用集成电路(Application Specific Integrated Circuit，ASIC)、可编程门阵列(Field－Programmable Gate Array，FPGA)、数字处理器(Digital Signal Processor，DSP)、嵌入式设备等。所述电子设备3还可包括网络设备和/或用户设备。其中，所述网络设备包括但不限于单个网络服务器、多个网络服务器组成的服务器组或基于云计算(Cloud Computing)的由大量主机或网络服务器构成的云，其中，云计算是分布式计算的一种，由一群松散耦合的计算机集组成的一个超级虚拟计算机。

[0128] 所述电子设备3可以是，但不限于任何一种可与用户通过键盘、触摸板或声控设备等方式进行人机交互的电子产品，例如，平板电脑、智能手机、个人数字助理(Personal Digital Assistant，PDA)、智能式穿戴式设备、摄像设备、监控设备等终端。

[0129] 所述电子设备3所处的网络包括，但不限于互联网、广域网、城域网、局域网、虚拟专用网络(Virtual Private Network，VPN)等。

[0130] 其中，所述接收装置34和所述发送装置31可以是有线发送端口，也可以为无线设备，例如包括天线装置，用于与其他设备进行数据通信。

[0131] 所述存储器32用于存储程序代码。所述存储器32可以是集成电路中没有实物形式的具有存储功能的电路，如RAM(Random-Access Memory，随机存取存储器)、FIFO(First In First Out，)等。或者，所述存储器32也可以是具有实物形式的存储器，如内存条、TF卡(Trans-flash Card)、智能媒体卡(smart media card)、安全数字卡(secure digital card)、快闪存储器卡(flash card)等储存设备等等。

[0132] 所述处理器33可以包括一个或者多个微处理器、数字处理器。所述处理器33可调用存储器32中存储的程序代码以执行相关的功能。例如，图2中所述的各个模块是存储在所述存储器32中的程序代码，并由所述处理器33所执行，以实现一种轨迹查询方法。所述处理器33又称中央处理器(CPU，Central Processing Unit)，是一块超大规模的集成电路，是运算核心(Core)和控制核心(Control Unit)。

[0133] 本发明实施例还提供一种计算机可读存储介质，其上存储有计算机指令，所述指令当被包括一个或多个处理器的电子设备执行时，使电子设备执行如上文方法实施例所述的轨迹查询方法。

[0134] 结合图1及图2所示，所述电子设备3中的所述存储器32存储多个指令以实现一种轨迹查询方法，所述处理器33可执行所述多个指令从而实现：

[0135] 获取包括每个查询点的描述的查询集；将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布；基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集的候选轨迹集；基于所述查询集的候选轨迹集，计算所述查询集与所述查询集的候选轨迹集中每个候选轨迹的距离，按照距离大小，对所述查询集的候选轨迹集中每个候选轨迹进行排序；根据排序后的候选轨迹集，输出结果给用户。

[0136] 以上说明的本发明的特征性的手段可以通过集成电路来实现，并控制实现上述任意实施例中所述轨迹查询方法的功能。即，本发明的集成电路安装于所述电子设备中，使所述电子设备发挥如下功能：获取包括每个查询点的描述的查询集；将每个查询点的描述转换为每个查询点对应的附有位置和时间标签的主题概率分布；基于每个查询点的对应的主题概率分布，将每个查询点与数据库中的语义轨迹数据集进行搜索匹配，查找所述查询集的候选轨迹集；基于所述查询集的候选轨迹集，计算所述查询集与所述查询集的候选轨迹集中每个候选轨迹的距离，按照距离大小，对所述查询集的候选轨迹集中每个候选轨迹进行排序；根据排序后的候选轨迹集，输出结果给用户。

[0137] 在任意实施例中所述轨迹查询方法所能实现的功能都能通过本发明的集成电路安装于所述电子设备中，使所述电子设备发挥任意实施例中所述轨迹查询方法所能实现的功能，在此不再详述。

[0138] 需要说明的是，对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本发明并不受所描述的动作顺序的限制，因为依据本发明，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定是本发明所必须的。

[0139] 在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。

[0140] 在本申请所提供的几个实施例中，应该理解到，所揭露的装置，可通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性或其它的形式。

[0141] 所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

[0142] 另外，在本发明的各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

[0143] 所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可为个人计算机、服务器或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、移动硬盘、磁碟或者光盘等各种可以存储程序代码的介质。

[0144] 以上所述，以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。