4R-TPUT: An efficient top-<i>k</i> query algorithm for structured peer-to-peer systems

Abstract
Figures/Tables
References
Related Articles
Metrics

Download: PDF(1140 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

The Top-k query returns to users the k best match results and is an important data processing technique in peer-to-peer systems. This paper focuses on accurate top-k query processing in structured peer-to-peer systems in which the data is vertically partitioned among peers. The three communication round-trip algorithm TPUT is expanded into a 4R-TPUT threshold algorithm involving 4 round-trip communications. The algorithm has lower bound estimation, pruning and results lookup phases. TPUT introduces an additional round-trip communication in the first phase to get more information on the data to obtain a better top-k lower bound estimation and pruning threshold which can reduce data accesses and transmissions in the query processing. Tests show that 4R-TPUT greatly reduces data transmissions compared with TPUT and, thus, requires less query response time, so 4R-TPUT is a more efficient top-k query algorithm.

Keywords peer-to-peer systems top-k query TPUT 4R-TPUT

Issue Date: 15 April 2014

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	Qiming FANG
	Guangwen YANG

Cite this article:

Qiming FANG,Guangwen YANG. 4R-TPUT: An efficient top-k query algorithm for structured peer-to-peer systems[J]. Journal of Tsinghua University(Science and Technology), 2014, 54(4): 480-484.

URL:

http://jst.tsinghuajournals.com/EN/ OR http://jst.tsinghuajournals.com/EN/Y2014/V54/I4/480

[1]	SUNYongjiao, YUAN Ye, WANG Guoren. Top-k query processing over uncertain data in distributed environments [J]. J World Wide Web, 2012, 15(4): 429-446. url: http://dx.doi.org/10.1007/s11280-011-0141-5
[2]	ZHANG Jiangong, Suel T. Efficient query evaluation on large textual collections in a peer-to-peer environment [C]// Proc 5th IEEE Int Conf Peer-to-Peer Computing. Konstanz, Germany: IEEE Computer Society, 2005: 225-233.
[3]	CAO Pei, WANG Zhe. Efficient top-k query calculation in distributed networks [C]// Proc 23rd Annual ACM Symp Principles of Distributed Computing. Newfoundland, Canada: ACM, 2004: 206-215.
[4]	Akbarinia R, Pacitti E, Valduriez P. Processing top-k queries in distributed hash tables [C]// Proc 13th European Int Conf Parallel Processing. Rennes, France: Springer, 2007: 489-502.
[5]	Michel S,Triantafillou P, Weikum G. KLEE: A framework for distributed top-k query algorithms [C]// Proc Int Conf Very Large Data Bases. Trondheim, Norway: ACM, 2005: 637-648.
[6]	Zeinalipour-Yazti D, Vagena Z, Kalogeraki V, et al.Finding the k highest-ranked answers in a distributed network[J]. Computer Networks, 2009, 53(9): 1431-1449. url: http://dx.doi.org/10.1016/j.comnet.2009.01.008
[7]	ZHAO Keping, TAO Yufei, ZHOU Shuigeng. Efficient top-k processing in large-scaled distributed environments[J]. Data and Knowledge Engineering, 2007, 63(2): 315-335. url: http://dx.doi.org/10.1016/j.datak.2007.03.012
[8]	Hose K,Karnstedt M, Sattler K U, et al.Processing top-n queries in P2P-based web integration systems with probabilistic guarantees [C]// Proc 8th Int Workshop Web and Databases. Baltimore, USA: ACM, 2005: 109-114.
[9]	Akbarinia R, Pacitti E, Valduriez P. Reducing network traffic in unstructured P2P systems using top-k queries[J]. Distributed and Parallel Databases, 2006, 19(2-3): 67-86. url: http://dx.doi.org/10.1007/s10619-006-8313-5
[10]	GUAN Zhitao, YAN Guangwei, HUANG Heqing. A novel top-k query scheme in unstructured p2p networks [C]// Proc 9th IEEE Int Conf Computer and Information Technology. Xiamen, China: IEEE Computer Society, 2009: 16-21.
[11]	Dedzoe W K, Lamarre P, Akbarinia R, et al.ASAP top-k query processing in unstructured p2p systems [C]// Proc 10th Int Conf Peer-to-Peer Computing. Delft, Netherlands: IEEE, 2010: 1-10.
[12]	Vlachou A, Doulkeridis C, Nørvåg K, et al.On efficient top-k query processing in highly distributed environments [C]// Proc 2008 ACM SIGMOD Int Conf Management of Data. Vancouver, Canada: ACM, 2008: 753-764.
[13]	Balke W T, Nejdl W, Siberski W, et al.Progressive distributed top-k retrieval in peer-to-peer networks [C]// Proc 21st Int Conf Data Engineering. Tokyo, Japan: IEEE Computer Society, 2005: 174-185.
[14]	Chrysakis I, Chalkidis C, Plexousakis D. Evaluation of top-k queries in peer-to-peer networks using threshold algorithms [C]// Proc 19th ACM Int Conf Information and Knowledge Management. Toronto, Canada: ACM, 2010: 1305-1308.
[15]	YU Hailing, LI Huagang, WU Ping, et al.Efficient processing of distributed top-k queries [C]// Proc 16th Int Conf Database and Expert Systems Applications. Copenhagen, Denmark: Springer, 2005: 65-74.
[16]	Chen B, Liang W, Yu J X. Energy-efficient top-k query evaluation and maintenance in wireless sensor networks [Z/OL].[2013-08-07]. http://link.springer.com/article/10.1007/s11276-013-0625-6.

[1]	ZHANG Hong, BI Zhijun, YU Anmiao. Positioning of China's real estate industry based on the input-output method[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(2): 153-159.
[2]	CHEN Dingjiang, PIAN Zihao, ZHU Bing, HU Shanying. Input-output analysis of the economic, resource and environmental impacts of China's chemical industry[J]. Journal of Tsinghua University(Science and Technology), 2020, 60(9): 773-778.
[3]	LIU Yu, ZHANG Xiujun, ZHOU Shidong. Reciprocity calibration of a massive MIMO based on a local calibration[J]. Journal of Tsinghua University(Science and Technology), 2017, 57(9): 939-944,951.
[4]	CHEN Dingjiang, ZHANG Xiaoyang, ZHOU Wenji, ZHU Bing. Material flow-related research using a Chinese multi-region input-output data approach[J]. Journal of Tsinghua University(Science and Technology), 2016, 56(8): 860-864.
[5]	REN Yinpeng, NI Zuyao, KUANG Linling, WU Sheng, LU Jianhua. Anti partial-band noise jamming interleaved hybrid spread spectrum system design and capacity analysis[J]. Journal of Tsinghua University(Science and Technology), 2015, 55(8): 866-872.
[6]	MEN Yanwu, ZHANG Hui, JIANG Wenxue, ZHOU Kai, YE Peiqing. Quantitative decoupling cooperative control of CMP multi-zone pressure systems[J]. Journal of Tsinghua University(Science and Technology), 2015, 55(7): 750-755.
[7]	HE Qiang, ZHANG Xiujun, XIAO Limin, ZHOU Shidong. Impact of multi-cell pilot reuse on the achievable uplink rate for massive MIMO systems[J]. Journal of Tsinghua University(Science and Technology), 2015, 55(5): 526-531.

Viewed

Full text

Abstract

Cited

Shared

Discussed