Efficient Multidimensional Top- k Query Processing in Wireless Multihop Networks

Abstract EN

Top- k queries, which retrieve the k most preferable data objects, have been receiving much attention.

An emerging challenge is to support efficient top- k queryprocessing in a wireless distributed network.

In this study, we investigated how to process multidimensional top- k queries efficiently in a wireless multihop network.

A major challenge for multidimensional top- k queries is that answers for different users are typically different, because each user has a unique preference and search range.

Meanwhile, it is desirable for wireless networks to reduce unnecessary traffic even if users issue top- k queries with their own unique preferences.

Therefore, we address the above problem and propose a top- k query processing method in wireless multihop networks, called ClusTo.

ClusTo performs a novel clustering scheme for multidimensional top- k query processing and routes queries based on the cluster while guaranteeing the user’s specified search range.

Moreover, ClusTo takes a dynamic threshold approach to suppress unnecessary query transmissions to nodes which do not contribute to top- k data retrieval.

Extensive experiments on both real and synthetic data have demonstrated that ClusTo outperforms existing methods in terms of traffic and delay.