Department of Computer Science and Engineering

Indian Institute of Technology Hyderabad (IITH) is a premier institute of science and technology established in 2008. IITH has been consistently ranked in the&nbsp;<a href="https://iith.ac.in/reports/" rel="noopener noreferrer">top 10 institutes</a>&nbsp;in India for Engineering&nbsp;<a href="https://www.nirfindia.org/2021/EngineeringRanking.html" rel="noopener noreferrer" target="_blank">according to NIRF</a>&nbsp;making it one of the most coveted schools for science and technology in the country.

IITH offers&nbsp;<a href="https://iith.ac.in/academics/under-graduate/">undergraduate programs</a>&nbsp;in all the classical engineering disciplines, applied sciences, design, as well as several modern interdisciplinary areas. Students are given a flexibility to explore a broad set of areas, and potentially pursue a minor or double major in a discipline that is not their own. Students who wish to seek a deeper understanding of their own discipline are strongly encouraged to get involved in cutting-edge research with the help of a faculty to mentor them, and earn an Honors in their own field.

The very foundation of IIT Hyderabad is based on&nbsp;<a href="https://iith.ac.in/research/">research and innovation</a>. The vibrant research culture is evident from the number of patents and publications that IITH produces consistently every year. IITH offers&nbsp;<a href="https://iith.ac.in/academics/programmes-offered/">graduate programs</a>&nbsp;at both a masters, and a doctoral level, in several diverse areas. There are separate programs for technology, design, science, and liberal arts. The&nbsp;<a href="https://iith.ac.in/academics/post-graduate/">MTech program</a>&nbsp;is offered in various modes and durations to cater to the ever-growing need of postgraduate level professionals in the country.

IITH encourages and supports&nbsp;<a href="https://iic-iith.netlify.app/index.html" rel="noopener noreferrer" target="_blank">innovation and entrepreneurship</a>&nbsp;at every stage. The minor program in entrepreneurship is open to all students of IITH, and many of the courses are offered by industrialists who are entrepreneurs themselves. There are various&nbsp;<a href="https://iith.ac.in/research/centres-incubators/">innovation centers and incubators</a>&nbsp;that promote entrepreneurship and help mentor young innovators. IITH has been very successful in building tie-ups with leading academic institutions around the globe.

IITH enjoys a very special relationship with Japanese universities and industries that goes beyond academic and research collaborations. In fact, some of the iconic buildings in IITH campus will carry the signature of Japanese architecture.

IITH creates a unique holistic ecosystem for education that offers interactive learning, a very flexible academic structure, cutting-edge research, strong industry collaboration, and entrepreneurship. This is an environment which enables students and faculty to translate their dreams into realities.

IIT Hyderabad

Categorical attributes are those that can take a discrete set of values, e.g., colours. This work is about compressing vectors over categorical attributes to low-dimension discrete vectors. The current hash-based methods do not provide any guarantee on the Hamming distances between the compressed representations. Here we present FSketch to create sketches for a sparse categorical data and an estimator to estimate the pairwise Hamming distances among the uncompressed data only from their sketches. We claim that these sketches can be used in the usual data mining tasks in place of the original data without compromising the quality of the task. For that we ensure that the sketches also are categorical, sparse, and the Hamming distance estimates are reasonably precise. Both the sketch construction and the Hamming distance estimation algorithms require just a single-pass; furthermore, changes to a data point can be incorporated into its sketch in an efficient manner. Our claims are backed by rigorous theoretical analysis of the properties of FSketch and supplemented by extensive comparative evaluations with related algorithms on some real-world datasets. We show that FSketch is significantly faster, and the accuracy obtained by using its sketches are among the top for the standard unsupervised tasks of RMSE, clustering and similarity search IEEE

World University root node

Fulltext

IEEE Transactions on Knowledge and Data Engineering

Dimensionality Reduction for Categorical Data

