微信服务号

微信订阅号

2025-4-6- 5
Home > Archive>Volume 31, Issue 10, 2020 >3197-3215. DOI:10.13328/j.cnki.jos.005810
PDF HTML XML Export Cite reminder
Efficient Algorithm of Top-k Spatial Keyword Search with OR Semantics
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61472340, 61303017); Natural Science Foundation of Hebei Province of China (F2018210109); Department of Education Key Project of Hebei Province (ZD2018040); Foundation of Introducing Overseas Student (C201822); Basic Research Team Project of Hebei Province (2019JT70803); The 4th Outstanding Youth Foundation of Shijiazhuang Tiedao University (Z661250444); College Innovative Training Program Foundation of China (201710107006, 201710107007)

  • Article
    • | |
  • Metrics
    • |
  • Reference [46]
    • |
  • Related [20]
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    In recent years, with the popularization of positioning system and mobile devices, the numbers of spatial-textual objects increase extraordinarily. Location-based services using geographical information play a critical role in daily lives. Spatial keyword search has attracted more attention from academia and industry. However, many of the existing techniques can only be appliable on AND semantics. There is relatively less research supporting OR semantics. When the users do not require the exact keyword matching, the search technology that supports OR semantic is particularly important. To solve this problem, this study proposes a virtual grid-based query algorithm VGrid. VGrid is an aggregate linear quadtree (AIL) based algorithm, utilizing the easy transformation between the Morton codes and the spatial locations in the space. The algorithm can support both OR and AND semantics. Finally, a series of experiments is conducted on a real dataset, and the effectiveness and efficiency of the proposed algorithm are verified.

    Reference
    [1] Zhu H, Yang X, Wang B, Lee WC. Range-based obstructed nearest neighbor queries. In:Proc. of the ACM SIGMOD. 2016. 2053-2068.
    [2] Li Y, Huang Z, Zhu R, Li G, Shu L, Tian S, Ma M. Parameterized spatio-textual publish/subscribe in rode sensor networks. IEEE Access, 2017,5(99):22940-22952.
    [3] Sanderson M, Kohler J. Analyzing geographic queries. In:Proc. of the Int'l ACM SIGIR Conf. 2004.
    [4] Chan KH, Long C, Wong CW. On generalizing collective spatial keyword queries. IEEE Trans. on Knowledge and Data Engineering, 2018,30(9):1712-1726.
    [5] Han XX, Yang DH, Li JZ. TKEP:An efficient top-K query processing algorithm on massive data. Chinese Journal of Computers, 2010,33(8):1405-1417(in Chinese with English abstract).
    [6] Zhu R, Wang B, Yang X, Zheng B, Wang G. SAP:Improving continuous top-k queries over streaming data. IEEE Trans. on Knowledge and Data Engineering, 2017,29(6):1310-1328.
    [7] Hu HQ, Li GL, Bao ZF, Feng JH, Wu YW, Gong ZG, Xu YQ. Top-k spatio-textual similarity join. IEEE Trans. on Knowledge and Data Engineering, 2016,28(2):551-565.
    [8] Wang Y, Jian X, Yang ZH, Li J. Query optimal k-plex based community in graphs. Data Science and Engineering, 2017,2(4):274-274.
    [9] Yang J, Zhang Y, et al. Categorical top-k spatial influence query. World Wide Web, 2017,20:175-203.
    [10] Cong G, Jensen CS, Wu D. Efficient retrieval of the top-k most relevant spatial Web objects. Proc. of the VLDB Endowment, 2009, 2(1):337-348.
    [11] Chan KH, Li C. Hybrid indexing and seamless ranking of spatial and textual features of Web documents. In:Proc. of the SSTD. 2017. 357-375.
    [12] Li ZS, Lee KC, Zheng BH, Lee WC, Lee D, Wang XF. IR-tree:An efficient index for geographic document search. IEEE Trans. on Knowledge and Data Engineering, 2011,23(4):585-599.
    [13] Rochajunior JB, Gkorgkas O, Jonassen S, Nørvåg K. Efficient processing of top-k spatial keyword queries. In:Proc. of the SSTD. 2011. 205-222.
    [14] Liu XP, Wan CX, Liu DX, Liao GQ. Survey on spatial keyword search. Ruan Jian Xue Bao/Journal of Software, 2016,27(2):329-347(in Chinese with English abstract). http://www.org.jos.cn/1000-9825/4934.htm[doi:10.13328/j.cnki.jos.004934]
    [15] Zhang D, Tan KL, Tung AKH. Scalable top-k spatial keyword search. In:Proc. of the EDBT. 2013. 359-370.
    [16] Zhang CY, Zhang Y, Zhang WJ, Lin XM. Inverted linear quadtree:Efficient top k spatial keyword search. In Proc. of the ICDE. 2013. 901-912.
    [17] Wu DM, Yiu ML, Cong G, Jensen CS. Joint top-k spatial keyword query processing. IEEE Trans. on Knowledge and Data Engineering, 2012,24(10):1889-1903.
    [18] Felipe ID, Hristidis V, Rishe N. Keyword search on spatial databases. In:Proc. of the ICDE. 2008. 656-665.
    [19] Chen L, Xu JL, Lin X, Jensen CS, Hu HB. Answering why-not spatial keyword top-k queries via keyword adaption. In:Proc. of the ICDE. 2016. 697-708.
    [20] Chan KH, Long C, Wong CW. Inherent-cost aware collective spatial keyword queries. In:Proc. of the SSTD. 2017. 357-375.
    [21] Zhang DX, Chan CY, Tan KL. Processing spatial keyword query as a top-k aggregation query. In:Proc. of the SIGIR. 2014. 355-364.
    [22] Wu DM, Cong G, Jensen CS. A framework for efficient spatial Web object retrieval. VLDB Journal, 2012,21(6):797-822.
    [23] Chen LS, Cong G, Cao X, Tan KL. Temporal spatial-keyword top-k publish/subscribe. In:Proc. of the ICDE. 2015. 255-266.
    [24] Liu J, Ke D, Sun H, Ge Y, Zhou X. Clue-based spatio-textual query. Proc. of the VLDB Endowment, 2017,10(5):529-540.
    [25] Wang J, Gao H, Li J, Yang D. An index supporting spatial approximate keyword search on disks. Journal of Computer Research and Development, 2012,49(10):2142-2152(in Chinese with English abstract).
    [26] Hu J, Fan J, Li GL, Chen SS. Top-k fuzzy spatial keyword search. Chinese Journal of Computers, 2012,35(11):2237-2246(in Chinese with English abstract).
    [27] Yao B, Li FF, Hadjieleftheriou M, Hou K. Approximate string search in spatial databases. In:Proc. of the ICDE. 2010. 545-556.
    [28] Lin X, Xu JL, Hu HB. Reverse keyword search for spatio-textual top-k queries in location-based services. In:Proc. of the ICDE. 2017. 375-386.
    [29] Zheng K, Zhou XF, Fung PC, Xie KX. Spatial query processing for fuzzy objects. VLDB Journal, 2012,21(5):729-751.
    [30] Cary A, Wolfson O, Rishe N. Efficient and scalable method for processing top-k spatial Boolean queries. In:Proc. of the SSDBM. 2010. 87-95.
    [31] Gao YJ, Qin X, Zheng BH, Chen G. Efficient reverse top-k Boolean spatial keyword queries on road networks. IEEE Trans. on Knowledge and Data Engineering, 2015,27(5):1205-1218.
    [32] Chen G, Zhao JW, Gao YJ, Chen L, Chen R. Time-aware Boolean spatial keyword queries. IEEE Trans. on Knowledge and Data Engineering, 2017,29(11):2601-2614.
    [33] Zhao PP, Fang HL, Sheng VS, Li ZX, Xu JJ, Wu J, Cui ZM. Monochromatic and bichromatic ranked reverse Boolean spatial keyword nearest neighbors search. World Wide Web, 2017,20(1):39-59.
    [34] Li GL, Feng JH, Xu J. DESKS:Direction-aware spatial keyword search. In:Proc. of the ICDE. 2012. 474-485.
    [35] Wu DM, Yiu ML, Jensen CS, Cong G. Efficient continuously moving top-k spatial keyword query processing. In:Proc. of the ICDE. 2011. 541-552.
    [36] Huang WH, Li GL, Tan KL, Feng JH. Efficient safe-region construction for moving top-k spatial keyword queries. In:Proc. of the CIKM. 2012. 932-941.
    [37] Shi JM, Wu DM, Mamoulis N. Textually relevant spatial skylines. IEEE Trans. on Knowledge and Data Engineering, 2016,28(1):224-237.
    [38] Choudhury FM, Culpepper JS, Sellis T, Cao X. Maximizing bichromatic reverse spatial and textual k nearest neighbor queries. Proc. of the VLDB Endowment, 2016,9(6):456-467.
    [39] Xie X, Lin X, Xu J, Jensen CS. Reverse keyword-based location search. In:Proc. of the ICDE. 2017. 375-386.
    [40] Aizawa K, Motomura K, Kimura S, Kadowaki R, Jia F. Constant time neighbor finding in quadtrees:An experimental result. In:Proc. of the Int'l Symp. on Communications, Control and Signal Processing. 2008. 505-510.
    [41] Bao J, Zheng Y, Mokbel MF. Location-based and preference-aware recommendation using sparse geo-social networking data. In:Proc. of the SIGSPATIAL. 2012. 199-208.
    [42] Wei LY, Zheng Y, Peng WC. Constructing popular routes from uncertain trajectories. In:Proc. of the KDD. 2012. 195-203.
    附中文参考文献:
    [5] 韩希先,杨东华,李建中.TKEP:海量数据上一种有效的Top-K查询处理算法.计算机学报,2010,33(8):1405-1417.
    [14] 刘喜平,万常选,刘德喜,廖国琼.空间关键字搜索研究综述.软件学报,2016,27(2):329-347. http://www.org.jos.cn/1000-9825/4934.htm[doi:10.13328/j.cnki.jos.004934]
    [26] 胡骏,范举,李国良.空间数据上Top-k关键词模糊查询算法.计算机学报,2012,35(11):2237-2246.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

潘晓,于启迪,马昂,孙亚欣,吴雷,郭景峰.支持OR语义的高效受限Top-k空间关键字查询技术.软件学报,2020,31(10):3197-3215

Copy
Share
Article Metrics
  • Abstract:1258
  • PDF: 3314
  • HTML: 1784
  • Cited by: 0
History
  • Received:March 21,2018
  • Revised:September 27,2018
  • Online: October 12,2020
  • Published: October 06,2020
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033295Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063