Abstract

The exponential performance growth guaranteed by Moore’s law has started to taper in recent years. At the same time, emerging applications like image processing demand heavy computational performance. These factors inevitably lead to the emergence of domain-specific accelerators (DSA) to fill the performance void left by conventional architectures. FPGAs are rapidly evolving towards becoming an alternative to custom ASICs for designing DSAs because of their low power consumption and a higher degree of parallelism. DSA design on FPGAs requires careful calibration of the FPGA compute and memory resources towards achieving optimal throughput. Hardware Descriptive Languages (HDL) like Verilog have been traditionally used to design FPGA hardware. HDLs are not geared towards any domain, and the user has to put in much effort to describe the hardware at the register transfer level. Domain Specific Languages (DSLs) and compilers have been recently used to weave together handwritten HDLs templates targeting a specific domain. Recent efforts have designed DSAs with image-processing DSLs targeting FPGAs. Image computations in the DSL are lowered to pre-existing templates or lower-level languages like HLS-C. This approach requires expensive FPGA re-flashing for every new workload. In contrast to this fixed-function hardware approach, overlays are gaining traction. Overlays are DSAs resembling a processor, which is synthesized and flashed on the FPGA once but is flexible enough to process a broad class of computations through soft reconfiguration. Image processing algorithms vary in size and shape, ranging from simple blurring operations to complex pyramid systems. The primary challenge in designing an image-processing overlay is maintaining flexibility in mapping different algorithms. This thesis proposes a domain-specific language (DSL)-based compiler, Flowpix, for image processing. Flowpix is capable of natively processing benchmarks and targeting FPGA implementation of these benchmarks using overlay configurations. This thesis discusses how an application can be expressed using the Flowpix language, and how the compiler processes the application to generate control words that enables the configuration of the hardware architecture. We also compare our results with the existing state-of-the-art frameworks: Polymage, Halide, Xilinx, Darkroom, and Rigel.

Abstract

Biometric authentication plays an increasingly prominent role in today’s products and services for verifying an individual’s identity. It is not only efficient but also practical, as it establishes a unique link to an individual through their physical and behavioral characteristics [43]. Unlike conventional authentication mechanisms like passwords or documents, biometric traits are inherent to each individual, eliminating the need to memorize additional information [64]. However, the security and privacy of biometric templates used in authentication remain primary concerns, as biometric data is strongly and irrevocably tied to an individual, as emphasized in the article [42]. In the context of remote authentication, Secure Multiparty Computation (SMC) offers a powerful solution. SMC enables two parties to interactively compute a function using their private inputs without disclosing any information except for the output itself [19]. This approach ensures that biometric template comparison is carried out in a privacy-preserving manner, enhancing both security and privacy in authentication services. In this thesis, we introduce a unique approach to iris, fingerprint, and face verification by incorporating ”noise” into the authentication process. In our work,“noise” refers to signals obtained from non-discriminatory or unreliable regions of biometric characteristics. Our extensive empirical evaluation reveals a correlation among noise features, and we leverage this correlation in a novel Secure Two-Party Computation (STPC) design. This STPC design operates on quantified uncertainty between noise features, providing informationtheoretic security. Our approach has low accuracy degradations, practical computational complexity, wide applicability making it suitable for practical real-time applications.

Abstract

