Aggregate keyword nearest neighbor queries on road networks

Given a group \(\mathcal {Q}\) of query points and a set \(\mathcal {P}\) of points of interest (POIs), aggregate nearest neighbor (ANN) queries find a POI p from \(\mathcal {P}\) that achieves the smallest aggregate distance. Specifically, the aggregate distance is defined over the set of distances between p and all query points in \(\mathcal {Q}\). Existing studies on ANN query mainly consider the spatial proximity, whereas the textual similarity has received considerable attention recently. In this work, we utilize user-specified query keywords to capture textual similarity. We study the aggregate keyword nearest neighbor (AKNN) queries, finding the POI that has the smallest aggregate distance and covers all query keywords. Nevertheless, existing methods on ANN query are either inapplicable or inefficient when applied to the AKNN query. To answer our query efficiently, we first develop a dual-granularity (DG) indexing schema. It preserves abstracts of the road network by a tree structure, and preserves detailed network information by an extended adjacency list. Then, we propose a minimal first search (MFS) algorithm. It traverses the tree and explores the node with the minimal aggregate distance iteratively. This method suffers from false hits arising from keyword tests. Thus, we propose the collaborative filtering technique, which performs keywords test by multiple keyword bitmaps collectively rather than by only one. Extensive experiments on both real and synthetic datasets demonstrate the superiority of our algorithms and optimizing strategies.