ISI Digital Commons (Indian Statistical Institute )
Not a member yet
7571 research outputs found
Sort by
Improved Streaming Algorithm for the Klee’s Measure Problem and Generalizations
No full textEstimating the size of the union of a stream of sets S1, S2, . . ., SM where each set is a subset of a known universe Ω is a fundamental problem in data streaming. This problem naturally generalizes the well-studied F0 estimation problem in the streaming literature, where each set contains a single element from the universe. We consider the general case when the sets Si can be succinctly represented and allow efficient membership, cardinality, and sampling queries (called a Delphic family of sets). A notable example in this framework is the Klee’s Measure Problem (KMP), where every set Si is an axis-parallel rectangle in d-dimensional spaces (Ω “r∆sd where r∆s:“t1, . . ., ∆u and ∆ P N). Recently, Meel, Chakraborty, and Vinodchandran (PODS-21, PODS-22) designed a streaming algorithm for pϵ, δq-estimation of the size of the union of set streams over Delphic family with space and update time complexity O ´ logε32|Ω| ¨ log 1δ¯ and Or ´ logε42|Ω| ¨ log 1δ¯, respectively. This work presents a new, sampling-based algorithm for estimating the size of the union of Delphic sets that has space and update time complexity Or ´ logε22|Ω| ¨ log 1δ¯ . This improves the space complexity bound by a log |Ω| factor and update time complexity bound by a log2 |Ω| factor. A critical question is whether quadratic dependence of log |Ω| on space and update time complexities is necessary. Specifically, can we design a streaming algorithm for estimating the size of the union of sets over Delphic family with space and complexity linear in log |Ω| and update time polyplog |Ω|q? While this appears technically challenging, we show that establishing a lower bound of ωplog |Ω|q with polyplog |Ω|q update time is beyond the reach of current techniques. Specifically, we show that under certain hard-to-prove computational complexity hypothesis, there is a streaming algorithm for the problem with optimal space complexity Oplog |Ω|q and update time polyplogp|Ω|qq. Thus, establishing a space lower bound of ωplog |Ω|q will lead to break-through complexity class separation results
Kummer and Hessian Meet in the Field of Characteristic 2
No full textOne can compute scalar multiplication on an ordinary short Weierstrass curve defined over a binary field. Also, one can move to the associated binary Kummer line BKL(1:c), or isomorphic generalized Hessian curve H(γ,δ) from short Weierstrass, and then compute the scalar multiplication. A generalized Hessian curve provides the best performance of scalar multiplication in RT coordinates where R=R3+S3 and T=T3 for a point P=(R:S:T) on H(γ,δ). Montgomery scalar multiplication gives us the nP and (n+1)P, again in RT. We propose a method to uniquely obtain the R and S coordinates of nP given P=(R:S:T) and RT coordinates of nP and (n+1)P. Next, we show that BKL(1:c) can be linked to an isomorphic H(γ,δ). But small c does not guarantee small γ or δ. First, we introduce two isogenies and their duals: one 2-isogeny between two short Weierstrass curves and one 3-isogeny between two generalized Hessian curves to solve the issue. Using the introduced isogenies, we show that there always exists a generalized Hessian curve H(γ,1) with γ3(γ+1)=c associated with a BKL(1:c). The obtained H(γ,1) needs 5[M]+4[S]+1[Cs] field operations for each ladder step of Montgomery scalar multiplication, and the operation count is the smallest one compared to any other curves over a binary field
Modeling GPP with Machine Learning using Multisource Features based on Fluxnet Data
No full textOne of the most crucial markers for forecasting the future trend of climate change and for adopting sustainable development plans is the understanding of the carbon that plants absorbs from the atmosphere. Terrestrial Gross Primary Productivity (GPP), a measure of carbon uptake, is the total amount of carbon that is assimilated by photosynthesis in a terrestrial ecosystem. Eddy covariance measurements taken from Flux-towers are regarded as accurate GPP estimates. However, building a tower is expensive and difficult to maintain, thus we only have a small number of towers for flux measurements. Because satellite data have a greater resolution and continuous coverage, we can use them create models to estimate GPP at larger geographical and temporal scales. Consequently, a method based on machine learning (ML) technique that directly affects the GPP by leveraging external elements such as remotely sensed data, geographic data, and meteorological data. We propose a random forest model that had an R2 value of 0.82 for estimating GPP based on 10-fold cross-validation, in the Australian region, and the findings are contrasted with those obtained using current state-of-the-art techniques like SVM and XGBoost. Performance of future prediction has been demonstrated by predicting the GPP for year 2014 for which the R2 value attained 0.84 with respect to the ground truth, whereas the MODIS GPP was only 0.52. Therefore, these characteristics can be used to model the GPP and can forecast values across a range of time scales and with varied levels of spatial detail
Panoptic Segmentation of CT Images of Non-Small Cell Lung Cancer Data
No full textThis paper proposes panoptic segmentation to identify regions of interest (RoIs) in medical images where intensity profiles of RoIs have significant overlap and inconsistent across different instances of same type of RoI. Inspired by the proposal of unified architecture and unified segmentation model for multi-task segmentation, namely semantic, instance and panoptic segmentation, we propose a custom panoptic segmentation scheme for the non-small cell lung cancer (NSCLC) dataset. A typical challenge of such dataset is to differentiate image segments representing primary and secondary focus of tumours having non-homogeneous and overlapping intensity profile. In the proposed architecture, outputs of image feature extractor for each 2D CT slice images and the corresponding text based description of the ground truth RoIs (e.g. photo of left lung) are mapped to a transformer-based decoder to generate segmented output. During inference, image along with a task query (e.g. panoptic or instance segmentation) generates test segmentation map. Based on a conservative performance metric introduced in this paper, we have shown that segmentation by the proposed model is better than its close competitors
Revisiting Convolutional Block Attention Module: Attention Enhancing Entropy For Semantic Segmentation of Images
No full textAn attention mechanism is important to measure the relevance of channels for a multi-channel convolutional neural net. An attention mechanism helps to concentrate on extracting features from input channels in order to produce a classification or segmentation of objects of interest from an image. Squeeze- and-Excitation (SE), Attention Gate (AG) and Convolutional Block Attention Module (CBAM) are introduced to enhance the important features of channels. CBAM uses channel attention and spatial attention within the channels. The channel attention of CBAM works out to prioritise essential channels using the global average and global maximum values of each channel processed by a shared multi-layer perceptron (MLP). The channel attention scales the important channels and forwards those channels to the spatial attention module. The spatial attention identifies the regions of interest (ROIs) for better feature processing. Drawing inspiration from CBAM, the channel attention mechanism is modified to use the entropy value of each channel to scale the global average value of the channel. In this proposal, U-Net and its skip connections are used as a baseline architecture. In the proposal, the skip connections are modified to apply attention mechanisms. The experiments show that the product of entropy and the global average of each channel is successful in better segmenting ROIs in an image that provides at least 1% improvement in terms of Dice Similarity Coefficient (DSC) for semantic segmentation
Roadside Traffic Monitoring Using Video Processing on the Edge
No full textRoadside traffic monitoring is increasingly performed by deploying roadside high-resolution video cameras and then running computer vision (CV) models on the video data. Since computer vision models are compute-intensive as they utilize deep neural networks (DNNs), the data is usually sent to one or more edge servers located adjacent to mobile base stations, thereby keeping the in-situ (on camera) processing load as less as possible. Recent techniques propose running CV models on tiles of videos separately to detect and track small objects. Several CV models exist, each with different requirements of compute and memory. Since more compute and memory-intensive CV models provide higher accuracy, a key challenge of such techniques is to determine which vision model should be used on which tile. This becomes even more challenging if multiple videos are processed by the same edge server. In this paper, we first formulate this problem of model selection and tile allocation as an Integer Linear Programming (ILP) instance, and then propose an approximation algorithm based on linear relaxation followed by randomized rounding to solve it. We present experimental results of our methods on an open source dataset based on trace-driven simulation to show that it gives result fast enough while also reducing execution time in a variety of scenarios
Sublinear Message Bounds of Authenticated Implicit Byzantine Agreement
No full textThis paper studies the message complexity of authenticated Byzantine agreement (BA) in synchronous, fully-connected distributed networks under an honest majority. We focus on the so-called implicit Byzantine agreement problem where each node starts with an input value and at the end a non-empty subset of the honest nodes should agree on a common input value by satisfying the BA properties (i.e., there can be undecided nodes)1. We show that a sublinear (in, number of nodes) message complexity BA protocol under honest majority is possible in the standard PKI model when the nodes have access to an unbiased global coin and hash function. In particular, we present a randomized Byzantine agreement algorithm which, with high probability achieves implicit agreement, uses (v) messages, and runs in (1) rounds while tolerating (1/2 -) Byzantine nodes for any fixed \u3e 0, the notation hides a(polylog) factor2. The algorithm requires standard cryptographic setup PKI and hash function with a static Byzantine adversary. The algorithm works in the CONGEST model and each node does not need to know the identity of its neighbors, i.e., works in the0 model. The message complexity (and also the time complexity) of our algorithm is optimal up to a polylog factor, as we show a O(v) lower bound on the message complexity. We further extend the result to Byzantine subset agreement, where a non-empty subset of nodes should agree on a common value. We analyze several relevant results which follow from the construction of the main result. To the best of our knowledge, this is the first sublinear message complexity result of Byzantine agreement. A quadratic message lower bound is known for any deterministic BA protocol (due to Dolev-Reischuk [JACM 1985]). The existing randomized BA protocols have at least quadratic message complexity in the honest majority setting. Our result shows the power of a global coin in achieving significant improvement over the existing results. It can be viewed as a step towards understanding the message complexity of randomized Byzantine agreement in distributed networks with PK
Proteasome, the Recycle Bin of the Cancer Cell
No full textProteolysis is an integral cellular function which not only allows correction of protein synthesis mistakes, such as misfolded protein, but also recycles unnecessary proteins, therefore maintaining an amino acid reservoir for protein synthesis. The bulk of protein break down falls to a large multi-subunit complex, the 26S proteasome, dubbed the ‘recycling bin of the cell’. Considering the extent of proteasomal involvement in most cellular processes, it is unsurprising that the proteasome is also implicated in pathogenesis such as cancer. This chapter provides an overview of the history of the proteasome discovery, proteasome structure and regulation; as well as an initial insight into the role it plays in different cancer types
Small Ball Probabilities for the Stochastic Heat Equation
No full textWe provide a gentle introduction to the area of small ball probabilities and state some recent results for the stochastic heat equation (SHE). We also briefly discuss the proof in the case when the noise term in SHE is independent of the solution
Tariff that Exports Unemployment: Home Market Effect Meets Shapiro and Stiglitz
No full textThis note points towards an important omission in the literature of trade with increasing returns to scale, and equilibrium unemployment as in shirking type models. The general consensus appears to be that free trade via proliferation of varieties is likely to increase real wage and thus relaxing the no-shirking constraint should increase employment. Upon recognising the presence of transport cost, this note shows otherwise