research-article

Efficient Reverse Top-<italic>k</italic> Boolean Spatial Keyword Queries on Road Networks

Authors:

Gang ChenAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 27, Issue 5

Pages 1205 - 1218

https://doi.org/10.1109/TKDE.2014.2365820

Published: 01 May 2015 Publication History

Abstract

Reverse k nearest neighbor (RkNN) queries have a broad application base such as decision support, profile-based marketing, and resource allocation. Previous work on RkNN search does not take textual information into consideration or limits to the Euclidean space. In the real world, however, most spatial objects are associated with textual information and lie on road networks. In this paper, we introduce a new type of queries, namely, reverse top-k Boolean spatial keyword (RkBSK) retrieval, which assumes objects are on the road network and considers both spatial and textual information. Given a data set P on a road network and a query point q with a set of keywords, an RkBSK query retrieves the points in P that have q as one of answer points for their top-k Boolean spatial keyword queries. We formalize the RkBSK query and then propose filter-and-refinement framework based algorithms for answering RkBSK search with arbitrary k and no any pre-computation. To accelerate the query process, several novel pruning heuristics that utilize both spatial and textual information are employed to shrink the search space efficiently. In addition, a new data structure called count tree has been developed to further improve query performance. A comprehensive experimental evaluation using both real and synthetic data sets demonstrates the effectiveness of our presented pruning heuristics and the performance of our proposed algorithms.

References

[1]

X. Cao, L. Chen, G. Cong, C. S. Jensen, Q. Qu, A. Skovsgaard, D. Wu, and M. L. Yiu, “Spatial keyword querying,” in Proc. Int. Conf. Conceptual Model., 2012, pp. 16–29.

[2]

X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi, “Collective spatial keyword querying,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2011, pp. 373– 384.

[3]

A. Cary, O. Wolfson, and N. Rishe, “Efficient and scalable method for processing top-k spatial Boolean queries,” in Proc. Int. Conf. Sci. Statistical Database Manage., 2010, pp. 87–95.

[4]

M. A. Cheema, W. Zhang, X. Lin, Y. Zhang, and X. Li, “Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks,” VLDB J., vol. 21, no. 1, pp. 69–95, Feb. 2012.

Digital Library

[5]

L. Chen, G. Cong, C. S. Jensen, and D. Wu, “Spatial keyword query processing: An experimental evaluation,” Proc. VLDB Endowment, vol. 6, no. 3, pp. 217–228, Jan. 2013.

Digital Library

[6]

G. Cong, C. S. Jensen, and D. Wu, “Efficient retrieval of the top-k most relevant spatial web objects,” Proc. VLDB Endowment, vol. 2, no. 1, pp. 337–348, Aug. 2009.

Digital Library

[7]

I. D. Felipe, V. Hristidis, and N. Rishe, “Keyword search on spatial databases,” in Proc. Int. Conf. Data Eng., 2008, pp. 656–665.

[8]

Y. Gao, B. Zheng, G. Chen, W.-C. Lee, K. C. Lee, and Q. Li, “ Visible reverse k-nearest neighbor query processing in spatial databases,” IEEE Trans. Knowl. Data Eng., vol. 21, no. 9, pp. 1314 –1327, Sep. 2009.

Digital Library

[9]

F. Korn and S. Muthukrishnan, “Influence sets based on reverse nearest neighbor queries,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2000, pp. 201– 212.

[10]

K. C. Lee, B. Zheng, and W.-C. Lee, “Ranked reverse nearest neighbor search,” IEEE Trans. Knowl. Data Eng., vol. 20, no. 7, pp. 894–910, Jul. 2008 .

Digital Library

[11]

G. Li, J. Feng, and J. Xu, “Desks: Direction-aware spatial keyword search,” in Proc. Int. Conf. Data Eng., 2012, pp. 474–485.

[12]

Z. Li, K. C. Lee, B. Zheng, W.-C. Lee, D. Lee, and X. Wang, “ IR-tree: An efficient index for geographic document search,” IEEE Trans. Knowl. Data Eng. , vol. 23, no. 4, pp. 585–599, Apr. 2011.

Digital Library

[13]

G. Li, Y. Li, J. Li, L. Shu, and F. Yang, “Continuous reverse k nearest neighbor monitoring on moving objects in road networks,” Inf. Syst., vol. 35, no. 8, pp. 860–883, Dec. 2010.

