[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN113792035A - 轨迹近邻查询方法、装置、电子设备和可读存储介质 - Google Patents

轨迹近邻查询方法、装置、电子设备和可读存储介质 Download PDF

Info

Publication number
CN113792035A
CN113792035A CN202011583540.9A CN202011583540A CN113792035A CN 113792035 A CN113792035 A CN 113792035A CN 202011583540 A CN202011583540 A CN 202011583540A CN 113792035 A CN113792035 A CN 113792035A
Authority
CN
China
Prior art keywords
track
queried
region
trajectory
lower bound
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN202011583540.9A
Other languages
English (en)
Other versions
CN113792035B (zh
Inventor
李瑞远
俞自生
鲍捷
郑宇�
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Jingdong City Beijing Digital Technology Co Ltd
Original Assignee
Jingdong City Beijing Digital Technology Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Jingdong City Beijing Digital Technology Co Ltd filed Critical Jingdong City Beijing Digital Technology Co Ltd
Priority to CN202011583540.9A priority Critical patent/CN113792035B/zh
Priority to PCT/CN2021/116994 priority patent/WO2022142449A1/zh
Priority to KR1020237021384A priority patent/KR20230107369A/ko
Priority to JP2023540697A priority patent/JP7683010B2/ja
Priority to US18/259,279 priority patent/US20240061821A1/en
Publication of CN113792035A publication Critical patent/CN113792035A/zh
Application granted granted Critical
Publication of CN113792035B publication Critical patent/CN113792035B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/29—Geographical information databases
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G06F16/2457—Query processing with adaptation to user needs
    • G06F16/24578—Query processing with adaptation to user needs using ranking
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/27—Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Software Systems (AREA)
  • Computational Linguistics (AREA)
  • Computing Systems (AREA)
  • Remote Sensing (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Traffic Control Systems (AREA)

Abstract

本公开提供了一种轨迹近邻查询方法、装置、电子设备和可读存储介质，涉及计算机技术领域。其中，轨迹近邻查询方法包括：获取待查询的第一轨迹，并确定第一轨迹的空间位置信息；根据第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名；通过XZ‑Ordering确定第一轨迹的空间位置索引编码；根据轨迹签名和空间位置索引编码，构建第一轨迹的空间范围索引。通过本公开的技术方案，减少了轨迹近邻查询过程中的时间复杂度的计算量，提高了索引和查询的效率，减少了磁盘读写和验证计算的开销。

Description

轨迹近邻查询方法、装置、电子设备和可读存储介质
技术领域
本公开涉及计算机技术领域，尤其涉及一种轨迹近邻查询方法、装置、电子设备和可读存储介质。
背景技术
轨迹k邻近查询，是指基于弗雷歇距离找到给定轨迹在空间上最近的k条轨迹。
传统的查询技术主要如下：以查询轨迹为中心，不断扩展周围空间范围，同时遍历该空间中的所有轨迹按并按与查询轨迹的距离排序，直到最近k条轨迹找到为止。
但是，随着智能设备与基于位置的服务的广泛应用，产生了规模巨大的轨迹数据，基于关系型数据库的传统方法已经无法支撑海量的数据存储与分析工作。
由于轨迹上的轨迹点数量巨大，因此，弗雷歇距离的计算量大，进而导致现有的轨迹近邻查询存在严重的效率问题。
需要说明的是，在上述背景技术部分公开的信息仅用于加强对本公开的背景的理解，因此可以包括不构成对本领域普通技术人员已知的现有技术的信息。
发明内容
本公开的目的在于提供一种轨迹近邻查询方法、装置、电子设备和可读存储介质，至少在一定程度上克服由于相关技术中轨迹近邻查询的效率低的问题。
本公开的其他特性和优点将通过后续的详细描述变得显然，或部分地通过本公开的实践而习得。
根据本公开的一个方面，提供一种轨迹近邻查询方法，包括：获取待查询的第一轨迹，并确定所述第一轨迹的空间位置信息；根据所述第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名；通过XZ-Ordering确定所述第一轨迹的空间位置索引编码；根据所述轨迹签名和所述空间位置索引编码，构建所述第一轨迹的空间范围索引。
在本公开的一个实施例中，还包括：确定所述第一轨迹的标识；将所述第一轨迹的标识添加至所述空间范围索引的后缀。
在本公开的一个实施例中，还包括：获取所述第一轨迹的随机数；将所述随机数添加至所述空间范围索引的前缀；根据所述前缀将所述空间范围索引随机存储至分布式服务器。
在本公开的一个实施例中，还包括：从存储所述待查询区域的第一优先队列中取出一个待查询区域；确定所述待查询区域的空间位置索引编码的编码长度；根据所述编码长度与预设长度之间的大小关系，对所述待查询区域进行扩展或对停止对所述待查询区域进行分裂。
在本公开的一个实施例中，根据所述编码长度与预设长度之间的大小关系，对所述待查询区域进行扩展或对停止对所述待查询区域进行分裂包括：判断所述编码长度是否大于所述预设长度；若判定所述编码长度大于所述预设长度，则不对所述待查询区域进行分裂；在所待查询区域内执行空间范围查询处理。
在本公开的一个实施例中，根据所述编码长度与预设长度之间的大小关系，对所述待查询区域进行扩展或对停止对所述待查询区域进行分裂还包括：判断所述编码长度是否大于所述预设长度；若判定所述编码长度小于或等于所述预设长度，则对所述待查询区域进行四叉树递归分裂，以生成所述待查询区域的子节点待查询区域，至所述子节点待查询区域的编码长度大于或等于所述预设长度为止。
在本公开的一个实施例中，还包括：在停止对所述待查询区域进行四叉树递归分裂后，确定所述待查询区域内的第二轨迹，并将所述第二轨迹存储至第二优先队列。
在本公开的一个实施例中，还包括：确定所述第一轨迹与所述待查询区域之间的第一弗雷歇距离；判断所述第一弗雷歇距离是否大于或等于最大距离阈值；若判定所述第一弗雷歇距离大于或等于所述最大距离阈值，对所述待查询区域进行区域剪枝处理；根据所述区域剪枝处理的结果对所述最大距离阈值进行更新。
在本公开的一个实施例中，还包括：确定所述第一轨迹的下界位置，以及所述待查询区域内的第二轨迹的下界位置；根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理，所述下界位置包括起点下界位置、终点下界位置和轨迹签名下界位置中的至少一种。
在本公开的一个实施例中，根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理包括：确定所述第一轨迹的起点下界位置和所述第二轨迹的起点下界位置之间的起点弗雷歇距离；根据所述起点弗雷歇距离与第一预设距离之间的大小关系，对所述第二轨迹进行第一下界剪枝处理。
在本公开的一个实施例中，根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理还包括：确定所述第一轨迹的终点下界位置和所述第二轨迹的终点下界位置之间的终点弗雷歇距离；根据所述终点弗雷歇距离与第二预设距离之间的大小关系，对所述第二轨迹进行第二下界剪枝处理。
在本公开的一个实施例中，根据所述第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名还包括：对任一所述待查询区域的四个子节点待查询区域进行有序编码；将被所述第一轨迹经过的子节点待查询区域记作第一标识，以及将未被所述第一轨迹经过的子节点待查询区域记作第二标识；根据所述有序编码、所述第一标识和所述第二标识，确定所述第一轨迹的轨迹签名。
在本公开的一个实施例中，根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理还包括：确定所述第一轨迹的轨迹签名下界和所述第二轨迹的轨迹签名下界的之间的轨迹签名弗雷歇距离；根据所述轨迹签名弗雷歇距离与第三预设距离之间的大小关系，对所述第二轨迹进行第三下界剪枝处理。
根据本公开的另一个方面，提供一种轨迹近邻查询装置，包括：获取模块，用于获取待查询的第一轨迹，并确定所述第一轨迹的空间位置信息；签名模块，用于根据所述第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名；确定模块，用于通过XZ-Ordering确定所述第一轨迹的空间位置索引编码；索引模块，用于根据所述轨迹签名和所述空间位置索引编码，构建所述第一轨迹的空间范围索引。
根据本公开的再一个方面，提供一种电子设备，包括：处理器；以及存储器，用于存储处理器的可执行指令；其中，处理器配置为经由执行可执行指令来执行上述任意一项的轨迹近邻查询方法。
根据本公开的又一个方面，提供一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现上述任意一项的轨迹近邻查询方法。
本公开的实施例所提供的轨迹近邻查询方案，通过构建第一轨迹的空间范围索引，提高了待查询区域的索引和查询的效率，进而提升了在待查询区域内确定与待查询轨迹临近的轨迹的效率和准确性。
进一步地，通过区域剪枝对待查询区域进行剪枝处理，精简了第二轨迹的查询范围，提高了空间范围查询的效率，加快了查询过程。
更进一步地，通过对第二轨迹进行下界剪枝处理，降低了弗雷歇距离的计算量，减少了不必要的轨迹查询和查询时间。
最后，通过将空间范围索引随机存储至分布式服务器，降低了轨迹数据的维护压力，提升了轨迹近邻查询的可靠性。
应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本公开。
附图说明
此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本公开的实施例，并与说明书一起用于解释本公开的原理。显而易见地，下面描述中的附图仅仅是本公开的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1A示出本公开实施例中一种轨迹近邻查询方案的编码示意图；
图1B示出本公开实施例中一种轨迹近邻查询方案的编码示意图；
图1C示出本公开实施例中一种轨迹近邻查询方案的编码示意图；
图1D示出本公开实施例中一种轨迹近邻查询方案的编码示意图；
图2示出本公开实施例中一种轨迹近邻查询方法的流程图；
图3示出本公开实施例中另一种轨迹近邻查询方法的流程图；
图4示出本公开实施例中另一种轨迹近邻查询方法的流程图；
图5示出本公开实施例中另一种轨迹近邻查询方法的流程图；
图6示出本公开实施例中又一种轨迹近邻查询方法的流程图；
图7示出本公开实施例中又一种轨迹近邻查询方法的流程图；
图8示出本公开实施例中又一种轨迹近邻查询方法的流程图；
图9示出本公开实施例中又一种轨迹近邻查询方法的流程图；
图10示出本公开实施例中又一种轨迹近邻查询方法的流程图；
图11示出本公开实施例中又一种轨迹近邻查询方法的流程图；
图12示出本公开实施例中又一种轨迹近邻查询方法的流程图；
图13示出本公开实施例中又一种轨迹近邻查询方法的流程图；
图14示出本公开实施例中一种轨迹近邻查询方案的示意图；
图15示出本公开实施例中又一种轨迹近邻查询方案的示意图；
图16示出本公开实施例中一种轨迹近邻查询方案的测试结果的示意图；
图17示出本公开实施例中一种轨迹近邻查询方案的测试结果的示意图；
图18示出本公开实施例中一种轨迹近邻查询方案的测试结果的示意图；
图19示出本公开实施例中一种轨迹近邻查询方案的测试结果的示意图；
图20示出本公开实施例中一种轨迹近邻查询装置的示意图；
图21示出本公开实施例中一种电子设备的示意图。
具体实施方式
现在将参考附图更全面地描述示例实施方式。然而，示例实施方式能够以多种形式实施，且不应被理解为限于在此阐述的范例；相反，提供这些实施方式使得本公开将更加全面和完整，并将示例实施方式的构思全面地传达给本领域的技术人员。所描述的特征、结构或特性可以以任何合适的方式结合在一个或更多实施方式中。
此外，附图仅为本公开的示意性图解，并非一定是按比例绘制。图中相同的附图标记表示相同或类似的部分，因而将省略对它们的重复描述。附图中所示的一些方框图是功能实体，不一定必须与物理或逻辑上独立的实体相对应。可以采用软件形式来实现这些功能实体，或在一个或多个硬件模块或集成电路中实现这些功能实体，或在不同网络和/或处理器装置和/或微控制器装置中实现这些功能实体。
本公开提供的方案，通过构建第一轨迹的空间范围索引，提高了待查询区域的索引和查询的效率，进而提升了在待查询区域内确定与待查询轨迹临近的轨迹的效率和准确性。进一步地，通过区域剪枝对待查询区域进行剪枝处理，精简了第二轨迹的查询范围，提高了空间范围查询的效率，加快了查询过程。更进一步地，通过对第二轨迹进行下界剪枝处理，降低了弗雷歇距离的计算量，减少了不必要的轨迹查询和查询时间。最后，通过将空间范围索引随机存储至分布式服务器，降低了轨迹数据的维护压力，提升了轨迹近邻查询的可靠性。
如图1所示，在本公开的轨迹近邻查询方案中，涉及到以下几个关键概念：
(1)GPS点(GPSPoint)：GPS点p＝(lat；lng；t)包含一个纬度lat，一个经度lng，以及一个时间戳t。表示移动物体在t时刻，位于地理坐标位置(lat；lng)。
(2)轨迹(Trajectory)：一条轨迹tr＝<P1→p2→…→pn>是将同一个移动对象产生的GPS点按时间先后顺序排序所组成的序列，即：
Figure BDA0002865699010000061
Figure BDA0002865699010000062
(3)路径(Path)：路径P＝<e1→e2→…→en>是一组连续路段的集合，其中路段的顺序即为对象移动的顺序。通常使用一个自然数代表路段标识。
(4)匹配后的轨迹(MapMatchTrajectory)：轨迹经过地图匹配算法后可映射至路段的路段，形成匹配后的轨迹tr＝<(e1,t1)→(e2,t2)→…→(en,tn)>。其中，ei指的是路网上路段的标识，ti指的是移动对象进入该路段的时间。下文中，如无特殊说明，所说的轨迹均为匹配后的轨迹。
(5)轨迹近邻查询(PathTemporalRangeQuery)：给定一条路径P，一个时间范围[ts,te]以及一个匹配轨迹集合T，轨迹近邻查询找到T中所有匹配轨迹tri，其存在某条子轨迹tr′i＝<(e1,t1)→(e2,t2)→…→(ek,tk)>恰好在给定时间段内经过路径P，即：t1≥ts,tk≤te。
(6)NoSQL：泛指非关系型数据库，其数据存储无需固定的表格模式，其产生是为了解决大数据集合多重数据种类带来的挑战，尤其是大数据应用难题。
(7)HBase：一个高可靠性、高性能、面向列和可伸缩的分布式存储系统，可在廉价机器上搭建起大规模结构化存储集群，是NoSQL的一种。
(8)弗雷歇距离：Fréchet Distance，一种路径空间相似性描述，常用来衡量轨迹之间的相似度。
(9)XZ-Ordering：一种结合时间信息的空间填充曲线的编码方式。
(10)优先队列：一种常见的数据结构，其元素被赋予优先级，具有最高优先级的元素最先删除，故于普通队列的先进先出相比，优先队列具有最高级先出的特征。
本公开实施例提供的方案涉及后缀树、路径分解和分布式架构等技术，具体通过如下实施例进行说明。
上述轨迹近邻查询方案可以通过多个终端和服务器集群的交互实现。
终端可以是手机、游戏主机、平板电脑、电子书阅读器、智能眼镜、MP4(MovingPicture Experts Group Audio Layer IV，动态影像专家压缩标准音频层面4)播放器、智能家居设备、AR(Augmented Reality，增强现实)设备、VR(Virtual Reality，虚拟现实)设备等移动终端，或者，终端也可以是个人计算机(Personal Computer，PC)，比如膝上型便携计算机和台式计算机等等。
其中，终端中可以安装有用于提供轨迹近邻查询的应用程序。
终端与服务器集群之间通过通信网络相连。可选的，通信网络是有线网络或无线网络。
服务器集群是一台服务器，或者由若干台服务器组成，或者是一个虚拟化平台，或者是一个云计算服务中心。服务器集群用于为提供轨迹近邻查询的应用程序提供后台服务。可选地，服务器集群承担主要计算工作，终端承担次要计算工作；或者，服务器集群承担次要计算工作，终端承担主要计算工作；或者，终端和服务器集群之间采用分布式计算架构进行协同计算。
在一些可选的实施例中，后缀树索引最开始是用来索引字符串，能够提高字符串后缀搜索的性能。在轨迹数据管理中，匹配后的轨迹可以看作是一个字符串，每个路段的标识等价于字符串的一个字符，路径查询(不考虑时间过滤条件)可以映射成字符串的后缀搜索问题，即：利用路段标识序列进行搜索可以看作是利用字符序列进行搜索。
可选地，不同的终端中安装的应用程序的客户端是相同的，或两个终端上安装的应用程序的客户端是不同控制系统平台的同一类型应用程序的客户端。基于终端平台的不同，该应用程序的客户端的具体形态也可以不同，比如，该应用程序客户端可以是手机客户端、PC客户端或者全球广域网客户端等。
本领域技术人员可以知晓，上述终端的数量可以更多或更少。比如上述终端可以仅为一个，或者上述终端为几十个或几百个，或者更多数量。本公开实施例对终端的数量和设备类型不加以限定。
可选的，该系统还可以包括管理设备，该管理设备与服务器集群之间通过通信网络相连。可选的，通信网络是有线网络或无线网络。
可选的，上述的无线网络或有线网络使用标准通信技术和/或协议。网络通常为因特网、但也可以是任何网络，包括但不限于局域网(Local Area Network，LAN)、城域网(Metropolitan Area Network，MAN)、广域网(W标识e Area Network，WAN)、移动、有线或者无线网络、专用网络或者虚拟专用网络的任何组合)。在一些实施例中，使用包括超文本标记语言(Hyper Text Mark-up Language，HTML)、可扩展标记语言(ExtensibleMarkupLanguage，XML)等的技术和/或格式来代表通过网络交换的数据。此外还可以使用诸如安全套接字层(Secure Socket Layer，SSL)、传输层安全(Transport Layer Security，TLS)、虚拟专用网络(Virtual Private Network，VPN)、网际协议安全(InternetProtocolSecurity，IPsec)等常规加密技术来加密所有或者一些链路。在另一些实施例中，还可以使用定制和/或专用数据通信技术取代或者补充上述数据通信技术。
下面，将结合附图及实施例对本示例实施方式中的轨迹近邻查询方法的各个步骤进行更详细的说明。
图2示出本公开实施例中一种轨迹近邻查询方法流程图。本公开实施例提供的方法可以由任意具备计算处理能力的电子设备执行，以服务器集群为执行主体进行示例说明。
如图2所示，服务器集群执行轨迹近邻查询方法，包括以下步骤：
步骤S202，获取待查询的第一轨迹，并确定所述第一轨迹的空间位置信息。
步骤S204，根据所述第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名。
在上述实施例中，如图1A所示，将待查询区域102划分成β×β个大小相同的区域，β为大于或等于1的整数，并对每个区域从0开始进行编码，也即轨迹(tr)104的空间位置信息可以通过一个β×β二进制序列来表示。
譬如，如果轨迹(tr)104内至少有一个GPS点落在某个区域中，其对应的二进制位置为1，否则置为0，如图1A和图1C所示，PosCode(tr)＝0011。
步骤S206，通过XZ-Ordering确定所述第一轨迹的空间位置索引编码。
在上述实施例中，如图1B所示，空间位置索引编码XZ2是基于XZ-Ordering生成的编码，首先获得一个轨迹的四进制序列，然后将这个四进制序列转化成一个十进制的长整型数字。
步骤S208，根据所述轨迹签名和所述空间位置索引编码，构建所述第一轨迹的空间范围索引。
在上述实施例中，如图1D所示，通过构建第一轨迹的空间范围索引XZ2+，提高了待查询区域的索引和查询的效率，进而提升了在待查询区域内确定与待查询轨迹临近的轨迹的效率和准确性。进一步地，通过区域剪枝对待查询区域进行剪枝处理，精简了第二轨迹的查询范围，提高了空间范围查询的效率，加快了查询过程。更进一步地，通过对第二轨迹进行下界剪枝处理，降低了弗雷歇距离的计算量，减少了不必要的轨迹查询和查询时间。
基于图2所示的步骤，如图3所示，轨迹近邻查询方法还包括：
步骤S302，确定所述第一轨迹的标识。
步骤S304，将所述第一轨迹的标识添加至所述空间范围索引XZ2+的后缀。
在上述实施例中，如图1D所示，通过将所述第一轨迹的标识添加至所述空间范围索引XZ2+的后缀tid，支持空间范围查询，即给定查询空间，便可查询出该空间内所有的轨迹记录。
基于图2所示的步骤，如图4所示，轨迹近邻查询方法还包括：
步骤S402，获取所述第一轨迹的随机数。
步骤S404，将所述随机数添加至所述空间范围索引XZ2+的前缀shard。
步骤S406，如图1D所示，根据所述前缀shard将所述空间范围索引XZ2+随机存储至分布式服务器。
在上述实施例中，通过将空间范围索引XZ2+随机存储至分布式服务器，能够有效地将数据分散到不同的数据服务器中，提升了负载均衡和数据热点的压力，降低了高量级的轨迹数据的维护压力，提升了轨迹近邻查询的可靠性。
基于图2所示的步骤，如图5所示，轨迹近邻查询方法还包括：
步骤S502，从存储所述待查询区域的第一优先队列中取出一个待查询区域。
步骤S504，确定所述待查询区域的空间位置索引编码XZ2的编码长度。
步骤S506，根据所述编码长度与预设长度之间的大小关系，对所述待查询区域进行扩展或对停止对所述待查询区域进行分裂。
在上述实施例中，由于待查询区域的空间位置索引编码XZ2的编码长度越大，表明轨迹的空间表示越精确，因此，通过预设长度来控制待查询区域的精度。
基于图2和图5所示的步骤，如图6所示，根据所述编码长度与预设长度之间的大小关系，对所述待查询区域进行扩展或对停止对所述待查询区域进行分裂包括：
步骤S6062，判断所述编码长度是否大于所述预设长度，若是，则执行步骤S6064，若否，则执行步骤S6068。
步骤S6064，若判定所述编码长度大于所述预设长度，则不对所述待查询区域进行分裂。
步骤S6066，在所待查询区域内执行空间范围查询处理。
在上述实施例中，若判定所述编码长度大于所述预设长度，则不对所述待查询区域进行分裂，并且在所待查询区域内执行空间范围查询处理，在保证查询精度的前提下，有效地缩减了第二轨迹的查询范围。
基于图2和图5所示的步骤，如图6所示，根据所述编码长度与预设长度之间的大小关系，对所述待查询区域进行扩展或对停止对所述待查询区域进行分裂还包括：
步骤S6062，判断所述编码长度是否大于所述预设长度。
步骤S6068，若判定所述编码长度小于或等于所述预设长度，则对所述待查询区域进行四叉树递归分裂，以生成所述待查询区域的子节点待查询区域，至所述子节点待查询区域的编码长度大于或等于所述预设长度为止。
在上述实施例中，若判定所述编码长度小于或等于所述预设长度，通过对所述待查询区域进行四叉树递归分裂，至所述子节点待查询区域的编码长度大于或等于所述预设长度为止，以准确地控制待查询区域的分裂过程。
基于图2所示的步骤，如图7所示，轨迹近邻查询方法还包括：
步骤S702，在停止对所述待查询区域进行四叉树递归分裂后，确定所述待查询区域内的第二轨迹，并将所述第二轨迹存储至第二优先队列。
在上述实施例中，在停止对所述待查询区域进行四叉树递归分裂后，确定所述待查询区域内的第二轨迹，并将所述第二轨迹存储至第二优先队列，且第二优先队列中的第二轨迹的数量满足查询数量的要求。
另外，第二优先队列中的第二轨迹也是具有优先级的，具有最高优先级的元素最先删除，也即在后续的下界剪枝处理过程中，优先被剪枝处理，以更快地获得满足查询距离要求的第二轨迹。
具体地，如果待查询区域的编码序列长度小于系统给定的一个常数g，将待查询区域的四个四叉树的子节点加入到第一优先队列中，然后检查第一优先队列中的下一个区域。如果待查询区域的编码序列长度达到了给定的常数g，不再对待查询区域进行分裂，直接利用待查询区域执行空间范围查询，得到轨迹结果集TSR。
基于图2所示的步骤，如图8所示，轨迹近邻查询方法还包括：
步骤S802，确定所述第一轨迹与所述待查询区域之间的第一弗雷歇距离。
步骤S804，判断所述第一弗雷歇距离是否大于或等于最大距离阈值，若是，则执行步骤S806，若否，则执行步骤S810。
步骤S806，若判定所述第一弗雷歇距离大于或等于所述最大距离阈值，对所述待查询区域进行区域剪枝处理。
步骤S808，根据所述区域剪枝处理的结果对所述最大距离阈值进行更新。
步骤S810，对待查询区域内的第二轨迹进行查询。
在上述实施例中，发明人经过验证和推理确定，如果
Figure BDA0002865699010000111
那么存在fF(q,tr)＞dmax成立，fF(q,tr)为轨迹与待查询空间之间的弗雷歇距离，其中，轨迹tr是由待查询空间进行空间范围查询时，第一次被检索出的轨迹。
具体地，如果第二轨迹不是第一次被检索出来，即被之前某个“内部”的查询区域检索出来，那么它必定被检查过是否存在k邻近轨迹查询的结果集中。
另外，如果第二轨迹是第一次被检索出来，那么有：
Figure BDA0002865699010000112
Figure BDA0002865699010000113
Figure BDA0002865699010000114
Figure BDA0002865699010000115
成立。
基于此，通过第一弗雷歇距离对待查询区域进行剪枝，能够有效地去除待查询区域的无效区域，进而能够提高轨迹近邻查询的效率和可靠性。
基于图2所示的步骤，如图9所示，轨迹近邻查询方法还包括：
步骤S902，确定所述第一轨迹的下界位置，以及所述待查询区域内的第二轨迹的下界位置。
步骤S904，根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理，所述下界位置包括起点下界位置、终点下界位置和轨迹签名下界位置中的至少一种。
在上述实施例中，通过第一轨迹的下界位置和第二轨迹的下界位置之间的弗雷歇距离进行剪枝处理，避免了对第一轨迹和第二轨迹的全部轨迹点进行距离计算的运算量，降低了时间复杂度。
基于图2所示的步骤，如图10所示，根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理包括：
步骤S10042，确定所述第一轨迹的起点下界位置和所述第二轨迹的起点下界位置之间的起点弗雷歇距离。
步骤S10044，根据所述起点弗雷歇距离与第一预设距离之间的大小关系，对所述第二轨迹进行第一下界剪枝处理。
基于图2和图9所示的步骤，如图11所示，据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理还包括：
步骤S11042，确定所述第一轨迹的终点下界位置和所述第二轨迹的终点下界位置之间的终点弗雷歇距离。
步骤S11044，根据所述终点弗雷歇距离与第二预设距离之间的大小关系，对所述第二轨迹进行第二下界剪枝处理。
在上述实施例中，基于轨迹的起始和终点，本公开提出了相似轨迹的起止点距离下界(Lower Bound，lower_bound()返回值是一个迭代器,返回指向大于等于key的第一个值的位置)。如果该距离下界大于给定的相似度阈值ε，那么第一轨迹和第二轨迹必定不会相似，基于此，对待查询区域的第二轨迹进行快速剪枝。
基于图2所示的步骤，如图12所示，根据所述第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名还包括：
步骤S12042，对任一所述待查询区域的四个子节点待查询区域进行有序编码。
步骤S12044，将被所述第一轨迹经过的子节点待查询区域记作第一标识，以及将未被所述第一轨迹经过的子节点待查询区域记作第二标识。
步骤S12046，根据所述有序编码、所述第一标识和所述第二标识，确定所述第一轨迹的轨迹签名。
在上述实施例中，第一标识可以为二进制的“1”，第二标识可以为二进制的“0”，按照有序编码的顺序来生成具备唯一性的轨迹签名。
基于图2和图9所示的步骤，如图13所示，根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理还包括：
步骤S13042，确定所述第一轨迹的轨迹签名下界和所述第二轨迹的轨迹签名下界的之间的轨迹签名弗雷歇距离。
步骤S13044，根据所述轨迹签名弗雷歇距离与第三预设距离之间的大小关系，对所述第二轨迹进行第三下界剪枝处理。
在上述实施例中，发明人经过验证和推理确定，如果
Figure BDA0002865699010000131
Figure BDA0002865699010000132
那么fF(tr,q)＞ε。
证明：对于任何一个点qi∈q和pj∈tr，它们必定分别落在待查询区域q和轨迹tr中的一个签名区域
Figure BDA0002865699010000133
和
Figure BDA0002865699010000134
中。
因此，可以证得：
Figure BDA0002865699010000135
Figure BDA0002865699010000136
Figure BDA0002865699010000137
Figure BDA0002865699010000138
其中，SIG_LB的计算时间复杂度为O(α2)，并且，α＜＜|q|，α＜＜|tr|，可以视为一个常数，因此仍能极大地加快过滤效果。
基于此，轨迹签名能够更加精确地表明轨迹的位置信息，因此，本公开提出了一个签名下界的手段，如果两条轨迹的签名下界大于给定阈值ε，那么第一轨迹和第二轨迹肯定不会相似，对待查询区域的第二轨迹进行更高效的快速剪枝。
图14至图19示出了轨迹近邻查询方案的一个实施例，在轨迹k邻近查询中，本公开将空间范围查询看作一个子操作。
如图14所示，给定一条查询轨迹q，一个距离阈值ε(假设本公开已经将其单位从长度转化成了空间坐标度数)，可以获得两个空间区域R1＝{lat1-ε,lng1-ε,lat1+ε,lng1+ε}和R2＝{latn-ε,lngn-ε,latn+ε,lngn+ε}，其中GPS点(lat1,lng1)和(latn,lngn)分别是查询轨迹q的起始点和终止点。对于弗雷歇距离fF来说，所有与q相似的轨迹必定包含在空间范围查询的结果T′＝SR_query(T；R1)∩SR_query(T；R2)中。
MBR(最小边界矩形)剪枝：给定一条查询查询轨迹q，一个相似度阈值ε，其中q.mbr＝{latmin,lngmin,latmax,lngmax}。本公开可以得到一个空间范围S＝{latmin-ε,lngmin-ε,latmax+ε,lngmax+ε}，所有与q相似的轨迹的MBR必完全包含在S中。
结合图15所示，发明人针对第一轨迹tr1和第二轨迹tr2的相似度，提出了下界剪枝和轨迹签名剪枝，提出并验证了以下定理来提升轨迹近邻查询的可靠性和效率。
定理1.相似轨迹查询完整性定理：对于弗雷歇距离fF而言，与给定查询轨迹形似的所有轨迹都在集合T′中。
定理2.区域剪枝定理：如果
Figure BDA0002865699010000141
那么fF(q,tr)＞dmax，其中轨迹tr是由r进行空间范围查询第一次被检索出的轨迹。
定理3.MBR剪枝定理：如果轨迹tr未完全包含于区域S中，即：tr中至少存在一个GPS点p落在了区域S之外，那么对于弗雷歇距离而言，tr必定不会与q相似。
定理4.起止点下界剪枝定理：如果
Figure BDA0002865699010000142
那么fF(tr,q)＞ε。如果
Figure BDA0002865699010000143
那么fF(tr,q)＞ε。
定理5.签名下界剪枝定理：如果
Figure BDA0002865699010000144
那么fF(tr,q)＞ε。
根据本公开的实施例，通过输入查询点q、弗雷歇距离函数fF、要返回的轨迹数目k，输出为k—近邻点查询轨迹结果集Tknn，具体可以分为以下三个阶段：
查询第一阶段：主要是初始化一些变量，其中，cdq是用于存储第二轨迹的第二优先队列，req标识第一优先队列，记录着将要检查的空间区域范围，dmax是当前查询轨迹q与cdq内所有轨迹距离的最大值。
查询第二阶段：从req中取出一个空间区域r。如果在候选集cdq中已经有k条轨迹，并且空间区域r与查询轨迹q的距离大于dmax，那么意味着那些未检索到的轨迹肯定不会在结果集中(见定理2，本公开称之为区域剪枝)，查询过程可以结束。
如果r的编码序列长度小于系统给定的一个常数g，本公开将r的四个四叉树的孩子节点加入到req中，然后检查req中的下一个区域。
如果r的编码序列长度达到了给定的常数g，本公开不再对r进行分裂，直接利用r执行一个空间范围查询，得到结果集TSR。
对于每条轨迹tr∈TSR，由于轨迹之间的相似度时间开销过大，本公开提出了两个下界剪枝策略。
如果tr满足以上所有的下界，本公开将其加入到候选结果集cdq中，然后更新dmax。
查询第三阶段：当req所有的候选区域都被检查完毕，本公开将候选结果cdq中的轨迹作为最后的结果并返回。
图16至图19给出了本公开的轨迹近邻查询的性能测试结果和查询性能结果。
(1)性能测试结果
本公开采用两个数据集来验证本公开所提方法的性能：1)T-Drive[1]，这是一个公开数据集，包含北京10000多辆出租车的GPS点信息，时间跨度从2008年2月2日到2008年2月8日共7天；2)Lorry，这是一个卡车GPS轨迹数据集，包含广州近50000辆京东物流卡车一个月的GPS轨迹信息，时间跨度为2014年3月1日到2014年3月31日。本公开使用Spark预处理处理轨迹，HBase作为底层NoSQL存储。所有的实验均在一个具有5个节点的集群中执行，每个节点安装有Centos7.4操作系统，具有8核的CPU、32GB的内存和1T的普通机械磁盘。
如图16和图17所示，本公开所提方法为TM，并提出三种对比实验：1)Dita，这是一个有代表性的基于内存的轨迹管理系统，它提出了一个有效地数据划分方法，解决了数据局部性问题，还提出了一个基于成本的技术实现了负载均衡，其主要思想是通过识别出有代表性的GPS点，然后基于这些代表点设计了一个树结构的索引，能够高效过滤掉那些不相似的轨迹；2)TMnps，这是TM方法的一个变种，在空间范围索引表中，没有采用PosCode编码技术；3)TMnlb，这是TM方法的另一个变种在相似查询的过程中，其不采用下界剪枝策略。
在考虑轨迹相似度量时，本公开采用弗雷歇距离fF，其他的距离度量函数例如豪斯多夫距离fH及动态时间规整fD的实验结果类似。
(2)查询性能比较。
如图18和图19所示，比较了不同的数据量情况下，相似查询时间的变化情况。相似度阈值默认为3km。
对于所有的方法来说，随着数据量的增大，相似查询所需时间越多，因为数据量越大，在相同的相似度阈值情况下，返回的轨迹也越多。TM比TMnps稍快，因为相似查询底层调用的是空间范围查询，其中PosCode编码能够减少不必要的轨迹扫描，提升查询效率。
若不使用下界剪枝过滤算法，本公开需要调用弗雷歇距离计算公式对所有满足空间范围查询的轨迹进行验证，这非常耗时，因此TMnlb比TM要慢一些。Dita比TM要慢很多，正如前面所述，Dita在内存中构建了很大的索引，对于每个查询，Dita都会扫描索引文件，花费了不少时间。
而TM能够直接产生查询窗口，然后再底层转化成并行的SCAN操作。由于需要较多的内存开销，Dita对集群要求比较高，其扩展性受到了限制。
实际上，当Lorry(载重)数据集大于60％时，Dita抛出了内存溢出异常，但是TM仍然能够运行得非常好，即使Lorry数据集达到100％，TM仍然能够平稳工作，这体现了TM方法强大的可扩展性。
如图18和图19所示，随着相似度阈值ε的增大，对于所有的方法来说，相似查询的时间开销也稍微增大，因为这会返回更多满足条件的轨迹。TM及其变种方法比Dita快很多，甚至有时候达到了3个数量级的效率提升，这进一步证明了本公开的效率。
下面参照图20来描述根据本公开的这种实施方式的轨迹近邻查询装置2000。图20所示的轨迹近邻查询装置2000仅仅是一个示例，不应对本公开实施例的功能和使用范围带来任何限制。
轨迹近邻查询装置2000以硬件模块的形式表现。轨迹近邻查询装置2000的组件可以包括但不限于：获取模块2002、签名模块2004、确定模块2006和索引模块2008。
获取模块2002，用于获取待查询的第一轨迹，并确定所述第一轨迹的空间位置信息。
签名模块2004，用于根据所述第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名。
确定模块2006，用于通过XZ-Ordering确定所述第一轨迹的空间位置索引编码。
索引模块2008，用于根据所述轨迹签名和所述空间位置索引编码，构建所述第一轨迹的空间范围索引。
本公开提出了一种轨迹近邻查询方案，通过构建第一轨迹的空间范围索引，提高了待查询区域的索引和查询的效率，进而提升了在待查询区域内确定与待查询轨迹临近的轨迹的效率和准确性。进一步地，通过区域剪枝对待查询区域进行剪枝处理，精简了第二轨迹的查询范围，提高了空间范围查询的效率，加快了查询过程。更进一步地，通过对第二轨迹进行下界剪枝处理，降低了弗雷歇距离的计算量，减少了不必要的轨迹查询和查询时间。最后，通过将空间范围索引随机存储至分布式服务器，降低了轨迹数据的维护压力，提升了轨迹近邻查询的可靠性。
下面参照图21来描述根据本公开的这种实施方式的电子设备2100。图21显示的电子设备2100仅仅是一个示例，不应对本公开实施例的功能和使用范围带来任何限制。
如图21所示，电子设备2100以通用计算设备的形式表现。电子设备2100的组件可以包括但不限于：上述至少一个处理单元2110、上述至少一个存储单元2120、连接不同系统组件(包括存储单元2120和处理单元2110)的总线2130。
其中，存储单元存储有程序代码，程序代码可以被处理单元2110执行，使得处理单元2110执行本说明书上述“示例性方法”部分中描述的根据本公开各种示例性实施方式的步骤。例如，处理单元2110可以执行如图2至图13中所示的轨迹近邻查询方法的步骤，以及本公开的其他实施例的轨迹近邻查询方法中限定的其他步骤。
存储单元2120可以包括易失性存储单元形式的可读介质，例如随机存取存储单元(RAM)21201和/或高速缓存存储单元21202，还可以进一步包括只读存储单元(ROM)21203。
存储单元2120还可以包括具有一组(至少一个)程序模块21205的程序/实用工具21204，这样的程序模块21205包括但不限于：操作系统、一个或者多个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。
总线2130可以为表示几类总线结构中的一种或多种，包括存储单元总线或者存储单元控制器、外围总线、图形加速端口、处理单元或者使用多种总线结构中的任意总线结构的局域总线。
电子设备2100也可以与一个或多个外部设备2140(例如键盘、指向设备、蓝牙设备等)通信，还可与一个或者多个使得用户能与该电子设备交互的设备通信，和/或与使得该电子设备2100能与一个或多个其它计算设备进行通信的任何设备(例如路由器、调制解调器等等)通信。这种通信可以通过输入/输出(I/O)接口2150进行。并且，电子设备2100还可以通过网络适配器2160与一个或者多个网络(例如局域网(LAN)，广域网(WAN)和/或公共网络，例如因特网)通信。网络适配器2160通过总线2130与电子设备2100的其它模块通信。应当明白，尽管图中未示出，可以结合电子设备使用其它硬件和/或软件模块，包括但不限于：微代码、设备驱动器、冗余处理单元、外部磁盘驱动阵列、RA标识系统、磁带驱动器以及数据备份存储系统等。
通过以上的实施方式的描述，本领域的技术人员易于理解，这里描述的示例实施方式可以通过软件实现，也可以通过软件结合必要的硬件的方式来实现。因此，根据本公开实施方式的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质(可以是CD-ROM，U盘，移动硬盘等)中或网络上，包括若干指令以使得一台计算设备(可以是个人计算机、服务器、终端装置、或者网络设备等)执行根据本公开实施方式的方法。
在本公开的示例性实施例中，还提供了一种计算机可读存储介质，其上存储有能够实现本说明书上述方法的程序产品。在一些可能的实施方式中，本公开的各个方面还可以实现为一种程序产品的形式，其包括程序代码，当程序产品在终端设备上运行时，程序代码用于使终端设备执行本说明书上述“示例性方法”部分中描述的根据本公开各种示例性实施方式的步骤。
根据本公开的实施方式的用于实现上述方法的程序产品，其可以采用便携式紧凑盘只读存储器(CD-ROM)并包括程序代码，并可以在终端设备，例如个人电脑上运行。然而，本公开的程序产品不限于此，在本文件中，可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。
计算机可读信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了可读程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。可读信号介质还可以是可读存储介质以外的任何可读介质，该可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。
可读介质上包含的程序代码可以用任何适当的介质传输，包括但不限于无线、有线、光缆、RF等等，或者上述的任意合适的组合。
可以以一种或多种程序设计语言的任意组合来编写用于执行本公开操作的程序代码，所述程序设计语言包括面向对象的程序设计语言—诸如Java、C++等，还包括常规的过程式程序设计语言—诸如“C”语言或类似的程序设计语言。程序代码可以完全地在用户计算设备上执行、部分地在用户设备上执行、作为一个独立的软件包执行、部分在用户计算设备上部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。在涉及远程计算设备的情形中，远程计算设备可以通过任意种类的网络，包括局域网(LAN)或广域网(WAN)，连接到用户计算设备，或者，可以连接到外部计算设备(例如利用因特网服务提供商来通过因特网连接)。
应当注意，尽管在上文详细描述中提及了用于动作执行的设备的若干模块或者单元，但是这种划分并非强制性的。实际上，根据本公开的实施方式，上文描述的两个或更多模块或者单元的特征和功能可以在一个模块或者单元中具体化。反之，上文描述的一个模块或者单元的特征和功能可以进一步划分为由多个模块或者单元来具体化。
此外，尽管在附图中以特定顺序描述了本公开中方法的各个步骤，但是，这并非要求或者暗示必须按照该特定顺序来执行这些步骤，或是必须执行全部所示的步骤才能实现期望的结果。附加的或备选的，可以省略某些步骤，将多个步骤合并为一个步骤执行，以及/或者将一个步骤分解为多个步骤执行等。
通过以上的实施方式的描述，本领域的技术人员易于理解，这里描述的示例实施方式可以通过软件实现，也可以通过软件结合必要的硬件的方式来实现。因此，根据本公开实施方式的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质(可以是CD-ROM，U盘，移动硬盘等)中或网络上，包括若干指令以使得一台计算设备(可以是个人计算机、服务器、移动终端、或者网络设备等)执行根据本公开实施方式的方法。
本领域技术人员在考虑说明书及实践这里公开的发明后，将容易想到本公开的其它实施方案。本公开旨在涵盖本公开的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本公开的一般性原理并包括本公开未公开的本技术领域中的公知常识或惯用技术手段。说明书和实施例仅被视为示例性的，本公开的真正范围和精神由所附的权利要求指出。