Location-Based Services (LBSs) have become increasingly prevalent in today’s mobile technology sector, delivering tailored information relevant to the users’ precise locations. These services grant users access to location-centric information like the proximity of hospitals, restaurants, or other points of interest, thereby facilitating routine tasks. However, such LBSs can pose significant concerns about user privacy. Consider a user querying, “What are the directions to the best cancer hospital from the current location?”. Such queries expose the user’s current location information to the LBS provider and other intermediate nodes (intruders) in the mobile network. Query location information can reveal sensitive information about the user, such as relationships, health, religion, and nightlife habits. In this thesis, we propose two improved approaches to preserve the privacy of users’ query location in the mobile environment. As the first approach, we propose an improved dummy generation approach for better privacy. In a dummy generation approach, the user sends additional dummy locations along with the user’s actual location in its query, thereby confusing the LBS provider and the other nodes. The existing approaches have the issue of generating dummies in regions with more infeasible regions (inaccessible regions). Moreover, the existing approaches do not consider the presence of time-dependent infeasible regions. For example, consider a supermarket with opening and closing times as 9am and 9pm, respectively. From 9am to 9pm, this supermarket can be considered a feasible region; otherwise, this area can be regarded as an infeasible region. Furthermore, if the intruder estimated the centre of cloaking region (CR) using the dummy locations, it would become more accessible for the intruder to know a given user’s actual location. To improve the performance, we propose an Annulus-based Gaussian Dummy Generation (AGDG) approach. AGDG introduces the concept of a virtual cloaking region to generate cloaking regions. In AGDG, unlike traditional methods, the user’s location is not fixed at a fixed distance from the centre of the cloaking region. Additionally, AGDG considers the infeasible regions and query probability in the surrounding environment when generating dummy locations. The approach also incorporates the concept of time-dependent infeasible regions and ensures that the generated dummy locations abide by these time-dependent constraints. As the second approach, we propose a cloaking-based approach to improve the privacy of spatial range queries. In distributed spatial cloaking-based approaches, the user’s query location information is cloaked using the distributed mobile network around the user (e.g., the p2p network). Existing approaches do not preserve the user’s intent privacy. For example, suppose a user queries all the cancer hospitals near her. In that case, her location and health information (searching for intent, which is about cancer hospitals) must be preserved from both LBS providers and peers in the surrounding. Moreover, the existing approaches require a large number of peers to be employed to cloak the user query location. Maintaining such structures in a highly dynamic mobile network is challenging. We propose the notion of ijkCloak framework to improve existing distributed spatial cloaking-based approaches. The ijkCloak framework introduces the notion of ijk-anonymity to protect both the user’s query location and intent information. This method divides the user’s query location information into multiple fragmented locations. This process helps keep the user’s query location private from their peers and the LBS provider. Additionally, dummy intents are sent to the LBS provider along with the user’s actual query to protect the user’s query intent. The proposed approach ijkCloak, adopts ijk-anonymity in a mobile network environment. Because of the efficiency of ijk-anonymity, this proposed method requires fewer peers to maintain user privacy, making it more practical in a highly dynamic mobile network environment. For each approach, the theoretical analyses and comprehensive experimental study exhibits its potential to preserve location privacy in different scenarios. We hope this research encourages further research and leads to the development of improved privacy preserving approaches in mobile networks.

Abstract

Player detection is a fundamental building block for numerous applications in sports analytics, encompassing player recognition, player tracking, and activity detection. However, the majority of existing research in this domain relies on fixed-camera top-view videos of the field, which inherently simplifies the player detection task. Regrettably, such videos are not readily accessible to the general public, rendering them an unreliable data source for comprehensive player analysis. In contrast, broadcast videos of matches offer a readily available resource. Performing player detection on these videos proves considerably more challenging due to the presence of diverse sources of noise. This study investigates player detection in the context of continuous long-shot broadcast videos, acknowledging the complexities associated with this particular setting. In the initial phase of our research, we thoroughly examine the distinctions between player detection and person detection while also investigating the multitude of challenges inherent to player detection. We begin by formulating player detection as a domain adaptation problem and analysing the various challenges associated with this approach. Our analysis encompasses an in-depth examination of the overarching challenges encountered in player detection, along with a comprehensive exploration of the unique obstacles posed specifically by broadcast videos and domain adaptation settings. During the subsequent phase of our research, we worked on the development of an extensively annotated player detection dataset, curated from soccer broadcast videos of the FIFA 2018 World Cup matches. This dataset serves as a robust foundation for evaluating the efficacy of player detection algorithms within the context of broadcast videos. We devise a comprehensive pipeline for generating automatic labels for our dataset, which are then corrected further down the pipeline to facilitate the annotation process. The resultant dataset comprises over 200,000 high-resolution frame images, encompassing more than 2,000,000 annotated bounding boxes extracted from three distinct FIFA 2018 World Cup matches. Notably, our dataset encompasses a diverse set of player positions, orientations, and bounding box sizes, effectively capturing the inherent variability encountered in soccer broadcasts. Additionally, the dataset incorporates numerous instances of challenging noisy data points, elevating its complexity beyond previous datasets in the field. In the third phase of our research, we present a novel transductive approach to address the player detection challenge, treating it as a domain adaptation problem. We demonstrate the significance of instance-level domain labels in achieving effective adaptation, specifically for soccer broadcast videos. To efficiently annotate these domain labels on the bounding box predictions generated by our inductive model, we propose a sophisticated multi-model greedy labelling scheme that leverages visual features. The annotated domain labels are then utilized to train a transductive counterpart of the model, utilizing reliable instances derived from the inductive model inferences. This approach proves to be highly advantageous, enabling remarkable performance enhancements for a given match with a minimal number of labelled samples. Our experimental results highlight an average increase of 16 points in mean Average Precision (mAP) for soccer broadcast videos, accomplished by annotating domain labels for approximately 100 samples per video. In the culminating phase of our research, we demonstrate the practical utilization of robust player detection algorithms in constructing analytical systems to enhance game analysis. Specifically, we develop field heat maps that effectively depict the spatial distribution of players on the field over time. Leveraging bounding box detections derived from our proposed approach, we employ homographic projections to achieve accurate top-view registration of the detected bounding boxes in each frame. These generated heat maps serve as a valuable resource for deriving insightful inferences that directly correlate with significant events transpiring during the match. Furthermore, we present additional potential applications for leveraging reliable detection systems, while also outlining avenues for future enhancements and refinements to our system.

