Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
World Wide Web
Published in: World Wide Web 1/2017

20-06-2016

Monochromatic and bichromatic ranked reverse boolean spatial keyword nearest neighbors search

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

Published in: World Wide Web | Issue 1/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article Aspect identification and ratings inference for hotel reviews
next article Using time-sensitive interactions to improve topic derivation in twitter

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
1.
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)
2.
Cao, X., Chen, L., Cong, G., Jensen, C.S., Qu, Q., Skovsgaard, A., Wu, D., Yiu, M.L.: Spatial keyword querying. In: Conceptual Modeling, pp. 16–29. Springer (2012)
3.
Chaudhuri, S., Gravano, L.: Evaluating top-k selection queries (1999)
4.
Cheema, M.A., Lin, X., Zhang, W., Zhang, Y.: Influence zone: Efficiently processing reverse k nearest neighbors queries. In: IEEE 27th International Conference on Data Engineering (ICDE) 2011. pp. 577–588. IEEE (2011)
5.
Cheema, M.A., Shen, Z., Lin, X., Zhang, W.: A unified framework for efficiently processing ranking related queries. In: EDBT. pp. 427–438 (2014)
6.
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
7.
Cong, G., Jensen, C.S., Wu, D.: Efficient retrieval of the top-k most relevant spatial Web objects. Proc. VLDB Endowment 2(1), 337–348 (2009)CrossRef
8.
De Felipe, I., Hristidis, V., Rishe, N.: Keyword search on spatial databases. In: IEEE 24th international conference on data engineering, 2008. ICDE 2008. pp. 656–665. IEEE (2008)
9.
Fang, H., Zhao, P., Sheng, V.S., Li, Z., Xu, J., Wu, J., Cui, Z.: Ranked reverse boolean spatial keyword nearest neighbors search. In: Web information systems engineering–WISE 2015, pp. 92–107. Springer (2015)
10.
Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40(4), 11 (2008)CrossRef
11.
Kriegel, H.P., Kroger, P., Renz, M., Zufle, A., Katzdobler, A.: Incremental reverse nearest neighbor ranking. In: IEEE 25th international conference on data engineering, 2009. ICDE’09. pp. 1560–1567. IEEE (2009)
12.
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)
13.
Lee, K.C., Zheng, B., Lee, W.C.: Ranked reverse nearest neighbor search. IEEE Trans. Knowl. Data Eng. 20(7), 894–910 (2008)CrossRef
14.
Lian, X., Chen, L.: Probabilistic inverse ranking queries in uncertain databases. The VLDB Journal The International Journal on Very Large Data Bases 20(1), 107–127 (2011)CrossRef
15.
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)
16.
Marian, A., Bruno, N., Gravano, L.: Evaluating top-k queries over web-accessible databases. ACM Trans. Database Syst. 29(2), 319–362 (2004)CrossRef
17.
Rocha-Junior, J.B., Gkorgkas, O., Jonassen, S.: Nørvåg, K.: Efficient processing of top-k spatial keyword queries. In: Advances in Spatial and Temporal Databases, pp. 205–222. Springer (2011)
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-volume 30. pp. 744–755. VLDB endowment (2004)
19.
Vlachou, A., Doulkeridis, C., Kotidis, Y., Norvag, K.: Reverse top-k queries. In: IEEE 26th International Conference on Data Engineering (ICDE), 2010. pp. 365–376. IEEE (2010)
20.
Vlachou, A., Doulkeridis, C., Kotidis, Y., Norvag, K.: Monochromatic and bichromatic reverse top-k queries. IEEE Trans. Knowl. Data Eng. 23(8), 1215–1229 (2011)CrossRef
21.
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
22.
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)
23.
Wang, W., Yin, H., Sadiq, S., Chen, L., Xie, M., Zhou, X.: Spore: A sequential personalized spatial item recommender system. In: The 32nd IEEE International Conference on Data Engineering. pp. 873–899. ACM (2016)
24.
Xin, D., Chen, C., Han, J.: Towards robust indexing for ranked queries. In: Proceedings of the 32nd international conference on Very large data bases. pp. 235–246. VLDB Endowment (2006)
25.
Yang, S., Cheema, M.A., Lin, X., Wang, W.: Reverse k nearest neighbors query processing: Experiments and analysis. Proc. VLDB Endowment 8(5) (2015)
26.
Yi, K., Yu, H., Yang, J., Xia, G., Chen, Y.: Efficient maintenance of materialized top-k views. In: 19th international conference on data engineering, 2003. Proceedings. pp. 189–200. IEEE (2003)
27.
Yin, H., Cui, B., Chen, L., Hu, Z., Zhang, C.: Modeling location-based user rating profiles for personalized recommendation. ACM Trans Knowl Discov Data 9(3), 19 (2015)CrossRef
28.
Yin, H., Cui, B., Sun, Y., Hu, Z., Chen, L.: Lcars: A spatial item recommender system. ACM Trans. Inf. Syst. 32(3), 11 (2014)CrossRef
29.
Yin, H., Hu, Z., Zhou, X., Wang, H., Zheng, K., Sadiq, S.: Discovering interpretable geo-social communities for user behavior prediction. In: The 32nd IEEE international conference on data engineering. pp. 845–867. ACM (2016)
30.
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)
31.
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)
32.
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)
33.
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)
34.
Zhang, Z., Jin, C., Kang, Q.: Reverse k-ranks query. Proc. VLDB Endowment 7(10) (2014)
35.
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)
36.
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)
Metadata
Title
Monochromatic and bichromatic ranked reverse boolean spatial keyword nearest neighbors search
Authors
Pengpeng Zhao
Hailin Fang
Victor S. Sheng
Zhixu Li
Jiajie Xu
Jian Wu
Zhiming Cui
Publication date
20-06-2016
Publisher
Springer US
Published in
World Wide Web / Issue 1/2017
Print ISSN: 1386-145X
Electronic ISSN: 1573-1413
DOI
https://doi.org/10.1007/s11280-016-0399-8

Other articles of this Issue 1/2017

World Wide Web 1/2017 Go to the issue

OriginalPaper

A feature based method for trajectory dataset segmentation and profiling

OriginalPaper

Crawling ranked deep Web data sources

OriginalPaper

Using time-sensitive interactions to improve topic derivation in twitter

EditorialNotes

Guest editorial: WWWJ special issue of the 16th International Conference on Web Information Systems Engineering (WISE 2015)

OriginalPaper

Aspect identification and ratings inference for hotel reviews

OriginalPaper

Effective and efficient trajectory outlier detection based on time-dependent popular route

Premium Partner

    Image Credits