买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉大连海事大学申请的专利一种动态路网上基于树分解的kNN查询方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN116881581B 。

龙图腾网通过国家知识产权局官网在2025-06-24发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202310874608.6，技术领域涉及：G06F16/9537；该发明授权一种动态路网上基于树分解的kNN查询方法是由白梅;南彦鑫;王习特设计研发完成，并于2023-07-17向国家知识产权局提交的专利申请。

本一种动态路网上基于树分解的kNN查询方法在说明书摘要公布了：本发明公开了一种动态路网上基于树分解的kNN查询方法，包括获取道路网络数据集，根据道路网络数据集构建道路无向加权图，所述道路无向加权图包括顶点集合、边集合以及权重集合，根据道路无向加权图中构建树节点，将连接后的树节点集合作为矮状树分解，对矮状树分解的每个树节点进行编号并获取所有树节点的祖先数组、耗时数组以及子孙表集合，获取待查询顶点，根据矮状树分解获取待查询顶点的最近邻集合。在保证kNN查询的正确性的前提下，极大提高了查询时间和效率。

本发明授权一种动态路网上基于树分解的kNN查询方法在权利要求书中公布了：1.一种动态路网上基于树分解的kNN查询方法，其特征在于，包括， 步骤一、获取道路网络数据集，根据道路网络数据集构建道路无向加权图，所述道路无向加权图包括顶点集合、边集合以及权重集合，所述顶点为道路网络数据集中的路口，所述边为道路网络数据集中两个路口之间的路段，所述权重为车辆经过路段所需的平均时间， 步骤二、根据顶点的度对顶点集合进行升序排序，依次从排序后的顶点集合中选择顶点作为删除顶点，将删除顶点作为主顶点，根据主顶点和主顶点的邻居顶点集构造树节点，并为树节点分配一个删点序号，将树节点与删点序号存储在树节点集合中，根据删点序号对树节点集合进行升序排序， 步骤三、获取排序后的树节点集合，对于树节点集合中的每个树节点，将当前树节点的邻居顶点集中最先作为删除顶点所对应的树节点作为当前树节点的父节点，将当前树节点与父节点进行连接，将连接后的树节点集合作为矮状树分解， 步骤四、对矮状树分解的每个树节点进行编号，对于编号后的每个树节点分别构造祖先数组、耗时数组以及子孙表，获取所有树节点的祖先数组、耗时数组以及子孙表集合， 步骤五、获取待查询顶点，根据矮状树分解获取待查询顶点的祖先数组，依次计算祖先数组中每一个顶点与待查询顶点之间的最短路网耗时并判断最短路网耗时是否满足第一阈值，若不满足，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值，反之，则将祖先数组中的顶点加入至结果集并根据最短路网耗时更新第一阈值，同时获取顶点的子孙表，分别计算结果集中每一个顶点与子孙表中顶点之间的最短路网耗时，并判断顶点与子孙表中顶点之间的最短路网耗时与顶点与待查询顶点之间的最短路网耗时之和是否满足更新后的第一阈值，若最短路网耗时之和满足更新后的第一阈值，则将子孙表中的顶点加入至结果集，并根据最短路网耗时之和更新第一阈值，若最短路网耗时之和不满足更新后的第一阈值，则获取祖先数组中的下一个顶点，并重新计算顶点与待查询顶点之间的最短路网耗时并判断是否满足更新后的第一阈值， 步骤六、将结果集中前k个顶点作为待查询顶点的最近邻集合。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人大连海事大学，其通讯地址为：116000 辽宁省大连市甘井子区凌水街道凌海路1号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。