Abstract

In the present era of Big Data, the demand for storing vast amounts of data is rapidly increasing among companies such as Facebook, Microsoft, Google, Intel, IBM, and others, for various applications. To address this need, Distributed Storage Systems (DSSs) have been established, offering improved capabilities in terms of flexibility, scalability, speed, and cost. In DSS, data is distributed and stored on different nodes and are connected through the network. However, data loss is inevitable due to physical limitations such as hardware failures and power shutdowns. Maximum Distance Separable (MDS) codes are very efficient in terms of storage overhead. For practicality, Locally Recoverable codes (LRCs) are discovered to facilitate the low reconstruction cost for single and multiple failures (Independent and correlated), with a slight increase in storage overhead. Maximally recoverable codes are a class of codes that recover from all potentially recoverable erasure patterns given the locality constraints of the code. Our main objectives are to provide MRCs for independent failures, correlated failures with low computational complexity, and encoding complexity. In earlier works, codes have been studied in the context of codes with the locality to handle independent failures. The notion of locality has been extended to the hierarchical locality, which allows for the locality to gradually increase in levels with the increase in the number of erasures. In one direction, we consider MRC for the case of codes with 2-level hierarchical locality for the specific topology (locality constraints) called Hierarchical Local MRC (HLMRC). We derive a field size lower bound on HL-MRC. We also give constructions of HLMRC for some parameters whose field size is smaller than that of earlier known constructions. We investigate Locally Recoverable Codes (LRCs) with availability, which refers to the ability to have multiple repair sets. The presence of multiple repair sets in LRCs is beneficial as it facilitates the distribution of the repair load among various nodes. This distribution helps prevent excessive strain on specific nodes and promotes a more balanced workload within the system. In our research, we expand on the concept of availability in Locally Recoverable Codes (LRCs) and apply it to codes with hierarchical locality. The minimum distance plays a vital role in determining the codes’ capability to handle erasures effectively. Our study focuses on investigating the upper bound of the minimum distance for the specific case of LRCs with hierarchical locality. To reduce the encoding complexity, Halbawi et al. introduced sparse and balanced generator matrices for MDS (Reed - Solomon) code and LRCs (Tamo-Barg code) for single erasure. Building upon this work, we contribute by presenting sparse generator matrices for MRC with locality for single erasure. Furthermore, we also provide sparse and balanced generator matrices for MRC with locality, specifically for single erasures where the locality value is set to 2. In order to deal with correlated failures, Gopalan et al. initiated the study of MRCs gridlike and product topologies. In another research direction, we focus on MR codes for product topology Tm,n(a, b). Product codes are a class of codes with generator matrices as the tensor product of the generator matrices of component codes. The codeword can be represented as an m × n array, where the component codes are referred to as the row and column codes. We derive a few properties of maximally recoverable product codes. We give a sufficient condition to characterize a certain subclass of erasure patterns as correctable and another necessary condition to characterize another subclass of erasure patterns as not correctable. We construct a certain bipartite graph based on the erasure pattern satisfying the regularity condition (a necessary condition for recoverability) for product topology and show that there exists a complete matching in this graph. We used this condition to identify a subset of recoverable erasure patterns for a = 2. In earlier work, higher-order MDS codes denoted by MDS(l) have been defined in terms of generic matrices, and these codes have been shown to be constituent row codes for maximally recoverable product codes for the case of a = 1. We derive a certain inclusion-exclusion type principle for characterizing the dimension of intersection spaces of generic matrices. Applying this, we formally derive a relation between MDS(3) codes and points/lines of the associated projective space

