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
Published in:
Detecting Anomalous Ratings Using Matrix Factorization for Recommender Systems Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Multidimensional Similarity Join Using MapReduce

Authors : Ye Li, Jian Wang, Leong Hou U

Published in: Web-Age Information Management

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Similarity join is arguably one of the most important operators in multidimensional data analysis tasks. However, processing a similarity join is costly especially for large volume and high dimensional data. In this work, we attempt to process the similarity join on MapReduce such that the join computation can be scaled horizontally. In order to make the workload balancing among all MapReduce nodes, we systemically select the most profitable feature based on a novel data selectivity approach. Given the selected feature, we develop the partitioning scheme for MapReduce processing based on two different optimization goals. Our proposed techniques are extensively evaluated on real datasets.

Dont have a licence yet? Then find out more about our products and how to get one 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

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
previous chapter ERPC: An Edge-Resources Based Framework to Reduce Bandwidth Cost in the Personal Cloud
next chapter Real-Time Logo Recognition from Live Video Streams Using an Elastic Cloud Platform
Literature
1.
Gunopulos, D., Kollios, G., Tsotras, J., Domeniconi, C.: Selectivity estimators for multidimensional range queries over real attributes. VLDB J.–Int. J. Very Large Data Bases 14(2), 137–154 (2005)CrossRef
2.
Dean, J., Ghemawat, S.: Mapreduce: simplified data processing on large clusters. Commun. ACM 5(1), 107–113 (2008)CrossRef
3.
Yang, H., Dasdan, A., Hsiao, R.L., Parker, D.S.: Map-reduce-merge: simplified relational data processing on large clusters. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, pp. 1029–1040. ACM (2007)
4.
Blanas, S., Patel, J.M., Ercegovac, V., Rao, J., Shekita, E.J., Tian, Y.: A comparison of join algorithms for log processing in mapreduce. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp. 975–986. ACM (2010)
5.
Wu, F., Wu, Q., Tan, Y.: Comparison and performance analysis of join approach in mapreduce. In: Yuan, Y., Wu, X., Lu, Y. (eds.) Trustworthy Computing and Services. CCIS, vol. 320, pp. 629–636. Springer, Heidelberg (2013)CrossRef
6.
Atta, F., Viglas, S.D., Niazi, S.: Sand joina skew handling join algorithm for google’s mapreduce framework. In: 2011 IEEE 14th International Multitopic Conference (INMIC), pp. 170–175. IEEE (2011)
7.
Lin, Z., Cai, M., Huang, Z., Lai, Y.: SALA: A skew-avoiding and locality-aware algorithm for mapreduce-based join. In: Dong, X.L., Yu, X., Dong, X.L., Li, J., Sun, Y., Sun, Y. (eds.) WAIM 2015. LNCS, vol. 9098, pp. 311–323. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-21042-1_​25 CrossRef
8.
Zhang, S., Han, J., Liu, Z., Wang, K., Xu, Z.: SJMR: Parallelizing spatial join with mapreduce on clusters. In: 2009 IEEE International Conference on Cluster Computing and Workshops, CLUSTER 2009, pp. 1–8. IEEE (2009)
9.
Vernica, R., Carey, M.J., Li, C.: Efficient parallel set-similarity joins using mapreduce. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp. 495–506. ACM (2010)
10.
Böhm, C., Braunmüller, B., Krebs, F., Kriegel, H.P.: Epsilon grid order: an algorithm for the similarity join on massive high-dimensional data. In: ACM SIGMOD Record, vol. 30, pp. 379–388. ACM (2001)
11.
Kalashnikov, D.V.: Super-ego: fast multi-dimensional similarity join. VLDB J. Int. J. Very Large Data Bases 22(4), 561–585 (2013)MathSciNetCrossRef
12.
Chaudhuri, S., Motwani, R., Narasayya, V.: On random sampling over joins. In: ACM SIGMOD Record, vol. 28, pp. 263–274. ACM (1999)
13.
Olken, F., Rotem, D.: Simple random sampling from relational databases. In: VLDB, vol. 86, pp. 25–28 (1986)
14.
Das Sarma, A., He, Y., Chaudhuri, S.: Clusterjoin: a similarity joins framework using map-reduce. Proc. VLDB Endowment 7(12), 1059–1070 (2014)CrossRef
15.
Wang, Y., Metwally, A., Parthasarathy, S.: Scalable all-pairs similarity search in metric spaces. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 829–837. ACM (2013)
Metadata
Title
Multidimensional Similarity Join Using MapReduce
Authors
Ye Li
Jian Wang
Leong Hou U
Copyright Year
2016
Book
Web-Age Information Management

Print ISBN: 978-3-319-39957-7

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

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-39958-4_36