More Web Proxy on the site http://driver.im/

research-article

CTR: An Efficient Cluster-based Top-k Query Routing in MANETs

Authors:

Daichi Amagata,

Shojiro NishioAuthors Info & Claims

MoMM '14: Proceedings of the 12th International Conference on Advances in Mobile Computing and Multimedia

Pages 225 - 234

https://doi.org/10.1145/2684103.2684104

Published: 08 December 2014 Publication History

Abstract

Top-k queries, which retrieve the k data items with the highest scores, have been receiving considerable attention because of their utility for many real life applications. In this paper, we propose an efficient query routing scheme enabling top-k data retrieval by only necessary nodes, named CTR. CTR employs a new clustering framework for top-k query processing, and in this framework, nodes holding high rank data items become ClusterHeads (CHs), and top-k queries are transmitted between CHs via gateway nodes which belong to multiple clusters. Each CH maintains a record of hop counts between itself and high rank data items, enabling it to judge whether or not to transmit a query on the fly. As a result, CTR reduces overhead while keeping high accuracy of the query result. Extensive experiments have demonstrated that CTR functions well in terms of accuracy of the query result, overhead, and delay.

References

[1]

R. Akbarinia, E. Pacitti, and P. Valduriez. Reducing network traffic in unstructured p2p systems using top-k queries. Distributed and Parallel Databases, 19(2-3):67--86, 2006.

Digital Library

[2]

R. Akbarinia, E. Pacitti, and P. Valduriez. Best position algorithms for top-k queries. In VLDB, pages 495-506, 2007.

Digital Library

[3]

D. Amagata, Y. Sasaki, T. Hara, and S. Nishio. A robust routing method for top-k queries in mobile ad hoc networks. In MDM, pages 251-256, 2013.

Digital Library

[4]

D. Amagata, Y. Sasaki, T. Hara, and S. Nishio. A routing method for top-k query processing in mobile ad hoc networks. In AINA, pages 161-168, 2013.

Digital Library

[5]

W.-T. Balke, W. Nejdl, W. Siberski, and U. Thaden. Progressive distributed top-k retrieval in peer-to-peer networks. In ICDE, pages 174-185, 2005.

Digital Library

[6]

P. Basu, N. Khan, and T. D. Little. A mobility based metric for clustering in mobile ad hoc networks. In ICDCS workshop, pages 413-418, 2001.

Digital Library

[7]

C. Buckley and E. M. Voorhees. Evaluating evaluation measure stability. In SIGIR, pages 33--40, 2000.

Digital Library

[8]

T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless communications and mobile computing, 2(5):483--502, 2002.

[9]

P. Cao and Z. Wang. Efficient top-k query calculation in distributed networks. In PODC, pages 206-215, 2004.

Digital Library

[10]

B. Chen, W. Liang, and G. Min. Top-k query evaluation in sensor networks with the guaranteed accuracy of query results. In DEXA, pages 156-171, 2011.

Digital Library

[11]

B. Chen, W. Liang, R. Zhou, and J. X. Yu. Energy-efficient top-k query processing in wireless sensor networks. In CIKM, pages 115-122, 2010.

Digital Library

[12]

S. Chinara and S. K. Rath. A survey on one-hop clustering algorithms in mobile ad hoc networks. Journal of Network and Systems Management, 17(1-2):183--207, 2009.

Digital Library

[13]

G. Das, D. Gunopulos, N. Koudas, and N. Sarkas. Ad-hoc top-k query answering for data streams. In VLDB, pages 183-194, 2007.

Digital Library

[14]

A. Ephremides, J. E. Wieselthier, and D. J. Baker. A design concept for reliable mobile radio networks with frequency hopping signaling. Proc. the IEEE, 75(1):56--73, 1987.

[15]

R. Hagihara, M. Shinohara, T. Hara, and S. Nishio. A message processing method for top-k query for traffic reduction in ad hoc networks. In MDM, pages 11-20, 2009.

Digital Library

[16]

H. Jiang, J. Cheng, C. W. D. Wang, and G. Tan. Continuous multi-dimensional top-k query processing in sensor networks. In INFOCOM, pages 793-801, 2011.

[17]

X. Liu, J. Xu, and W. C. Lee. A cross pruning framework for top-k data collection in wireless sensor network. In MDM, pages 157-166, 2010.

Digital Library

[18]

S. Michel, T. Peter, and G. Weikum. Klee: A framework for distributed top-k query algorithms. In VLDB, pages 637-648, 2005.

Digital Library

[19]

J. Niedermayer, M. A. Nascimento, M. Renz, P. krøger, and H. P. Kriegel. Exploiting local node cache in top-k queries within wireless sensor networks. In ACM Sigspatial GIS, pages 434-437, 2010.

Digital Library

[20]

N. Padhariya, A. Mondai, V. Goyal, R. Shankar, and S. Madria. Ecotop: an economic model for dynamic processing of top-k queries in mobile-p2p networks. In DASFAA, pages 251-265, 2011.

Digital Library

[21]

A. K. Parekh. Selecting routers in ad-hoc wireless networks. In Proc. Int. Telecommunications Symposium, pages 420-424, 1994.

[22]

Y. Sasaki, R. Hagihara, T. Hara, M. Shinohara, and S. Nishio. A top-k query method by estimating score distribution in mobile ad hoc networks. In AINA workshop, pages 944-949, 2010.

Digital Library

[23]

