An efficient index structure for distributed k-nearest neighbours query processing
An efficient index structure for distributed k-nearest neighbours query processing
复制标题
DOI：
10.1007/s00500-018-3548-4
复制
发表时间：
2020-04-01
期刊：
影响因子：
4.1
通讯作者：
Yu, Xiaohui
中科院分区：
文献类型：
--
作者：
Yang, Min;Ma, Kun;Yu, Xiaohui
许多基于位置的服务都支持移动k-最近邻（k-NN）查询，它连续返回查询点的k-最近的数据对象。大多数现有的解决这个问题的方法都集中在一个集中式的设置，这显示出很差的可扩展性，以解决大规模和分布式数据集。在本文中，我们提出了一个有效的分布式解决方案的k-NN查询移动对象，以解决日益庞大的数据规模。该方法包括一个新的基于网格的索引称为块网格索引（BGI），和一个分布式k-NN查询算法的基础上BGI。我们的方法有三个优点：（1）BGI可以很容易地在分布式环境中构建和维护;（2）该算法能够在两次迭代中返回结果集。(3)提高了k-NN查询的效率。我们的解决方案的效率是通过数百万个节点的大量实验验证。
Many location-based services are supported by the moving k-nearest neighbour (k-NN) query, which continuously returns the k-nearest data objects for a query point. Most of existing approaches to this problem have focused on a centralized setting, which show poor scalability to work around massive-scale and distributed data sets. In this paper, we propose an efficient distributed solution for k-NN query over moving objects to tackle the increasingly large scale of data. This approach includes a new grid-based index called Block Grid Index (BGI), and a distributed k-NN query algorithm based on BGI. There are three advantages of our approach: (1) BGI can be easily constructed and maintained in a distributed setting; (2) the algorithm is able to return the results set in only two iterations. (3) the efficiency of k-NN query is improved. The efficiency of our solution is verified by extensive experiments with millions of nodes.