The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Beyond streams and graphs: dynamic tensor analysis
Abstract
How do we find patterns in author-keyword associations, evolving over time? Or in Data Cubes, with product-branch-customer sales information? Matrix decompositions, like principal component analysis (PCA) and variants, are invaluable tools for mining, dimensionality reduction, feature selection, rule identification in numerous settings like streaming data, text, graphs, social networks and many more. However, they have only two orders, like author and keyword, in the above example.We propose to envision such higher order data as tensors,and tap the vast literature on the topic. However, these methods do not necessarily scale up, let alone operate on semi-infinite streams. Thus, we introduce the dynamic tensor analysis (DTA) method, and its variants. DTA provides a compact summary for high-order and high-dimensional data, and it also reveals the hidden correlations. Algorithmically, we designed DTA very carefully so that it is (a) scalable, (b) space efficient (it does not need to store the past) and (c) fully automatic with no need for user defined parameters. Moreover, we propose STA, a streaming tensor analysis method, which provides a fast, streaming approximation to DTA.We implemented all our methods, and applied them in two real settings, namely, anomaly detection and multi-way latent semantic indexing. We used two real, large datasets, one on network flow data (100GB over 1 month) and one from DBLP (200MB over 25 years). Our experiments show that our methods are fast, accurate and that they find interesting patterns and outliers on the real datasets.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170072 · Cited by 14,907 · cited 1×
“Important applications of this view point include numerous settings like: 1) information retrieval, where the data can be turned into a document-term matrix, and then apply LSI [9, 24]; 2) market basket analysis, with customer-products matrices, where we can apply association rules [2] or “Ratio Rules” [21]; 3) the we…”
BackgroundJolliffe, I. (2005) · Encyclopedia of Statistics in Behavioral Science · doi:10.1002/0470013192.bsa501 · Cited by 14,310
Haykin, S. (1986) · Cited by 12,603
Chiang, L. H., Russell, E. L., & Braatz, R. D. (2001) · Advanced Textbooks in Control and Signal Processing · doi:10.1007/978-1-4471-0347-9_4 · Cited by 6,594
Carroll, J. D., & Chang, J.-J. (1970) · Psychometrika · doi:10.1007/bf02310791 · Cited by 4,678
Some Mathematical Notes on Three-Mode Factor Analysis
Tucker, L. R. (1966) · Psychometrika · doi:10.1007/bf02289464 · Cited by 3,492
Wittenmark, B. (1993) · Automatica · doi:10.1016/0005-1098(93)90162-m · Cited by 3,056
Harshman, R. A. (1970) · Cited by 2,255
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1998) · Symposium on Discrete Algorithms · doi:10.5555/314613.315045 · Cited by 1,814
Mining time-changing data streams
Hulten, G., Spencer, L., & Domingos, P. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502529 · Cited by 1,748
Multilevelk-way Partitioning Scheme for Irregular Graphs
Karypis, G., & Kumar, V. (1998) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1997.1404 · Cited by 1,675
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · now publishers, Inc. eBooks · doi:10.1561/9781933019604 · Cited by 1,527
Information-theoretic co-clustering
Dhillon, I. S., Mallela, S., & Modha, D. S. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956764 · Cited by 1,006
Latent semantic indexing: a probabilistic analysis
Papadimitriou, C. H., Tamaki, H., Raghavan, P., & Vempala, S. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275505 · Cited by 863
Multilinear Analysis of Image Ensembles: TensorFaces
Vasilescu, M. A. O., & Terzopoulos, D. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47969-4_30 · Cited by 836
Principal Component Analysis of Three-Mode Data by Means of Alternating Least Squares Algorithms
Kroonenberg, P. M., & de Leeuw, J. (1980) · Psychometrika · doi:10.1007/bf02293599 · Cited by 724
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000002 · Cited by 718
Personalized information delivery: an analysis of information filtering methods
Foltz, P. W., & Dumais, S. T. (1992) · Communications of the ACM · doi:10.1145/138859.138866 · Cited by 500
Generalized Low Rank Approximations of Matrices
Ye, J. (2005) · Machine Learning · doi:10.1007/s10994-005-3561-6 · Cited by 428
On clusterings-good, bad and spectral
Kannan, R., Vempala, S., & Veta, A. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892125 · Cited by 372
Signal Processing based on Multilinear Algebra
Lathauwer, L. D. (1997) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 360
He, X., Cai, D., & Niyogi, P. (2005) · Cited by 360
Streaming Pattern Discovery in Multiple Time-Series
Papadimitriou, S., Sun, J., & Faloutsos, C. (2018) · doi:10.1184/r1/6609941 · Cited by 348
Self-citationHigher-Order Web Link Analysis Using Multilinear Algebra
Kolda, T. G., Bader, B. W., & Kenny, J. P. (2006) · Fifth IEEE International Conference on Data Mining (ICDM'05) · doi:10.1109/icdm.2005.77 · Cited by 252
TRICLUSTER: an effective algorithm for mining coherent clusters in 3D microarray data
Zhao, L., & Zaki, M. J. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066236 · Cited by 209
Identifying Representative Trends in Massive Time Series Data Sets Using Sketches
Indyk, P., Koudas, N., & Muthukrishnan, S. (2000) · Very Large Data Bases · Cited by 208
Linear image coding for regression and classification using the tensor-rank principle
Shashua, A., & Levin, A. (2005) · Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001 · doi:10.1109/cvpr.2001.990454 · Cited by 193
Xu, D., Yan, S., Zhang, L., Zhang, H.-J., Liu, Z., & Shum, H. (2005) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2005.107 · Cited by 90
2-Dimensional Singular Value Decomposition for 2D Maps and Images
Ding, C. H. Q., & Ye, J. (2005) · doi:10.1137/1.9781611972757.4 · Cited by 75
Monitoring Thermal Processes by NMR Technology
Viereck, N., Dyrby, M., & Engelsen, S. B. (2005) · Elsevier eBooks · doi:10.1016/b978-012676757-5/50023-2 · Cited by 4
Cited by
Tensor Decompositions and Applications
Kolda, T. G., & Bader, B. W. (2009) · SIAM Review · doi:10.1137/07070111x · Cited by 10,301
Kivela, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., & Porter, M. A. (2014) · Journal of Complex Networks · doi:10.1093/comnet/cnu016 · Cited by 3,235
Graph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504
“…3 3 3 3 3 3 role memberships 3 3 role memberships DBMM [Rossi et al., 2013] 3 3 3 7 3 3 role memberships 3 3 role memberships EIGEN-SPACE BASED [Idé and Kashima, 2004] 3 3 3 7 7 7 dissim. score [0,1] 3 3 sim. scores & activ. vector change STA [Sun et al., 2006] 3 3 3 3 7 3+ reconstruction err.”
MethodInfluentialFast Local Algorithms for Large Scale Nonnegative Matrix and Tensor Factorizations
CICHOCKI, A., & PHAN, A.-H. (2009) · IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences · doi:10.1587/transfun.e92.a.708 · Cited by 575
GraphScope: parameter-free mining of large time-evolving graphs
Sun, J., Faloutsos, C., Papadimitriou, S., & Yu, P. S. (2007) · Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1281192.1281266 · Cited by 532
Self-citation
Metadata
- Authors
- Sun, J., Tao, D., & Faloutsos, C.
- Venue
- Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2006-08-20
- Pages
- 374-383
- OpenAlex
- W2037360998
- Cited by
- 462
- References
- 31
- FWCI
- 7.16
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.