Claims (16)

1.一种轨迹近邻查询方法，其特征在于，包括：
获取待查询的第一轨迹，并确定所述第一轨迹的空间位置信息；
根据所述第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名；
通过XZ-Ordering确定所述第一轨迹的空间位置索引编码；
根据所述轨迹签名和所述空间位置索引编码，构建所述第一轨迹的空间范围索引。
2.根据权利要求1所述的轨迹近邻查询方法，其特征在于，还包括：
确定所述第一轨迹的标识；
将所述第一轨迹的标识添加至所述空间范围索引的后缀。
3.根据权利要求2所述的轨迹近邻查询方法，其特征在于，还包括：
获取所述第一轨迹的随机数；
将所述随机数添加至所述空间范围索引的前缀；
根据所述前缀将所述空间范围索引随机存储至分布式服务器。
4.根据权利要求1所述的轨迹近邻查询方法，其特征在于，还包括：
从存储所述待查询区域的第一优先队列中取出一个待查询区域；
确定所述待查询区域的空间位置索引编码的编码长度；
根据所述编码长度与预设长度之间的大小关系，对所述待查询区域进行扩展或对停止对所述待查询区域进行分裂。
5.根据权利要求4所述的轨迹近邻查询方法，其特征在于，根据所述编码长度与预设长度之间的大小关系，对所述待查询区域进行扩展或对停止对所述待查询区域进行分裂包括：
判断所述编码长度是否大于所述预设长度；
若判定所述编码长度大于所述预设长度，则不对所述待查询区域进行分裂；
在所待查询区域内执行空间范围查询处理。
6.根据权利要求4所述的轨迹近邻查询方法，其特征在于，根据所述编码长度与预设长度之间的大小关系，对所述待查询区域进行扩展或对停止对所述待查询区域进行分裂还包括：
判断所述编码长度是否大于所述预设长度；
若判定所述编码长度小于或等于所述预设长度，则对所述待查询区域进行四叉树递归分裂，以生成所述待查询区域的子节点待查询区域，至所述子节点待查询区域的编码长度大于或等于所述预设长度为止。
7.根据权利要求1所述的轨迹近邻查询方法，其特征在于，还包括：
在停止对所述待查询区域进行四叉树递归分裂后，确定所述待查询区域内的第二轨迹，并将所述第二轨迹存储至第二优先队列。
8.根据权利要求1所述的轨迹近邻查询方法，其特征在于，还包括：
确定所述第一轨迹与所述待查询区域之间的第一弗雷歇距离；
判断所述第一弗雷歇距离是否大于或等于最大距离阈值；
若判定所述第一弗雷歇距离大于或等于所述最大距离阈值，对所述待查询区域进行区域剪枝处理；
根据所述区域剪枝处理的结果对所述最大距离阈值进行更新。
9.根据权利要求1所述的轨迹近邻查询方法，其特征在于，还包括：
确定所述第一轨迹的下界位置，以及所述待查询区域内的第二轨迹的下界位置；
根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理，
所述下界位置包括起点下界位置、终点下界位置和轨迹签名下界位置中的至少一种。
10.根据权利要求9所述的轨迹近邻查询方法，其特征在于，根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理包括：
确定所述第一轨迹的起点下界位置和所述第二轨迹的起点下界位置之间的起点弗雷歇距离；
根据所述起点弗雷歇距离与第一预设距离之间的大小关系，对所述第二轨迹进行第一下界剪枝处理。
11.根据权利要求9所述的轨迹近邻查询方法，其特征在于，根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理还包括：
确定所述第一轨迹的终点下界位置和所述第二轨迹的终点下界位置之间的终点弗雷歇距离；
根据所述终点弗雷歇距离与第二预设距离之间的大小关系，对所述第二轨迹进行第二下界剪枝处理。
12.根据权利要求1所述的轨迹近邻查询方法，其特征在于，根据所述第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名还包括：
对任一所述待查询区域的四个子节点待查询区域进行有序编码；
将被所述第一轨迹经过的子节点待查询区域记作第一标识，以及将未被所述第一轨迹经过的子节点待查询区域记作第二标识；
根据所述有序编码、所述第一标识和所述第二标识，确定所述第一轨迹的轨迹签名。
13.根据权利要求12所述的轨迹近邻查询方法，其特征在于，根据所述第一轨迹的下界位置和所述第二轨迹的下界位置，对所述待查询区域的第二轨迹进行下界剪枝处理还包括：
确定所述第一轨迹的轨迹签名下界和所述第二轨迹的轨迹签名下界的之间的轨迹签名弗雷歇距离；
根据所述轨迹签名弗雷歇距离与第三预设距离之间的大小关系，对所述第二轨迹进行第三下界剪枝处理。
14.一种轨迹近邻查询装置，其特征在于，包括：
获取模块，用于获取待查询的第一轨迹，并确定所述第一轨迹的空间位置信息；
签名模块，用于根据所述第一轨迹的空间位置信息与待查询区域之间的位置关系，生成轨迹签名；
确定模块，用于通过XZ-Ordering确定所述第一轨迹的空间位置索引编码；
索引模块，用于根据所述轨迹签名和所述空间位置索引编码，构建所述第一轨迹的空间范围索引。
15.一种电子设备，其特征在于，包括：
处理器；以及
存储器，用于存储所述处理器的可执行指令；
其中，所述处理器配置为经由执行所述可执行指令来执行权利要求1-13中任一项所述的轨迹近邻查询方法。
16.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，
所述计算机程序被处理器执行时实现权利要求1-13中任一项所述的轨迹近邻查询方法。
CN202011583540.9A 2020-12-28 2020-12-28 轨迹近邻查询方法、装置、电子设备和可读存储介质 Active CN113792035B (zh)

