Search

In carpooling systems, a set of drivers owning a private car can accept a small detour to pick-up and drop-off other riders. However, carpooling is widely used for long-distance trips, where rider-driver matching can be done days ahead. Making carpooling a viable option for daily commute is more challenging, as trips are shorter and, proportionally, the detours tolerated by drivers are more tight. As a consequence, finding riders and drivers sharing close-enough origins, destinations and departure time is less likely, which limits potential matching. In this paper we propose an Integrated System, where carpooling matching is synchronized with Public Transit (PT) schedules, so as to serve as a feeder service to PT in the first mile. Driver detours are proposed towards PT selected stations, which are used as consolidation points, thus increasing matching probability. We present a computationally efficient method to represent PT schedules and drivers trajectory in a single General Transit Feed Specification database, which allows to compute multimodal rider journeys using any off the shelf planners. We showcase our approach in the metropolitan area of Portland, Oregon, considering 8k randomly generated trips. We show the benefits of our Integrated System. We find that 10% more riders find a feasible matching with respect to the status quo, where carpooling and PT are operated separately. We release our code as open source., 15th ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS 2022)

Lithography simulation is a critical step in VLSI design and optimization for manufacturability. Existing solutions for highly accurate lithography simulation with rigorous models are computationally expensive and slow, even when equipped with various approximation techniques. Recently, machine learning has provided alternative solutions for lithography simulation tasks such as coarse-grained edge placement error regression and complete contour prediction. However, the impact of these learning-based methods has been limited due to restrictive usage scenarios or low simulation accuracy. To tackle these concerns, we introduce an dual-band optics-inspired neural network design that considers the optical physics underlying lithography. To the best of our knowledge, our approach yields the first published via/metal layer contour simulation at 1nm^2/pixel resolution with any tile size. Compared to previous machine learning based solutions, we demonstrate that our framework can be trained much faster and offers a significant improvement on efficiency and image quality with 20X smaller model size. We also achieve 85X simulation speedup over traditional lithography simulator with 1% accuracy loss., 9 pages, 9 figures; accepted at 59th Design Automation Conference

The increasing complexity of JavaScript in modern mobile web pages has become a critical performance bottleneck for low-end mobile phone users, especially in developing regions. In this paper, we propose SlimWeb, a novel approach that automatically derives lightweight versions of mobile web pages on-the-fly by eliminating the use of unnecessary JavaScript. SlimWeb consists of a JavaScript classification service powered by a supervised Machine Learning (ML) model that provides insights into each JavaScript element embedded in a web page. SlimWeb aims to improve the web browsing experience by predicting the class of each element, such that essential elements are preserved and non-essential elements are blocked by the browsers using the service. We motivate the core design of SlimWeb using a user preference survey of 306 users and perform a detailed evaluation of SlimWeb across 500 popular web pages in a developing region on real 3G and 4G cellular networks, along with a user experience study with 20 real-world users and a usage willingness survey of 588 users. Evaluation results show that SlimWeb achieves a 50% reduction in the page load time compared to the original pages, and more than 30% reduction compared to competing solutions, while achieving high similarity scores to the original pages measured via a qualitative evaluation study of 62 users. SlimWeb improves the overall user experience by more than 60% compared to the original pages, while maintaining 90%-100% of the visual and functional components of most pages. Finally, the SlimWeb classifier achieves a median accuracy of 90% in predicting the JavaScript category., Comment: 11 pages, 11 figures

Statistically significant patterns mining (SSPM) is an essential and challenging data mining task in the field of knowledge discovery in databases (KDD), in which each pattern is evaluated via a hypothesis test. Our study aims to introduce a preference relation into patterns and to discover the most preferred patterns under the constraint of statistical significance, which has never been considered in existing SSPM problems. We propose an iterative multiple testing procedure that can alternately reject a hypothesis and safely ignore the hypotheses that are less useful than the rejected hypothesis. One advantage of filtering out patterns with low utility is that it avoids consumption of the significance budget by rejection of useless (that is, uninteresting) patterns. This allows the significance budget to be focused on useful patterns, leading to more useful discoveries. We show that the proposed method can control the familywise error rate (FWER) under certain assumptions, that can be satisfied by a realistic problem class in SSPM.\@We also show that the proposed method always discovers a set of patterns that is at least equally or more useful than those discovered using the standard Tarone-Bonferroni method SSPM.\@Finally, we conducted several experiments with both synthetic and real-world data to evaluate the performance of our method. As a result, in the experiments with real-world datasets, the proposed method discovered a larger number of more useful patterns than the existing method for all five conducted tasks., Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD '20), August 23--27, 2020, Virtual Event, CA, USA

