Skip to main content
Erschienen in: World Wide Web 4/2016

01.07.2016

Efficient batch similarity join processing of social images based on arbitrary features

verfasst von: Yi Zhuang, Nan Jiang, Zhi-Ang Wu, Jie Cao, Chunhua Ju

Erschienen in: World Wide Web | Ausgabe 4/2016

Einloggen

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

search-config
loading …

Abstract

In this paper, we identify and solve a multi-join optimization problem for Arbitrary Feature-based social image Similarity JOINs(AFS-JOIN). Given two collections(i.e., R and S) of social images that carry both visual, spatial and textual(i.e., tag) information, the multiple joins based on arbitrary features retrieves the pairs of images that are visually, textually similar or spatially close from different users. To address this problem, in this paper, we have proposed three methods to facilitate the multi-join processing: 1) two baseline approaches(i.e., a naïve join approach and a maximal threshold(MT)-based), and 2) a Batch Similarity Join(BSJ) method. For the BSJ method, given m users’ join requests, they are first conversed and grouped into m″ clusters which correspond to m″ join boxes, where m > m″. To speedup the BSJ processing, a feature distance space is first partitioned into some cubes based on four segmentation schemes; the image pairs falling in the cubes are indexed by the cube tree index; thus BSJ processing is transformed into the searching of the image pairs falling in some affected cubes for m″ AFS-JOINs with the aid of the index. An extensive experimental evaluation using real and synthetic datasets shows that our proposed BSJ technique outperforms the state-of-the-art solutions.

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

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!

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!

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!

Fußnoten
1
Note that, the total number of features in the AFS-JOIN is three (e.g., visual, textual and spatial features) in this paper, it can be easily extended to support multiple features AFS-JOINs such as textual, shape and temporal features, etc.
 