Representation of spatio-temporal properties of human body silhouette and human-to-ground relationship, significantly contribute to the fall detection process. So, we propose an approach to efficiently model the spatio-temporal features using fall motion vector. First, we construct a Gaussian mixture model (GMM) called fall motion mixture model (FMMM) using histogram of optical flow and motion boundary histogram features to implicitly capture motion attributes in both the fall and non-fall videos. The FMMM contains both fall and non-fall attributes resulting in a high-dimensional representation. In order to extract only the relevant attributes for a particular fall or non-fall videos, we perform factor analysis on FMMM to get a low dimensional representation known as fall motion vector. Using fall motion vector, we are able to efficiently identify fall events in varieties of scenarios, such as the narrow angle camera (Le2i dataset), wide angle camera (URFall dataset), and multiple cameras (Montreal dataset). In all these scenarios, we show that the proposed fall motion vector achieves better performance than the existing methods. © 2001-2012 IEEE.

IEEE Sensors Journal

Human Fall Detection in Surveillance Videos Using Fall Motion Vector Modeling

Generating succinct summaries (also known as sketches) of massive data streams is becoming increasingly important. Such a task typically requires fast, accurate, and small space algorithms in order to support the downstream applications, mainly in areas such as data analysis, machine learning and data mining. A fundamental and well-studied problem in this context is that of estimating the frequencies of the items appearing in a data stream. The Count-Min-Sketch Cormode and Muthukrishnan [2005] and Count-Sketch Charikar et al. [2004] are two known classical algorithms for this purpose. However, a limitation of these techniques is that the variance of their estimate tends to be large. In this work, we address this problem and suggest a technique that reduces the variance in their respective estimates, at the cost of little computational overhead. Our technique relies on the classical Control-Variate trick Lavenberg and Welch [1981] used for reducing variance in Monte-Carlo simulation. We present a theoretical analysis of our proposal by carefully choosing the control variates and complement them with experiments on synthetic as well as real-world datasets. © 2021 Proceedings of Machine Learning Research. All Rights Reserved.

Proceedings of Machine Learning Research

Variance Reduction in Frequency Estimators via Control Variates Method

Statistical Model Checking (SMC) for the analysis of Multi-Agent Systems has been studied in the recent past. A feature peculiar to Multi-Agent Systems in the context of Statistical Model Checking is that of aggregate queries-temporal logic formula that involve a large number of agents. To answer such queries through Monte Carlo sampling, the statistical approach to model checking simulates the entire agent population and evaluates the query. This makes the simulation overhead significantly higher than the query evaluation overhead. To alleviate this problem, one strategy is to choose only a subset of the agents to simulate, through sampling. Further, this problem becomes particularly challenging when the model checking queries involve multiple attributes of the agents. We propose a population sampling algorithm that simulates only a subset of all the agents and scales to multiple attributes, thus making the solution generic. The population sampling approach results in increased efficiency (a gain in running time of 50% to 100% in most experiments) for a marginal loss in accuracy (between 1% to 5% in most experiments), especially for queries that involve limited time horizons. © 2021 SCS.

Proceedings of the 2021 Annual Modeling and Simulation Conference, ANNSIM 2021

Multi-Attribute Queries for Stochastic Multi Agent Systems over Short Time Horizons

Classification of scenes across multi-sensor remote sensing images with different spatial, spectral, temporal resolutions involves identification of variable length spatial patterns of objects in a scene. So, it necessitates the use of local representations from different regions of a scene in order to comprehend the scene formation. In this paper, we propose a dynamic kernel based representation to handle the patterns of variable lengths in the scenes of remote sensing images. These kernels help to assimilate spatial variability captured using convolutional features in a Gaussian mixture model. The statistics of GMM facilitate the dynamic kernels in preserving the local spatial similarities while handling the changes in spatial content globally within the same scene. The efficacy of the proposed method using two variants of the dynamic kernels is demonstrated on three benchmark scene classification datasets, namely, UCM Land Use (21 classes), Aerial image dataset (30 classes), and NWPU-RESISC45 (45 classes). Our experiments show that the mean interval kernel is better discriminative as it makes use of first and second-order statistics of GMM. © 2021 IEEE.

