In Vehicle-to-Everything (V2X) networks with multi-hop communication, Road Side Units (RSUs) intend to gather location data from the vehicles to offer various location-based services. Although vehicles use the Global Positioning System (GPS) for navigation, they may refrain from sharing their exact GPS coordinates to the RSUs due to privacy considerations. Thus, to address the localization expectations of the RSUs and the privacy concerns of the vehicles, we introduce a relaxed-privacy model wherein the vehicles share their partial location information in order to avail the location-based services. To implement this notion of relaxed-privacy, we propose a low-latency protocol for spatial-provenance recovery, wherein vehicles use correlated linear Bloom filters to embed their position information. Our proposed spatial-provenance recovery process takes into account the resolution of localization, the underlying ad hoc protocol, and the coverage range of the wireless technology used by the vehicles. Through a rigorous theoretical analysis, we present extensive analysis on the underlying trade-off between relaxed-privacy and the communication-overhead of the protocol. Finally, using a wireless testbed, we show that our proposed method requires a few bits in the packet header to provide security features such as localizing a low-power jammer executing a denial-of-service attack.

In multihop Vehicle-to-Everything (V2X) networks, Road Side Units (RSUs) intend to collect information on vehicles' location in a low-latency manner while respecting their privacy constraints to support real-time location-based services. To facilitate data collection, provenance is known to ensure trust and accountability of data. Although existing joint data- and spatial-provenance techniques preserve the privacy of vehicles up to a certain granularity with respect to the RSU and other vehicles, they are unsuitable when stringent deadlines are imposed on the end-to-end delay on the packets. As a consequence, there is a need for designing spatial-provenance methods for V2X networks that satisfy stringent deadlines on the end-to-end delays while managing the privacy concerns. To fill this research gap, we propose two novel protocols, namely: Bi-Segment Embedding (BSE) and Tri-Segment Embedding (TSE), which provide a skipping mechanism for joint data- and spatial-provenance while trading off privacy features among the vehicles. Through an extensive theoretical framework, we provide an analysis of the proposed schemes in terms of reliability, privacy, and communication overhead. When compared to the baselines, our protocols offer lower end-to-end delay, higher reliability in provenance reconstruction, and the same level of privacy with respect to the RSU. We validate latency gains using practical radio parameters, and our study reveals that our proposed protocols offer significant benefits in latency when implemented over a 5G stack.

In this paper, we introduce cameras view-frame placement problem (denoted by CFP) in the presence of an adversary whose objective is to minimize the maximum coverage by$p$cameras in response to input provided by$n$autonomous agents in a remote location. We allow uncertainty in the success of attacks, incomplete information of the probability distribution associated with the uncertain data, and varying levels of risk-appetite of the adversary. We present an exact cutting planes based algorithm to solve this problem and provide conditions under which it is finitely convergent. Since this approach solves deterministic CFP in each iteration, we also present improved exact method for CFP with$p=1$, approximation algorithm and heuristics for Multi-CFP with$p\geq 2$, and Multi-CFP with fixed tilt of the cameras. To evaluate the effectiveness and performance of the proposed approaches, we conduct computational experiments using randomly generated instances and simulation experiments where these approaches are utilized to find a hidden object in a remote location.Note to Practitioners—Telerobotic cameras have been widely used for a variety of applications in environment where it is tedious for humans to collect information such as surveillance, natural environment observation, search and rescue, satellite imaging, and many more. Therefore, computationally efficient approaches proposed in this paper for placement of view-frame of camera(s), by adjusting their pan, tilt, and zoom, will improve the effective utilization of a telerobotic cameras system. Additionally, before operating such systems in a military environment, a decision maker needs to analyze vulnerable cameras in the system whose disruption can significantly impact the information acquisition process. The algorithms presented for adversarial camera view-frame placement problem can identify the set of cameras (or vehicles carrying them) that are susceptible to attacks by a reasonable (risk-averse) attacker. Likewise, the proposed algebraic modeling framework and solution approaches are also applicable for planning interdiction actions to minimize the information acquisition by an evader/enemy. These results can be leveraged by autonomy solutions developed by the Army for both logistics (Autonomous Ground Resupply program) and combat missions (Combat Vehicle Robotics program).

