基于空间网络的关键字查询关键技术研究

发布时间：2018-07-12 15:33

本文选题：空间网络 + 关键字查询　；参考：《北京邮电大学》2017年博士论文

【摘要】：基于位置的服务是通过网络运营商的无线网络或外部定位系统获取移动终端用户的位置信息,在地理信息系统平台的支持下,为用户提供相应的服务。随着移动互联网的快速发展和带有定位模块的智能设备的广泛普及,基于位置的服务已经逐渐渗透到人们日常生活的方方面面,为人们的生活带来了极大的便利。例如,人们经常利用社交网络应用来查找附近的人,或使用地图软件来进行路线导航。作为位置服务中的一种重要应用,基于空间网络的关键字查询受到学术界和工业界的广泛关注。基于空间网络的关键字查询是根据用户输入的关键字,查询空间网络中该关键字所匹配的兴趣点信息。为提供优质的关键字查询服务,需要研究高效的基于空间网络的关键字查询方法,在满足用户查询需求的同时,保证查询结果的准确性和查询过程的高效性。随着社会的发展和人们生活水平的提高,用户的查询需求日趋多样化。例如,覆盖多个关键字的最受欢迎的区域查询,或基于多个用户的查询。然而,现有的研究在满足用户需求的多样化、查询结果的准确性以及查询时间的高效性等方面仍存在不足。因此,本文针对用户复杂查询需求(最受欢迎的多关键字兴趣点查询、满足多用户的多关键字区域查询和满足多用户的关键字路径查询),对基于空间网络的关键字查询问题进行了深入研究,并取得了以下创新性成果:(1)提出了一种基于空间网络的最受欢迎的多关键字兴趣点查询方法。首先,将该查询问题定义为找到既能覆盖用户需求关键字又能满足用户输入的约束条件(即查询范围约束以及分布范围约束)的最受欢迎的一个或多个兴趣点。然后,将带有兴趣点的空间网络数据建模为一个空间网络图。其中,每个带有坐标信息的节点表示一个兴趣点或一个交叉口(例如,路口等),每个兴趣点附着一个或多个关键字,每个关键字包含一个对应的评分用来表示其受欢迎程度;每一条边表示一段路径,边的权重表示路径长度。其次,针对小规模和大规模的空间网络,分别设计出精确的解决方案和启发式解决方案。为了进一步提高查询效率,分别提出了两个优化技术。其中,第一个是评分最大值预测技术,用来减少搜索空间。另一个是冗余计算减少技术,用来避免一些不必要的计算开销。最后,基于两个真实的数据集开展了实验,实验结果表明,针对大规模空间网络数据设计的查询算法不仅能够返回高精度的查询结果,而且随着数据规模的增大,其查询效率仍具有良好的可扩展性。(2)提出了一种基于空间网络的多用户多关键字区域查询方法。首先,将该查询定义为找到一个能够覆盖用户需求关键字的多个兴趣点组成的区域,且该区域满足与所有的用户之间的距离近和其中的兴趣点分布密集两个约束条件。然后,将带有兴趣点的空间网络数据建模为一个加权无向图。图中每一个节点表示一个兴趣点或一个交叉口(例如,路口等),它包含坐标信息;每一条边表示一段路径,边的权重表示该段路径的距离开销。基于该图模型,利用最短路径树算法和距离预测技术,建立高效的索引。其次,基于用户组分治技术,提出一个近似因子为5的高效算法,用来快速找到一个可行解,利用该可行解有效限制搜索空间。基于动态剪枝技术进一步提出了一个精确算法,和一个近似因子为7/15的近似算法。最后,基于两个真实的数据集开展了实验,实验结果表明,提出的近似查询算法不仅保证了查询结果的精确度,而且大幅度提高了查询效率。(3)提出了一种基于空间网络的多用户多关键字路径查询方法。首先,将该查询定义为找到一条能够顺序覆盖用户需求关键字且距离开销最小的路径。然后,提出了两个近似因子分别为n+3和n+1的近似算法,以快速找到第一个可行解,其中,n表示需求关键字的个数。利用该可行解的成本开销可以有效限制之后算法的搜索空间。其次,基于限制的搜索空间,提出了两个精确算法和一个贪心算法。其中,第一个精确算法是通过枚举出搜索空间中所有的可行解来找出最优解。为了提高搜索效率,基于成本函数的分离属性和动态剪枝技术提出了一个优化的精确算法。最后,基于两个真实的数据集开展了实验,实验结果表明,该算法在保证查询结果精确性的同时,满足了用户实时查询的要求。
[Abstract]:The invention provides a space network based keyword query method , which is based on a keyword query of a user input and a query result of a plurality of users . ( 2 ) A multi - user multi - key region query method based on spatial network is proposed . First , the query is defined as a region composed of multiple points of interest that can cover the user ' s demand key , and the region satisfies the distance between all users .
【学位授予单位】：北京邮电大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP391.3

【参考文献】