[14]

J. Lu, Y. Lu, and G. Cong, “Reverse spatial and textual k nearest neighbor search,” in Proc. ACM SIGMOD Int. Conf. Manage. Data , 2011, pp. 349–360.

[15]

S. Luo, Y. Luo, S. Zhou, G. Cong, and J. Guan, “Distributed spatial keyword querying on road networks,” in Proc. Int. Conf. Extending Database Technol., 2014, pp. 235–246.

[16]

D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao, “Query processing in spatial network databases,” in Proc. Int. Conf. Very Large Data Bases, 2003, pp. 802–813.

[17]

J. B. Rocha-Junior, O. Gkorgkas, S. Jonassen, and K. Norvag, “Efficient processing of top-k spatial keyword queries,” in Proc. Int. Symp. Advances Spatial Temporal Databases, 2011, pp. 205–222.

[18]

J. B. Rocha-Junior and K. Norvag, “Top-k spatial keyword queries on road networks,” in Proc. Int. Conf. Extending Database Technol., 2012, pp. 168– 179.

[19]

M. Safar, D. Ibrahimi, and D. Taniar, “ Voronoi-based reverse nearest neighbor query processing on spatial networks,” Multimedia Syst., vol. 15, no. 5, pp. 295–308, Oct. 2009.

[20]

S. Shekhar and D.-R. Liu, “CCAM: A connectivity-clustered access method for networks and network computations,” IEEE Trans. Knowl. Data Eng., vol. 9, no. 1, pp. 102–119, Jan. 1997.

Digital Library

[21]

I. Stanoi, D. Agrawal, and A. El Abbadi, “Reverse nearest neighbor queries for dynamic databases,” in Proc. ACM SIGMOD Workshop DMKD , 2000, pp. 44–53.

[22]

Y. Tao, D. Papadias, and X. Lian, “Reverse k NN search in arbitrary dimensionality,” in Proc. Int. Conf. Very Large Data Bases, 2004, pp. 744–755.

[23]

Y. Tao and C. Sheng, “ Fast nearest neighbor search with keywords,” IEEE Trans. Knowl. Data Eng. , vol. 26, no. 4, pp. 878–888, Apr. 2014.

Digital Library

[24]

A. Vlachou, C. Doulkeridis, Y. Kotidis, and K. Norvag, “Reverse top-k queries,” in Proc. Int. Conf. Data Eng., 2010, pp. 365 –376.

[25]

A. Vlachou, C. Doulkeridis, K. Norvag, and Y. Kotidis. “Branch-and-bound algorithm for reverse top-k queries,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2013, pp. 481–492.

[26]

L. Wu, X. Xiao, D. Deng, G. Cong, A. D. Zhu, and S. Zhou, “Shortest path and distance queries on road networks: An experimental evaluation,” Proc. VLDB Endowment , vol. 5, no. 5, pp. 406–417, 2012.

Digital Library

[27]

W. Wu, F. Yang, C.-Y. Chan, and K.-L. Tan, “Finch: Evaluating reverse k -nearest-neighbor queries on location data,” Proc. VLDB Endowment, vol. 1, no. 1, pp. 1056–1067, 2008.

Digital Library

[28]

D. Wu, M. L. Yiu, G. Cong, and C. S. Jensen, “Joint top-k spatial keyword query processing,” IEEE Trans. Knowl. Data Eng., vol. 24, no. 10, pp. 1889–1903, Oct. 2012.

Digital Library

[29]

M. L. Yiu, D. Papadias, N. Mamoulis, and Y. Tao, “Reverse nearest neighbors in large graphs,” IEEE Trans. Knowl. Data Eng., vol. 18, no. 4, pp. 540–553, Apr. 2006.

[30]

J. Zhang, W.-S. Ku, X. Jiang, X. Qin, and Y.-L. Hsueh, “Evaluation of spatial keyword queries with partial result support on spatial networks,” in Proc. Int. Conf. Mobile Data Manage., 2013, pp. 279–282.

[31]

D. Zhang, K. L. Tan, and A. K. H. Tung, “ Scalable top-k spatial keyword search,” in Proc. Int. Conf. Extending Database Technol., 2013, pp. 359–370.

[32]

C. Zhang, Y. Zhang, W. Zhang, X. Lin, M. A. Cheema, and X. Wang, “Diversified spatial keyword search on road networks,” in Proc. Int. Conf. Extending Database Technol., 2014, pp. 367–378.