Priority Applications (5)

Application Number Priority Date Filing Date Title
CN202011583540.9A CN113792035B (zh) 2020-12-28 2020-12-28 轨迹近邻查询方法、装置、电子设备和可读存储介质
PCT/CN2021/116994 WO2022142449A1 (zh) 2020-12-28 2021-09-07 轨迹近邻查询方法、装置、电子设备和可读存储介质
KR1020237021384A KR20230107369A (ko) 2020-12-28 2021-09-07 궤적 근접 조회 방법, 장치, 전자 기기 및 판독 가능한 저장 매체
JP2023540697A JP7683010B2 (ja) 2020-12-28 2021-09-07 軌跡近接クエリー方法、装置、電子デバイス及び読み取り可能な記憶媒体
US18/259,279 US20240061821A1 (en) 2020-12-28 2021-09-07 Nearest neighbor trajectory query method and apparatus, electronic device, and readable storage medium

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202011583540.9A CN113792035B (zh) 2020-12-28 2020-12-28 轨迹近邻查询方法、装置、电子设备和可读存储介质

Publications (2)

Publication Number Publication Date
CN113792035A true CN113792035A (zh) 2021-12-14
CN113792035B CN113792035B (zh) 2025-02-21

Family

ID=79181181

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202011583540.9A Active CN113792035B (zh) 2020-12-28 2020-12-28 轨迹近邻查询方法、装置、电子设备和可读存储介质

