The problem of continuously monitoring multiple K-nearest neighbor (K-NN) queries with dynamic object and query dataset is valuable for many location-based applications. A practical method is to partition the data spa...The problem of continuously monitoring multiple K-nearest neighbor (K-NN) queries with dynamic object and query dataset is valuable for many location-based applications. A practical method is to partition the data space into grid cells, with both object and query table being indexed by this grid structure, while solving the problem by periodically joining cells of objects with queries having their influence regions intersecting the cells. In the worst case, all cells of objects will be accessed once. Object and query cache strategies are proposed to further reduce the I/O cost. With object cache strategy, queries remaining static in current processing cycle seldom need I/O cost, they can be returned quickly. The main I/O cost comes from moving queries, the query cache strategy is used to restrict their search-regions, which uses current results of queries in the main memory buffer. The queries can share not only the accessing of object pages, but also their influence regions. Theoretical analysis of the expected I/O cost is presented, with the I/O cost being about 40% that of the SEA-CNN method in the experiment results.展开更多
命名数据网络(named data network,NDN)是一种以数据为中心的新型网络体系结构。现有NDN网络路由策略未能充分利用路由结点缓存导致转发效率不高。为了在路由决策中充分利用NDN网络中的缓存,提出了一种邻居缓存路由(neighbor cache expl...命名数据网络(named data network,NDN)是一种以数据为中心的新型网络体系结构。现有NDN网络路由策略未能充分利用路由结点缓存导致转发效率不高。为了在路由决策中充分利用NDN网络中的缓存,提出了一种邻居缓存路由(neighbor cache explore routing,NCE)策略,将路由结点缓存因素引入到路由决策中,并设计了相应的报文格式及路由选择算法。模拟实验结果表明,邻居缓存路由策略在减少网络冗余流量的同时提高了整体网络的性能,验证了NCE策略在NDN网络中的有效性。展开更多
路网k近邻查询返回距离查询点路径距离最短的k个兴趣点,是基于位置服务的重要技术之一。以往研究或采用无索引的在线扩展方式,或利用预先计算的索引结构来加快查找效率,前者需要大量的在线计算,后者需要较长的预处理时间及较大的存储空...路网k近邻查询返回距离查询点路径距离最短的k个兴趣点,是基于位置服务的重要技术之一。以往研究或采用无索引的在线扩展方式,或利用预先计算的索引结构来加快查找效率,前者需要大量的在线计算,后者需要较长的预处理时间及较大的存储空间,并未考虑到历史结果的复用情况,而实际应用中有大量的查询点位置相近,它们的查询结果相似。为了解决上述问题,提出了基于历史结果缓存的k近邻查询算法(CB k NN),通过选择性地缓存k近邻查询结果,对缓存的历史记录进行共享前缀检测,使更多的查询能够快速得到可利用的历史缓存记录,仅通过少量计算即可得到查询结果。实验证明,CB k NN算法在兴趣点密度较低的情况下,比无缓存算法的响应时间快25%。展开更多
基金Project (No.ABA048) supported by the Natural Science Foundationof Hubei Province,China
文摘The problem of continuously monitoring multiple K-nearest neighbor (K-NN) queries with dynamic object and query dataset is valuable for many location-based applications. A practical method is to partition the data space into grid cells, with both object and query table being indexed by this grid structure, while solving the problem by periodically joining cells of objects with queries having their influence regions intersecting the cells. In the worst case, all cells of objects will be accessed once. Object and query cache strategies are proposed to further reduce the I/O cost. With object cache strategy, queries remaining static in current processing cycle seldom need I/O cost, they can be returned quickly. The main I/O cost comes from moving queries, the query cache strategy is used to restrict their search-regions, which uses current results of queries in the main memory buffer. The queries can share not only the accessing of object pages, but also their influence regions. Theoretical analysis of the expected I/O cost is presented, with the I/O cost being about 40% that of the SEA-CNN method in the experiment results.
文摘路网k近邻查询返回距离查询点路径距离最短的k个兴趣点,是基于位置服务的重要技术之一。以往研究或采用无索引的在线扩展方式,或利用预先计算的索引结构来加快查找效率,前者需要大量的在线计算,后者需要较长的预处理时间及较大的存储空间,并未考虑到历史结果的复用情况,而实际应用中有大量的查询点位置相近,它们的查询结果相似。为了解决上述问题,提出了基于历史结果缓存的k近邻查询算法(CB k NN),通过选择性地缓存k近邻查询结果,对缓存的历史记录进行共享前缀检测,使更多的查询能够快速得到可利用的历史缓存记录,仅通过少量计算即可得到查询结果。实验证明,CB k NN算法在兴趣点密度较低的情况下,比无缓存算法的响应时间快25%。
