Dynamic Group Nearest Neighbor Group Query over Streaming Data

This paper studies the problem of dynamic group nearest neighbor group query (DGNNQ for short) over streaming data, an important problem in the domain of streaming data management. Let \(\mathcal {S}\) be the set of streaming data. A DGNNQ, denoted as \(q(n, s, k, \mathcal {Q})\) , monitors objects within the window that contains q(n) objects. Whenever q(s) objects pass, q returns q(k) objects with the smallest distance sum to the query point set \(\mathcal {Q}\) . Although some efforts can support this kind of queries, they incur highly running cost, especially when query points are allowed to be inserted into, or remove from \(\mathcal {Q}\) . In this paper, we propose a novel framework named Q2WP (short for Query points and Window-based Partition) over streaming data. We group nearby query points into k subsets, and form a group of k virtual points based on these subsets. We then propose a novel index named PM-Tree to organize these virtual points, as well as evaluate which objects have chance to become query result objects based on PM-Tree. We further propose a group of novel algorithms to support incremental maintenance when \(\mathcal {Q}\) updates. Extensive performance studies on large real-world and synthetic datasets demonstrate that the proposed framework can efficiently support DGNNQ over streaming data.