Abstract

Representing knowledge in a diagrammatic form has been a long-standing goal of humanity. Early efforts in the field of knowledge representation, such as symbolic logic and semantic net, have led to the development of The Semantic Web, which provided a strong foundation for the development of Knowledge Graphs (KGs). KGs were first introduced in 1986 and were popularized recently in 2012 with the introduction of the Google knowledge graph. Most KGs suffer from the problem of incompleteness, which has led to many efforts in the field of KG completion. In this thesis, we address a specific subproblem from this field called link forecasting. Link forecasting is the problem of predicting future links in a given temporal knowledge graph (TKG) using the existing data. Although several link forecasting frameworks exist in the literature, most previous studies suffer from reduced performance as they cannot efficiently capture the time dynamics of a TKG. We present a novel rule-based link forecasting framework by introducing two new concepts: relaxed temporal random walks and link-star rules. The former concept involves generating rules by performing random walks on a TKG, considering the real-world phenomenon that the order of any two events may be ignored if their occurrence time gap is within a threshold value. The latter concept defines a class of acyclic rules generated based on the natural phenomenon that history repeats after a particular time. Our framework also accounts for the problem of combinatorial rule explosion, making our framework practicable. Experimental results demonstrate that our framework outperforms the state-of-the-art by a substantial margin

Abstract

Hedgehog (HH) signaling pathway is the cellular pathway for patterning and morphogenesis. It is controlled by two membrane proteins, the HH receptor Patched1 (PTCH1), a 12-pass transmembrane (TM) protein, and Smoothened (SMO), a 7-pass transmembrane (TM) signal transducer. SMO transduces the signal from the extracellular (EC) region to the cytoplasmic (CP) region. Binding of HH ligand to PTCH1 receptor allows SMO entry to the primary cilium (PC) and activates the downstream signaling process. The malfunctioning of SMO results in misregulation of the HH signaling pathway, which contributes to birth defects and various cancers. The story has evolved from initial conjectures involving direct communication of PTCH1 with SMO to indirect communication between the two TM proteins. In the process, some of the old theories have been discarded in recent literature. However, the underlying mechanism of how PTCH1 controls SMO is still not very clear, and thus constitutes an important area of research. Based on available evidence, the consensus appears to be limited to the assertion that, driven by HH signaling, PTCH1 regulates the activity of SMO activity through the intermediacy of some small molecules (such as cholesterol). In addition, it appears that the lipid bilayer composition affects SMO orientation and function. In this context, several earlier hypotheses involving the primary role of cholesterol are being disputed. At the same time, several HH pathway inhibitors viz., cyclopamine, taladegib, and vismodegib, which target SMO have been reported. Notwithstanding their potential utility in the treatment of cancer, long-term administration of these drugs was reported to lead to the development of resistance. The broad aim of my research is to build upon the existing molecular-level understanding of the functioning of the HH pathway, with a view to facilitate the formulation of newer approaches towards therapeutic intervention. The focus of my research is to investigate the structure and domain organization of SMO, which is a class F GPCR. This thesis attempts to provide some insights into the functioning of the SMO receptor, using molecular dynamics-based approaches. It is shown that SMO is activated by cholesterol molecules and that its dynamics is influenced by other membrane lipids such as PI4P. The specific objectives include 1. To identify important motifs, especially including, but not limited to, the lipid-binding sites/motifs. 2. To study the conformational dynamics of SMO, to help understand its molecular behavior and also the role of the composition of the primary cilia. 3. To study the regulation mechanisms in SMO by exploring the different cholesterol-bound structures of SMO.