In Vehicle-to-Everything networks that involve multi-hop communication, the Road Side Units (RSUs) typically aim to collect location information from the participating vehicles to provide security and network diagnostics features. While the vehicles commonly use the Global Positioning System (GPS) for navigation, they may refrain from sharing their precise GPS coordinates with the RSUs due to privacy concerns. Therefore, to jointly address the high localization requirements by the RSUs as well as the vehicles' privacy, we present a novel spatial-provenance framework wherein each vehicle uses Bloom filters to embed their partial location information when forwarding the packets. In this framework, the RSUs and the vehicles agree upon fragmenting the coverage area into several smaller regions so that the vehicles can embed the identity of their regions through Bloom filters. Given the probabilistic nature of Bloom filters, we derive an analytical expression on the error-rates in provenance recovery and then pose an optimization problem to choose the underlying parameters. With the help of extensive simulation results, we show that our method offers near-optimal Bloom filter parameters in learning spatial provenance. Some interesting trade-offs between the communication-overhead, spatial privacy of the vehicles and the error rates in provenance recovery are also discussed.

Abstract We introduce generalizations of stochastic network interdiction problem with distributional ambiguity. Specifically, we consider a distributionally risk‐averse (or robust) network interdiction problem (DRA‐NIP) and a distributionally risk‐receptive network interdiction problem (DRR‐NIP) where a leader maximizes a follower's minimal expected objective value for either the worst‐case or the best‐case, respectively, probability distribution belonging to ambiguity set (a set of distributions). The DRA‐NIP arises in applications where a risk‐averse leader interdicts a follower to cause delays in their supply convoy. In contrast, the DRR‐NIP provides network vulnerability analysis where a network‐user seeks to identify vulnerabilities in the network against potential disruptions by an adversary (or leader) who is receptive to risk for improving the expected objective values. We present finitely convergent algorithms for solving DRA‐NIP and DRR‐NIP with a general ambiguity set. To evaluate their performance, we provide results of our extensive computational experiments performed on instances known for (risk‐neutral) stochastic NIP.

For an E-commerce search engine, users finding the right product critically depend on spell correction. A misspelled query can fetch totally unrelated results which in turn leads to a bad customer experience. Around 32% of queries have spelling mistakes on our e-commerce search engine. The spell problem becomes more challenging when most spell errors arise from customers with little or no exposure to the English language besides the usual source of accidental mistyping on keyboard. These spell errors are heavily influenced by the colloquial and spoken accents of the customers. This limits the benefit from using generic spell correction systems which are learnt from cleaner English sources like Brown Corpus and Wikipedia with a very low focus on phonetic/vernacular spell errors. In this work, we present a novel approach towards spell correction that effectively solves a very diverse set of spell errors and outperforms several state-of-the-art systems in the domain of E-commerce search. Our strategy combines Learning-to-Rank on a small strongly labelled data with multiple learners trained with weakly labelled data. We report the effectiveness of our solution WellSpell (Weak and strong Labels for Learning to Spell) with both the offline evaluations and online A/B experiment.

Systematically discovering semantic relationships in text is an important and extensively studied area in Natural Language Processing, with various tasks such as entailment, semantic similarity, etc. Decomposability of sentence-level scores via subsequence alignments has been proposed as a way to make models more interpretable. We study the problem of aligning components of sentences leading to an interpretable model for semantic textual similarity. In this paper, we introduce a novel pointer network based model with a sentinel gating function to align constituent chunks, which are represented using BERT. We improve this base model with a loss function to equally penalize misalignments in both sentences, ensuring the alignments are bidirectional. Finally, to guide the network with structured external knowledge, we introduce first-order logic constraints based on ConceptNet and syntactic knowledge. The model achieves an F1 score of 97.73 and 96.32 on the benchmark SemEval datasets for the chunk alignment task, showing large improvements over the existing solutions. Source code is available at https://github.com/manishb89/interpretable_sentence_similarity