Proceedings of the International Joint Conference on Neural Networks

Scene Classification in Remote Sensing Images using Dynamic Kernels

To access an unlicensed channel, Wi-Fi follows the Listen Before Talk (LBT) mechanism, whereas LTE-U (and future New Radio in Unlicensed (NR-U) Patriciello et al., 2020; Lagen et al., 2019) adopts the ON–OFF duty-cycled mechanism to fairly share the channel with Wi-Fi. These different mechanisms result in quite different performance for Wi-Fi and LTE-U/NR-U based on their relative deployment and density in the environment. In this work, we present an analytical model for the characterization of achievable throughputs of Wi-Fi and LTE-U networks in spatially distributed scenarios with downlink-prevalent traffic. The proposed model is used to study how LTE-U and Wi-Fi coexist with each other in spatially distributed scenarios. Our extensive simulation results show that it is a reliable model for estimating the throughput of both Wi-Fi and LTE-U in a spatially distributed deployment. The impact of various network parameters such as energy detection and carrier sense threshold on Wi-Fi and LTE-U coexistence is explored as a byproduct and corroborated via a National Instrument experimental test bed. Our model gives very high accuracy in throughput estimation and the mean normalized error is less than 3% for a 80-node scenario in which 50% of nodes belong to each of Wi-Fi and LTE-U network. The analytical model is also used to conduct coexistence studies of LTE-U and Wi-Fi. © 2021

Journal of Network and Computer Applications

Performance analysis of spatially distributed LTE-U/NR-U and Wi-Fi networks: An analytical model for coexistence study

3GPP has introduced C-V2X technology in the Rel. 14 for improving road safety. There are two modes of vehicular communication in C-V2X viz., Mode 3 and Mode 4. Since Mode 4 allows vehicles to communicate with each other even outside the cellular coverage, it is acknowledged as the baseline mode. In Mode 4, vehicles select the best available least interfered radio resource by utilising Semi-Persistent Scheduling (SPS) in a distributed fashion. Medium Access Control (MAC) parameters like pKeep (probability of keeping a radio resource) and Resource Counter (RC) affect the duration of radio resource collision, so these need to be configured carefully for efficient C-V2X communication. This paper explicates the impact of pKeep and RC on the overall performance of C-V2X system. A new algorithm called Traffic-Aware SPS (TA-SPS) is then proposed, which optimally configures these parameters according to the current density of road traffic by estimating it from periodic Cooperative Awareness Messages (CAMs) broadcasted by the vehicles. By reducing the number of resource collisions, TA-SPS increases transmission reliability of the C-V2X system. Through extensive simulation studies, we show how TA-SPS outperforms the traditional SPS in mixed road traffic scenarios. © 2021 IEEE.

IEEE Vehicular Technology Conference

Traffic-Aware Sensing-Based Semi-Persistent Scheduling for High Efficacy of C-V2X Networks

