{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:23:26Z","timestamp":1760243006574,"version":"build-2065373602"},"reference-count":35,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2015,3,12]],"date-time":"2015-03-12T00:00:00Z","timestamp":1426118400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>We investigate the in-network processing of an iceberg join query in wireless sensor networks (WSNs). An iceberg join is a special type of join where only those joined tuples whose cardinality exceeds a certain threshold (called iceberg threshold) are qualified for the result. Processing such a join involves the value matching for the join predicate as well as the checking of the cardinality constraint for the iceberg threshold. In the previous scheme, the value matching is carried out as the main task for filtering non-joinable tuples while the iceberg threshold is treated as an additional constraint. We take an alternative approach, meeting the cardinality constraint first and matching values next. In this approach, with a logical fragmentation of the join operand relations on the aggregate counts of the joining attribute values, the optimal sequence of 2-way fragment semijoins is generated, where each fragment semijoin employs a Bloom filter as a synopsis of the joining attribute values. This sequence filters non-joinable tuples in an energy-efficient way in WSNs. Through implementation and a set of detailed experiments, we show that our alternative approach considerably outperforms the previous one.<\/jats:p>","DOI":"10.3390\/s150306105","type":"journal-article","created":{"date-parts":[[2015,3,12]],"date-time":"2015-03-12T11:30:24Z","timestamp":1426159824000},"page":"6105-6132","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["In-Network Processing of an Iceberg Join Query in Wireless Sensor Networks Based on 2-Way Fragment Semijoins"],"prefix":"10.3390","volume":"15","author":[{"given":"Hyunchul","family":"Kang","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Chung-Ang University, Seoul 156-756, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2015,3,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1145\/1061318.1061322","article-title":"TinyDB: An Acquisitional Query Processing System for Sensor Networks","volume":"1","author":"Madden","year":"2005","journal-title":"ACM Trans. Database Syst."},{"key":"ref_2","unstructured":"Yu, H., Lim, E., and Zhang, J. (2006, January 9\u201313). On In-Network Synopsis Join Processing for Sensor Networks. Proceedings of the 7th International Conference on Mobile Data Management, Nara, Japan."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3358","DOI":"10.3390\/s130303358","article-title":"In-network processing of joins in wireless sensor networks","volume":"13","author":"Kang","year":"2013","journal-title":"Sensors"},{"key":"ref_4","unstructured":"Zhao, F., and Guibas, L. (2004). Wireless Sensor Networks: An Information Processing Approach, Morgan Kaufmann."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Stattner, E., Vidot, N., Hunel, P., and Collard, M. (2012, January 22\u201325). Wireless Sensor Network for Habitat Monitoring: A Counting Heuristic. Proceedings of the 37th Annual IEEE Conference on Local Computer Networks Workshops, Clearwater, FL, USA.","DOI":"10.1109\/LCNW.2012.6424060"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Lai, Y., Lin, Z., and Gao, X. (2010, January 27\u201328). SRJA: Iceberg Join Processing in Wireless Sensor Networks. Proceedings of the International Workshop on Database Technology and Applications, Wuhan, China.","DOI":"10.1109\/DBTA.2010.5659011"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Shou, Y., Mamoulis, N., Cao, H., Papadias, D., and Cheung, D. (2003, January 24\u201327). Evaluation of Iceberg Distance Joins. Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases, Santorini Island, Greece.","DOI":"10.1007\/978-3-540-45072-6_16"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Cohen, S., and Matias, Y. (2003, January 9\u201312). Spectral Bloom Filters. Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego, CA, USA.","DOI":"10.1145\/872757.872787"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s00778-004-0147-z","article-title":"The CQL continuous query language: Semantic foundations and query execution","volume":"2","author":"Arasu","year":"2006","journal-title":"VLDB J."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"7","author":"Bloom","year":"1970","journal-title":"Comm. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Kang, H., and Roussopoulos, N. (1987, January 3\u20135). Using 2-way Semijoins in Distributed Query Processing. Proceedings of the 3rd IEEE International Conference on Data Engineering, Los Angeles, CA, USA.","DOI":"10.1109\/ICDE.1987.7272434"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1109\/69.109109","article-title":"A pipeline n-way join algorithm based on the 2-way semijoin program","volume":"4","author":"Roussopoulos","year":"1991","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/322234.322238","article-title":"Using semi-joins to solve relational queries","volume":"1","author":"Bernstein","year":"1981","journal-title":"J. ACM"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"\u00d6zsu, M.T., and Valduriez, P. (2011). Principles of Distributed Database Systems, Springer. [3rd ed.].","DOI":"10.1007\/978-1-4419-8834-8"},{"key":"ref_15","unstructured":"Li, Z., and Ross, K.A. (December, January 28). RERF Join: An Alternative to Two-way Semijoin and Bloomjoin. Proceedings of the 4th International Conference on Information and Knowledge Management, Baltimore, MD, USA."},{"key":"ref_16","first-page":"485","article-title":"Network applications of Bloom filters: A survey","volume":"4","author":"Andrei","year":"2004","journal-title":"Internet Math."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1109\/32.52778","article-title":"Optimal semijoins for distributed database systems","volume":"5","author":"Mullin","year":"1990","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_18","unstructured":"Abadi, D., Madden, S., and Lindner, W. (September, January 30). REED: Robust, Efficient Filtering and Event Detection in sensor networks. Proceedings of the 31st International Conference on very Large Data Bases, Trondheim, Norway."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1007\/s11390-008-9191-2","article-title":"PEJA: Progressive energy-efficient join processing for sensor networks","volume":"6","author":"Lai","year":"2008","journal-title":"J. Comput. Sci. Technol."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Pandit, A., and Gupta, H. (2006, January 12\u201315). Communication-Efficient Implementation of Range-Join in Sensor Networks. Proceedings of 11th International Conference on Database Systems for Advanced Applications, Singapore.","DOI":"10.1007\/11733836_63"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Chowdhary, V., and Gupta, H. (2005, January 17\u201320). Communication-efficient Implementation of Join in Sensor Networks. Proceedings of the 10th International Conference on Database Systems for Advanced Applications, Beijing, China.","DOI":"10.1007\/11408079_40"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Coman, A., and Nascimento, M. (2007, January 9\u201311). Distributed Algorithm for Joins in Sensor Networks. Proceedings of the 19th International Conference on Scientific and Statistical Database Management, Banff, Canada.","DOI":"10.1109\/SSDBM.2007.26"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Coman, A., Nascimento, M., and Sander, J. (2007, January 7\u201311). On Join Location in Sensor Networks. Proceedings of the 8th International Conference on Mobile Data Management, Mannheim, Germany.","DOI":"10.1109\/MDM.2007.35"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"3443","DOI":"10.1016\/j.ins.2011.04.017","article-title":"Cost based in-network join strategy in tree routing sensor networks","volume":"16","author":"Min","year":"2011","journal-title":"Inf. Sci."},{"key":"ref_25","unstructured":"Mihaylov, S., Jacob, M., Ives, Z., and Guha, S. (2010, January 13\u201317). Dynamic Join Optimization in Multi-Hop Wireless Sensor Networks. Proceedings of the 36th International Conference on very Large Data Bases, Singapore."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Mihaylov, S., Jacob, M., Ives, Z., and Guha, S. (2008, January 24). A Substrate for In-Network Sensor Data Integration. Proceedings of the 5th Workshop on Data Management for Sensor Networks, Auckland, New Zealand.","DOI":"10.1145\/1402050.1402059"},{"key":"ref_27","unstructured":"Stern, M., Buchmann, E., and B\u00f6hm, K. (April, January 29). Towards Efficient Processing of General-Purpose Joins in Sensor Networks. Proceedings of the 25th IEEE International Conference on Data Engineering, Shanghai, China."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Stern, M., B\u00f6hm, K., and Buchmann, E. (2010, January 6\u201311). Processing Continuous Join Queries in Sensor Networks: A Filtering Approach. Proceedings of the ACM SIGMOD International Conference on Management of Data, Indianapolis, IN, USA.","DOI":"10.1145\/1807167.1807198"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Yang, X., Lim, H., \u00d6zsu, M., and Tan, K. (2007, January 12\u201314). In-Network Execution of Monitoring Queries in Sensor Networks. Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China.","DOI":"10.1145\/1247480.1247538"},{"key":"ref_30","first-page":"2702","article-title":"Multi-Attribute Join Query Processing in Sensor Networks","volume":"10","author":"Mo","year":"2014","journal-title":"J. Netw."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.ins.2013.09.026","article-title":"TWINS: Efficient time-windowed in-network joins for sensor networks","volume":"1","author":"Min","year":"2014","journal-title":"Inf. Sci."},{"key":"ref_32","unstructured":"Fang, M., Shivakumar, N., Garcia-Molina, H., Motwani, R., and Ullman, J.D. (1998, January 24\u201327). Computing Iceberg Queries Efficiently. Proceedings of the 24th International Conference on Very Large Data Bases, New York, NY, USA."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Zhao, H., Lall, A., Ogihara, M., and Xu, J. (2010, January 1\u20136). Global Iceberg Detection over Distributed Data Streams. Proceedings of the 26th International Conference on Data Engineering, Long Beach, CA, USA.","DOI":"10.1109\/ICDE.2010.5447825"},{"key":"ref_34","unstructured":"Manjhi, A., Shkapenyuk, V., Dhamdhere, K., and Olston, C. (2005, January 5\u20138). Finding (Recently) Frequent Items in Distributed Data Streams. Proceedings of the 21st International Conference on Data Engineering, Tokyo, Japan."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Zhao, Q., Ogihara, M., Wang, H., and Xu, J. (2006, January 26\u201328). Finding Global Icebergs over Distributed Data Sets. Proceedings of the 25th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Chicago, IL, USA.","DOI":"10.1145\/1142351.1142394"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/15\/3\/6105\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:43:26Z","timestamp":1760215406000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/15\/3\/6105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,12]]},"references-count":35,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2015,3]]}},"alternative-id":["s150306105"],"URL":"https:\/\/doi.org\/10.3390\/s150306105","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2015,3,12]]}}}