Literatur
1.
Zurück zum Zitat Alamery, M., Faraahi, A., Javadi, H.H.S., et al.: Multi-joins query optimization using the bees algorithm. In: Advances in Intelligent and Soft Computing. 79. pp.449–457. (2010) Alamery, M., Faraahi, A., Javadi, H.H.S., et al.: Multi-joins query optimization using the bees algorithm. In: Advances in Intelligent and Soft Computing. 79. pp.449–457. (2010)
2.
Zurück zum Zitat Arasu, A., Ganti, V., Kaushik, R,: Efficient exact set-similarity joins. In: VLDB, (2006) Arasu, A., Ganti, V., Kaushik, R,: Efficient exact set-similarity joins. In: VLDB, (2006)
3.
Zurück zum Zitat Baeza-Yates, R., Ribeiro-Neto, B.: Modern Information Retrieval. Addison Wesley, 1st edition, (1999) Baeza-Yates, R., Ribeiro-Neto, B.: Modern Information Retrieval. Addison Wesley, 1st edition, (1999)
4.
Zurück zum Zitat Ballesteros, J., Cary, A., Rishe, N.: Spsjoin: parallel spatial similarity joins. In: GIS, pp. 481–484. (2011) Ballesteros, J., Cary, A., Rishe, N.: Spsjoin: parallel spatial similarity joins. In: GIS, pp. 481–484. (2011)
5.
Zurück zum Zitat Bayardo, R.J., Ma, Y., Srikant, R.: Scaling up all pairs similarity search. In: WWW. (2007) Bayardo, R.J., Ma, Y., Srikant, R.: Scaling up all pairs similarity search. In: WWW. (2007)
6.
Zurück zum Zitat Bouros, P., Ge, S., Mamoulis, N.: Spatio-textual similarity joins. In: VLDB. (2013) Bouros, P., Ge, S., Mamoulis, N.: Spatio-textual similarity joins. In: VLDB. (2013)
7.
Zurück zum Zitat Brinkhoff, T., Kriegel, H.-P., Seeger, B.: Efficient processing of spatial joins using r-trees. In SIGMOD, (1993) Brinkhoff, T., Kriegel, H.-P., Seeger, B.: Efficient processing of spatial joins using r-trees. In SIGMOD, (1993)
8.
Zurück zum Zitat Broder A.Z.: On the resemblance and containment of documents. In: SEQS. (1997) Broder A.Z.: On the resemblance and containment of documents. In: SEQS. (1997)
9.
Zurück zum Zitat Chan, E.P.F.: Buffer queries. TKDE 15(4), 895–910 (2003) Chan, E.P.F.: Buffer queries. TKDE 15(4), 895–910 (2003)
10.
Zurück zum Zitat Charikar, M.: Similarity estimation techniques from rounding algorithms. In: STOC. (2002) Charikar, M.: Similarity estimation techniques from rounding algorithms. In: STOC. (2002)
11.
Zurück zum Zitat Chaudhuri, S., Ganti, V., Kaushik, R.: A primitive operator for similarity joins in data cleaning. In: ICDE. (2006) Chaudhuri, S., Ganti, V., Kaushik, R.: A primitive operator for similarity joins in data cleaning. In: ICDE. (2006)
12.
Zurück zum Zitat Chowdhury, A., Frieder, O., Grossman, D.A., et al.: Collection statistics for fast duplicate document detection. In TOIS. 20(2): 171–191, (2002) Chowdhury, A., Frieder, O., Grossman, D.A., et al.: Collection statistics for fast duplicate document detection. In TOIS. 20(2): 171–191, (2002)
13.
Zurück zum Zitat Elmagarmid, A.K., Ipeirotis, P.G., Verykios, V.S.: Duplicate record detection: a survey. In: TKDE, 19(1):1–16. (2007) Elmagarmid, A.K., Ipeirotis, P.G., Verykios, V.S.: Duplicate record detection: a survey. In: TKDE, 19(1):1–16. (2007)
14.
Zurück zum Zitat Gravano, L., Ipeirotis, P.G., Jagadish, H.V., Koudas, N., Muthukrishnan, S., Srivastava, D.: Approximate string joins in a database (almost) for free. In: VLDB. (2001) Gravano, L., Ipeirotis, P.G., Jagadish, H.V., Koudas, N., Muthukrishnan, S., Srivastava, D.: Approximate string joins in a database (almost) for free. In: VLDB. (2001)
15.
Zurück zum Zitat Kementsietsidis, A., Neven, F., Van de Craen, D.: Scalable multi query optimization for exploratory queries over federated scientific databases. In: VLDB. (2008) Kementsietsidis, A., Neven, F., Van de Craen, D.: Scalable multi query optimization for exploratory queries over federated scientific databases. In: VLDB. (2008)
16.
Zurück zum Zitat Li, G.L., Deng, D., Wang, J.N., Feng, J.H.: Pass-join: a partition-based method for similarity joins. In VLDB. (2012) Li, G.L., Deng, D., Wang, J.N., Feng, J.H.: Pass-join: a partition-based method for similarity joins. In VLDB. (2012)
17.
Zurück zum Zitat Lu, H.J., Shan, M.C., Tan, K.L.: Optimization of multi-way join queries for parallel execution. In VLDB. (1991) Lu, H.J., Shan, M.C., Tan, K.L.: Optimization of multi-way join queries for parallel execution. In VLDB. (1991)
18.
Zurück zum Zitat Roy, P., Seshadri S., Sudarshan, S., et al.: Efficient and extensible algorithms for multi query optimization. In: SIGOMOD. (2000) Roy, P., Seshadri S., Sudarshan, S., et al.: Efficient and extensible algorithms for multi query optimization. In: SIGOMOD. (2000)
19.
Zurück zum Zitat Sarawagi, S., Kirpal, A.: Efficient set joins on similarity predicates. In: SIGMOD, (2004) Sarawagi, S., Kirpal, A.: Efficient set joins on similarity predicates. In: SIGMOD, (2004)
20.
Zurück zum Zitat Sarma, A. D., He, Y, Chaudhuri, S.: ClusterJoin: a similarity joins framework using MapReduce. In: VLDB. (2014) Sarma, A. D., He, Y, Chaudhuri, S.: ClusterJoin: a similarity joins framework using MapReduce. In: VLDB. (2014)
21.
Zurück zum Zitat Sellis, T.K., Multi-query optimization. In: TODS. 13(1). (1988) Sellis, T.K., Multi-query optimization. In: TODS. 13(1). (1988)
22.
Zurück zum Zitat Shan, M.C., Yu, P., Wu, K.L.: Optimization of parallel execution for multi-join queries. In: TKDE. 8(3) pp. 416–428. (1996) Shan, M.C., Yu, P., Wu, K.L.: Optimization of parallel execution for multi-join queries. In: TKDE. 8(3) pp. 416–428. (1996)
23.
Zurück zum Zitat Shekita, E.J., Young, H.C., Tan, K.L.: Multi-join optimization for symmetric multiprocessors. In: VLDB. (1993) Shekita, E.J., Young, H.C., Tan, K.L.: Multi-join optimization for symmetric multiprocessors. In: VLDB. (1993)
24.
Zurück zum Zitat Sun, A.X., Bhowmick, S.S., Nguyen, K.T.N. et al.: Tag-based social image retrieval: an empirical evaluation. In: JASIST. 62(12): 2364–2381. (2011) Sun, A.X., Bhowmick, S.S., Nguyen, K.T.N. et al.: Tag-based social image retrieval: an empirical evaluation. In: JASIST. 62(12): 2364–2381. (2011)
25.
Zurück zum Zitat Xiao, C., Wang, W., Lin, X., Yu, J.X., Wang, G.: Efficient similarity joins for near-duplicate detection. In: TODS. 36(3):15, (2011) Xiao, C., Wang, W., Lin, X., Yu, J.X., Wang, G.: Efficient similarity joins for near-duplicate detection. In: TODS. 36(3):15, (2011)
26.
Zurück zum Zitat Xiao, C., Wang, W., Lin, X., Yu, J.X.: Efficient similarity joins for near duplicate detection. In: WWW. (2008) Xiao, C., Wang, W., Lin, X., Yu, J.X.: Efficient similarity joins for near duplicate detection. In: WWW. (2008)
27.
Zurück zum Zitat Xiao, C., Wang, W., Lin, X., Shang, H.: Top-k set similarity joins. In: ICDE. (2009) Xiao, C., Wang, W., Lin, X., Shang, H.: Top-k set similarity joins. In: ICDE. (2009)
28.
Zurück zum Zitat Zhuang, Y., Li, Q., Chen, L.: Multi-query optimization for distributed similarity query processing. In: ICDCS. (2008) Zhuang, Y., Li, Q., Chen, L.: Multi-query optimization for distributed similarity query processing. In: ICDCS. (2008)
Metadaten
Titel
Efficient batch similarity join processing of social images based on arbitrary features
verfasst von
Yi Zhuang
Nan Jiang
Zhi-Ang Wu
Jie Cao
Chunhua Ju
Publikationsdatum
01.07.2016
Verlag
Springer US
Erschienen in
World Wide Web / Ausgabe 4/2016
Print ISSN: 1386-145X
Elektronische ISSN: 1573-1413
DOI
https://doi.org/10.1007/s11280-015-0355-z

Weitere Artikel der Ausgabe 4/2016

World Wide Web 4/2016 Zur Ausgabe