This paper presents a proposal for learning users' behavior patterns when they interactively analyse data. Users' explorations (sequences of queries) are compared looking for subsequences of common actions or operations performed by the users during data analysis. We use a hierarchical clustering algorithm to retrieve groups of similar explorations. The main dificulty is to devise a similarity measure suitable to measure similarities between sequences of human actions. We propose to use a Contextual Edit Distance (CED), a generalization of Edit Distance that manages context-dependent edition costs. CED compares two users' explorations, making special emphasis in the similarity of queries with nearby queries in the exploration, which determines a local context. We test our approach on three workloads of real users' explorations, extracting common analysis patterns, both in explorations devised by students and expert analysts. We also experiment on an artificial workload, generated with CubeLoad [19], showing that our approach is able to identify the patterns imposed by the generator. To the best of our knowledge, this is the first attempt to characterize human analysis behavior in workloads of data explorations.
Analyzing a database workload ofers many practical interests,
from the monitoring of database physical access structures [
Identifying analysis behavior has several applications. The
more natural one is a better support of IDE, for instance to
understand users’ information needs, to identify "struggling" during
the exploration, or to provide better query recommendations.
Notably, IDE systems usually do not ofer such facilities. The
prediction of next analysis steps is particularly interesting, enabling
beforehand execution of probable queries and caching of results,
as well as advanced optimization strategies. Another benefit is
the design of more realistic workloads for database
benchmarking. Classical benchmarks like TPC-H or TPC-DS poorly include
interactive exploration activities in their synthetic workloads,
and are not appropriate to evaluate modern IDE systems [
In this paper we deal with the identification of analysis
patterns in a log of explorations devised by real users. We consider
that an exploration is a coherent sequence of queries over a
database schema, done by a user with the goal of fulfilling an
information need. In [
Many distances proposed to compare sequences, for example
the Damerau-Levenshtein distance [
Indeed, while edition cost is constant in classical Edit Distance, for comparing interconnected actions, it should take context (i.e. the nearby actions) into account. For example, removing a measure should be costly within a focused sequence of drills down and filters, while it should be cheaper inside a sequence with other changes in measures. In addition, sequences of filters should be similar, no matter how many filters there are. Furthermore, permuting operations should have little impact, e.g. filtering and then drilling vs. drilling then filtering.
Previous attempts made for measuring the similarity of
sequences of OLAP queries (like e.g. [
Our contributions, sketched in Figure 1 include: (i) a representation of queries and explorations in the space of OLAP operations, including a similarity function among OLAP operations in such space (described in Section 3), (ii) a CED for comparing explorations considering context (Section 4), (iii) a proposal for clustering explorations, based on CED (Section 5), and (iv) a set of experiments showing that CED outperforms state of the art distances allowing the learning of analysis behavior in varied logs of explorations (Section 6). 2
The recurrent types of user analyses described by Rizzi and
Gallinucci [
A e1 = hq1, q2, ..., qmi e2 = hq1, q2, ..., qni T S .
.
M´e.trique de comparaison sur leesktr=ajehcqt1o,iqre2s, .s.´e.m,qapnitiques Exploration sessions {e1, e2, ..., ek} ✓ Q⇤ (a)
Partitionnement Regroupement des trajectoiresHeienramrcohtiifcsal de comportements csliumsitleariirnesg (c)
d : Q⇤ ⇥ Q⇤ ! R++ d : TMSeas u⇥re oTn S ! R exploration sessions (b) e t a c i d re 6 p n o it c e lse 2 • Slice All. Users are sometimes interested in navigating a cube by slices, i.e., repeatedly running the same query but with diferent selection predicates. Then, this templates generates sequences of unfilter/filter operations. • Exploratory. The motivation for this template is the assumption that several users, while exploring the cube in search of significant correlations, will be “attracted” by one surprising query and then evolve casually. So, explorations based on this template contain varied random operations. • Goal Oriented. Explorations of this type are run by users who have a specific analysis goal, but whose OLAP skills are limited so they may follow a complex path to reach their destination. Explorations of this template contain varied operations but converging to some specific point.
Other works analyse real workloads and observe tendences
or patterns. Aligon et al. [
To our knowledge, our work is the first devoted to discover exploration patterns in OLAP workloads.
Many recent works aimed at comparing queries and sessions.
We mention as good recent surveys [
Aligon et al. [
This section introduces the description of queries and explorations used all along the paper as well as their representation in a space of OLAP operations. 3.1
In order to keep the formalism simple, we only take into account
cubes under a ROLAP perspective, described by a star schema
[
Definition 3.1 (OLAP query). An OLAP query over cube schema S is a triple q = ⟨G, P, M⟩ where: (1) G = {д1, . . . , дj } is the query group-by set, each дi being a level of a hierarchy of the cube; (2) P = {p1, . . . , pk } is a set of Boolean predicates, of the form l = v, with l a level and v a value. Compound predicates are build as the disjunction of predicates on a same level (l ), at most one for each hierarchy, whose conjunction defines the selection predicate for q; (3) M = {m1, . . . , ml } is the measure set whose values are returned by q.
We intentionally remain independent of presentation and optimization aspects, specially the order in which attributes are projected (and visualized), the order of joins, etc.
Finally, an exploration is a coherent sequence of queries over a cube schema, devised by a user with the goal of fulfilling an information need that may not be well defined initially.
Definition 3.2 (Exploration). Let S be a cube schema. An exploration e = ⟨q1, . . . , qp ⟩ is a sequence of queries over S. We note q ∈ e if q appears in the exploration e, and exploration(q) to refer to the explorations where q appears. 3.2
For each query, we extract a set of simple features computed from
the query text and its relationship with previous query in an
exploration. The set of features is inspired from our previous works
[
For the following definitions let qk = ⟨Gk , Pk , Mk ⟩ be the query occurring at position k in the exploration e over cube schema S. All the queries we considered are supposed to be well formed, and so we do not deal with query errors. Features are computed comparing the query qk to the previous query in the exploration e, qk−1 = ⟨Gk−1, Pk−1, Mk−1⟩. For the first query of e, i.e. q1, we consider as predecessor the "empty" query q0 = ⟨∅, ∅, ∅⟩. All the following features are defined for k ≥ 1.
Number of Added Levels. N AL(qk , qk−1) counts the number of levels in the group by set of qk that were not part of the group by set of qk−1.
N AL(qk , qk−1) = |Gk − Gk−1 |
Number of Deleted Levels. N DL(qk , qk−1) counts the number of levels in the group by set of qk−1 that are not longer used in qk .
N DL(qk , qk−1) = |Gk−1 − Gk |
Number of Added Filters. N AF (qk , qk−1) counts the number of filters of qk that were not filters of qk−1.
N AF (qk , qk−1) = |Pk − Pk−1 | (1) (2) (3)
Description Number of added levels Number of deleted levels Number of added filters Number of deleted filters Number of added measures Number of deleted measures Aggregation depth
Filter depth
Table 1: Query features
Number of Deleted Filters. N DF (qk , qk−1) counts the number of filters of qk−1 that are not longer used in qk .
N DF (qk , qk−1) = |Pk−1 − Pk |
Number of Added Measures. N AM(qk , qk−1) counts the number of measures of qk that were not measures of qk−1.
N AM(qk , qk−1) = |Mk − Mk−1 |
Number of Deleted Measures. N DM(qk , qk−1) counts the number of measures of qk−1 that are not longer used in qk .
N DM(qk , qk−1) = |Mk−1 − Mk |
Aggregation Depth. Adepth(qk ) measures the granularity of qk in terms of the depth of each level in its hierarchy. It can be seen as the number of drills down necessaries for obtaining Gk from the most aggregated group-by set. Let depth(дi ) be the depth of level дi in the hierarchy hi to which it belongs (ranging from 0 if дi is the top level of hi to |hi | − 1 if дi is the bottom level of hi ):
Adepth(qk ) = depth(дi ) (4) (5) (6) (7) Õ дi ∈Gk
Filter Depth. Fdepth(qk ) measures the number of filters appearing in qk .
Fdepth(qk ) = |Pk | (8)
In what follows, we represent an OLAP query in the space of query features, i.e. as a 8-dimensional vector, each position corresponding to one of the features described above. This representation is at the core of our proposal for computing the similarity between queries and then between explorations. It focuses in operations between queries and is independent of the underlying data cube, i.e. a given sequence of operations, even on diferent data cubes, will result in the same sequence of query vectors.
Example 1. Consider an exploration e1 composed of 4 queries: q1 = ⟨{year }, ∅, {qty}⟩ – sales quantity per year; q2 = ⟨{year }, {year = “2019”}, {qty}⟩ – adds a filter; q3 = ⟨{year, country}, ∅, {qty}⟩ – unfilter, drill-down; q4 = ⟨{year, city}, ∅, {qty, amount }⟩ – drill-down, adds measure; Vector for q1, ⟨1, 0, 0, 0, 1, 0, 1, 0⟩, indicates an added level (year) and an added measure (qty) w.r.t. the empty query; last positions correspond to aggregation and filter depths. Vectors for q2, q3 and q4 indicate the diferences w.r.t. previous queries and the changes in aggregation and filter depths: ⟨0, 0, 1, 0, 0, 0, 1, 1⟩, ⟨1, 0, 0, 1, 0, 0, 2, 0⟩, ⟨1, 0, 0, 0, 1, 0, 3, 0⟩, resp.
Finally, we use cosine similarity for computing similarity
between queries. This measure is adapted to compute similarity of
two vectors and is normalized in [
This section describes our proposal of Contextual Edit Distance: definition and implementation issues.
CED is a generalization of the Edit Distance that incorporates the following requirements: (1) Context-dependent cost: Edition cost depends on the similarity of nearby queries. The more similar and closer the queries, the lower the cost of operation. (2) Repetition: Edition of repeated close queries has low cost. (3) Permutation: Similar and close queries can be exchanged with a low cost.
Example 2. Consider an exploration reflecting an exploratory behavior at the beginning (many changes in measures and group by set) and more focus at the end (drilling and filtering). We can sketch it as follows (where L, F and M means level, filter and measure, + means addition and - means deletion; we skip aggregation and iflter depth for simplicity): ⟨ +D+M, +M, +M, +D, +M-M, -M+D, -D+D, +F+D, +F+D, +F, +F ⟩.
Consider the insertion of a query adding an additional measure (+M). The edition cost should be low if the query is inserted at the beginning (as it is similar to near queries), even lower at positions 2 to 4 (because repeating the same operations), but high at the end.
This requirements ensure that explorations reflecting a given pattern (e.g. sequences of drill-downs) are judged to be very similar no matter the exploration length (i.e. how many drilldowns) nor the underlying data (which data was drilled-down).
We remark that although this paper deals with explorations, CED definition and properties are independent on the type of explorations, the type of queries and even the nature of data. Indeed, CED can be adapted to any type of sequence on an alphabet of symbols provided that exists a similarity metric among them. 4.1
The main contribution of CED is the modification of the cost function γ which generalizes the classical definition of Edit Distance and takes into account the local context of each query in the exploration. Intuitively, the cost of an edit operation will be lower if the edited query (e.g. a query to be added to an exploration) is similar to nearby queries (e.g. the queries that are near the position where the query is added). This notion of local context is modeled as a context vector, which controls the zone of influence of the context. This subsection presents these concepts and a formal definition of CED.
Let Q be the set of all possible queries over a cube schema S
and Q∗ the set of all possible explorations on Q. For the following
definitions, let e = ⟨q1, ..., qn ⟩ be an exploration, qk be a query
in e, 1 ≤ k ≤ n, and qx be a new query to be edited in e. These
notations are partially adapted from the formal language theory
community and particularly from [
CED extends the set of edit operations of Edit Distance (usually modification, addition, deletion) to take context into account.
Definition 4.1 (Contextual edit operation). A contextual edit operation o is a function o : (Q∗ × Q ∪ {ε } × N) → Q∗ whose arguments are an exploration, a new query to be included in the exploration (or none) and the index (position) in the exploration where the edition takes place. We consider the following set O = {mod, add, del} of edit operations: • mod : (e, qx , k) 7→ q1, ..., qk−1, qx , qk+1, ..., qn
Replace the query at index k by the query qx . • add : (e, qx , k) 7→ q1, ..., qk−1, qx , qk , ..., qn
Insert query qx at index k. The queries at and after index k are shifted forward. • del : (e, ε, k) 7→ q1, ..., qk−1, qk+1, ..., qn
Delete the query at position k. The queries after position k are shifted backward.
Given an operation o(e, qx , k), a context vector is a numeric vector that indicates the level of influence of nearby queries for this operation, being stronger near index k and softening farther. We use the context vector for weighting the similarity between queries. Intuitively, the context vector quantifies the relationship between a query qx and another query qi . Thus, the greater vi , the greater the impact of query qi on qx . A seed function is used to generate context vectors.
Definition 4.2 (Context function and context vector). Consider
a contextual edit operation o(e, qx , k) and a seed function fk :
N → [
The third property guarantees to take with the same importance previous and future queries located at equal distance from qk .
A context function φo : N∗ → [
if x ≥ k
fk (x + 1) if x ≤ k − 1
• φdel(x ) = 0 if x = k
fk (x − 1) if x ≥ k + 1
Finally, a context vector v : O → [
About add and del contextual vector functions: • For an insertion add : (e, qx , k), query qk−1 and qk are fully taken into account for the addition of qx in e because we insert qx between index k − 1 and k i.e. φadd(k − 1) = 1 and φadd(k) = 1. • For a deletion del : (e, ε, k), the absence of the query qk in e is quantified in relation to the remaining of e i.e. φdel(k) = 0.
φ"##
1 x − 4 2 f4 = exp (− 2 ( 2 ) ) o = "## : (e, q x,4) q 1 | q 2
q 3 {ez q 4 }
Example 3. Consider the operation o = add(e, qx , 4), adding a query at index 4 of an exploration. Figure 2 illustrates the computation of φadd (plotted in blue) from a given seed function (in red). The corresponding context vector is v(o) = ⟨0.61, 0.88, 1, 1⟩. It indicates that the similarity score of queries at indexes 3 and 4 is fully considered (weight of 1) while a lower score is considered for query at index 1.
The cost function γ of CED generalizes the classical definition of Edit Distance and takes into account the local context of each query in the exploration. is defined as:
Definition 4.3 (Cost function γ ). Given an operation o(e, qx , k),
a cost function γ : O → [
If α → 0 the contextual part is maximal and therefore the distance between two queries will be strongly evaluated according to the content of the exploration being edited ; • δ (o) =
1 if α → (1 then cost of edition is fixed.
1 − sim(qk , qx ) i f o = mod is the local cost of the Edit Distance.
else queries, computed as the cosine of query vectors.
• sim : Q × Q → [
cos(q3, qx ) × φadd(3) ® cos(q4, qx ) × φadd(4) ¬ = 0.1 + 0.9 1 − max 0.94 × 0.88 ª © ® ® = 0.1 + 0.9 «× (1 − 0.83) = 0.25 distance from an exploration e1 to an exploration e2. « such that:
Definition 4.5 (One-sided Contextual Edit Distance). Let d˜C ED : Q∗ × Q∗ → R+ be the Contextual Edit Distance from e1 to e2 (10) ˜ dC ED (e1, e2) =
min P ∈ P(e1,e2) i=1 Õ|P| γ (oi )
In this form, CED would be very similar to Hausdorf distance
[
Definition 4.6 (Contextual Edit Distance).
Q∗ → R+ be the Contextual Edit Distance such that: Let dC ED : Q∗ × dC ED (e1, e2) = max nd˜C ED (e1, e2), d˜C ED (e2, e1) o (11) 4.2
computation of CED.
We can compute dC ED using a Dynamic Programming approach
like the classical Edit Distance [
Algorithm 1 computes the context vector and the cost function
(as in Equation 9). Note that φo : N∗ → [
v(o) ← v(o) · ⟨φo (i)⟩ v(o) ← ⟨⟩ for i ∈ ⟦1, |e |⟧ do vsim ← ⟨⟩ for i ∈ ⟦1, |e |⟧ do if e = mod then else δ (o) ← 1 vsim ← vsim · ⟨sim(qi , qx ) × vi (o)⟩ δ (o) ← 1 − sim(qk , qx ) return α × δ (o) + (1 − α ) × (1 − max(vsim )) time: and |e2 | = p.
algorithm Ai , with i ∈ {1, 2, 3}.
Next, we prove that the computation of CED is polynomial in Theorem 4.7. CED is in O(n × p × max(n, p)) where |e1 | = n Proof : Let’s note T (Ai ) the big O time complexity of the • T (A2(e1, e2)) = n × p × T (A1(o : e1, qx , k)) • T (A1(o)) = |e | where e is the edited exploration. • T (A2(e2, e1)) = n × p × T (A1(o : e2, qx , k)) • T (A3(e1, e2)) = T (A2(e1, e2)) + T (A2(e2, e1)) = n2 × p = n × p
2 = n2p + p2n ∈ O(n × p × max(n, p)) max(n, p)).
As a result, the Algorithm 3 has a time complexity in O(n × p × □ else Algorithm 2: One-sided Contextual Edit Distance d˜C ED
Result: One-sided Context Edit Distance d˜C ED (e1, e2) D ← [0...|e1 |][0...|e2 |] for i ∈ ⟦0, |e1 |⟧ do for j ∈ ⟦0, |e2 |⟧ do if i = 0 ∨ j = 0 then
D[i, j] ← i + j omod ← mod : (e1, q(j2−)1, i − 1) odel ← del : (e1, qi(1−)1, i − 1) oadd ← add : (e1, q(j2−)1, i − 1) D[i, j] ← min{
D[i − 1, j − 1] + γ (omod), D[i − 1, j] + γ (odel), D[i, j − 1] + γ (oadd) } Algorithm 3: Contextual Edit Distance dC ED
Result: Context Edit Distance dC ED (e1, e2). o return max nd˜C ED (e1, e2), d˜C ED (e2, e1) 5
Our objective is to cluster together explorations showing the same user behavior. To this end, we pair CED to an of-the-shell clustering algorithm, and we test it against several workloads concerning users with varied analytical skills and diferent UI, aiming to discover diferent types of patterns. In addition, as some datasets come with a ground truth, they allow for the quantification of clustering quality and the comparison to state of the art distances. The following subsections describe the workload used in experiments, the experimental protocol and implementation details. 5.1
In our experiments, we reuse several workloads described in
the literature [
Real explorations on ipums data. The first workload,
henceforth dubed Ipums, consists of navigation traces of OLAP users
collected during the testing phase of the development of Falseto
[
During a preliminary analysis of the workload, Aligon et al. labelled explorations distinguishing five analysis styles: • FOCUS. The exploration is more focused as time passes, • OSCILLATE-FOCUS. The exploration is more exploratory (the levels of detail and filtering oscillate) at the beginning but is more focused at the end, • OSCILLATE. The exploration is always exploratory, • FIX. The exploration keeps constant levels of detail and ifltering, • ATYPICAL. The exploration has atypical or erratic behavior.
Real explorations on open data. The second workload,
henceforth dubed Open, consists of navigation traces collected in the
context of a French project on energy vulnerability. These traces
were produced by 8 volunteer students of a Master’s degree in
Business Intelligence, answering fuzzy information needs defined
by their lecturer, to develop explorative OLAP navigations using
Saiku2 over three cubes instances [
Real explorations on cyber security data. The third workload,
henceforth dubed Security, consists of analysis sessions made by
real analysts in the context of the "Honeynet Project" [
Even if there is no ground truth for this workload, it is interesting because queries were devised by expert analysts.
Artificial explorations. The last workload, with artificial data,
comes from the Star Schema Benchmark [
Instead of using the rather limited SSB workload, we generated
artificial explorations using CubeLoad [
Firstly, when we have some knowledge qualifying explorations, even if it is not exactly a ground truth, we compare our results to such knowledge. For the artificial explorations we compare the obtained clusters with the Cubeload templates used for the generation of the workload. This experiment aims to show that our approach is able to cluster together all the explorations corresponding to a given template. For the ipums workload we compare to the preliminary labels assigned by Aligon et al. Actually, such labels are not a ground truth, as there were not produced with the goal of clustering explorations, but they may provide a nice idea of the quality of the exploration. We report Adjusted Rand Index (ARI) and V-measure (harmonic mean of clusters homogeneity and completeness) scores3, and we compare our clustering scores to those obtained with ED and AD distances.
Second, for the four workloads, we report further scores concerning intrinsic cluster quality. Indeed, too few clusters will mix diferent behaviors, too many clusters will overfit user behavior. We aim to balance: number of clusters, cluster diameter (the distance between the farthest objects in the cluster) and mean Silhouette Coeficient (a measure of how similar an object is to its own cluster (cohesion) compared to other clusters (separation)). Silhouette scores3 are merely informative in out tests, as the metric is more adapted to hyper-spherical clusters.
Finally, we study the medoids of each cluster (the exploration that is the most similar to all other explorations in the cluster) and we manually observe the OLAP operations of the medoid for providing an explanation of the concerned behavior pattern. 5.3
Our methods are implemented in Python, using Scipy, Sklearn
[
1 2√k + 1(x − k) fk (x ) = exp ©− 2 |e | ª ® « ¬
It is a Gaussian function centered at k, therefore satisfying
the properties announced in Definition 4.2. Furthermore, it is
!2
3Metrics for clustering performance evaluation are well described in
https://scikit-learn.org/stable/modules/clustering.html sect. 2.3.10.
[
As we do not know, a priori, the form of clusters, nor their density, we use a hierarchical clustering algorithm, which provides more flexibility than hyper-spherical and density-based algorithms. In addition, it outputs a dendrogram that allows to parameter the setting of number of clusters and eases the visual analysis of clusters. In order to find a good balance, we experimentally combine some criteria to cut the dendrogram: relative loss of inertia, cluster diameter and minimum number of clusters. We use the Ward method as agglomeration criteria.
Finally, a correlation study among query features revealed that Fdepth was highly correlated with Adepth in all workloads. In consequence, we excluded Fdepth from query vector. 6
In this section we report the results of the experiments conducted to validate our proposal. 6.1
In this experiment on Artificial and Ipums workloads, we compared the clusters obtained with our method to the available ground truth (i.e. the template used to generate each exploration and the preliminary classification of Ipums).
Figure 4 (a and d) shows the obtained dendrograms. Explorations (identified by numbers) are arranged in the horizontal axis, plotting similar explorations close (according to CED). Links indicate which explorations are clustered together, shorter links meaning more similar explorations (vertical axis reports distances). Links of the same color represent a cluster, while dotted links just indicate inter-cluster distances. For easing the interpretation we also color explorations ids, according to ground truth labels. We deliberately chose the same set of colors as clusters to visually highlight the good matches.
Artificial workload. The dendrogram exhibits a perfect match among CubeLoad templates (Slice and Drill, Slide All, Exploratory and Goal Oriented, described in Section 2) constituting well separated clusters. We expected a good result with this workload, as CubeLoad templates are well diferentiated.
Colored Dendrogram ( 4 groups) (a): CED on Artificial
(d): CED on Ipums Oscillate focus
Focus and Fix _P _S _Z J_ _F V _B L Q AA _T _U R X _Y 0 6 0 4 0 3 0 2 0 1 0 2 0 1 ICAL explorations. However, it fails to distinguish between OSCILLATE-FOCUS and OSCILLATE explorations, the frontier being quite fuzzy, and FIX explorations are not distinguished from FOCUS ones. We remind that these labels are not a real ground truth, but a preliminary classification for other purpose. Table 2 indicates ARI and V-measure scores.
In this experiment we compare the clusters obtained using 3 distances: CED, ED and AD. Results are reported in Table 2 and in both Artificial and Ipums workloads on both quality metrics.
With ED, clusters reflect exploration sizes instead of query operations. For example, in Figure 4(e) the first cluster includes short explorations, the second cluster contains the longest ones, and the last cluster contains medium ones. Conversely, AD relies
In addition to ARI and V-measure scores (calculated w.r.t. a ground truth), we computed cluster diameters and Silhouette scores to complete our quality analysis. Results are reported in Table 3 for the 4 datasets.
Globally, we observe that most diameters are low, indicating that clusters are compact. Therefore, medoids are good representatives of each cluster. Most Silhouette scores are also positive, which is a good result given that our clusters are not hyperspherical. In particular, we note that even if CED was able to generate a pure partition for the Artificial workload, we observe a low Silhouette score. 6.4
The next experiment clusters students explorations of the Ipums and Open workloads. We manually examine some explorations of each cluster, including the centroid, with the goal of abstracting students explorations patterns.
Ipums workload. The 27 explorations are arranged in 4 clusters of diferent sizes.
Clusters of explorations represent the following behavior: • The 2 explorations in the first cluster start by many changes in the measure set (as trying to choose the good measures), followed by a long period of filter/unfilter operations, combined with some drill-downs and roll-ups, but with little changes in the level of detail. • Globally, explorations in the second cluster alternates drilldowns and roll-ups. Some of them include a few filters, but most of them (this is the case of the medoid) do not iflter any data. • The 3 explorations of the third cluster start alternating drills down and rolls up (as in cluster 2), then alternate iflters/unfilters, some of them focusing at the end (as in cluster 4). This cluster has common points with clusters 2 and 4, some kind of intermediate behavior. • The last cluster includes focused explorations, which regularly increase the level of detail and filtering by adding drill-down and filter operations. Some of them mix other operations, mostly at the beginning, but drill-downs and iflters are the predominant operations.
From a more general perspective, our study shows that half of the explorations follow a focused pattern (cluster 4) translating that those students have developed a particular type of analysis skills, while other students are more exploratory (cluster 2), perhaps translating a lack of maturity in their analysis skills, perhaps just showing their style. Clusters 1 and 3 depicts outlier behaviors.
Open workload. Our method organizes the 28 explorations in 6 clusters, 3 of them containing an outlier exploration, the first one being very diferent from all the others (inter-cluster distance around 50).
The interpretation of clusters is harder for this workload, as Saiku tool produce very longs explorations (the longest in this workload counts 127 queries). So manual inspection of explorations is tedious and may lead to judgement errors. With this disclaimer, we summarize the behavior represented by clusters as follows: • The outlier in first cluster is the shortest exploration (4 queries), whose queries are fully aggregated (only ALL levels), and operations only change measures. • The second cluster contains 10 explorations, many ones being very short, including the medoid. A general behavior is a constant or lightly increasing level of detail, sometimes being high, sometimes medium. Most explorations (except one) have little filters, but exhibit some changes in the measure set. • The third cluster contains 7 explorations, all of them continuously increasing the level of detail and filtering. There are multiple drill-downs and multiple filters all along the explorations. • Cluster 4 contains another outlier clustered alone. It exhibits several abrupt changes in the level of detail with several peaks, continuous changes of measures and some iflters in the middle. • Another exploration also clustered alone. It also shows many abrupt changes in the level of detail, with some changes in filters and measures at the beginning and an increase in the filter level at the end. • The last cluster contains 8 explorations. Its medoid has no iflters nor changes in the measure set. OLAP operations include only drill-downs and roll-ups, with an increase of the level of detail in the middle, decreasing at the end of the exploration. Other explorations in the cluster include other OLAP operations. The common behavior resides in the increasing-decreasing pattern in the level of detail.
In conclusion, this clustering confirmed some of the already identified patterns and enabled to discover a new one. Specifically, cluster 3 corresponds quite well to the Focus cluster of Ipums workload and the Slice and Drill template of CubeLoad; while cluster 6 corresponds to the Oscillate cluster of Ipums (having no equivalent template in CubeLoad). The new pattern, reflected by cluster 2, corresponds to less skilled students, making timid usage of OLAP operations (some drill-downs and roll-ups, few filters, some changes of measure). The recognition of outlier behavior is another strong point of our method. 6.5
This experiment shows the application of our approach to a larger workload, whose explorations were devised by expert analysts using an advanced IDE interface. Surprisingly, many explorations of the Security workload contain only one query (260 out of 723); we excluded them from the study. Another interesting point is that there are long sequences of repeated queries (i.e. the exploration contains many times the same query). This may reflect movements in the way query results are arranged and visualized, while referring to the same underlying query.
There is no ground truth and a manual observation of the 723 explorations is not doable, however, we provide some general comments and a detailed analysis of the medoids of the 5 retrieved clusters (and some randomly picked explorations): • Explorations in cluster 1 do many movements in the group by set, oscillating the level of detail, with some peaks in
and few filters. the middle. There are other operations; the medoid does many changes in measure set. • Cluster 2 contains many long explorations, which characteristic is the alternation of adding and deleting one fragment (a level in the group by set, a filter or a measure). • Explorations in the third cluster are highly similar (many distances are around 0). It includes many short explorations (as the medoid), with few operations, mainly drill• Explorations in cluster 4 have very few operations, and globally exhibit long subsequences of identical queries. • In the last cluster, queries have constant level of detail (generally low), with some movements in the group by set As expected, analysts’ behavior is diferent from students’. Globally, their explorations exhibit less operations, with more emphasis in the grouping of data, probably also in their arrangement and visualization (which is not captured in our method) of the data; while students are more click-oriented and produce longer explorations with much more operations.
Clusters 3 and 4 evidence this behavior and Cluster 2 is some kind of generalization of the Slice All pattern of CubeLoad. Clusters 1 and 5 coincide with those of the other workloads. Table 4 summarizes the discovered patterns. 7
This paper addressed the problem of learning analysis patterns in OLAP explorations, which is a hot topic for the understanding of human behavior and providing IDE support. Concretely, we propose to cluster similar explorations using a Contextual Edit Distance, and then extract analysis behavior from clusters. CED is a new distance that is well-suited for comparing explorations taking into account their local context, and then lowering the edition cost of similar queries, repetitions and permutations. Our experiments with four workloads allowed to detect CubeLoad templates and to learn some new analysis patterns from students and expert analysts explorations. Even if these results are promising, our method needs to be tested in larger workloads, with varied skilled and non-skilled users and diferent types of user interfaces, before abstracting more general patterns.
As future work, we plan to tune our method and study its sensibility and robustness with respect to CED parameters, query features and query similarity. We would also like to compare our results to other clustering methods and distances. Our long term goal is to automatically classify explorations and qualify users skills, allowing the recommendation of pertinent next queries, among other applications.
Finally, we remark that CED is not endemic to analysis
behavior and it can be adapted to study other types of human behavior
(provided that such behavior could be represented as a sequence
of symbols). In particular, we have used CED for comparing
human daily moves [
The authors would like to thank Nicolas Labroche for their useful insights on clustering quality. This work is partially supported by French ANR Agency, in the context of Mobi’kids project.