NDLI: Fast Discovery of Group Lag Correlations in Streams

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

Fast Discovery of Group Lag Correlations in Streams

Content Provider	ACM Digital Library
Author	Faloutsos, Christos Papadimitriou, Spiros Sakurai, Yasushi
Copyright Year	2010
Abstract	The study of data streams has received considerable attention in various communities (theory, databases, data mining, networking), due to several important applications, such as network analysis, sensor monitoring, financial data analysis, and moving object tracking. Our goal in this article is to monitor multiple numerical streams and determine which pairs are correlated with lags, as well as the value of each such lag. Lag correlations and anticorrelations are frequent and very interesting in practice. For example, a decrease in interest rates typically precedes an increase in house sales by a few months; higher amounts of fluoride in drinking water may lead to fewer dental cavities some years later. Other lag settings include network analysis, sensor monitoring, financial data analysis, and tracking of moving objects. Such data streams are often correlated or anticorrelated, but with unknown lag. We propose BRAID, a method of detecting lag correlations among data streams. BRAID can handle data streams of semi-infinite length incrementally, quickly, and with small resource consumption. However, BRAID requires space and time quadratic on a number of streams $\textit{k}.$ We also propose ThinBRAID, which is even faster than BRAID, requiring $\textit{O}(\textit{k})$ space and time per time tick. Our theoretical analysis shows that BRAID/ThinBRAID can estimate lag correlations with little or, often, with $\textit{no}$ error. Our experiments on real and realistic data show that BRAID and ThinBRAID detect the correct lag perfectly most of the time (the largest relative error was about 1%), while they are significantly faster (up to 40,000 times) than the naïve implementation.
Starting Page	1
Ending Page	43
Page Count	43
File Format	PDF
ISSN	15564681
e-ISSN	1556472X
DOI	10.1145/1870096.1870101
Volume Number	5
Issue Number	1
Journal	ACM Transactions on Knowledge Discovery from Data (TKDD)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-12-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Time-series Cross-correlation Data streams
Content Type	Text
Resource Type	Article
Subject	Computer Science

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

RLC: ranking lag correlations with flexible sliding windows in data streams

Discovering sub-patterns from time series using a normalized cross-match algorithm

A general framework for never-ending learning from time series streams

Multi-stream join answering for mining significant cross-stream correlations

Real-Time Visual Analytics for Text Streams

Time-lag cross-correlations in collective phenomena.

AutoLag: Automatic discovery of lag correlations in stream data (2005)

AutoLag: Automatic discovery of lag correlations in stream data (2005)

Detecting Time Correlations in Time-Series Data Streams

Fast Discovery of Group Lag Correlations in Streams

Similar Documents

RLC: ranking lag correlations with flexible sliding windows in data streams

Discovering sub-patterns from time series using a normalized cross-match algorithm

A general framework for never-ending learning from time series streams

Multi-stream join answering for mining significant cross-stream correlations

Real-Time Visual Analytics for Text Streams

Time-lag cross-correlations in collective phenomena.

AutoLag: Automatic discovery of lag correlations in stream data (2005)

AutoLag: Automatic discovery of lag correlations in stream data (2005)

Detecting Time Correlations in Time-Series Data Streams

Fast Discovery of Group Lag Correlations in Streams