Continuous k nearest neighbor queries over large multi-attribute trajectories: a systematic approach
- 所属单位：计算机科学与技术学院/人工智能学院/软件学院
- 发表刊物：GEOINFORMATICA
- 关键字：Trajectories Multi-attribute Continuous queries Nearest neighbors Index structure Update
- 摘要：We study multi-attribute trajectories by combining standard trajectories (i.e., a sequence of timestamped locations) and descriptive attributes. A new form of continuous k nearest neighbor queries is proposed by integrating attributes into the evaluation. To enhance the query performance, a hybrid and flexible index is developed to manage both spatio-temporal data and attribute values. The index includes a 3D R-tree and a composite structure which can be popularized to work together with any R-tree based index and Grid-based index. We establish an efficient mechanism to update the index and define a cost model to estimate the I/Os. Query algorithms are proposed, in particular, an efficient method to determine the subtrees containing query attributes. Using synthetic and real datasets, we carry out comprehensive experiments in a prototype database system to evaluate the efficiency, scalability and generality. Our approach gains more than an order of magnitude speedup compared to three alternative approaches by using 1.8 millions of trajectories and hundreds of attribute values. The update performance is evaluated and the cost model is validated.
- ISSN号：1384-6175
- 是否译文：否
- 合写作者：Gueting, Ralf Hartmut,Gao, Yunjun
- 通讯作者：许建秋
- 发表时间：2018-10-01