Abstract

Data mining is a collection of algorithms for extracting valuable insights from large amounts of data. Data mining based approaches are being employed to improve the performance of decision support systems in the fields of customer relationship management, inventory management, fraud detection, surveillance, and recommendation systems. Pattern mining is an important task of data mining, which involves identifying significant associations in transactional databases. These associations reveal valuable trends and relationships that aid businesses in improving efficiency. The field of pattern mining has started with the model to extract frequent patterns from large transactional data. The model of frequent patterns has become popular and resulted in the development of algorithms to improve the performance of several applications, like recommendation systems. In the literature, encouraged by the potential of pattern mining, active research is going on to investigate new pattern mining models such as periodic, utility, coverage, and correlated patterns. In this thesis, we propose an improved approach to mine periodic patterns from temporal databases. The model of periodic patterns facilitates the discovery of recurring behaviours and trends in the temporal databases. The model of periodic pattern, which we call partial periodic pattern (3P), captures periodic associations subject to periodic support (P S) and inter-arrival time (IAT) constraints. Here, the IAT value is the time difference between the successive occurrence of a pattern. The percentage of occurrences of a pattern in a database that satisfies the user-given maximum IAT constraint is called P S. Overall, all patterns that satisfy user given maximum IAT (maxIAT) and minimum PS (minP S) are called 3P s. In this thesis, we address the following issue of the 3P s model. It was observed that if we set the minP S value too low, the number of 3Ps explodes. On the other hand, if set minP S value high, several interesting 3Ps will be missed. We call this problem as a rare item problem. To address this issue, in this thesis, we have proposed an improved model and present an improved depth-first search algorithm to extract 3Ps. In the proposed model, we introduce a new measure called periodic-conf idence, which satisfies both null-invariant and anti-monotonic properties. We also propose a better depth-first search algorithm to mine 3Ps. The proposed algorithm uses irregularity pruning to reduce the search space and computational cost while maintaining the same amount of information. Through experimental results, we show that the proposed algorithm is efficient and scalable. We illustrate the usefulness of the discovered patterns through case studies on air pollution and traffic congestion databases. Extracting interesting trends from large temporal databases in different domains is an active research area. We hope that the proposed approach could facilitate the development of improved approaches to extract regular trends for fraud detection from sensor (surveillance) databases and loyalty mining in e-commerce systems.

Abstract

The current research aims to develop a multichannel phonocardiography system to improve the efficiency in detecting low-frequency cardiac auscultation and diagnosis of heart failures. In particular, the research work has been carried out with respect to two aspects. Firstly, a hardware prototype of a MEMS-based multichannel phonocardiography system has been developed, along with the placement of microphones and methods for heart sound localization to enhance signal quality. Secondly, proposed the signal processing algorithm for heart sound segmentation to identify the low-frequency components and neural network-based data analytic technique for feature extraction and implemented the proposed algorithms on SoC-FPGA to differentiate the normal and abnormal heart sound components. Cardiac auscultation is one of the non-invasive methods to diagnose heart abnormalities. Along with four significant heart sounds (S1, S2, S3, and S4), other murmur sounds are generated due to pathological conditions. These anomalies help in proper diagnosis and prevent the possibility of heart failure. MEMS are becoming the most popular due to their size and free ambient noises and are vital in developing noninvasive diagnostic instruments. In addition, The development of cardiac auscultation devices advantages significantly from using MEMS microphones. This research has developed the MEMS-based phonocardiography instrument to capture and analyze the heart sound S3, S4, and murmur components at cardiac auscultation points. The main contribution of this thesis is developing the mathematical model for source localization algorithms to derive microphone positions with a high signal-to-noise ratio (SNR). The proposed cross-correlation method improves the system's sensitivity in detecting low-frequency cardiac sound components (S1, S2, S3, S4 and stenosis, regurgitation murmurs). The segmentation approach combining wavelet and Shannon energy was implemented on Field Programmable Gate Arrays (FPGAs) to categorize the heart sound components. The proposed segmentation algorithm revealed an excellent sensitivity of 99.17 percent and a detection error rate of 1.5 percent. Accurate measurements of the cardiac components were obtained using a combination of traditional statistical approaches and neural network based algorithms from multiple signals received simultaneously from several PCG systems. The proposed multichannel phonocardiography system analysis the cardiac sound components using artificial neural networks (ANN). The Inverse delayed (ID) function model of a neuron is used to compute synaptic weights after being simulated in MATLAB. The proposed ANN model was implemented in a Field Programmable Gate Array (FPGA). An SoC FPGA (ZYNQ SoC) performs most of the required data processing, eliminating the need for robust and expensive computer systems. Using regression analysis, a statistical model was developed to identify abnormal heart sounds from the captured signals. The receiver operating characteristic (ROC) curve has been used to evaluate the performances of the proposed model. The ANN system examined both abnormal and normal samples, and experimental results revealed a good sensitivity of 99.1% and an accuracy of 0.9. The research concluded that signal acquisition from multiple sensors and source localization methods produces a high-quality signal suitable for analyzing low-frequency cardiac sounds (S1, S2, S3, S4, stenosis, regurgitation murmurs). In addition, the proposed ANN classification method, based on the inverse delayed (ID) function model of neuron, can resolve combinatorial optimization problems. The negative resistance of the ID model can destabilize a neural network's stable equilibrium points, reducing the possibility of unknown values in suboptimal synaptic weight solutions obtained using an ANN based on a traditional neuron model. Furthermore, the repeatability and reproducibility measurements are used for the performance analysis.

