Publication Type

Journal Article

Version

publishedVersion

Publication Date

10-2018

Abstract

Nowadays, many location-based applications require the ability of querying k-nearest neighbors over a very large scale of5 moving objects in road networks, e.g., taxi-calling and ride-sharing services. Traditional grid index with equal-sized cells can not adapt6 to the skewed distribution of moving objects in real scenarios. Thus, to obtain the fast querying response time, the grid needs to be split7 into more smaller cells which introduces the side-effect of higher memory cost, i.e., maintaining such a large volume of cells requires a8 much larger memory space at the server side. In this paper, we present SIMkNN, a scalable and in-memory kNN query processing9 technique. SIMkNN is dual-index driven, where we adopt a R-tree to store the topology of the road network and a hierarchical grid10 model to manage the moving objects in non-uniform distribution. To answer a kNN query in real time, SIMkNN adopts the strategy that11 incrementally enlarges the search area for network distance based nearest neighbor evaluation. It is far from trivial to perform the12 space expansion within the hierarchical grid index. For a given cell, we first define its neighbors in different directions, then propose a13 cell communication technique which allows each cell in the hierarchical grid index to be aware of its neighbors at any time. Accordingly,14 an efficient space expansion algorithm to generate the estimation area is proposed. The experimental evaluation shows that SIMkNN15 outperforms the baseline algorithm in terms of time and memory efficiency

Keywords

—k-nearest neighbors, road network, hierarchical grid index

Discipline

Data Storage Systems | OS and Networks

Research Areas

Data Science and Engineering

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

30

Issue

10

First Page

1957

Last Page

1970

ISSN

1041-4347

Identifier

10.1109/TKDE.2018.2808971

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Additional URL

https://doi.org/10.1109/TKDE.2018.2808971

Download

Share

COinS