Username   Password       Forgot your password?  Forgot your username? 

 

Spatio-Textual Query: Review and Opportunities

Volume 14, Number 11, November 2018, pp. 2842-2851
DOI: 10.23940/ijpe.18.11.p30.28422851

Lianyin Jiaa, Binglin Shena, Mengjuan Lib, Jing Zhanga, and Jiaman Dinga

aFaculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming, 650500, China
bLibrary, Yunnan Normal University, Kunming, 650500, China

(Submitted on August 20, 2018; Revised on September 2, 2018; Accepted on October 18, 2018)

Abstract:

Recent years have seen a rapid development of location-based services. As a consequence, spatio-textual query is becoming ubiquitous in real life. A great number of works have been conducted in this area over the last decade to efficiently support a variety of different queries. Unfortunately, scarce literatures have been witnessed to systematically categorize these works and to comprehensively compare them. To tackle this issue, in this paper, we provide a detailed survey in this field. Firstly, to capture the main differences among different algorithms, we divide spatio-textual queries into two categories from the textual perspective: spatio-textual containment query and spatio-textual similarity query. Secondly, the existing indexes in each category are compared and analyzed in detail. Finally, the paper points out the challenges and opportunities in this area.

 

References: 66

                  1.     L. Chen, G. Cong, C. S. Jensen, and D. Wu, “Spatial Keyword Query Processing: An Experimental Evaluation,” Proceedings of the VLDB Endowment, Vol. 6, No. 3, pp. 217-228, 2013

                  2.     C. Gao and C. S. Jensen, “Querying Geo-Textual Data: Spatial Keyword Queries and Beyond,” in Proceedings of International Conference on Management of Data, pp. 2207-2212, 2016

                  3.     X. P. Liu, C. X. Wan, D. X. Liu, and G. Q. Liao, “Survey on Spatial Keyword Search,” Journal of Software, Vol. 27, No. 2, pp. 329-347, 2016

                  4.     J. Nievergelt, H. Hinterberger, and K. C. Sevcik, “The Grid File: An Adaptable, Symmetric Multi-Key File Structure,” ACM Tods, Vol. 9, No. 1, pp. 38-71, 1984

                  5.     R. A. Finkel and J. L. Bentley, “Quad Trees a Data Structure for Retrieval on Composite Keys,” Acta Informatica, Vol. 4, No. 1, pp. 1-9, 1974

                  6.     J. L. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Communications of the ACM, Vol. 18, No. 9, pp. 509-517, 1975

                  7.     N. Beckmann, H. P. Kriegel, R. Schneider, and B. Seeger, “The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles,” in Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 322-331, 1990

                  8.     A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” in Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 47-57, 1984

                  9.     T. K. Sellis, N. Roussopoulos, and C. Faloutsos, “The R+-Tree: A Dynamic Index for Multi-Dimensional Objects,” in Proceedings of International Conference on Very Large Data Bases, pp. 507-518, 1987

                  10.   R. Bayer, “The Universal B-Tree for Multidimensional Indexing: General Concepts,” in Proceedings of International Conference on Worldwide Computing and ITS Applications, pp. 198-209, 1997

                  11.   P. Nagarkar, K. S. Candan, and A. Bhat, “Compressed Spatial Hierarchical Bitmap (Cshb) Indexes for Efficiently Processing Spatial Range Query Workloads,” Proceedings of the VLDB Endowment, Vol. 8, No. 12, pp. 1382-1393, 2015

                  12.   P. Bozanis and P. Foteinos, “Wer-Trees,” Data & Knowledge Engineering, Vol. 63, No. 2, pp. 397-413, 2007

                  13.   S. Brakatsoulas, D. Pfoser, and Y. Theodoridis, “Revisiting R-Tree Construction Principles,” Revision, Vol. 2435, pp. 17-24, 2002

                  14.   I. Kamel and C. Faloutsos, “Hilbert R-Tree: An Improved R-Tree Using Fractals,” in Proceedings of International Conference on Very Large Data Bases, pp. 500-509, 1994

                  15.   S. T. Leutenegger, J. M. Edgington, and M. A. Lopez, “Str: A Simple and Efficient Algorithm for R-Tree Packing,” in Proceedings of International Conference on Data Engineering, pp. 497-506, 1997

                  16.   T. Skopal, M. Krátký, J. Pokorný, and V. Snášel, “A New Range Query Algorithm for Universal B-Trees ☆,” Information Systems, Vol. 31, No. 6, pp. 489-511, 2006

                  17.   R. Ganti, M. Srivatsa, D. Agrawal, P. Zerfos, and J. Ortiz, “Mp-Trie: Fast Spatial Queries on Moving Objects,” in Proceedings of Industrial Track of the International MIDDLEWARE Conference, pp. 1, 2016

                  18.   Y. Ishikawa, H. Kitagawa, and N. Ohbo, “Evaluation of Signature Files as Set Access Facilities in Oodbs,” in Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., USA, 1993

                  19.   H. Kitagawa and K. Fukushima, “Composite Bit-Sliced Signature File: An Efficient Access Method for Set-Valued Object Retrieval,” CODAS, 1996

                  20.   J. M. Hellerstein and A. Pfeffer, “The Rd-Tree: An Index Structure for Sets,” University of Wisconsin, Madison, 1994

                  21.   B. Ding, “Fast Set Intersection in Memory,” Proceedings of the VLDB Endowment, Vol. 4, No. 4, pp. 255-266, 2011

                  22.   O. Kaser and D. Lemire, “Compressed Bitmap Indexes: Beyond Unions and Intersections,” Software Practice Experience, Vol. 46, No. 2, pp. 167-198, 2016

                  23.   S. Helmer and G. Moerkotte, “A Performance Study of Four Index Structures for Set-Valued Attributes of Low Cardinality,” The VLDB Journal, Vol. 12, No. 3, pp. 244-261, 2003

                  24.   E. D. Demaine and J. I. Munro, “Experiments on Adaptive Set Intersections for Text Retrieval Systems,” in Proceedings of Revised Papers from the Third International Workshop on Algorithm Engineering and Experimentation, pp. 91-104, 2001

                  25.   C. D. Manning and P. Raghavan, “Introduction to Information Retrieval,” Cambridge University Press, 2010

                  26.   J. Wang, C. Lin, R. He, M. Chae, Y. Papakonstantinou, and S. Swanson, “Milc: Inverted List Compression in Memory,” Proceedings of the VLDB Endowment, Vol. 10, No. 8, pp. 853-864, 2017

                  27.   M. Yu, G. Li, D. Deng, and J. Feng, “String Similarity Search and Join: A Survey,” Frontiers Computer Science, Vol. 10, No. 3, pp. 399-417, 2016

                  28.   Y. Kim and K. Shim, “Efficient Top-K Algorithms for Approximate Substring Matching,” in Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 385-396, 2013

                  29.   M. Hadjieleftheriou and D. Srivastava, “Weighted Set-based String Similarity,” Bulletin of the Technical Committee on Data Engineering, Vol. 33, No. 1, pp. 25-36, 2010

                  30.   A. Arasu, V. Ganti, and R. Kaushik, “Efficient Exact Set-Similarity Joins,” in Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, 2006

                  31.   S. Chaudhuri, V. Ganti, and R. Kaushik, “A Primitive Operator for Similarity Joins in Data Cleaning,” in Proceedings of the 22nd International Conference on Data Engineering, 2006

                  32.   S. Sarawagi and A. Kirpal, “Efficient Set Joins on Similarity Predicates,” in Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, 2004

                  33.   C. Xiao, W. Wang, X. Lin, J. X. Yu, and G. Wang, “Efficient Similarity Joins for near-Duplicate Detection,” ACM Transactions on Database Systems, Vol. 36, No. 3, pp. 1-41, 2011

                  34.   J. Wang, G. Li, and J. Feng, “Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search,” in Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, Scottsdale, Arizona, USA, 2012

                  35.   C. Li, J. Lu, and Y. Lu, “Efficient Merging and Filtering Algorithms for Approximate String Searches,” in Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, 2008

                  36.   D. Fenz, D. Lange, F. Naumann, and U. Leser, “Efficient Similarity Search in Very Large String Sets,” in Proceedings of International Conference on Scientific and Statistical Database Management, pp. 262-279, 2012

                  37.   J. Feng, J. Wang, and G. Li, “Trie-Join: A Trie-based Method for Efficient String Similarity Joins,” The VLDB Journal, Vol. 21, No. 4, pp. 437-461, 2012

                  38.   Z. Zhang, M. Hadjieleftheriou, B. C. Ooi, and D. Srivastava, “Bed-Tree: An All-Purpose Index Structure for String Similarity Search based on Edit Distance,” in Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 915-926, SIGMOD 2010, Indianapolis, Indiana, USA, June 2010

                  39.   L. Jia, L. Zhang, G. Yu, J. You, J. Ding, and M. Li, “A Survey on Set Similarity Search and Join,” International Journal of Performability Engineering, Vol. 14, No. 2, pp. 245-258, 2018

                  40.   I. D. Felipe, V. Hristidis, and N. Rishe, “Keyword Search on Spatial Databases,” in Proceedings of IEEE International Conference on Data Engineering, pp. 656-665, 2008

                  41.   R. Hariharan, B. Hore, C. Li, and S. Mehrotra, “Processing Spatial-Keyword (Sk) Queries in Geographic Information Retrieval (Gir) Systems,” in Proceedings of International Conference on Scientific and Statistical Database Management, pp. 16, 2007

                  42.   D. Zhang, Y. M. Chee, A. Mondal, A. K. H. Tung, and M. Kitsuregawa, “Keyword Search in Spatial Databases: Towards Searching by Document,” in Proceedings of IEEE International Conference on Data Engineering, pp. 688-699, 2009

                  43.   Z. Li, K. C. K. Lee, B. Zheng, W. C. Lee, D. Lee, and X. Wang, “Ir-Tree: An Efficient Index for Geographic Document Search,” IEEE Transactions on Knowledge & Data Engineering, Vol. 23, No. 4, pp. 585-599, 2011

                  44.   S. Vaid, C. B. Jones, H. Joho, and M. Sanderson, “Spatio-Textual Indexing for Geographical Search on the Web,” Springer Berlin Heidelberg, 2005

                  45.   A. Skovsgaard and C. S. Jensen, “Top-K Point of Interest Retrieval Using Standard Indexes,” ACM Sigspatial, Vol. 35, No. 1, pp. 173-182, 2014

                  46.   M. Christoforaki, J. He, C. Dimopoulos, A. Markowetz, and T. Suel, “Text Vs. Space:Efficient Geo-Search Query Processing,” in Proceedings of ACM International Conference on Information & Knowledge Management, pp. 423-432, 2011

                  47.   A. Khodaei, C. Shahabi, and C. Li, “Hybrid Indexing and Seamless Ranking of Spatial and Textual Features of Web Documents,” in Proceedings of International Conference on Database and Expert Systems Applications, pp. 450-466, 2010

                  48.   A. Cary, O. Wolfson, and N. Rishe, “Efficient and Scalable Method for Processing Top-K Spatial Boolean Queries,” in Proceedings of International Conference on Scientific and Statistical Database Management, pp. 87-95, 2010

                  49.   Y. Zhou, X. Xie, C. Wang, Y. Gong, and W. Y. Ma, “Hybrid Index Structures for Location-based Web Search,” in Proceedings of ACM International Conference on Information and Knowledge Management, pp. 155-162, 2005

                  50.   D. Wu, L. Y. Man, G. Cong, and C. S. Jensen, “Joint Top-K Spatial Keyword Query Processing,” IEEE Transactions on Knowledge & Data Engineering, Vol. 24, No. 10, pp. 1889-1903, 2012

                  51.   L. Chen, G. Cong, and X. Cao, “An Efficient Query Indexing Mechanism for Filtering Geo-Textual Data,” in Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 749-760, 2013

                  52.   G. Li, Y. Wang, T. Wang, and J. Feng, “Location-Aware Publish/Subscribe,” in Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 802-810, 2013

                  53.   M. Yu, G. Li, and J. Feng, “A Cost-based Method for Location-Aware Publish/Subscribe Services,” in Proceedings of ACM International on Conference on Information and Knowledge Management, pp. 693-702, 2015

                  54.   X. Wang, Y. Zhang, W. Zhang, X. Lin, and W. Wang, “Ap-Tree: Efficiently Support Continuous Spatial-Keyword Queries over Stream,” in Proceedings of IEEE International Conference on Data Engineering, pp. 1107-1118, 2015

                  55.   Z. Chen, G. Cong, Z. Zhang, T. Z. J. Fuz, and L. Chen, “Distributed Publish/Subscribe Query Processing on the Spatio-Textual Data Stream,” in Proceedings of IEEE International Conference on Data Engineering, 2017

                  56.   G. Cong, C. S. Jensen, and D. Wu, “Efficient Retrieval of the Top-K Most Relevant Spatial Web Objects,” Proceedings of the VLDB Endowment, Vol. 2, No. 1, pp. 337-348, 2009

                  57.   J. Fan, G. Li, L. Zhou, S. Chen, and J. Hu, “Seal: Spatio-Textual Similarity Search,” in Proceedings of the Vldb Endowment, Vol. 5, No. 9, pp. 824-835, 2012

                  58.   J. B. Rocha-Junior, O. Gkorgkas, S. Jonassen, and K. Nørvåg, “Efficient Processing of Top-K Spatial Keyword Queries,” in Proceedings of International Symposium on Spatial and Temporal Databases, pp. 205-222, 2011

                  59.   L. Chen, G. Cong, X. Cao, and K. L. Tan, “Temporal Spatial-Keyword Top-K Publish/Subscribe,” in Proceedings of IEEE International Conference on Data Engineering, pp. 255-266, 2015

                  60.   H. Hu, Y. Liu, G. Li, and J. Feng, “A Location-Aware Publish/Subscribe Framework for Parameterized Spatio-Textual Subscriptions,” in Proceedings of IEEE International Conference on Data Engineering, pp. 711-722, 2015

                  61.   M. Zhu, D. Shen, L. Liu, and G. Yu, “Hybrid-Lsh for Spatio-Textual Similarity Queries,” in Proceedings of the APWeb, pp. 166-177, Guangzhou, China, 2015

                  62.   J. Liu, K. Deng, H. Sun, Y. Ge, X. Zhou, and C. S. Jensen, “Clue-based Spatio-Textual Query,” Proceedings of the VLDB Endowment, Vol. 10, No. 5, pp. 529-540, 2017

                  63.   S. Liu, G. Li, and J. Feng, “Star-Join: Spatio-Textual Similarity Join,” pp. 2194-2198, 2012

                  64.   S. Liu, G. Li, and J. Feng, “A Prefix-Filter based Method for Spatio-Textual Similarity Join,” IEEE Transactions on Knowledge & Data Engineering, Vol. 26, No. 10, pp. 2354-2367, 2014

                  65.   P. Bouros, G. Shen, and N. Mamoulis, “Spatio-Textual Similarity Joins,” Proceedings of the VLDB Endowment, Vol. 6, No. 1, pp. 1-12, 2013

                  66.   J. Rao, J. Lin, and H. Samet, “Partitioning Strategies for Spatio-Textual Similarity Join,” in Proceedings of ACM Sigspatial International Workshop on Analytics for Big Geospatial Data, pp. 40-49, 2014

                                   

                                  Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

                                   
                                  This site uses encryption for transmitting your passwords. ratmilwebsolutions.com