Aggregate Nearest Neighbor Search Methods Using SSMTA* Algorithm on Road-Network
Aggregate Nearest Neighbor Search Methods Using SSMTA* Algorithm on Road-Network
复制标题
DOI：
10.1007/978-3-642-33074-2_14
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
H. Htoo;Y. Ohsawa;N. Sonehara;M. Sakauchi
中科院分区：
文献类型：
--
作者：
H. Htoo;Y. Ohsawa;N. Sonehara;M. Sakauchi
聚集最近邻(ANN)查询在基于位置的服务(LBSS)中扮演着重要的角色，当一群用户想要找到对他们所有人都有利的合适的兴趣点(POI)(例如，餐馆)时。在人工神经网络查询中，给定一组查询点q和一个聚合函数(例如，SUM)，然后确定一个POI(或k个POI)，该POI给出从每个查询点到POI的最小总行程距离。首先提出了以欧氏距离表示结果的人工神经网络查询方法，然后将其应用于基于路网距离的查询方法，为日常生活提供了更实用的解决方案。其中，增量欧几里德约束(IER)框架是一种简单而强大的策略，用于解决使用路网距离的ANN查询。IER框架由两个阶段组成：候选生成阶段和验证阶段。提出了一种适用于验证阶段的有效算法--单源多目标A*(SSMTA*)算法。本文首先介绍了SSMTA*，然后给出了一种将SSMTA*应用于ANN查询的方法。通过实验证明，本文提出的方法优于已有的方法。
Aggregate nearest neighbor (ANN) queries play an important role in location-based services (LBSs) when a group of users wants to find a suitable point of interest (POI)(eg, a restaurant) beneficial to all of them. In ANN queries, a set of query points Q and an aggregate function (eg, sum) are given, and then a POI is determined (or k POIs), which gives the minimum total travel distance from each query point to the POI. ANN query methods were first proposed giving results in Euclidean distance, and then were adapted to provide results using road-network distances which offer more practical solutions in the daily life. Among them, the incremental Euclidean restriction (IER) framework is a simple and powerful strategy for solving an ANN query using road-network distances. The IER framework consists of two phases: a candidate-generation phase and a verification phase. This paper proposes a powerful method that can be adapted to the verification phase, named a single-source multitarget A*(SSMTA*) algorithm. This paper first describes the SSMTA*, and then presents a method for its suitable application to ANN queries. Through experiments, this paper demonstrates that the proposed method outperforms the existing methods.