{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,18]],"date-time":"2026-11-18T03:13:07Z","timestamp":1794971587047,"version":"4.9.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,5,1]],"date-time":"2014-05-01T00:00:00Z","timestamp":1398902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004260","name":"Renmin University of China","doi-asserted-by":"publisher","award":["11XNJ003"],"award-info":[{"award-number":["11XNJ003"]}],"id":[{"id":"10.13039\/501100004260","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61170011"],"award-info":[{"award-number":["61170011"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["ARC30\/12"],"award-info":[{"award-number":["ARC30\/12"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["RG66\/12"],"award-info":[{"award-number":["RG66\/12"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2012CB316205"],"award-info":[{"award-number":["2012CB316205"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,5]]},"abstract":"<jats:p>\n            Geographic objects associated with descriptive texts are becoming prevalent, justifying the need for spatial-keyword queries that consider both locations and textual descriptions of the objects. Specifically, the relevance of an object to a query is measured by\n            <jats:italic>spatial-textual similarity<\/jats:italic>\n            that is based on both spatial proximity and textual similarity. In this article, we introduce the Reverse Spatial-Keyword\n            <jats:italic>k<\/jats:italic>\n            -Nearest Neighbor (RSK\n            <jats:italic>k<\/jats:italic>\n            NN) query, which finds those objects that have the query as one of their\n            <jats:italic>k<\/jats:italic>\n            -nearest spatial-textual objects. The RSK\n            <jats:italic>k<\/jats:italic>\n            NN queries have numerous applications in online maps and GIS decision support systems.\n          <\/jats:p>\n          <jats:p>\n            To answer RSK\n            <jats:italic>k<\/jats:italic>\n            NN queries efficiently, we propose a hybrid index tree, called IUR-tree (Intersection-Union R-tree) that effectively combines location proximity with textual similarity. Subsequently, we design a branch-and-bound search algorithm based on the IUR-tree. To accelerate the query processing, we improve IUR-tree by leveraging the distribution of textual description, leading to some variants of the IUR-tree called Clustered IUR-tree (CIUR-tree) and combined clustered IUR-tree (C\n            <jats:sup>2<\/jats:sup>\n            IUR-tree), for each of which we develop optimized algorithms. We also provide a theoretical cost model to analyze the efficiency of our algorithms. Our empirical studies show that the proposed algorithms are efficient and scalable.\n          <\/jats:p>","DOI":"10.1145\/2576232","type":"journal-article","created":{"date-parts":[[2014,5,27]],"date-time":"2014-05-27T12:56:59Z","timestamp":1401195419000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Efficient Algorithms and Cost Models for Reverse Spatial-Keyword\n            <i>k<\/i>\n            -Nearest Neighbor Search"],"prefix":"10.1145","volume":"39","author":[{"given":"Ying","family":"Lu","sequence":"first","affiliation":[{"name":"Renmin University of China, Los Angeles, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiaheng","family":"Lu","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gao","family":"Cong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Wu","sequence":"additional","affiliation":[{"name":"Institute for Infocomm Research, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cyrus","family":"Shahabi","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,5,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142531"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516462"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263671"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE'01)","author":"Bohm C.","unstructured":"C. Bohm and H. Kriegel . 2001. A cost model and index architecture for the similarity join . In Proceedings of the IEEE International Conference on Data Engineering (ICDE'01) . 411--420. C. Bohm and H. Kriegel. 2001. A cost model and index architecture for the similarity join. In Proceedings of the IEEE International Conference on Data Engineering (ICDE'01). 411--420."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the SIAM International Conference on Data Mining. 243--254","author":"Boriah S.","unstructured":"S. Boriah , V. Chandola , and V. Kumar . 2008. Similarity measures for categorical data: A comparative evaluation . In Proceedings of the SIAM International Conference on Data Mining. 243--254 . S. Boriah, V. Chandola, and V. Kumar. 2008. Similarity measures for categorical data: A comparative evaluation. In Proceedings of the SIAM International Conference on Data Mining. 243--254."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920891"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767904"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0265-y"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687755"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687666"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2005.03.004"},{"key":"e_1_2_1_12_1","unstructured":"M. H. Degroot and M. J. Schervish. 2004. Probability and Statistics. Pearson Education.  M. H. Degroot and M. J. Schervish. 2004. Probability and Statistics. Pearson Education."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869870"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 2nd International Conference on Knowledge, Discovery and Data Mining (KDD'96)","author":"Ester M.","unstructured":"M. Ester , H.-P. Kriegel , J. Sander , and X. Xu . 1996. A density-based algorithm for discovering clusters in large spatial databases with noise . In Proceedings of the 2nd International Conference on Knowledge, Discovery and Data Mining (KDD'96) . 226--231. M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge, Discovery and Data Mining (KDD'96). 226--231."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182593"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38758"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497474"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/125187.125200"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511502"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the New Zealand Computer Science Research Student Conference. 49--56","author":"Huang A.","year":"2008","unstructured":"A. Huang . 2008 . Similarity measures for text document clustering . In Proceedings of the New Zealand Computer Science Research Student Conference. 49--56 . A. Huang. 2008. Similarity measures for text document clustering. In Proceedings of the New Zealand Computer Science Research Student Conference. 49--56."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.1997.621148"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'94)","author":"Johnson T.","unstructured":"T. Johnson and D. Shasha . 1994. 2q: A low overhead high performance buffer management replacement algorithm . In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'94) . 439--450. T. Johnson and D. Shasha. 1994. 2q: A low overhead high performance buffer management replacement algorithm. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'94). 439--450."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/170088.170403"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE'09)","author":"Kang J. M.","unstructured":"J. M. Kang , M. F. Mokbel , S. Shekhar , T. Xia , and D. Zhang . 2007. Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors . In Proceedings of the IEEE International Conference on Data Engineering (ICDE'09) . 806--815. J. M. Kang, M. F. Mokbel, S. Shekhar, T. Xia, and D. Zhang. 2007. Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors. In Proceedings of the IEEE International Conference on Data Engineering (ICDE'09). 806--815."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-011-0142-7"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335415"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908983"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729694"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Annual Conference of the Cognitive Science Society (CogSci'05)","author":"Lee M. D.","unstructured":"M. D. Lee and M. Welsh . 2005. An empirical evaluation of models of text document similarity . In Proceedings of the Annual Conference of the Cognitive Science Society (CogSci'05) . 1254--1259. M. D. Lee and M. Welsh. 2005. An empirical evaluation of models of text document similarity. In Proceedings of the Annual Conference of the Cognitive Science Society (CogSci'05). 1254--1259."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.149"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the International Database Engineering and Applications Symposium (IDEAS'03)","author":"Lin K.-I.","unstructured":"K.-I. Lin , M. Nolen , and C. Yang . 2003. Applying bulk insertion techniques for dynamic reverse nearest neighbor problems . In Proceedings of the International Database Engineering and Applications Symposium (IDEAS'03) . 290--297. K.-I. Lin, M. Nolen, and C. Yang. 2003. Applying bulk insertion techniques for dynamic reverse nearest neighbor problems. In Proceedings of the International Database Engineering and Applications Symposium (IDEAS'03). 290--297."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989361"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153878"},{"key":"e_1_2_1_36_1","volume-title":"Proceeding of the 6th International Conference on Database Theory. 394--408","author":"Papadopoulos A.","unstructured":"A. Papadopoulos and Y. Manolopoulos . 1997. Performance of nearest neighbour queries in r-trees . In Proceeding of the 6th International Conference on Database Theory. 394--408 . A. Papadopoulos and Y. Manolopoulos. 1997. Performance of nearest neighbour queries in r-trees. In Proceeding of the 6th International Conference on Database Theory. 394--408."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335427"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(88)90021-0"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956882"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 44--53","author":"Stanoi I.","unstructured":"I. Stanoi , D. Agrawal , and A. E. Abbadi . 2000. Reverse nearest neighbor queries for dynamic databases . In Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 44--53 . I. Stanoi, D. Agrawal, and A. E. Abbadi. 2000. Reverse nearest neighbor queries for dynamic databases. In Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 44--53."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases (VLDB'01)","author":"Stanoi I.","unstructured":"I. Stanoi , M. Riedewald , D. Agrawal , and A. Abbadi . 2001. Discovery of influence sets in frequently updated databases . In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB'01) . 99--108. I. Stanoi, M. Riedewald, D. Agrawal, and A. Abbadi. 2001. Discovery of influence sets in frequently updated databases. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB'01). 99--108."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the Workshop on Artificial Intelligence for Web Search (AAAI'00)","author":"Strehl A.","unstructured":"A. Strehl , E. Strehl , J. Ghosh , and R. Mooney . 2000. Impact of similarity measures on web-page clustering . In Proceedings of the Workshop on Artificial Intelligence for Web Search (AAAI'00) . 58--64. A. Strehl, E. Strehl, J. Ghosh, and R. Mooney. 2000. Impact of similarity measures on web-page clustering. In Proceedings of the Workshop on Artificial Intelligence for Web Search (AAAI'00). 58--64."},{"key":"e_1_2_1_44_1","unstructured":"P.-N. Tan M. Steinbach and V. Kumar. 2005. Introduction to Data Mining. Addison-Wesley.   P.-N. Tan M. Steinbach and V. Kumar. 2005. Introduction to Data Mining. Addison-Wesley."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/777943.777944"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 13th International Conference on Very Large Data Bases (VLDB'04)","author":"Tao Y.","unstructured":"Y. Tao , D. Papadias , and X. Lian . 2004a. Reverse knn search in arbitrary dimensionality . In Proceedings of the 13th International Conference on Very Large Data Bases (VLDB'04) . 744--755. Y. Tao, D. Papadias, and X. Lian. 2004a. Reverse knn search in arbitrary dimensionality. In Proceedings of the 13th International Conference on Very Large Data Bases (VLDB'04). 744--755."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.48"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237705"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842247"},{"key":"e_1_2_1_50_1","volume-title":"The Theory of the Riemann Zeta-Function","author":"Titchmarsh E. C.","unstructured":"E. C. Titchmarsh . 2005. The Theory of the Riemann Zeta-Function . Oxford University Press . E. C. Titchmarsh. 2005. The Theory of the Riemann Zeta-Function. Oxford University Press."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_13"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE'10)","author":"Vlachou A.","unstructured":"A. Vlachou , C. Doulkeridis , Y. Kotidis , and K. N\u00f8rvag . 2010. Reverse top-k queries . In Proceedings of the IEEE International Conference on Data Engineering (ICDE'10) . 365--376. A. Vlachou, C. Doulkeridis, Y. Kotidis, and K. N\u00f8rvag. 2010. Reverse top-k queries. In Proceedings of the IEEE International Conference on Data Engineering (ICDE'10). 365--376."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2008.31"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453970"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.77"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099584"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2576232","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2576232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:13:59Z","timestamp":1750277639000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2576232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1145\/2576232"],"URL":"https:\/\/doi.org\/10.1145\/2576232","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}