This paper studies gerrymandering on graphs from a computational viewpoint (introduced by Cohen-Zemach et al. [AAMAS 2018] and continued by Ito et al. [AAMAS 2019]). Our contributions are two-fold: conceptual and computational. We propose a generalization of the model studied by Ito et al., where the input consists of a graph on n vertices representing the set of voters, a set of m candidates C, a weight function wv: C→ Z+ for each voter v∈ V(G) representing the preference of the voter over the candidates, a distinguished candidate p∈ C, and a positive integer k. The objective is to decide if it is possible to partition the vertex set into k districts (i.e., pairwise disjoint connected sets) such that the candidate p wins more districts than any other candidate. There are several natural parameters associated with the problem: the number of districts (k), the number of voters (n), and the number of candidates (m). The problem is known to be NP-complete even if k= 2, m= 2, and G is either a complete bipartite graph (in fact K2,n, i.e., partitions of size 2 and n) or a complete graph. Moreover, recently we and Bentert et al. [WG 2021], independently, showed that the problem is NP-hard for paths. This means that the search for FPT algorithms needs to focus either on the parameter n, or subclasses of forest (as the problem is NP-complete on K2,n, a family of graphs that can be transformed into a forest by deleting one vertex). Circumventing these intractability results we successfully obtain the following algorithmic results. A 2 n(n+ m) O(1) time algorithm on general graphs.FPT algorithm with respect to k (an algorithm with running time 2 O(k)nO(1) ) on paths in both deterministic and randomized settings, even for arbitrary weight functions. Whether the problem is FPT parameterized by k on trees remains an interesting open problem. Our algorithmic results use sophisticated technical tools such as representative set family and Fast Fourier Transform based polynomial multiplication, and their (possibly first) application to problems arising in social choice theory and/or algorithmic game theory is likely of independent interest to the community. © 2021, Springer Nature Switzerland AG.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Gerrymandering on Graphs: Computational Complexity and Parameterized Algorithms

With the advancement in technology and digitalization of society, the number of smartphone users has increased drastically. According to [1], there will be 5.3 billion Internet users by 2023. Due to this, Wi-Fi penetration rate will also increase. For tracking smartphones present inside the vehicles, the uniqueness of Wi-Fi Medium Access Control (MAC) addresses helps a lot. Road traffic monitoring systems can make use of this information for estimating travel time, average speed, and traffic flow in the areas of interest. This article focuses on utilizing Wi-Fi based road-side sniffers to listen to Wi-Fi probe signals broadcasted by the smartphones present inside vehicles for estimating traffic stats of road segments. Hopping Interval (HI) is the rate at which Wi-Fi radio of the sniffer is changed to one of the available channels in ISM band. A channel hopping algorithm is proposed, which adjusts HI of the sniffer according to the current traffic conditions. The proposed algorithm reduces the estimation error and increases the robustness and efficiency of the traffic monitoring system. To validate the algorithm, simulation experiments have been performed in Indian traffic scenarios, and results show that the proposed algorithm is better than static channel assignment on the sniffer with an improvement of 4%. Also, estimated travel time and the ground truth values are found out to be closely related, which assures the suitability of the Wi-Fi based road-side sniffers for traffic monitoring. © 2021 IEEE.

2021 International Conference on COMmunication Systems and NETworkS, COMSNETS 2021

Wi-Fi based Road Traffic Monitoring System with Channel Hopping Functionality

Verifying the integrity of IoT data in cloud-based IoT architectures is crucial for building reliable IoT applications. Traditional data integrity verification methods rely on a Trusted Third Party (TTP) that has issues of risk and operational cost by centralization. Distributed Ledger Technology (DLT) has a high potential to verify IoT data integrity and overcome the problems with TTPs. However, the existing DLTs have low transaction throughput, high computational and storage overhead, and are unsuitable for IoT environments, where a massive scale of data is generated. Recently, Directed Acyclic Graph (DAG) based DLTs have been proposed to address the low transaction throughput of linear DLTs. However, the integration of IoT Gateways (GWs) into the peer to peer (P2P) DLT network is challenging because of their low storage and computational capacity. This paper proposes Lightweight and Scalable DAG based distributed ledger for IoT (LSDI) that can work with resource-constrained IoT GWs to provide fast and scalable IoT data integrity verification. LSDI uses two key techniques: Pruning and Clustering, to reduce 1) storage overhead in IoT GWs by removing sufficiently old transactions, and 2) computational overhead of IoT GWs by partitioning a large P2P network into smaller P2P networks. The evaluation results of the proof of concept implementation showed that the proposed LSDI system achieves high transaction throughput and scalability while efficiently managing storage and computation overhead of the IoT GWs. © 2021 IEEE.