A Top-k Closest Pairs Data Search Scheme  Based on MapReduce

doi:10.3969/j.issn.1006-2475.2014.08.009

Abstract

Abstract:

There is a wide range of applications that require finding the top-k most similar pairs of records in a

given database. However, computing such top-k similarity joins is a challenging problem today, as there is an

increasing trend of applications that expect to deal with vast amounts of data. This paper proposes a top-k

closest pairs data search scheme based on MapReduce, firstly, the proposed scheme splits conceptually all pairs of

points into partitions, and then the all pair partitioning and the essential pair partitioning methods are

proposed, we can correctly find the top-k closest pairs by computing the top-k closest pairs in each partition

separately and selecting the top-k closest pairs among the top-k closest pairs from all partitions. We finally

perform the experiments with not only synthetic but also real-life data sets. The performance study confirms the

effectiveness and scalability of the proposed MapReduce algorithms.

Key words: database, similarity, MapReduce, data search, partitioning

CLC Number:

TP311.131

LIU Shu-ying. A Top-k Closest Pairs Data Search Scheme Based on MapReduce[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2014.08.009.

References ［19］

［1］	Bhm C, Braunmüller B, Krebs F, et al. Epsilon grid order: An algorithm for the similarity join on massive high-
	dimensional data［J］. ACM SIGMOD Record, 2001,30(2):379-388.
［2］	李朝鹏，李肯立，成运，等. 基于数据预处理的并行分层聚类算法［J］. 计算机应用研究, 2010,27(1):71-73.
［3］	Lee K H, Lee Y J, Choi H, et al. Parallel data processing with MapReduce: A survey［J］. ACM SIGMOD Record,
20	12,40(4):11-20.
［4］	Corral A, Manolopoulos Y, Theodoridis Y, et al. Algorithms for processing K-closest-pair queries in spatial
	databases ［J］. Data & Knowledge Engineering, 2004,49(1):67-104.
［5］	Pereira J C, Lobo F G. An optimized divide-and-conquer algorithm for the closest-pair problem in the planar
	case［J］. Journal of Computer Science and Technology, 2012,27(4):891-896.
［6］	Yang S W, Choi Y, Jung C K. A divide-and-conquer delaunay triangulation algorithm with a vertex array and
	flip operations in two-dimensional space［J］. International Journal of Precision Engineering and Manufacturing,
20	11,12(3):435-442.
［7］	Salowe J S. Enumerating interdistances in space［J］. International Journal of Computational Geometry &
	Applications, 1992,2(1):49-59.
［8］	Lenhof H P, Smid M. Sequential and parallel algorithms for the k closest pairs problem ［J］. International
	Journal of Computational Geometry & Applications, 1995,5(3):273-288.
［9］	Katoh N, Iwano K. Finding k farthest pairs and k closest farthest bichromatic pairs for points in the plane
［C］	// Proceedings of the 8th Annual Symposium on Computational Geometry. 1992:320-329.
［10］	Qi Shuyao, Bouros P, Mamoulis N. Efficient Top-k spatial distance joins ［C］// Proceedings of the 13th
	International Conference on Advances in Spatial and Temporal Databases. 2013:1-18.
［11］	卢鑫,陈华辉,董一鸿,等. MapReduce框架下的不确定数据Top-k查询计算［J］. 模式识别与人工智能, 2013,26(7):695-704.
	
［12］	黄山. 基于Map-Reduce框架云环境时空查询技术研究与实现［D］. 沈阳：东北大学, 2011.
［13］	Xiao Chuan, Wang Wei, Lin Xuemin, et al. Efficient similarity joins for near-duplicate detection［J］. ACM
	Transactions on Database Systems(TODS), 2011,36(3):No. 15.
［14］	Vernica R, Carey M J, Li Chen. Efficient parallel set-similarity joins using MapReduce［C］// Proceedings
	of the 2010 ACM SIGMOD International Conference on Management of data. 2010:495-506.
［15］	Merigó J M, Gil-Lafuente A M. Using the OWA operator in the Minkowski distance［J］. International Journal
	of Computer Science, 2008,3(3):149-157.
［16］	Kim Y, Shim K. Parallel Top-k similarity join algorithms using MapReduce［C］// 2012 IEEE 28th
	International Conference on Data Engineering (ICDE). 2012:510-521.
［17］	段松青，吴斌，于乐，等. PDM: 基于Hadoop的并行数据分析系统［J］. 湖南大学学报（自然科学版）， 2012,39(10):87-
	92.
［18］	Palmer C R, Faloutsos C. Density biased sampling: An improved method for data mining and clustering
［C］	//Proceedings of the 2000 ACM SIGMOO International Conference on Management of Data. 2000:82-92.
［19］	UCSB. Datadownload［EB/OL］. http://vision.ece.ucsb.edu/download.html, 2014-04-25.

[1]	WANG Hong-jie, XU Sheng-chao. Clustering Method of Cloud Platform Abnormal Transmission Data Based on Hilbert Similarity [J]. Computer and Modernization, 2023, 0(09): 27-31.
[2]	WANG Hong, GE Hong. Cross Modal Hash Retrieval Based on Attention Mechanism and Semantic Similarity [J]. Computer and Modernization, 2023, 0(08): 44-53.
[3]	LIU Guo-li, XU Hong-nan, TAN You-qian. Collaborative Filtering Recommendation Algorithm Combined with Expert Trust [J]. Computer and Modernization, 2022, 0(11): 60-68.
[4]	TIAN Feng, DENG Xiao-ping, ZHANG Gui-qing, WANG Bao-yi. A Non-intrusive Load Monitoring Method Based on Improved kNN Algorithm and Transient Steady State Features [J]. Computer and Modernization, 2022, 0(10): 29-35.
[5]	ZENG Yi-bin, GE Hong. Cross-modal Retrieval Based on Context Fusion and Multi-similarity Learning [J]. Computer and Modernization, 2022, 0(08): 50-56.
[6]	ZHANG Li, LUO Chun-shan, XIE Wei-yuan, LI Bei-bei. Adaptive Encryption Method for Private Database Based on Branch Obfuscation Algorithm [J]. Computer and Modernization, 2022, 0(03): 43-47.
[7]	ZOU Meng-yuan, FAN Zhi-qiang, XU Luo, LIU Jie, LIANG Wan-lu. Similarity Measurement Method of Inf-ProA Information Activity Process Model [J]. Computer and Modernization, 2022, 0(02): 26-32.
[8]	ZHU Ding-kai, TIE Zhi-xin, HONG Shun-he. An Initialization Algorithm of HRG Model and Its Application in Link Prediction [J]. Computer and Modernization, 2022, 0(02): 38-44.
[9]	GENG Hua-cong, LIANG Hong-tao, LIU Guo-zhu. Recipe Recommendation Algorithm Based on Knowledge Graph and Collaborative Filtering [J]. Computer and Modernization, 2021, 0(08): 24-29.
[10]	LI Wen-quan, XU Su-ping. Tourism Resource Information Database System Based on Geographic Information [J]. Computer and Modernization, 2021, 0(08): 100-103.
[11]	WAN Yang-ye, GUO Jin-li. Link Prediction Algorithm Based on Resource Allocation and Graph Embedding Weighting [J]. Computer and Modernization, 2021, 0(07): 12-17.
[12]	HUANG Hao, CHEN Li. A Collaborative Filtering Algorithm Based on Information Entropy and Improved Similarity [J]. Computer and Modernization, 2021, 0(06): 29-34.
[13]	SHU Peng, DU Qing-wei. A Method for Mobile Community Detection Based on Multi-dimensional Informational Fusion [J]. Computer and Modernization, 2021, 0(05): 88-92.
[14]	SHAO Meng-qiao, JI Shun-hui, ZHANG Peng-cheng. AC-Rec: Academic Collaborators Recommendation Method Based on Multi-features [J]. Computer and Modernization, 2021, 0(03): 94-100.
[15]	YANG Quan. Semantic Similarity Calculation of Cilin Based on Logistic Function [J]. Computer and Modernization, 2021, 0(01): 111-119.

A Top-k Closest Pairs Data Search Scheme Based on MapReduce

Knowledge

Abstract

Cite this article

share this article

References ［19］

Related Articles 15

Recommended Articles

Metrics

Comments