Abstract

In this thesis, we consider three problems relating to coding theory. The first problem is the application of codes to cryptography, while the other two problems tackle the ongoing developments of coding theory. We consider the secret sharing problem in the context of distributed storage. In this setup, there is a dealer, n storage nodes, m secrets, and m t
users. The dealer wants to share with each user a t-subset of secrets via storage nodes while ensuring weak secrecy condition. The user downloads shares from the storage nodes based on the designed storage structure and reconstructs its secrets. We extend upon a recent framework [1] (considering t = 1) to the case where each user requests a subset of secrets. We identify a necessary condition on the storage structure to ensure weak secrecy. A distributed secret sharing protocol (DSSP) encodes secrets into shares and distributes them onto the storage node. The number of shares created per secret is defined as the storage overhead of the DSSP, which is at least one to ensure the correctness condition. The goal is to design a DSSP with optimal storage overhead. We relate the storage structure of a DSSP to t-disjunct matrices used in group testing. Using a storage structure obtained from disjunct matrices, we design a weakly secure DSSP that achieves optimal storage overhead. Using several constructions for t-disjunct matrices, we compare their performance in terms of the number of storage nodes and communication complexity (total number of shares needed to be downloaded from storage nodes). The rate of a secret is the size of the secret normalized by the size of a share, and the capacity region of the problem is the set of all achievable rate tuples. For a specified storage structure, we characterize the capacity region of the problem. Next, we consider the unique decoding algorithms for Reed-Muller (RM) codes. RM codes were shown to be capacity-achieving on the binary memoryless symmetric channels using bitwise maximuma-posteriori (bit MAP) decoding [2]. We propose an RXA-Syndrome decoding algorithm for RM(m, m− 4) code that exploits the large symmetry in the automorphism group of RM codes and the optimality of the maximum likelihood (ML) decoder. Codes that meet the Singleton bound with equality are called Maximum Distance Separable (MDS) codes. In a sense, MDS codes achieve the optimal trade-off between the size of the code and its minimum distance. However, unique decoding of MDS codes can correct errors only up to a certain limit which is related to the minimum distance of the code. In the third problem, we consider the construction of codes that can correct errors beyond this limit. To this end, list decoding was introduced recently, which returns a list of codewords containing the correct codeword. We derive necessary and sufficient conditions for a code to be (t, L)-list decodable. Recently, list decodable codes that meet generalized Singleton bound were considered as the higher-order generalization of MDS codes. It is important to understand the structural properties of these codes to develop explicit constructions and efficient decoding algorithms. Motivated by these developments, we present new results on the structure of higher order MDS codes. We identify conditions under which (n1, k1)-MDS(ℓ1) codes can be obtained from (n2, k2)-MDS(ℓ2) codes. We also simplify the conditions under which an (n, k)-MDS(k − 1) code is also an MDS(k) code.