E-commerce customers express their purchase intents in several ways, some of which may use a different vocabulary than that of the product catalog. For example, the intent for "women maternity gown" is often expressed with the query, "ladies pregnancy dress". Search engines typically suffer from poor performance on such queries because of low overlap between query terms and specifications of the desired products. Past work has referred to these queries as vocabulary gap queries. In our experiments, we show that our technique significantly outperforms strong baselines and also show its real-world effectiveness with an online A/B experiment.

We study the planar maximum coverage location problem (MCLP) with rectilinear distance and rectangular demand zones in the case where “partial coverage” is allowed in its true sense, i.e., when covering part of a demand zone is allowed and the coverage accrued as a result of this is proportional to the demand of the covered part only. We pose the problem in a slightly more general form by allowing service zones to be rectangular instead of squares, thereby addressing applications in camera view-frame selection as well. More specifically, our problem, referred to as PMCLP-PCR (planar MCLP with partial coverage and rectangular demand and service zones), is to position a given number of rectangular service zones (SZs) on the two-dimensional plane to (partially) cover a set of existing (possibly overlapping) rectangular demand zones (DZs) such that the total covered demand is maximized. Previous studies on (planar) MCLP have assumed binary coverage, even when nonpoint objects such as lines or polygons have been used to represent demand. Under the binary coverage assumption, the problem can be readily formulated and solved as a binary linear program; whereas, partial coverage, although much more realistic, cannot be efficiently handled by binary linear programming, making PMCLP-PCR much more challenging to solve. In this paper, we first prove that PMCLP-PCR is NP-hard if the number of SZs is part of the input. We then present an improved algorithm for the single-SZ PMCLP-PCR, which is at least two times faster than the existing exact plateau vertex traversal algorithm. Next, we study multi-SZ PMCLP-PCR for the first time and prove theoretical properties that significantly reduce the search space for solving this problem, and we present a customized branch-and-bound exact algorithm to solve it. Our computational experiments show that this algorithm can solve relatively large instances of multi-SZ PMCLP-PCR in a short time. We also propose a fast polynomial time heuristic algorithm. Having optimal solutions from our exact algorithm, we benchmark the quality of solutions obtained from our heuristic algorithm. Our results show that for all the random instances solved to optimality by our exact algorithm, our heuristic algorithm finds a solution in a fraction of a second, where its objective value is at least 91% of the optimal objective in 90% of the instances (and at least 69% of the optimal objective in all the instances).

Computing the degree of redundancy for structured linear systems is proven to be NP-hard. A linear system whose model matrix is of size n×p is considered structured if some p row vectors in the model matrix are linearly dependent. Bound-and-decompose and 0-1 mixed integer programming (MIP) are two approaches to compute the degree of redundancy, which were previously proposed and compared in the literature. In this paper, first we present an enhanced version of the bound-and-decompose algorithm, which is substantially (up to 30 times) faster than the original version. We then present a novel hybrid algorithm to measure redundancy in structured linear systems. This algorithm uses a 0-1 mixed integer feasibility checking algorithm embedded within a bound-and-decompose framework. Our computational study indicates that this new hybrid approach significantly outperforms the existing algorithms as well as our enhanced version of bound-and-decompose in several instances. We also perform a computational study that shows matrix density has a significant effect on the runtime of the algorithms.

We present here an idea of compression of user fed data from a touch screen input interface for storage and transmission over relatively lower bandwidth. The input is taken in the form of hand-written text, graphics, symbols or patterns and recorded as strokes in order of their temporal occurrence. The patterns are segmented into primitive forms each of which is then modeled with third order B-Spline Curves. The number of control points driving the Spline Curve is determined beforehand by recognizing the dominant points in the pattern. The significant reduction of redundancy in data can be exploited in wide application base including low-cost handheld device communication. This algorithm hence proposes a language independent tool for recording the handwriting of user in its original essence. Results obtained from preliminary testing on MATLAB and Android platform show significant improvement in compression ratio over the traditional storage and compression schemes.