Country Status (5)

Country Link
US (1) US20240061821A1 (zh)
JP (1) JP7683010B2 (zh)
KR (1) KR20230107369A (zh)
CN (1) CN113792035B (zh)
WO (1) WO2022142449A1 (zh)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN117522921A (zh) * 2023-11-15 2024-02-06 广州市城市规划勘测设计研究院有限公司 一种时空轨迹索引方法、装置、设备及存储介质
CN118312474A (zh) * 2024-06-06 2024-07-09 华侨大学 基于时空特性的车牌识别数据分布式存储索引方法及系统

Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20170227364A1 (en) * 2016-02-10 2017-08-10 Fujitsu Limited Information processing apparatus and trajectory information generating method
CN107291842A (zh) * 2017-06-01 2017-10-24 武汉理工大学 基于轨迹编码的轨迹查询方法
CN108920499A (zh) * 2018-05-24 2018-11-30 河海大学 一种面向周期性检索的时空轨迹索引与检索方法
CN109005512A (zh) * 2018-06-26 2018-12-14 西北工业大学 一种面向特定时间间隔的位置预测方法
CN109165215A (zh) * 2018-07-27 2019-01-08 苏州视锐信息科技有限公司 一种云环境下时空索引的构建方法、装置及电子设备
WO2019024348A1 (zh) * 2017-08-04 2019-02-07 深圳大学 基于兴趣区域的轨迹查询的匀速搜索算法
US10331753B1 (en) * 2018-04-04 2019-06-25 The Florida International University Board Of Trustees Efficient progressive continuous k-nearest neighbor query algorithm for moving objects with a tree-like index
JP2020016984A (ja) * 2018-07-24 2020-01-30 株式会社豊田中央研究所 軌跡検索装置及び軌跡検索プログラム
CN111783738A (zh) * 2020-07-29 2020-10-16 中国人民解放军国防科技大学 一种通信辐射源异常运动轨迹检测方法

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050114331A1 (en) * 2003-11-26 2005-05-26 International Business Machines Corporation Near-neighbor search in pattern distance spaces
JP4946744B2 (ja) 2007-09-07 2012-06-06 株式会社デンソー 車載通信装置
US9593957B2 (en) * 2010-06-04 2017-03-14 Microsoft Technology Licensing, Llc Searching similar trajectories by locations
JP6350251B2 (ja) 2014-12-04 2018-07-04 富士通株式会社 経路情報処理装置、方法、及びプログラム
CN107463673A (zh) 2017-08-04 2017-12-12 深圳大学 基于兴趣区域的轨迹查询的扩张搜索算法
CN110543539B (zh) * 2019-08-29 2022-09-16 河海大学 一种分布式的路网环境下移动对象轨迹相似性查询方法
US11994863B2 (en) * 2019-12-03 2024-05-28 International Business Machines Corporation Trajectory similarity search