Y. Sasaki, T. Hara, and S. Nishio. Two-phase top-k query processing in mobile ad hoc networks. In NBiS, pages 42-49, 2011.

Digital Library

[24]

Y. Sasaki, T. Hara, and S. Nishio. Top-k query processing for replicated data in mobile peer to peer networks. Journal of Systems and Software, Elsevier, 92:45--58, 2014.

[25]

Scalable Network Technologoes: Creaters of QualNet Network Simulator Software. http://www.scalable-networks.com/.

[26]

Y.-C. Tseng, S.-Y Ni, Y.-S. Chen, and J.-P Sheu. The broadcast storm problem in a mobile ad hoc network. Wireless networks, 8(2-3):153--167, 2002.

Digital Library

[27]

A. Vlachou, C. Doulkeridis, and K. Nørvåg. Distributed top-k query processing by exploiting skyline summaries. Distributed and Parallel Databases, 30(3-4):239--271, 2012.

Digital Library

[28]

A. Vlachou, C. Doulkeridis, K. Nørvåg, and M. Vazirgiannis. On efficient top-k query processing in highly distributed environments. In SIGMOD, pages 753-764, 2008.

Digital Library

[29]

M. Wu, J. Jianliang Xu, X. Xueyan Tang, and W.-C. Wang-Chien Lee. Top-k monitoring in wireless sensor networks. IEEE TKDE, (7):962--976, 2007.

Digital Library

[30]

W.-d. Yang and G.-z. Zhang. A weight-based clustering algorithm for mobile ad hoc network. In Int. Conf. Wireless and Mobile Communications, page 3, 2007.

Digital Library

Cited By

Amagata DHara TSasaki YNishio S(2018)Efficient cluster-based top-k query routing with data replication in MANETsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1867-221:15(4161-4178)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s00500-015-1867-2
Nakayama YAmagata DHara T(2016)An Efficient Method for Identifying MaxRS Location in Mobile Ad Hoc NetworksProceedings, Part I, 27th International Conference on Database and Expert Systems Applications - Volume 982710.1007/978-3-319-44403-1_3(37-51)Online publication date: 5-Sep-2016
https://dl.acm.org/doi/10.1007/978-3-319-44403-1_3
Nakayama YAmagata DHara TNishio S(2015)Range-based Continuous Threshold Query Processing in Mobile Ad Hoc NetworksProceedings of the 13th International Conference on Advances in Mobile Computing and Multimedia10.1145/2837126.2837131(169-178)Online publication date: 11-Dec-2015
https://dl.acm.org/doi/10.1145/2837126.2837131
Show More Cited By

Index Terms

CTR: An Efficient Cluster-based Top-k Query Routing in MANETs

Recommendations

Efficient cluster-based top-k query routing with data replication in MANETs

Top-k queries, which retrieve k data items with the best score, have been receiving considerable attention because they can support many real life applications. In this paper, we propose an efficient query routing scheme in mobile ad hoc networks (...
Supporting top-k join queries in relational databases

Ranking queries, also known as top-k queries, produce results that are ordered on some computed score. Typically, these queries involve joins, where users are usually interested only in the top-k join results. Top-k queries are dominant in many emerging ...
View usability and safety for the answering of top-k queries via materialized views
DOLAP '09: Proceedings of the ACM twelfth international workshop on Data warehousing and OLAP

In this paper, we investigate the problem of answering top-k queries via materialized views. We provide theoretical guarantees for the adequacy of a view to answer a top-k query, along with algorithmic techniques to compute the query via a view when ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

MoMM '14: Proceedings of the 12th International Conference on Advances in Mobile Computing and Multimedia

December 2014

464 pages

ISBN:9781450330084

DOI:10.1145/2684103

General Chair:
Shyue-Liang Leon Wang
National University of Kaohsiung, Taiwan
,
Program Chairs:
Yu-Hui Tao
National University of Kaohsiung, Taiwan
,
Liming Chen
University of Ulster, UK
,
Chung-Nan Lee
National Sun Yat-sen University, Taiwan

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

JKU: Johannes Kepler Universität Linz

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 December 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

MoMM '14

MoMM '14: The 12th International Conference on Advances in Mobile Computing and Multimedia

December 8 - 10, 2014

Kaohsiung, Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
87
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Amagata DHara TSasaki YNishio S(2018)Efficient cluster-based top-k query routing with data replication in MANETsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1867-221:15(4161-4178)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s00500-015-1867-2
Nakayama YAmagata DHara T(2016)An Efficient Method for Identifying MaxRS Location in Mobile Ad Hoc NetworksProceedings, Part I, 27th International Conference on Database and Expert Systems Applications - Volume 982710.1007/978-3-319-44403-1_3(37-51)Online publication date: 5-Sep-2016
https://dl.acm.org/doi/10.1007/978-3-319-44403-1_3
Nakayama YAmagata DHara TNishio S(2015)Range-based Continuous Threshold Query Processing in Mobile Ad Hoc NetworksProceedings of the 13th International Conference on Advances in Mobile Computing and Multimedia10.1145/2837126.2837131(169-178)Online publication date: 11-Dec-2015
https://dl.acm.org/doi/10.1145/2837126.2837131
Tsuda TKomai YHara TNishio S(2015)Signature-Based Top-k Query Processing against Data Replacement Attacks in MANETsProceedings of the 2015 IEEE 34th Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS.2015.34(130-139)Online publication date: 28-Sep-2015
https://dl.acm.org/doi/10.1109/SRDS.2015.34

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents