Some pairs problems
Article No.: 8, Pages 1 - 7
Abstract
A common form of MapReduce application involves discovering relationships between certain pairs of inputs. Similarity joins serve as a good example of this type of problem, which we call a "some-pairs" problem. In the framework of [4], algorithms are measured by the tradeoff between reducer size (maximum number of inputs a reducer can handle) and the replication rate (average number of reducers to which an input must be sent. There are two obvious approaches to solving some-pairs problems in general. We show that no general-purpose MapReduce algorithm can beat both of these two algorithms in the worst case. We then explore a recursive algorithm for solving some-pairs problems and heuristics for beating the lower bound on common instances of the some-pairs class of problems.
References
[1]
F. N. Afrati, S. Dolev, E. Korach, S. Sharma, and J. D. Ullman. Assignment of different-sized inputs in mapreduce. In Proceedings of the Workshops of the EDBT/ICDT 2015 Joint Conference (EDBT/ICDT), Brussels, Belgium, March 27th, 2015., pages 28--37, 2015.
[2]
F. N. Afrati, A. D. Sarma, D. Menestrina, A. G. Parameswaran, and J. D. Ullman. Fuzzy joins using mapreduce. In IEEE 28th International Conference on Data Engineering (ICDE 2012), Washington, DC, USA (Arlington, Virginia), 1-5 April, 2012, pages 498--509, 2012.
[3]
F. N. Afrati, A. D. Sarma, A. Rajaraman, P. Rule, S. Salihoglu, and J. D. Ullman. Anchor-points algorithms for hamming and edit distances using mapreduce. In Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014., pages 4--14, 2014.
[4]
F. N. Afrati, A. D. Sarma, S. Salihoglu, and J. D. Ullman. Upper and lower bounds on the cost of a map-reduce computation. PVLDB, 6(4):277--288, 2013.
[5]
L. A. Bassalygo. Asymptotically optimal switching circuits. Problems of Information Transmission, 17(3):206--211, 1981.
[6]
J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. Commun. ACM, 51(1):107--113, Jan. 2008.
[7]
S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. BULL. AMER. MATH. SOC., 43(4):439--561, 2006.
[8]
A. Okcan and M. Riedewald. Processing theta-joins using mapreduce. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD '11, pages 949--960, New York, NY, USA, 2011. ACM.
[9]
M. S. Pinsker. On the complexity of a concentrator. In 7th International Teletraffic Conference, 1973.
[10]
J. D. Ullman. Designing good mapreduce algorithms. ACM Crossroads, 19(1):30--34, 2012.
Recommendations
Assignment Problems of Different-Sized Inputs in MapReduce
A MapReduce algorithm can be described by a mapping schema, which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all the inputs participating in the computation of this output. Reducers have ...
BigFCM
Clustering plays an important role in mining big data both as a modeling technique and a preprocessing step in many data mining process implementations. Fuzzy clustering provides more flexibility than non-fuzzy methods by allowing each data record to ...
MapReduce algorithms for the K group nearest-neighbor query
SAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied ComputingGiven two datasets of points (called Query and Training), the Group (K) Nearest Neighbor (GNN) query retrieves (K) points of the Training dataset with the smallest sum of distances to every point of the Query one. This spatial query has been studied ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2016
70 pages
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 26 June 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SIGMOD/PODS'16
Sponsor:
SIGMOD/PODS'16: International Conference on Management of Data
June 26 - July 1, 2016
California, San Francisco
Acceptance Rates
BeyondMR '16 Paper Acceptance Rate 10 of 19 submissions, 53%;
Overall Acceptance Rate 19 of 36 submissions, 53%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 107Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in