We propose an influential set based moving k keyword query processing model, which avoids the shortcoming of safe region-based approaches that the update cost and update frequency cannot be optimized simultaneously. Based on the model, we design a parallel query processing method and a parallel validation method for multicore processing platforms. The time complexity of the algorithms is O((log|D|+p.k)/p.k)？and O(log p.k), respectively, which are all O(1/k) times the time complexity of the state-of-the-art method. The experiment result confirms the superiority of our algorithms over the state-of-the-art method.
References
[1]
Li, C.W., Gu, Y., Qi, J.Z., Zhang, R. and Yu, G. (2014) A Safe Region Based Approach to Moving KNN Queries in Obstructed Space. Knowledge and Information Systems, 45, 1-35.
[2]
Wu, D., Yiu, M.L., Jensen, C.S. and Cong, G. (2011) Efficient Continuously Moving Top-K Spatial Keyword Query Processing. Proceedings of 2011 IEEE 27th International Conference on the Data Engineering (ICDE), Hannover, 11-16 April 2011, 541-552. https://doi.org/10.1109/ICDE.2011.5767861
[3]
Huang, W., Li, G., Tan, K.-L. and Feng, J.H. (2012) Efficient Safe-Region Construction for Moving Top-K Spatial Keyword Queries. Proceedings of the 21st ACM International Conference on Information and Knowledge Management, Maui, Hawaii, 29 October-November 2 2012, 932-941.
https://doi.org/10.1145/2396761.2396879
[4]
Li, C.W., Gu, Y., Qi, J.Z., Yu, G., Zhang, R. and Wang, Y. (2014) Processing Moving kNN Queries Using Influential Neighbor Sets. Proceedings of the VLDB Endowment, 8, 113-124.
[5]
Li, C.W., Yu, G., Qi, J.Z., He, J.Y., Deng, Q.X. and Yu, G. (2018) A GPU Accelerated Update Efficient Index for kNN Queries in Road Networks. 2018 IEEE 34th International Conference on Data Engineering (ICDE), Paris, 16-19 April 2018, 881-892.
https://doi.org/10.1109/ICDE.2018.00084
[6]
Li, C.W., Yu, G., Qi, J.Z., Yu, G., Zhang, R. and Deng, Q.X. (2016) INSQ: An Influential Neighbor Set Based Moving Knn Query Processing System. 2016 IEEE 32nd International Conference on Data Engineering (ICDE), Helsinki, 16-20 May 2016, 1338-1341. https://doi.org/10.1109/ICDE.2016.7498339
[7]
Salton, G. and McGill, M.J. (1983) Introduction to Modern Information Retrieval.
[8]
Beckmann, N., Kriegel, H., Schneider, R. and Seeger, B. (1990) The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. ACM SIGMOD Record, 19, 322-331. https://doi.org/10.1145/93605.98741
[9]
Hjaltason, G. and Samet, H. (1995) Ranking in Spatial Databases. Springer, Berlin.
https://doi.org/10.1007/3-540-60159-7_6
[10]
Okabe, A., Boots, B., Sugihara, K., et al. (2000) Spatial Tessellations. John Wiley & Sons, Inc., Hoboken. https://doi.org/10.1002/9780470317013
[11]
Cong, G., Jensen, C.S. and Wu, D. (2009) Efficient Retrieval of the Top-K Most Relevant Spatial Web Objects. Proceedings of the VLDB Endowment, 2, 337-348.
https://doi.org/10.14778/1687627.1687666
[12]
Preparata, F. and Shamos, M. (1985) Computational Geometry: An Introduction. Springer, Berlin. https://doi.org/10.1007/978-1-4612-1098-6
[13]
Chen, G.L. (1994) Design and Analysis of Parallel Algorithm. Higher Education Press, Beijing.
[14]
Brinkhoff, T. (2002) A Framework for Generating Network-Based Moving Objects. GeoInformatica, 6, 153-180. https://doi.org/10.1023/A:1015231126594