The effects of soft errors in processor cores have been widely studied. However, little has been published about soft errors in uncore components, such as memory subsystem and I/O controllers, of a System-on-a-Chip (SoC). In this work, we study how soft errors in uncore components affect system-level behaviors. We have created a new mixed-mode simulation platform that combines simulators at two different levels of abstraction, and achieves 20,000x speedup over RTL-only simulation. Using this platform, we present the first study of the system-level impact of soft errors inside various uncore components of a large-scale, multi-core SoC using the industrial-grade, open-source OpenSPARC T2 SoC design. Our results show that soft errors in uncore components can significantly impact system-level reliability. We also demonstrate that uncore soft errors can create major challenges for traditional system-level checkpoint recovery techniques. To overcome such recovery challenges, we present a new replay recovery technique for uncore components belonging to the memory subsystem. For the L2 cache controller and the DRAM controller components of OpenSPARC T2, our new technique reduces the probability that an application run fails to produce correct results due to soft errors by more than 100x with 3.32% and 6.09% chip-level area and power impact, respectively., to be published in Proceedings of the 52nd Annual Design Automation Conference

Radio tomographic imaging (RTI) enables device free localisation of people and objects in many challenging environments and situations. Its basic principle is to detect the changes in the statistics of radio signals due to the radio link obstruction by people or objects. However, the localisation accuracy of RTI suffers from complicated multipath propagation behaviours in radio links. We propose to use inexpensive and energy efficient electronically switched directional (ESD) antennas to improve the quality of radio link behaviour observations, and therefore, the localisation accuracy of RTI. We implement a directional RTI (dRTI) system to understand how directional antennas can be used to improve RTI localisation accuracy. We also study the impact of the choice of antenna directions on the localisation accuracy of dRTI and propose methods to effectively choose informative antenna directions to improve localisation accuracy while reducing overhead. Furthermore, we analyse radio link obstruction performance in both theory and simulation, as well as false positives and false negatives of the obstruction measurements to show the superiority of the directional communication for RTI. We evaluate the performance of dRTI in diverse indoor environments and show that dRTI significantly outperforms the existing RTI localisation methods based on omni-directional antennas.

We consider the neighborhood tree induced by alternating the use of different neighborhood structures within a local search descent. We investigate the issue of designing a search strategy operating at the neighborhood tree level by exploring different paths of the tree in a heuristic way. We show that allowing the search to 'backtrack' to a previously visited solution and resuming the iterative variable neighborhood descent by 'pruning' the already explored neighborhood branches leads to the design of effective and efficient search heuristics. We describe this idea by discussing its basic design components within a generic algorithmic scheme and we propose some simple and intuitive strategies to guide the search when traversing the neighborhood tree. We conduct a thorough experimental analysis of this approach by considering two different problem domains, namely, the Total Weighted Tardiness Problem (SMTWTP), and the more sophisticated Location Routing Problem (LRP). We show that independently of the considered domain, the approach is highly competitive. In particular, we show that using different branching and backtracking strategies when exploring the neighborhood tree allows us to achieve different trade-offs in terms of solution quality and computing cost., Comment: Genetic and Evolutionary Computation Conference (GECCO'12) (2012)

We consider the design of self-testers for quantum gates. A self-tester for the gates F_1,...,F_m is a classical procedure that, given any gates G_1,...,G_m, decides with high probability if each G_i is close to F_i. This decision has to rely only on measuring in the computational basis the effect of iterating the gates on the classical states. It turns out that instead of individual gates, we can only design procedures for families of gates. To achieve our goal we borrow some elegant ideas of the theory of program testing: we characterize the gate families by specific properties, we develop a theory of robustness for them, and show that they lead to self-testers. In particular we prove that the universal and fault-tolerant set of gates consisting of a Hadamard gate, a c-NOT gate, and a phase rotation gate of angle pi/4 is self-testable., Comment: LaTeX2e, 14 pages, no figures, usepackage{a4wide,amssymb,amsmath}; major changes (Feb 2000), results expanded to 2-qubit gates. To appear in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing