Category: Publications

Paper by Yakov Nekrich Accepted for ACM-SIAM SODA21 Symposium

A paper by Associate Professor Yakov Nekrich, Computer Science, has been accepted for the 61st ACM-SIAM Symposium on Discrete Algorithms 2021 (SODA21), which will take place virtually January 10-13, 2021.

Nekrich is sole author of the accepted article, “New Data Structures for Orthogonal Range Reporting and Range Minima Queries.” An extended version of the paper is available for download on ArXiv.

The annual ACM-SIAM Symposium on Discrete Algorithms (SODA) is an academic conference in the fields of algorithm design and discrete mathematics. It is considered among the top conferences for research in algorithms.


Paper Abstract

In this paper we present new data structures for two extensively studied variants of the orthogonal range searching problem.
First, we describe a data structure that supports two-dimensional orthogonal range minima queries in O(n) space and O(logεn) time, where n is the number of points in the data structure and ε is an arbitrarily small positive constant. Previously known linear-space solutions for this problem require O(log1+εn) (Chazelle, 1988) or O(lognloglogn) time (Farzan et al., 2012). A modification of our data structure uses space O(nloglogn) and supports range minima queries in time O(loglogn). Both results can be extended to support three-dimensional five-sided reporting queries.

Next, we turn to the four-dimensional orthogonal range reporting problem and present a data structure that answers queries in optimal O(logn/loglogn+k) time, where k is the number of points in the answer. This is the first data structure that achieves the optimal query time for this problem. Our results are obtained by exploiting the properties of three-dimensional shallow cuttings.


The Society for Industrial and Applied Mathematics (SIAM) is an international community of 14,500+ individual members. Almost 500 academic, manufacturing, research and development, service and consulting organizations, government, and military organizations worldwide are institutional members.

What Lies Ahead: Cooperative, Data-Driven Automated Driving

Kuilin Zhang

Associate Professor Kuilin Zhang, Civil and Environmental Engineering and affiliated associate professor, Computer Science, was featured in a recent article on Michigan Tech News. The article appears below. Link to the original article here.


By Kelley Christensen, September 28, 2020.

Networked data-driven vehicles can adapt to road hazards at longer range, increasing safety and preventing slowdowns.

Vehicle manufacturers offer smart features such as lane and braking assist to aid drivers in hazardous situations when human reflexes may not be fast enough. But most options only provide immediate benefits to a single vehicle. What if entire groups of vehicles could respond? What if instead of responding solely to the vehicle immediately in front of us, our cars reacted proactively to events happening hundreds of meters ahead?

What if, like a murmuration of starlings, our cars and trucks moved cooperatively on the road in response to each vehicle’s environmental sensors, reacting as a group to lessen traffic jams and protect the humans inside?

This question forms the basis of Kuilin Zhang’s National Science Foundation CAREER Award research. Zhang, an associate professor of civil and environmental engineering at Michigan Technological University, has published “A distributionally robust stochastic optimization-based model predictive control with distributionally robust chance constraints for cooperative adaptive cruise control under uncertain traffic conditions” in the journal Transportation Research Part B: Methodological.

The paper is coauthored with Shuaidong Zhao ’19, now a senior quantitative analyst at National Grid, where he continues to conduct research on the interdependency between smart grid and electric vehicle transportation systems.

Vehicle Platoons Operate in Sync

Creating vehicle systems adept at avoiding traffic accidents is an exercise in proving Newton’s First Law: An object in motion remains so unless acted on by an external force. Without much warning of what’s ahead, car accidents are more likely because drivers don’t have enough time to react. So what stops the car? A collision with another car or obstacle — causing injuries, damage and in the worst case, fatalities.

But cars communicating vehicle-to-vehicle can calculate possible obstacles in the road at increasing distances — and their synchronous reactions can prevent traffic jams and car accidents.

“On the freeway, one bad decision propagates other bad decisions. If we can consider what’s happening 300 meters in front of us, it can really improve road safety. It reduces congestion and accidents.”Kuilin Zhang

Zhang’s research asks how vehicles connect to other vehicles, how those vehicles make decisions together based on data from the driving environment and how to integrate disparate observations into a network.

Zhang and Zhao created a data-driven, optimization-based control model for a “platoon” of automated vehicles driving cooperatively under uncertain traffic conditions. Their model, based on the concept of forecasting the forecasts of others, uses streaming data from the modeled vehicles to predict the driving states (accelerating, decelerating or stopped) of preceding platoon vehicles. The predictions are integrated into real-time, machine-learning controllers that provide onboard sensed data. For these automated vehicles, data from controllers across the platoon become resources for cooperative decision-making. 

CAREER Award 

Kuilin Zhang won an NSF CAREER Award in 2019 for research on connected, autonomous vehicles and predictive modeling

Proving-Grounds Ready

The next phase of Zhang’s CAREER Award-supported research is to test the model’s simulations using actual connected, autonomous vehicles. Among the locations well-suited to this kind of testing is Michigan Tech’s Keweenaw Research Center, a proving ground for autonomous vehicles, with expertise in unpredictable environments.

Ground truthing the model will enable data-driven, predictive controllers to consider all kinds of hazards vehicles might encounter while driving and create a safer, more certain future for everyone sharing the road.

Tomorrow Needs Mobility

Michigan Technological University is a public research university, home to more than 7,000 students from 54 countries. Founded in 1885, the University offers more than 120 undergraduate and graduate degree programs in science and technology, engineering, forestry, business and economics, health professions, humanities, mathematics, and social sciences. Our campus in Michigan’s Upper Peninsula overlooks the Keweenaw Waterway and is just a few miles from Lake Superior.

Kuilin Zhang

About the Researcher: Kuilin Zhang

  • Data-driven optimization and control models for connected and automated vehicles (CAVs)
  • Big traffic data analytics using machine learning
  • Mobile and crowd sensing of dynamic traffic systems
  • Dynamic network equilibrium and optimization
  • Modeling and simulation of large-scale complex systems
  • Freight logistics and supply chain systems
  • Impact of plug-in electric vehicles to smart grid and transportation network systems
  • Interdependency and resiliency of large-scale networked infrastructure systems
  • Vehicular Ad-hoc Networks (VANETs)
  • Smart Cities
  • Cyber-Physical Systems

Bo Chen’s Research on COVID-19 Prevention Method to be Published in IEEE IoT Magazine

A paper authored by Michigan Tech Assistant Professor Bo Chen, Computer Science, and Data Science master’s student Shashank Reddy Danda, has been accepted for publication in the IEEE Internet of Things Magazine special issue on Smart IoT Solutions for Combating COVID-19 Pandemic. The special issue will be published in September 2020.

The paper focuses on Chen’s research of COVID-19 prevention through the leveraging of computing technology. The project is currently supported by a Michigan Tech College of Computing seed grant, and external funding for further development is being pursued.

Chen is a member of the ICC’s Center for Cybersecurity.

Download a preprint of the paper here.

Abstract:
Recently, the impact of coronavirus has been witnessed by almost every country around the world. To mitigate spreading of coronavirus, a fundamental strategy would be reducing the chance of healthy people from being exposed to it. Having observed the fact that most viruses come from coughing/sneezing/runny nose of infected people, in this work we propose to detect such symptom events via mobile devices (e.g., smartphones, smart watches, and other IoT devices) possessed by most people in modern world and, to instantly broadcast locations where the symptoms have been observed to other people. This would be able to significantly reduce risk that healthy people get exposed to the viruses. The mobile devices today are usually equipped with various sensors including microphone, accelerometer, and GPS, as well as network connection (4G, LTE, Wi-Fi), which makes our proposal feasible. Further experimental evaluation shows that coronavirus-like symptoms (coughing/sneezing/runny nose) can be detected with an accuracy around 90%; in addition, the dry cough (more likely happening to COVID-19 patients) and wet cough can also be differentiated with a high accuracy.

Bo Chen is an assistant professor in the Department of Computer Science. His areas of expertise include mobile device security, cloud computing security, named data networking security, big data security, and blockchain.

Shashank Reddy Danda is an MS student in Data Science. He is currently working as a research assistant in MTU Security and Privacy (SnP) Lab under the supervision of Dr. Bo Chen.

IEEE Internet of Things Magazine (IEEE IoTM) is a publication of the IEEE Internet of Things Initiative, a Multi-Society Technical Group.

Tim Havens, Tony Pinar Co-Authors of Article in IEEE Trans. Fuzzy Systems

An article by Anthony Pinar (DataS/ECE) and Timothy Havens (DataS/CC), in collaboration with University of Missouri researchers Muhammad Islam, Derek Anderson, Grant Scott, and Jim Keller, all of University of Missouri, has been published in the July 2020 issue of the journal IEEE Transactions on Fuzzy Systems.

The article is titled, “Enabling explainable fusion in deep learning with fuzzy integral neural networks.” Link to the article here.

Abstract:
Information fusion is an essential part of numerous engineering systems and biological functions, e.g., human cognition. Fusion occurs at many levels, ranging from the low-level combination of signals to the high-level aggregation of heterogeneous decision-making processes. While the last decade has witnessed an explosion of research in deep learning, fusion in neural networks has not observed the same revolution. Specifically, most neural fusion approaches are ad hoc, are not understood, are distributed versus localized, and/or explainability is low (if present at all). Herein, we prove that the fuzzy Choquet integral (ChI), a powerful nonlinear aggregation function, can be represented as a multilayer network, referred to hereafter as ChIMP.

We also put forth an improved ChIMP (iChIMP) that leads to a stochastic-gradient-descent-based optimization in light of the exponential number of ChI inequality constraints. An additional benefit of ChIMP/iChIMP is that it enables explainable artificial intelligence (XAI). Synthetic validation experiments are provided, and iChIMP is applied to the fusion of a set of heterogeneous architecture deep models in remote sensing. We show an improvement in model accuracy, and our previously established XAI indices shed light on the quality of our data, model, and its decisions.

Citation
M. Islam, D. T. Anderson, A. J. Pinar, T. C. Havens, G. Scott and J. M. Keller, “Enabling Explainable Fusion in Deep Learning With Fuzzy Integral Neural Networks,” in IEEE Transactions on Fuzzy Systems, vol. 28, no. 7, pp. 1291-1300, July 2020, doi: 10.1109/TFUZZ.2019.2917124.

ICC Releases FY19 Annual Report

The Institute of Computing and Cybersystems has released its FY 19 Annual Report, which can be viewed and downloaded on the ICC website.

We had a strong year in 2018-19,” says Timothy Havens, director of the ICC and associate dean for research, College of Computing.

“In FY20, new awards and research expenditures were even stronger, and I look forward to sharing more accomplishments with you in the coming months.”

Tim Havens, ICC Director

Nathir Rawashdeh Publishes Paper in BioSciences Journal

A paper co-authored by Assistant Professor Nathir Rawashdeh (DataS, Applied Computing) on Skin Cancer Image Feature Extraction, has been published this month in the EurAsian Journal of BioSciences.

View the open access article, “Visual feature extraction from dermoscopic colour images for classification of melanocytic skin lesions,” here.

Additional authors are Walid Al-Zyoud, Athar Abu Helou, and Eslam AlQasem, all with the Department of Biomedical Engineering, German Jordanian University, Amman, Jordan.

Citation: Al-Zyoud, Walid et al. “Visual feature extraction from dermoscopic colour images for classification of melanocytic skin lesions”. Eurasian Journal of Biosciences, vol. 14, no. 1, 2020, pp. 1299-1307.

Rawashdeh’s interests include unmanned ground vehicles, electromobility, robotics, image analysis, and color science. He is a senior member of the IEEE.

Sergeyev, Students Earn ASEE Conference Awards

Professor Aleksandr Segeyev (DataS), Applied Computing, and a group of Michigan Tech students presented two papers at the 2020 American Society for Engineering Education (ASEE) Gulf-Southwest Annual conference, which was conducted online April 23-24, 2020. Both papers received conference awards.

Faculty Paper Award

“Pioneering Approach for Offering the Convergence MS Degree in Mechatronics and Associate Graduate Certificate”
by Sergeyev, Professor and Associate Chair John Irwin (MMET), and Dean Adrienne Minerick (CC).

Student Paper Award

“Efficient Way of Converting outdated Allen Bradley PLC-5 System into Modern ControlLogix 5000 suit”, by Spencer Thompson (pictured), Larry Stambeck, Andy Posa, Sergeyev, and Lecturer Paniz Hazaveh, Applied Computing.

Sergeyev is director of the Michigan Tech Mechatronics Graduate Program and FANUC Certified Industrial Robotics Training Center.

Founded in 1893, the American Society for Engineering Education is a nonprofit organization of individuals and institutions committed to furthering education in engineering and engineering technology.

Bo Chen, Grad Students Present Posters at Security Symposium

College of Computing Assistant Professor Bo Chen, Computer Science, and his graduate students presented two posters at the 41st IEEE Symposium on Security and Privacy, which took place online May 18 to 21, 2020.

Since 1980, the IEEE Symposium on Security and Privacy has been the premier forum for presenting developments in computer security and electronic privacy, and for bringing together researchers and practitioners in the field.

Chen leads the Security and Privacy (SnP) lab at Michigan Tech. He is a member of Michigan Tech’s Institute of Computing and Cybersystems (ICC) Center for Cybersecurity (CyberS).

Chen’s research focuses on applied cryptography and data security and he investigates novel techniques to protect sensitive data in mobile devices/flash storage media and cloud infrastructures. Chen is also interested in designing novel techniques to ensure security and privacy of big data.

Chen will serve as general chair for the First EAI International Conference on Applied Cryptography in Computer and Communications (AC3), which will be held in Xiamen, China, in May 2021.

Visit Bo Chen’s faculty webpage here.

Poster: A Secure Plausibly Deniable System for Mobile Devices against Multi-snapshot Adversaries
Authors: Bo Chen, Niusen Chen
Abstract: Mobile computing devices have been used broadly to store, manage and process critical data. To protect confidentiality of stored data, major mobile operating systems provide full disk encryption, which relies on traditional encryption and requires keeping the decryption keys secret. This however, may not be true as an active attacker may coerce victims for decryption keys. Plausibly deniable encryption (PDE) can defend against such a coercive attacker by disguising the secret keys with decoy keys. Leveraging concept of PDE, various PDE systems have been built for mobile devices. However, a practical PDE system is still missing which can be compatible with mainstream mobile devices and, meanwhile, remains secure when facing a strong multi- snapshot adversary. This work fills this gap by designing the first mobile PDE system against the multi-snapshot adversaries.