Patent Citations (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20170227364A1 (en) * 2016-02-10 2017-08-10 Fujitsu Limited Information processing apparatus and trajectory information generating method
CN107291842A (zh) * 2017-06-01 2017-10-24 武汉理工大学 基于轨迹编码的轨迹查询方法
WO2019024348A1 (zh) * 2017-08-04 2019-02-07 深圳大学 基于兴趣区域的轨迹查询的匀速搜索算法
US10331753B1 (en) * 2018-04-04 2019-06-25 The Florida International University Board Of Trustees Efficient progressive continuous k-nearest neighbor query algorithm for moving objects with a tree-like index
CN108920499A (zh) * 2018-05-24 2018-11-30 河海大学 一种面向周期性检索的时空轨迹索引与检索方法
CN109005512A (zh) * 2018-06-26 2018-12-14 西北工业大学 一种面向特定时间间隔的位置预测方法
JP2020016984A (ja) * 2018-07-24 2020-01-30 株式会社豊田中央研究所 軌跡検索装置及び軌跡検索プログラム
CN109165215A (zh) * 2018-07-27 2019-01-08 苏州视锐信息科技有限公司 一种云环境下时空索引的构建方法、装置及电子设备
CN111783738A (zh) * 2020-07-29 2020-10-16 中国人民解放军国防科技大学 一种通信辐射源异常运动轨迹检测方法

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN117522921A (zh) * 2023-11-15 2024-02-06 广州市城市规划勘测设计研究院有限公司 一种时空轨迹索引方法、装置、设备及存储介质
CN118312474A (zh) * 2024-06-06 2024-07-09 华侨大学 基于时空特性的车牌识别数据分布式存储索引方法及系统
CN118312474B (zh) * 2024-06-06 2024-08-09 华侨大学 基于时空特性的车牌识别数据分布式存储索引方法及系统

Also Published As

Publication number Publication date
US20240061821A1 (en) 2024-02-22
JP7683010B2 (ja) 2025-05-26
WO2022142449A1 (zh) 2022-07-07
JP2024502829A (ja) 2024-01-23
KR20230107369A (ko) 2023-07-14
CN113792035B (zh) 2025-02-21

Similar Documents

Publication Publication Date Title
US11461289B2 (en) Apparatus, systems, and methods for providing location information
Benetis et al. Nearest and reverse nearest neighbor queries for moving objects
CN112597190B (zh) 点近邻轨迹查询方法、装置、电子设备和可读存储介质
CN102521364B (zh) 一种图上两点间最短路径查询方法
CN113792035B (zh) 轨迹近邻查询方法、装置、电子设备和可读存储介质
CN113868351B (zh) 一种地址聚类方法、装置、电子设备及存储介质
CN111259282A (zh) Url去重方法、装置、电子设备及计算机可读存储介质
US9436715B2 (en) Data management apparatus and data management method
CN113312432A (zh) 关联信息处理方法及装置、计算机存储介质、电子设备
US20200005163A1 (en) Inference-use knowledge generation apparatus, inference-use knowledge generation method, and computer-readable recording medium
Zhang et al. DT-KST: Distributed top-k similarity query on big trajectory streams
Wang et al. ASQT: an efficient index for queries on compressed trajectories
Singh et al. Indexing hs code-a hybrid indexer for an optimized search of geotagged data
CN111797183A (zh) 挖掘信息点的道路属性的方法、装置及电子设备
Zhou et al. HDKV: supporting efficient high‐dimensional similarity search in key‐value stores
Peng et al. DOS: a spatial system offering extremely high-throughput road distance computations
US12339874B2 (en) Density-based data clustering apparatus and method
CN119474096A (zh) 一种基于地址结构化解析的自定义地址处理方法及装置
JP6510125B1 (ja) 情報処理装置、情報処理方法、及び情報処理プログラム
CN117931818A (zh) 空间变化数据联动更新方法、系统、设备及存储介质
HK40080885A (zh) 用於提供位置信息的裝置、系統和方法
KR20250008701A (ko) 사물데이터 관리장치 및 그 동작 방법
CN119106032A (zh) 数据存储方法、数据检索方法及相关装置
HK40024033A (zh) Url去重方法、裝置、電子設備及計算機可讀存儲介質

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant