publications

2023

1. SIGMOD

   Detock: High Performance Multi-region Transactions at Scale

   Cuong Nguyen, Johann Miller, and Daniel Abadi

   In SIGMOD, 2023

   Abs PDF Code

   Many globally distributed data stores need to replicate data across large geographic distances. Since synchronously replicating data across such distances is slow, those systems with high consistency requirements often geo-partition data and direct all linearizable requests to the primary region of the accessed data. This significantly improves performance for workloads where most transactions access data close to where they originate from. However, supporting serializable multi-geo-partition transactions is a challenge, and they often degrade the performance of the whole system. This becomes even more challenging when they conflict with single-partition requests, where optimistic protocols lead to high numbers of aborts, and pessimistic protocols lead to high numbers of distributed deadlocks. In this paper, we describe the design of concurrency control and deadlock resolution protocols, built within a practical, complete implementation of a geographically replicated database system called Detock, that enables processing strictly-serializable multi-region transactions with near-zero performance degradation at extremely high conflict and order of magnitude higher throughput relative to state-of-the art geo-replication approaches, while improving latency by up to a factor of 5.

2020

1. IEEE

   A General Approach For Supporting Time Series Matching using Multiple-Warped Distances

   Rodica Neamtu, Ramoza Ahsan, Cuong Nguyen, and 3 more authors

   In IEEE Transactions on Knowledge and Data Engineering, 2020

   Abs

   Time series are generated at an unprecedented rate in domains ranging from finance, medicine to education. Collections composed of heterogeneous, variable-length and misaligned times series are best explored using a plethora of dynamic time warping distances. However, the computational costs of using such elastic distances result in unacceptable response times. We thus design the first practical solution for the efficient GEN eral EX ploration of time series leveraging multiple warped distances. GENEX pre-processes time series data in metric point-wise distance spaces, while providing bounds for the accuracy of corresponding analytics derived in non-metric warped distance spaces. Our empirical evaluation on 66 benchmark datasets provides a comparative study of the accuracy and response times of diverse warped distances. We show that GENEX is a versatile yet highly efficient solution for processing expensive-to-compute warped distances over large datasets, with response times 3 to 5 orders of magnitude faster than state-of-art systems.

2018

1. HCI

   Fact or fiction

   Charles Lovering, Anqi Lu, Cuong Nguyen, and 3 more authors

   In PACMHCI, 2018

   Abs

   Subjective reporting polarizes competing viewpoints. However, helping readers to recognize subjective content leads to more impartial discussions. Towards this end, we develop machine learning models that classify sentence objectivity. We contribute a set of linguistic rules for determining sentence objectivity collated from previous work. We also develop a labeled dataset with over 5000 sentences retrieved from various news sources. Further, we evaluate traditional machine learning classification models and artificial neural networks on our dataset. The best performing model, a convolutional neural network, achieved an accuracy of 85% and an AUC of 0.933. Using our subjective-objective sentence classification model, we implement Fact-or-Fiction, an end-to-end web system that highlights objective sentences in user text. Fact-or-Fiction provides additional information, such as links to related web pages and related previous submissions.

2. ICDE

   Generalized dynamic time warping: Unleashing the warping power hidden in point-wise distances

   Rodica Neamtu, Ramoza Ahsan, Elke A Rundensteiner, and 5 more authors

   In ICDE, 2018

   Abs

   Domain-specific distances preferred by analysts for exploring similarities among time series tend to be "point-to-point" distances. Unfortunately, this point-wise nature limits their ability to perform meaningful comparisons between sequences of different lengths and with temporal mis-alignments. Analysts instead need "elastic" alignment tools such as Dynamic Time Warping (DTW) to perform such flexible comparisons. However, the existing alignment tools are limited in that they do not incorporate diverse distances. To address this shortcoming, our work introduces the first conceptual framework called Generalized Dynamic Time Warping (GDTW) that supports now alignment (warping) of a large array of domain-specific distances in a uniform manner. While the classic DTW and its prior extensions focus on the Euclidean Distance, our GDTW is the first method that generalizes the ubiquitous DTW and "extends" its warping capabilities to a rich diversity of point-to-point distances. Based on our GDTW paradigm that preserves the efficiency of the dynamic programming paradigm of DTW, we design an abstraction that implemented by our GDTW Design Tool enables analysts to "warp" new distances with little programming effort. Through extensive evaluation studies on 85 real public domain benchmark datasets, we show that our newly warped distances offer higher classification accuracy than the previously available distances for the majority of these datasets. Further, our case study on heart arrhythmia data illustrates the utility of the new distances enabled by our GDTW warping methodology.

2017

1. BigData

   Ranked time series matching by interleaving similarity distances

   Cuong Nguyen, Charles Lovering, and Rodica Neamtu

   In BigData, 2017

   Abs

   Similarity analytics of time series data are critical for a wide range of applications ranging from medical to financial, and from weather forecasting to image processing. Yet these analytics tasks are known to be prohibitively expensive for large data sets, especially when accounting for varying temporal alignments and lengths. Our proposed framework tackles this challenge by adopting a preprocess-once and query-many-times paradigm. We extend a previous formal model interleaving the inexpensive Euclidean distance with the robust Dynamic Time Warping (DTW) to retrieve the k most similar matches to a given sample sequence. Our extended ONline EXploration of top k time series similarity system (K-ONEX) first encodes similarity relationships by compressing the raw time series into Euclidean-based groups; these groups are further explored using the elastic DTW to find similar sequences of any length and temporal alignment with response times that are almost as fast as retrieving only one best match. Our empirical results illustrate that K-ONEX provides response times that are 2-3 orders of magnitude faster than the benchmark and state-of-the-art methods while achieving 100% accuracy by exploring less than 0.5% of the sequences in each dataset.

2. SIGMOD

   Interactive time series analytics powered by ONEX

   Rodica Neamtu, Ramoza Ahsan, Charles Lovering, and 3 more authors

   In SIGMOD, 2017

   Abs

   Modern applications in this digital age collect a staggering amount of time series data from economic growth rates to electrical household consumption habits. To make sense of it, domain analysts interactively sift through these time series collections in search of critical relationships between and recurring patterns within these time series. The ONEX (Online Exploration of Time Series) system supports effective exploratory analysis of time series collections composed of heterogeneous, variable-length and misaligned time series using robust alignment dynamic time warping (DTW) methods. To assure real-time responsiveness even for these complex and compute-intensive analytics, ONEX precomputes and then encodes time series relationships based on the inexpensive-to-compute Euclidean distance into the ONEX base. Thereafter, based on a solid formal foundation, ONEX uses DTW-enhanced analytics to correctly extract relevant time series matches on this Euclidean-prepared ONEX base. Our live interactive demonstration shows how our ONEX exploratory tool, supported by a rich array of visual interactions and expressive visualizations, enables efficient mining and interpretation of the MATTERS real data collection composed of economic, social, and education data trends across the fifty American states.