OLAP on sequence data
Published 9 June 2008
Eric Lo, Ben Kao, Wai-Shing Ho, Sau Dan Lee, Chun Kit Chui, David W. Cheung
Citations84
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper proposes the concept of Sequence OLAP, or S-OLAP for short, a system that can be characterized not only by the attributes' values of its constituting items, but also by the subsequence/substring patterns it possesses.
Abstract
Many kinds of real-life data exhibit logical ordering among their data items and are thus sequential in nature. However, traditional online analytical processing (OLAP) systems and techniques were not designed for sequence data and they are incapable of supporting sequence data analysis. In this paper, we propose the concept of Sequence OLAP, or S-OLAP for short. The biggest distinction of S-OLAP from traditional OLAP is that a sequence can be characterized not only by the attributes' values of its constituting items, but also by the subsequence/substring patterns it possesses. This paper studies many aspects related to Sequence OLAP. The concepts of sequence cuboid and sequence data cube are introduced. A prototype S-OLAP system is built in order to validate the proposed concepts. The prototype is able to support "pattern-based" grouping and aggregation, which is currently not supported by any OLAP system. The implementation details of the prototype system as well as experimental results are presented. Copyright 2008 ACM.
Keywords
Computer Science
Rfid Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification
2,164 Citations2003Klaus Finkenzeller
Data Mining and Knowledge DiscoveryData Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals
2,134 Citations1997Jim Gray, Surajit Chaudhuri +6 more
This paper explains the cube and roll-up operators, shows how they fit in SQL, explains how users can define new aggregatefunctions for cubes, and discusses efficient techniques to compute the cube.
Online aggregation
923 Citations1997Joseph M. Hellerstein, Peter J. Haas +1 more
A new online aggregation interface is proposed that permits users to both observe the progress of their aggregation queries and control execution on the fly, and a suite of techniques that extend a database system to meet these requirements are presented.
Data cube: a relational aggregation operator generalizing GROUP-BY, CROSS-TAB, and SUB-TOTALS
562 Citations2002Jodi Gray, Ailsa Bosworth +2 more
ACM Transactions on Database SystemsJoin indices
504 Citations1987Patrick Valduriez
This paper proposes a simple data structure, called a join index, for improving the performance of joins in the context of complex queries, and analysis of the join algorithm using join indices shows its excellent performance.
ACM SIGMOD RecordBottom-up computation of sparse and Iceberg CUBE
464 Citations1999Kevin Beyer, Raghu Ramakrishnan
Computing Iceberg Queries Efficiently
341 Citations1998Min Fang, Narayanan Shivakumar +3 more
This work proposes efficient algorithms to evaluate iceberg queries using very little memory and significantly fewer passes over data, as compared to current techniques that use sorting or hashing.
Elsevier eBooksMulti-Dimensional Regression Analysis of Time-Series Data Streams
303 Citations2002Yixin Chen, Guozhu Dong +3 more
An exception-guided drilling approach is developed for on-line, multi-dimensional exception-based regression analysis, and algorithms are proposed for efficient analysis of time-series data streams.
Summarizability in OLAP and statistical data bases
292 Citations2002H. Lenz, Arie Shoshani
A framework for precisely specifying the context in which statistical objects are defined is introduced, which uses a three-step process to define normalized statistical objects.
ACM SIGMOD RecordMulti-table joins through bitmapped join indices
285 Citations1995Patrick O’Neil, Goetz Graefe
This technical note shows how to combine some well-known techniques to create a method that will efficiently execute common multi-table joins, and outlines realistic examples where the combination of these techniques yields substantial performance improvements over alternative, more traditional query evaluation plans.
Warehousing and Analyzing Massive RFID Data Sets
267 Citations2006Héctor González, Jiawei Han +2 more
This work proposes a new warehousing model that preserves object transitions while providing significant compression and path-dependent aggregates, and designs and algorithms for summarizing and indexing data based on this framework.
ACM SIGKDD Explorations NewsletterKDD-Cup 2000 organizers' report
255 Citations2000Ron Kohavi, Carla E. Brodley +3 more
KDD-Cup 2000, the yearly competition in data mining, is described, for the first time the Cup included insight problems in addition to prediction problems, thus posing new challenges in both the knowledge discovery and the evaluation criteria and highlighting the need to "peel the onion" and drill deeper into the reasons for the initial patterns found.
Bottom-up computation of sparse and Iceberg CUBE
238 Citations1999Kevin Beyer, Raghu Ramakrishnan
The pruning in BUC, combined with an efficient sort method, enables BUC to outperform all previous algorithms for sparse CUBEs, even for computing entire CUBes, and to dramatically improve Iceberg-CUBE computation.
Materialized views: techniques, implementations, and applications
235 Citations1999Ashish Gupta, Iderpal Singh Mumick
This comprehensive volume, with a foreword by Jeff Ullman of Stanford University, will serve as a reference for students and commercial users, and encourage further use and development of materialized views.
Fast Computation of Sparse Datacubes
198 Citations1997Kenneth A. Ross, Divesh Srivastava
This work proposes a novel algorithm for the fast computation of datacubes over sparse relations, and demonstrates the efficiency of the algorithm using synthetic, benchmark and real-world data sets.
The Design and Implementation of a Sequence Database System
150 Citations1996Praveen Seshadri, Miron Livny +1 more
The issues that were addressed when building the SEQ sequence database system, a database system with support for sequence data, are described and a novel nested design paradigm used in PREDATOR to combine sequence ‘and relational data is presented.
Sequence query processing
127 Citations1994Praveen Seshadri, Miron Livny +1 more
This work presents a bottom-up algorithm that generates an efficient query evaluation plan based on cost estimates, and identifies a number of directions in which future research can be directed.
High-dimensional OLAP: a minimal cubing approach
110 Citations2004Xiaolei Li, Jiawei Han +1 more
Optimization of sequence queries in database systems
94 Citations2001Reza Sadri, Carlo Zaniolo +2 more
This paper takes the optimal text search algorithm of Knuth, Morris and Pratt, and generalize it to handle complex queries on sequences, and exploits the inter-dependencies between the elements of a sequential pattern to minimize repeated passes over the same data.
Flowcube: constructing RFID flowcubes for multi-dimensional analysis of commodity flows
91 Citations2006Héctor González, Jiawei Han +1 more
The importance of the model is motivated, and an efficient method to compute it is presented by performing simultaneous aggregation of paths to all interesting abstraction levels, and pruning low support path segments along the item and path stage abstraction lattices.
SRQL: Sorted Relational Query Language
73 Citations2002R. Ramakrsihnan, D. Donjerkovic +3 more
This work shows how a rich class of queries reflecting sort order can be naturally expressed and efficiently executed with simple extensions to SQL.
X^ 3: A Cube Operator for XML OLAP
57 Citations2007Nuwee Wiwatwattana, H. V. Jagadish +2 more
A definition for cube adapted for XML data warehouse is proposed, including a suitably generalized specification mechanism, and the results of an extensive performance evaluation experiment gauging the behavior of alternative algorithms for cube computation are presented.