NDLI: Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy

Please wait, while we are loading the content...

Online Controlled Experiments: Lessons from Running A/B/n Tests for 12 Years

Large-Scale Distributed Bayesian Matrix Factorization using Stochastic Gradient MCMC

Data-Driven Activity Prediction: Algorithms, Evaluation Methodology, and Applications

Scaling Machine Learning and Statistics for Web Applications

The Effectiveness of Marketing Strategies in Social Media: Evidence from Promotional Events

Web Personalization and Recommender Systems

Data Driven Science: SIGKDD Panel

MOOCS: What Have We Learned?

TimeMachine: Timeline Generation for Knowledge-Base Entities

Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling

Hadoop's Impact on the Future of Data Management

Personalizing LinkedIn Feed

Graph-Based User Behavior Modeling: From Prediction to Fraud Detection

Machine Learning and Causal Inference for Policy Evaluation

Estimating Local Intrinsic Dimensionality

Graph Query Reformulation with Diversity

Should You Trust Your Money to a Robot?

Whither Social Networks for Web Search?

Data-Driven Product Innovation

Data, Knowledge and Discovery: Machine Learning meets Natural Science

Portraying Collective Spatial Attention in Twitter

Flexible and Robust Multi-Network Clustering

Data Science at Visa

Exploiting Data Mining for Authenticity Assessment and Protection of High-Quality Italian Wines from Piedmont

Dense Subgraph Discovery: KDD 2015 tutorial

Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy

Extreme States Distribution Decomposition Method for Search Engine Online Evaluation

How Artificial Intelligence and Big Data Created Rocket Fuel: A Case Study

Predictive Approaches for Low-Cost Preventive Medicine Program in Developing Countries

Diffusion in Social and Information Networks: Research Problems, Probabilistic Models and Machine Learning Methods

Efficient Online Evaluation of Big Data Stream Classifiers

Simultaneous Modeling of Multiple Diseases for Mortality Prediction in Acute Hospital Care

Optimizing Marketing Impact through Data Driven Decisioning

Dynamic Hierarchical Classification for Patient Risk-of-Readmission

Social Media Anomaly Detection: Challenges and Solutions

Dynamically Modeling Patient's Health State from Electronic Medical Records: A Time Series Approach

Fast and Robust Parallel SGD Matrix Factorization

Powering Real-time Decision Engines in Finance and Healthcare using Open Source Software

ALOJA-ML: A Framework for Automating Characterization and Knowledge Discovery in Hadoop Deployments

Automatic Entity Recognition and Typing from Massive Text Corpora: A Phrase and Network Mining Approach

Facets: Fast Comprehensive Mining of Coevolving High-order Time Series

Efficient PageRank Tracking in Evolving Networks

Clouded Intelligence

Multi-View Incident Ticket Clustering for Optimal Ticket Dispatching

VC-Dimension and Rademacher Averages: From Statistical Learning Theory to Sampling Algorithms

Online Outlier Exploration Over Large Datasets

Quick Sensitivity Analysis for Incremental Data Modification and Its Application to Leave-one-out CV in Linear Classification Problems

Data Science from the Lab to the Field to the Enterprise

Intelligible Models for HealthCare: Predicting Pneumonia Risk and Hospital 30-day Readmission

Large Scale Distributed Data Science using Apache Spark

BatchRank: A Novel Batch Mode Active Learning Framework for Hierarchical Classification

Non-transitive Hashing with Latent Similarity Components

User Modeling in Telecommunications and Internet Industry

User Conditional Hashtag Prediction for Images

Medical Mining: KDD 2015 Tutorial

On the Formation of Circles in Co-authorship Networks

Optimal Kernel Group Transformation for Exploratory Regression Analysis and Graphics

Big Data System for Analyzing Risky Procurement Entities

Big Data Analytics: Optimization and Randomization

Heterogeneous Network Embedding via Deep Architectures

Discovering and Exploiting Deterministic Label Relationships in Multi-Label Learning

Probabilistic Modeling of a Sales Funnel to Prioritize Leads

Differentially Private High-Dimensional Data Publication via Sampling-Based Inference

Subspace Clustering Using Log-determinant Rank Approximation

Online Topic-based Social Influence Analysis for the Wimbledon Championships

Efficient Algorithms for Public-Private Social Networks

A PCA-Based Change Detection Framework for Multidimensional Data Streams: Change Detection in Multidimensional Data Streams

Collective Spammer Detection in Evolving Multi-Relational Social Networks

Warm Start for Parameter Selection of Linear Classifiers

State-Driven Dynamic Sensor Selection and Prediction with State-Stacked Sparseness

Utilizing Text Mining on Online Medical Forums to Predict Label Change due to Adverse Drug Reactions

Stream Sampling for Frequency Cap Statistics

SCRAM: A Sharing Considered Route Assignment Mechanism for Fair Taxi Route Recommendations

One-Pass Ranking Models for Low-Latency Product Recommendations

Adaptation Algorithm and Theory Based on Generalized Discrepancy

Locally Densest Subgraph Discovery

On the Reliability of Profile Matching Across Large Online Social Networks

Optimal Action Extraction for Random Forests and Boosted Trees

Virus Propagation in Multiple Profile Networks

E-commerce in Your Inbox: Product Recommendations at Scale

Dynamic Matrix Factorization with Priors on Unknown Values

Collective Opinion Spam Detection: Bridging Review Networks and Metadata

Gender and Interest Targeting for Sponsored Post Advertising at Tumblr

CoupledLP: Link Prediction in Coupled Networks

ClusType: Effective Entity Recognition and Typing by Relation Phrase-Based Clustering

Mining Administrative Data to Spur Urban Revitalization

Unsupervised Feature Selection with Adaptive Structure Learning

Mining Frequent Itemsets through Progressive Sampling with Rademacher Averages

Measuring Causal Impact of Online Actions via Natural Experiments: Application to Display Advertising

Dirichlet-Hawkes Processes with Applications to Clustering Continuous-Time Document Streams

Why It Happened: Identifying and Modeling the Reasons of the Happening of Social Events

Focusing on the Long-term: It's Good for Users and Business

Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs

Matrix Completion with Queries

Traffic Measurement and Route Recommendation System for Mass Rapid Transit (MRT)

Hierarchical Graph-Coupled HMMs for Heterogeneous Personalized Health Data

Stochastic Divergence Minimization for Online Collapsed Variational Bayes Zero Inference of Latent Dirichlet Allocation

Real-Time Bid Prediction using Thompson Sampling-Based Expert Selection

More Constraints, Smaller Coresets: Constrained Matrix Approximation of Sparse Big Data

Bayesian Poisson Tensor Factorization for Inferring Multilateral Relations from Sparse Dyadic Event Counts

Life-stage Prediction for Product Recommendation in E-commerce

Certifying and Removing Disparate Impact

TimeCrunch: Interpretable Dynamic Graph Summarization

Visual Search at Pinterest

RSC: Mining and Modeling Temporal Activity in Social Media

Inside Jokes: Identifying Humorous Cartoon Captions

Discovering Collective Narratives of Theme Parks from Large Collections of Visitors' Photo Streams

A Clustering-Based Framework to Control Block Sizes for Entity Resolution

Community Detection based on Distance Dynamics

A Machine Learning Framework to Identify Students at Risk of Adverse Academic Outcomes

Who Supported Obama in 2012?: Ecological Inference through Distribution Regression

Discovery of Meaningful Rules in Time Series

Probabilistic Graphical Models of Dyslexia

Real Estate Ranking via Mixed Land-use Latent Models

An Evaluation of Parallel Eccentricity Estimation Algorithms on Undirected Real-World Graphs

Promoting Positive Post-Click Experience for In-Stream Yahoo Gemini Users

Adaptive Message Update for Fast Affinity Propagation

Efficient Latent Link Recommendation in Signed Networks

Generic and Scalable Framework for Automated Time-series Anomaly Detection

Monitoring Least Squares Models of Distributed Streams

Turn Waste into Wealth: On Simultaneous Clustering and Cleaning over Dirty Data

Leveraging Knowledge Bases for Contextual Entity Exploration

Reconstructing Textual Documents from n-grams

Set Cover at Web Scale

Click-through Prediction for Advertising in Twitter Timeline

Anatomical Annotations for Drosophila Gene Expression Patterns via Multi-Dimensional Visual Descriptors Integration: Multi-Dimensional Feature Learning

Exploiting Relevance Feedback in Knowledge Graph Search

Predicting Voice Elicited Emotions

Selective Hashing: Closing the Gap between Radius Search and k-NN Search

LINKAGE: An Approach for Comprehensive Risk Prediction for Care Management

Discovery of Glaucoma Progressive Patterns Using Hierarchical MDL-Based Clustering

Using Local Spectral Methods to Robustify Graph-Based Learning Algorithms

Transitive Transfer Learning

Distributed Personalization

Instance Weighting for Patient-Specific Risk Stratification Models

PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks

Voltage Correlations in Smart Meter Data

A Deep Hybrid Model for Weather Forecasting

An Effective Marketing Strategy for Revenue Maximization with a Quantity Constraint

Analyzing Invariants in Cyber-Physical Systems using Latent Factor Regression

Network Lasso: Clustering and Optimization in Large Graphs

Scaling Up Stochastic Dual Coordinate Ascent

Predicting Future Scientific Discoveries Based on a Networked Analysis of the Past Literature

Learning Tree Structure in Multi-Task Learning

Discovering Valuable items from Massive Data

Learning a Hierarchical Monitoring System for Detecting and Diagnosing Service Issues

Probabilistic Community and Role Model for Social Networks

Deep Learning Architecture with Dynamically Programmed Layers for Brain Connectome Prediction

Predictive Modeling for Public Health: Preventing Childhood Lead Poisoning

Real-Time Top-R Topic Detection on Twitter with Topic Hijack Filtering

Incorporating World Knowledge to Document Clustering via Heterogeneous Information Networks

Proof Protocol for a Machine Learning Technique Making Longitudinal Predictions in Dynamic Contexts

Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming

Towards Interactive Construction of Topical Hierarchy: A Recursive Tensor Decomposition Approach

An Architecture for Agile Machine Learning in Real-Time Applications

Inferring Air Quality for Station Location Recommendation Based on Urban Big Data

Collaborative Deep Learning for Recommender Systems

Scalable Machine Learning Approaches for Neighborhood Classification Using Very High Resolution Remote Sensing Imagery

Website Optimization Problem and Its Solutions

Trading Interpretability for Accuracy: Oblique Treed Sparse Additive Models

Early Identification of Violent Criminal Gang Members

Reciprocity in Social Networks with Capacity Constraints

Geo-SAGE: A Geographical Sparse Additive Generative Model for Spatial Item Recommendation

Spoken English Grading: Machine Learning with Crowd Intelligence

Learning with Similarity Functions on Graphs using Matchings of Geometric Embeddings

Rubik: Knowledge Guided Tensor Factorization and Completion for Health Data Analytics

Effective Audience Extension in Online Advertising

Structured Hedging for Resource Allocations with Leverage

Regularity and Conformity: Location Prediction Using Heterogeneous Mobility Data

Going In-Depth: Finding Longform on the Web

Improved Bounds on the Dot Product under Random Projection and Random Sign Projection

Dynamic Poisson Autoregression for Influenza-Like-Illness Case Count Prediction

Early Prediction of Cardiac Arrest (Code Blue) using Electronic Medical Records

Accelerated Alternating Direction Method of Multipliers

Cinema Data Mining: The Smell of Fear

When-To-Post on Social Networks

Deep Computational Phenotyping

Predicting Winning Price in Real Time Bidding with Censored Data

Mining for Causal Relationships: A Data-Driven Study of the Islamic State

Leveraging Social Context for Modeling Topic Evolution

Diversifying Restricted Boltzmann Machine for Document Modeling

Transfer Learning for Bilingual Content Classification

Scalable Blocking for Privacy Preserving Record Linkage

Edge-Weighted Personalized PageRank: Breaking A Decade-Old Performance Barrier

FrauDetector: A Graph-Mining-based Framework for Fraudulent Phone Call Detection

Real Time Recommendations from Connoisseurs

Petuum: A New Platform for Distributed Machine Learning on Big Data

Efficient Long-Term Degradation Profiling in Time Series for Complex Physical Systems

Towards Decision Support and Goal Achievement: Identifying Action-Outcome Relationships From Social Media

Longitudinal LASSO: Jointly Learning Features and Temporal Contingency for Outcome Prediction

Interpreting Advertiser Intent in Sponsored Search

On Estimating the Swapping Rate for Categorical Data

Performance Modeling and Scalability Optimization of Distributed Deep Learning Systems

Client Clustering for Hiring Modeling in Work Marketplaces

Simultaneous Discovery of Common and Discriminative Topics via Joint Nonnegative Matrix Factorization

Deep Graph Kernels

Discerning Tactical Patterns for Professional Soccer Teams: An Enhanced Topic Model with Applications

A Decision Tree Framework for Spatiotemporal Sequence Prediction

Model Multiple Heterogeneity via Hierarchical Multi-Latent Space Learning

Predicting Serves in Tennis using Style Priors

TOPTRAC: Topical Trajectory Pattern Mining

Structural Graphical Lasso for Learning Mouse Brain Connectivity

Smart Pacing for Effective Online Ad Campaign Optimization

From Group to Individual Labels Using Deep Features

Entity Matching across Heterogeneous Sources

From Infrastructure to Culture: A/B Testing Challenges in Large Scale Social Networks

VEWS: A Wikipedia Vandal Early Warning System

An Efficient Semi-Supervised Clustering Algorithm with Sequential Constraints

Tornado Forecasting with Multiple Markov Boundaries

Unified and Contrasting Cuts in Multiple Graphs: Application to Medical Imaging Segmentation

Assembler: Efficient Discovery of Spatial Co-evolving Patterns in Massive Geo-sensory Data

Gas Concentration Reconstruction for Coal-Fired Boilers Using Gaussian Process

Reducing the Unlabeled Sample Complexity of Semi-Supervised Multi-View Learning

Dynamic Topic Modeling for Monitoring Market Competition from Online Text and Image Data

Annotating Needles in the Haystack without Looking: Product Information Extraction from Emails

Maximum Likelihood Postprocessing for Differential Privacy under Consistency Constraints

Organizational Chart Inference

Forecasting Fine-Grained Air Quality Based on Big Data

Online Influence Maximization

Panther: Fast Top-k Similarity Search on Large Networks

Building Discriminative User Profiles for Large-scale Content Recommendation

The Child is Father of the Man: Foresee the Success at the Early Stage

A Collective Bayesian Poisson Factorization Model for Cold-start Local Event Recommendation

Stock Constrained Recommendation in Tmall

0-Bit Consistent Weighted Sampling

Statistical Arbitrage Mining for Display Advertising

Predicting Ambulance Demand: a Spatio-Temporal Kernel Approach

On the Discovery of Evolving Truth

Deep Model Based Transfer and Multi-Task Learning for Biological Image Analysis

MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams

COSNET: Connecting Heterogeneous Social Networks with Local and Global Consistency

A Learning-based Framework to Handle Multi-round Multi-party Influence Maximization on Social Networks

SAME but Different: Fast and High Quality Gibbs Parameter Estimation

Temporal Phenotyping from Longitudinal Electronic Health Records: A Graph Based Framework

Multi-Task Learning for Spatio-Temporal Event Forecasting

Spectral Ensemble Clustering

SEISMIC: A Self-Exciting Point Process Model for Predicting Tweet Popularity

Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing

Linear Time Samplers for Supervised Topic Models using Compositional Proposals

Influence at Scale: Distributed Computation of Complex Contagion in Networks

L∞ Error and Bandwidth Selection for Kernel Density Estimates of Large Data

FaitCrowd: Fine Grained Truth Discovery for Crowdsourced Data Aggregation

Modeling Truth Existence in Truth Discovery

Algorithmic Cartography: Placing Points of Interest and Ads on Maps

Cuckoo Linear Algebra

Dimensionality Reduction Via Graph Structure Learning

Integrating Vertex-centric Clustering with Edge-centric Clustering for Meta Path Graph Analysis

Robust Treecode Approximation for Kernel Machines

Modeling User Mobility for Location Promotion in Location-based Social Networks

Inferring Networks of Substitutable and Complementary Products

Co-Clustering based Dual Prediction for Cargo Pricing Optimization

Debiasing Crowdsourced Batches

Query Workloads for Data Series Indexes

Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy

Content Provider	ACM Digital Library
Author	Begum, Nurjahan Ulanova, Liudmila Wang, Jun Keogh, Eamonn
Abstract	Clustering time series is a useful operation in its own right, and an important subroutine in many higher-level data mining analyses, including data editing for classifiers, summarization, and outlier detection. While it has been noted that the general superiority of Dynamic Time Warping (DTW) over Euclidean Distance for similarity search diminishes as we consider ever larger datasets, as we shall show, the same is not true for clustering. Thus, clustering time series under DTW remains a computationally challenging task. In this work, we address this lethargy in two ways. We propose a novel pruning strategy that exploits both upper and lower bounds to prune off a large fraction of the expensive distance calculations. This pruning strategy is admissible; giving us provably identical results to the brute force algorithm, but is at least an order of magnitude faster. For datasets where even this level of speedup is inadequate, we show that we can use a simple heuristic to order the unavoidable calculations in a most-useful-first ordering, thus casting the clustering as an anytime algorithm. We demonstrate the utility of our ideas with both single and multidimensional case studies in the domains of astronomy, speech physiology, medicine and entomology.
Starting Page	49
Ending Page	58
Page Count	10
File Format	PDF MP4
ISBN	9781450336642
DOI	10.1145/2783258.2783286
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-08-10
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Anytime algorithms Time series Clustering
Content Type	Audio Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in