Volume 9 Number 9 (Sep. 2014)
Home > Archive > 2014 > Volume 9 Number 9 (Sep. 2014) >
JCP 2014 Vol.9(9): 2000-2006 ISSN: 1796-203X
doi: 10.4304/jcp.9.9.2000-2006

Efficient Top-k Query Processing Algorithms in Highly Distributed Environments

Qiming Fanga1, Guangwen Yang2
1School of Computer, Hangzhou Dianzi University, Hangzhou 310018, China
2Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China


Abstract—Efficient top-k query processing in highly distributed environments is a valuable but challenging research topic. This paper focuses on the problem over vertically partitioned data and aims to propose more efficient algorithms.. The effort is put on limiting the data transferred and communication round trips among nodes to reduce the communication cost of the query processing. Two novel algorithms, BulkDBPA and 4RUT, are proposed. BulkDBPA is derived from the centralized algorithm BPA2 which requires very low data access. BulkDBPA borrows the idea of best position from BPA2 and so has the advantage of low data transferred. It further reduces the communication round trips by utilizing bulk read and bulk transfer mechanism. 4RUT is inspired by the algorithm TPUT which only requires three communication round trips to get the exact top-k results. 4RUT improves its top-k lower bound estimate by introducing one additional communication round trip, which can subsequently reduce the data transferred in query processing. Experimental results show that both BulkDBPA and 4RUT require much less data transferred and response time than the competitors including Simple Algorithm and TPUT and each has its own suitable application environments respectively.

Index Terms—top-k query, highly distributed, communication cost, BulkDBPA, 4RUT

[PDF]

Cite: Qiming Fanga, Guangwen Yang, "Efficient Top-k Query Processing Algorithms in Highly Distributed Environments," Journal of Computers vol. 9, no. 9, pp. 2000-2006, 2014.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>