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: Monthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Jul 19, 2019 News!

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

  • Jun 21, 2019 News!

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

  • Apr 28, 2019 News!

    Vol 14, No 5 has been published with online version 7 papers are published in this issue after peer review   [Click]

  • Mar 20, 2019 News!

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

  • Feb 22, 2019 News!

    Vol 14, No 2 has been published with online version 8 papers are published in this issue after peer review   [Click]

  • Read more>>