Cited By

Luo CLiu QGao YChen LWei ZGe C(2023)Task: An Efficient Framework for Instant Error-Tolerant Spatial Keyword Queries on Road NetworksProceedings of the VLDB Endowment10.14778/3603581.360358416:10(2418-2430)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.14778/3603581.3603584
Long WLi XWang LZhang FLin ZLin X(2023)Efficient m-closest entity matching over heterogeneous information networksKnowledge-Based Systems10.1016/j.knosys.2023.110299263:COnline publication date: 5-Mar-2023
https://dl.acm.org/doi/10.1016/j.knosys.2023.110299
Tang JLu XXiang YShi CGu J(2023)Blockchain search engineFuture Generation Computer Systems10.1016/j.future.2022.08.008138:C(120-141)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.future.2022.08.008
Show More Cited By

Index Terms

Efficient Reverse Top-k Boolean Spatial Keyword Queries on Road Networks

Index terms have been assigned to the content through auto-classification.

Recommendations

Top-k spatial keyword queries on road networks
EDBT '12: Proceedings of the 15th International Conference on Extending Database Technology

With the popularization of GPS-enabled devices there is an increasing interest for location-based queries. In this context, one interesting problem is processing top-k spatial keyword queries. Given a set of objects with a textual description (e.g., ...
Efficient algorithms for answering reverse spatial-keyword nearest neighbor queries
SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

With the proliferation of local services and GPS-enabled mobile phones, reverse spatial-keyword Nearest Neighbor queries are becoming an important type of query. Given a service object (e.g., shop) q as the query, which has a location and a text ...
Towards Efficient Framework for Time-Aware Spatial Keyword Queries on Road Networks

The spatial keyword query takes as inputs a query location and a set of query keywords and returns the answer objects by considering both their spatial distances to the query location and textual similarity with the query keywords. However, temporal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 27, Issue 5

May 2015

315 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © 2014.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 May 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Luo CLiu QGao YChen LWei ZGe C(2023)Task: An Efficient Framework for Instant Error-Tolerant Spatial Keyword Queries on Road NetworksProceedings of the VLDB Endowment10.14778/3603581.360358416:10(2418-2430)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.14778/3603581.3603584
Long WLi XWang LZhang FLin ZLin X(2023)Efficient m-closest entity matching over heterogeneous information networksKnowledge-Based Systems10.1016/j.knosys.2023.110299263:COnline publication date: 5-Mar-2023
https://dl.acm.org/doi/10.1016/j.knosys.2023.110299
Tang JLu XXiang YShi CGu J(2023)Blockchain search engineFuture Generation Computer Systems10.1016/j.future.2022.08.008138:C(120-141)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.future.2022.08.008
Chen FZhang PYu CLin HTang SHu X(2022)Path–Based Continuous Spatial Keyword QueriesComplexity10.1155/2022/40912452022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/4091245
Allheeib NAdhinugraha KTaniar DIslam M(2022)Computing reverse nearest neighbourhood on road mapsWorld Wide Web10.1007/s11280-021-00969-125:1(99-130)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s11280-021-00969-1
Park SPark S(2022)Nearly most influential location selection with differentially private user locations in a road networkThe Journal of Supercomputing10.1007/s11227-022-04601-578:16(18336-18360)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s11227-022-04601-5
Chung MHyun SLoh W(2022)Efficient exact k-flexible aggregate nearest neighbor search in road networks using the M-treeThe Journal of Supercomputing10.1007/s11227-022-04496-278:14(16286-16302)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11227-022-04496-2
Ding XZheng YWang ZChoo KJin H(2022)A learned spatial textual index for efficient keyword queriesJournal of Intelligent Information Systems10.1007/s10844-022-00752-260:3(803-827)Online publication date: 13-Oct-2022
https://dl.acm.org/doi/10.1007/s10844-022-00752-2
Chen ZWang XLiu W(2022)Reverse keyword-based location search on road networksGeoinformatica10.1007/s10707-021-00440-326:1(201-231)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10707-021-00440-3
Ahmed PEldawy AHristidis VTsotras V(2022)Reverse spatial top-k keyword queriesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-022-00759-932:3(501-524)Online publication date: 25-Jul-2022
https://dl.acm.org/doi/10.1007/s00778-022-00759-9
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents