nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Ranked Reverse Boolean Spatial Keyword Nearest Neighbors Search

verfasst von : Hailin Fang, Pengpeng Zhao, Victor S. Sheng, Zhixu Li, Jiajie Xu, Jian Wu, Zhiming Cui

Erschienen in: Web Information Systems Engineering – WISE 2015

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Recently, Reverse k Nearest Neighbors (RkNN) queries, returning every answer for which the query is one of its k nearest neighbors, have been extensively studied on the database research community. But the RkNN query cannot retrieve spatio-textual objects which are described by their spatial location and a set of keywords. Therefore, researchers proposed a RSTkNN query to find these objects, taking both spatial and textual similarity into consideration. However, the RSTkNN query cannot control the size of answer set and to be sorted according to the degree of influence on the query. In this paper, we propose a new problem Ranked Reverse Boolean Spatial Keyword Nearest Neighbors query called Ranked-RBSKNN query, which considers both spatial similarity and textual relevance, and returns t answers with most degree of influence. We propose a separate index and a hybrid index to process such queries efficiently. Experimental results on different real-world and synthetic datasets show that our approaches achieve better performance.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Twitter Sarcasm Detection Exploiting a Context-Based Model

Nächstes Kapitel GraSS: An Efficient Method for RDF Subgraph Matching

Akbarinia, R., Pacitti, E., Valduriez, P.: Best position algorithms for top-k queries. In: Proceedings of the 33rd International Conference on Very Large Data Bases, pp. 495–506. VLDB Endowment (2007)

Cao, X., Chen, L., Cong, G., Jensen, C.S., Qu, Q., Skovsgaard, A., Wu, D., Yiu, M.L.: Spatial keyword querying. In: Atzeni, P., Cheung, D., Ram, S. (eds.) ER 2012. LNCS, vol. 7532, pp. 16–29. Springer, Heidelberg (2012) CrossRef

Chaudhuri, S., Gravano, L.: Evaluating top-k selection queries. In: VLDB, vol. 99, pp. 397–410 (1999)

Cheema, M.A., Lin, X., Zhang, W., Zhang, Y.: Influence zone: efficiently processing reverse k nearest neighbors queries. In: 2011 IEEE 27th International Conference on Data Engineering (ICDE), pp. 577–588. IEEE (2011)

Cheema, M.A., Shen, Z., Lin, X., Zhang, W.: A unified framework for efficiently processing ranking related queries. In: EDBT, pp. 427–438 (2014)

Chen, L., Cong, G., Jensen, C.S., Wu, D.: Spatial keyword query processing: an experimental evaluation. Proc. VLDB Endowment 6(3), 217–228 (2013)CrossRef

De Felipe, I., Hristidis, V., Rishe, N.: Keyword search on spatial databases. In: IEEE 24th International Conference on Data Engineering, ICDE 2008, pp. 656–665. IEEE (2008)

Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. (CSUR) 40(4), 11 (2008)CrossRef

Kriegel, H.P., Kroger, P., Renz, M., Zufle, A., Katzdobler, A.: Incremental reverse nearest neighbor ranking. In: IEEE 25th International Conference on Data Engineering, ICDE 2009, pp. 1560–1567. IEEE (2009)

10.

Lee, K.C., Ye, M., Lee, W.C.: Reverse ranking query over imprecise spatial data. In: Proceedings of the 1st International Conference and Exhibition on Computing for Geospatial Research & Application, p. 17. ACM (2010)

11.

Lee, K.C., Zheng, B., Lee, W.C.: Ranked reverse nearest neighbor search. IEEE Trans. Knowl. Data Eng. 20(7), 894–910 (2008)CrossRef

12.

Li, G., Wang, Y., Wang, T., Feng, J.: Location-aware publish/subscribe. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 802–810. ACM (2013)

13.

Lian, X., Chen, L.: Probabilistic inverse ranking queries in uncertain databases. VLDB J. Int. J. Very Large Data Bases 20(1), 107–127 (2011)CrossRef

14.

Lu, J., Lu, Y., Cong, G.: Reverse spatial and textual k nearest neighbor search. In: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pp. 349–360. ACM (2011)

15.