Poster: Incorporating Malware Detection into Flash Translation Layer
Authors: Wen Xie, Niusen Chen, Bo Chen
Abstract: OS-level malware may compromise OS and obtain root privilege. Detecting this type of strong malware is challeng- ing, since it can easily hide its intrusion behaviors or even subvert the malware detection software (or malware detector). Having observed that flash storage devices have been used broadly by computing devices today, we propose to move the malware detector to the flash translation layer (FTL), located inside a flash storage device. Due to physical isolation provided by the FTL, the OS-level malware can neither subvert our malware detector, nor hide its access behaviors from our malware detector.

The 41st IEEE Symposium on Security and Privacy was sponsored by the IEEE Computer Society Technical Committee on Security and Privacy in cooperation with the International Association for Cryptologic Research. The Symposium was May 18-20, 2020, and the Security and Privacy Workshops were May 21, 2020.

Havens, Yazdanparast Publish Article in IEEE Transactions on Big Data

Timothy Havens

An article by Audrey Yazdanparast (2019, PhD, Electrical Engineering) and Dr. Timothy Havens, “Linear Time Community Detection by a Novel Modularity Gain Acceleration in Label Propagation,” has been accepted for publication in the journal, IEEE Transactions on Big Data.

The paper presents an efficient approach for detecting self-similar communities in weighted graphs, with applications in social network analysis, online commodity recommendation systems, user clustering, biology, communications network analysis, etc.

Paper Abstract: Community detection is an important problem in complex network analysis. Among numerous approaches for community detection, label propagation (LP) has attracted a lot of attention. LP selects the optimum community (i.e., label) of a network vertex by optimizing an objective function (e.g., Newman’s modularity) subject to the available labels in the vicinity of the vertex. In this paper, a novel analysis of Newman’s modularity gain with respect to label transitions in graphs is presented. Here, we propose a new form of Newman’s modularity gain calculation that quantifies available label transitions for any LP based community detection.

The proposed approach is called Modularity Gain Acceleration (MGA) and is simplified and divided into two components, the local and global sum-weights. The Local Sum-Weight (LSW) is the component with lower complexity and is calculated for each candidate label transition. The General Sum-Weight (GSW) is more computationally complex, and is calculated only once per each label. GSW is updated by leveraging a simple process for each node-label transition, instead of for all available labels. The MGA approach leads to significant efficiency improvements by reducing time consumption up to 85% relative to the original algorithms with the exact same quality in terms of modularity value which is highly valuable in analyses of big data sets.

Timothy Havens is director of Michigan Tech’s Institute of Computing and Cybersystems (ICC), the associate dean for research for the College of Computing , and the William and Gloria Jackson Associate Professor of Computer Systems.

View the article abstract here.

Article by Tim Havens in IEEE Transactions on Fuzzy Systems

An article co-authored by Tim Havens, associate dean for research, College off Computing, “Soft Overlapping Community Detection in Large-Scale Networks via Fast Fuzzy Modularity Maximization,” was published in the March 2020 issue of IEEE Transactions on Fuzzy Systems.

Havens’s co-authors are Audrey Yazdanparast (ECE) and Mohsen Jamalabdollahi of Cisco Systems.

Article Abstract: Soft overlapping clustering is one of the notable problems of community detection. Extensive research has been conducted to develop efficient methods for non-overlapping and crisp-overlapping community detection in large-scale networks. In this paper, Fast Fuzzy Modularity Maximization (FFMM) for soft overlapping community detection is proposed.

FFMM exploits novel iterative equations to calculate the modularity gain associated with changing the fuzzy membership values of network vertices. The simplicity of the proposed scheme enables efficient modifications, reducing computational complexity to a linear function of the network size and the number of communities. Moreover, to further reduce the complexity of FFMM for very large networks, Multi-cycle FFMM (McFFMM) is proposed.

The proposed McFFMM reduces complexity by breaking networks into multiple sub-networks and applying FFMM to detect their communities. Performance of the proposed techniques are demonstrated with real-world data and the Lancichinetti-Fortunato-Radicchi (LFR) benchmark networks. Moreover, the performance of the proposed techniques is eval- uated versus some state-of-the-art soft overlapping community detection approaches. Results show that the McFFMM produces a remarkable performance in terms of overlapping modularity with fuzzy memberships, computational time, number of detected overlapping nodes, and Overlapping Normalized Mutual Informa- tion (ONMI).

View more info here.