TY - GEN
T1 - Indoor top-k keyword-aware routing query
AU - Feng, Zijin
AU - Liu, Tiantian
AU - Li, Huan
AU - Lu, Hua
AU - Shou, Lidan
AU - Xu, Jianliang
N1 - Funding Information:
Acknowledgement. This work was supported by HK-RGC (Nos. 12200817 and 12201018), Independent Research Fund Denmark (No. 8022-00366B), and National Science Foundation of China (No. 61672455). The authors would like to thank Ronghao Ni and Yijie Xie for preprocessing the real dataset.
PY - 2020/4
Y1 - 2020/4
N2 - People have many activities indoors and there is an increasing demand of keyword-aware route planning for indoor venues. In this paper, we study the indoor top-k keyword-aware routing query (IKRQ). Given two indoor points s and t, an IKRQ returns k s-to-t routes that do not exceed a given distance constraint but have optimal ranking scores integrating keyword relevance and spatial distance. It is challenging to efficiently compute the ranking scores and find the best yet diverse routes in a large indoor space with complex topology. We propose prime routes to diversify top-k routes, devise mapping structures to organize indoor keywords and compute route keyword relevances, and derive pruning rules to reduce search space in routing. With these techniques, we design two search algorithms with different routing expansions. Experiments on synthetic and real data demonstrate the efficiency of our proposals.
AB - People have many activities indoors and there is an increasing demand of keyword-aware route planning for indoor venues. In this paper, we study the indoor top-k keyword-aware routing query (IKRQ). Given two indoor points s and t, an IKRQ returns k s-to-t routes that do not exceed a given distance constraint but have optimal ranking scores integrating keyword relevance and spatial distance. It is challenging to efficiently compute the ranking scores and find the best yet diverse routes in a large indoor space with complex topology. We propose prime routes to diversify top-k routes, devise mapping structures to organize indoor keywords and compute route keyword relevances, and derive pruning rules to reduce search space in routing. With these techniques, we design two search algorithms with different routing expansions. Experiments on synthetic and real data demonstrate the efficiency of our proposals.
UR - http://www.scopus.com/inward/record.url?scp=85085866168&partnerID=8YFLogxK
U2 - 10.1109/ICDE48307.2020.00109
DO - 10.1109/ICDE48307.2020.00109
M3 - Conference proceeding
AN - SCOPUS:85085866168
T3 - Proceedings - International Conference on Data Engineering
SP - 1213
EP - 1224
BT - Proceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020
PB - IEEE Computer Society
T2 - 36th IEEE International Conference on Data Engineering, ICDE 2020
Y2 - 20 April 2020 through 24 April 2020
ER -