Marian, A., Bruno, N., Gravano, L.: Evaluating top-k queries over web-accessible databases. ACM Trans. Database Syst. (TODS) 29(2), 319–362 (2004)CrossRef

16.

Rocha-Junior, J.B., Gkorgkas, O., Jonassen, S., Nørvåg, K.: Efficient processing of top-k spatial keyword queries. In: Pfoser, D., Tao, Y., Mouratidis, K., Nascimento, M.A., Mokbel, M., Shekhar, S., Huang, Y. (eds.) SSTD 2011. LNCS, vol. 6849, pp. 205–222. Springer, Heidelberg (2011) CrossRef

17.

Rocha-Junior, J.B., Nørvåg, K.: Top-k spatial keyword queries on road networks. In: Proceedings of the 15th International Conference on Extending Database Technology, pp. 168–179. ACM (2012)

18.

Tao, Y., Papadias, D., Lian, X.: Reverse knn search in arbitrary dimensionality. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases, vol. 30, pp. 744–755. VLDB Endowment (2004)

19.

Vlachou, A., Doulkeridis, C., Kotidis, Y., Norvag, K.: Reverse top-k queries. In: 2010 IEEE 26th International Conference on Data Engineering (ICDE), pp. 365–376. IEEE (2010)

20.

Vlachou, A., Doulkeridis, C., Nørvåg, K., Kotidis, Y.: Identifying the most influential data objects with reverse top-k queries. Proc. VLDB Endowment 3(1–2), 364–372 (2010)CrossRef

21.

Vlachou, A., Doulkeridis, C., Nørvåg, K., Kotidis, Y.: Branch-and-bound algorithm for reverse top-k queries. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 481–492. ACM (2013)

22.

Wu, D., Yiu, M.L., Jensen, C.S., Cong, G.: Efficient continuously moving top-k spatial keyword query processing. In: 2011 IEEE 27th International Conference on Data Engineering (ICDE), pp. 541–552. IEEE (2011)

23.

Yang, S., Cheema, M.A., Lin, X., Wang, W.: Reverse k nearest neighbors query processing: experiments and analysis. Proc. VLDB Endowment 8(5), 605–616 (2015)CrossRef

24.

Yi, K., Yu, H., Yang, J., Xia, G., Chen, Y.: Efficient maintenance of materialized top-k views. In: Proceedings of the 19th International Conference on Data Engineering, pp. 189–200. IEEE (2003)

25.

Yu, A., Agarwal, P.K., Yang, J.: Processing a large number of continuous preference top-k queries. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pp. 397–408. ACM (2012)

26.

Zhang, C., Zhang, Y., Zhang, W., Lin, X.: Inverted linear quadtree: efficient top k spatial keyword search. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 901–912. IEEE (2013)

27.

Zhang, D., Chan, C.Y., Tan, K.L.: Processing spatial keyword query as a top-k aggregation query. In: Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 355–364. ACM (2014)

28.

Zhang, D., Tan, K.L., Tung, A.K.: Scalable top-k spatial keyword search. In: Proceedings of the 16th International Conference on Extending Database Technology, pp. 359–370. ACM (2013)

29.

Zhang, Z., Jin, C., Kang, Q.: Reverse k-ranks query. Proc. VLDB Endowment 7(10), 785–796 (2014)CrossRef

30.

Zheng, K., Fung, P.C., Zhou, X.: K-nearest neighbor search for fuzzy objects. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 699–710. ACM (2010)

31.

Zheng, K., Su, H., Zheng, B., Shang, S., Xu, J., Liu, J., Zhou, X.: Interactive top-k spatial keyword queries. In: 2015 IEEE 31st International Conference on Data Engineering (ICDE), pp. 423–434. IEEE (2015)

Titel: Ranked Reverse Boolean Spatial Keyword Nearest Neighbors Search
verfasst von: Hailin Fang
Pengpeng Zhao
Victor S. Sheng
Zhixu Li
Jiajie Xu
Jian Wu
Zhiming Cui
Verlag: Springer International Publishing
Buch: Web Information Systems Engineering – WISE 2015
Print ISBN: 978-3-319-26189-8

Electronic ISBN: 978-3-319-26190-4

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-26190-4_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"