- Hi everyone, I'm Meraj,
I'm a PhD student at The Ohio State
and I work with the interactive data systems group
which is led by my advisor Arnab Nandi
and despite the introduction,
this talk is not about time travel.
So, a quick overview of this talk:
first, I'll go through the motivation behind this work,
which is "how do you enable interactive
"data exploration over clash data volumes?"
and then I'll walk through very high overview of
existing solutions, a classification
of the existing solutions and techniques,
and then I'll present typical user interaction behavior
and typical characteristics
of certain user interaction widgets
that the current techniques do not utilize
and how we actually exploit those
to come up with better prefetching and caching strategies.
Then I'll present the performance evaluation for the system.
and I'll end the talk with the takeaways
and a brief discussion of future work.
So, the motivation behind this work -
data-driven analysis, the entire process
has pretty much become a lot about ad-hoc explorations
and this has shifted the traditional
database interaction paradigm
from the question answering style of interaction
where users used to basically submit a single query
then wait for the result.
Now you have interfaces like maps or range sliders
and you basically are issuing queries
almost at the rate of screen refresh - which is a lot,
and if there are multiple kinds connected to the back end
this can overwhelm your database,
so the idea is to have this caching layer,
a middleware, buffering the database
from this sort of work load.
So, it's kind of obvious that an interactive interface
which updates in real-time is kind of a hard requirement
for ad-hoc explorations, but then,
users generally prefer interactive visualizations
even if it does not really help them
in performing a specific task,
and we always had this intuition,
we did a user study to validate it.
It was a very simple task -
a pre-specified date selection,
you just had to select a date range,
and we had three different interfaces:
the first interface was basically
just a from and to date text input box,
but you also had associated calendar widgets with it,
so you could just select the dates on the calendar
and you didn't really have to type.
The second interface was a range slider
and you basically select the range on the slider,
but the associated result, which was basically a histogram,
and that result was not updated
until the user was done performing the selection
or they could explicitly issue the query
by clicking a button,
and the third interface was an interactive interface
where, when the user would move the slider handle,
the visualization would update in real time,
and we employed 24 users, divided them in groups of eight,
and to each user we showed two of these interfaces,
so the first one is the interactive version,
which basically updates in real time
with the slider handle movement,
and there was a clear preference for it.
We also measured the task response time,
but there was no difference in the task response time
across all three interfaces.
In fact, most of the users performed,
completed the task faster with the text input one
which is the least interactive,
because they just had to select the date
on the calendar, and we set the calendar
to be current year,
the year that they had to select.
So, most of the solutions enabling
interactive data explorations,
you could classify them in these three techniques:
the first one is query-rate limiting,
which is very common in web apps.
The bouncing and throttling you basically
limit the number of queries which can be issued
in a fixed range of time,
or, and you set the minimum threshold between consecutive,
time threshold between consecutive queries,
or you could prefetch and cache results
or if it's a semantic data cache,
you can prefetch and cache data into a cache
for the speculated or predicted queries
that you probably would issue in the future,
or there are approximate query processing techniques
where you would sacrifice accuracy for faster response time.
Our work basically uses all of these techniques
and hopefully can make these better.
So, these are the two main characteristics
which we use,
so a typical user interaction behavior,
there's some sort of predictable interaction pattern
or directionality to it.
If there is a fixed axis of motion,
like in a range slider you can only move linearly,
or even if it's a map you can predict the direction.
Even though there are prefetching techniques
which actually exploit the directionality of the motion,
none of them actually use the queried rate -
how fast the queries are generated,
or how many queries are generated
in a specific interval of time, which we do,
and there are certain UI widgets now
which have inherent physics associated with them.
So, you have controls which basically simulate
friction, inertia, springiness,
like most smart phones, scrolling the list,
just a quick flick initiates the list
and without any further interaction from the user
the list accelerates very quickly
and then it starts slowing down gradually
and its a very gradual motion,
as if it's sliding under friction,
so the main part about that
is that's a simulated motion,
and you can predict that entire motion
at the very start of the user action.
So, for example, this is -
the top image shows the range, range slider handles
ghosted out trace at every 100 millisecond
for a fixed range selection.
So, if you see, at the very start,
the traces are separated far apart,
which means queries are being issued at a very high rate,
and then it slows down towards the goal query,
or towards the target,
and the bottom image is basically showing
the displacement over time,
at the start, the queries are being generated
at a very high rate,
that basically being the point,
and this is a displacement over time trace
for a range slider which simulates friction,
and if you notice this is a very perfect parallel curve
of the velocity over time,
and you notice at the start at the action,
so you can probably utilize the
design prefetching strategies.
So, how do we use these?
The first technique - interaction-rate aware prefetching,
so, once you know what's the rate of query
being issued at any instant, how do you use that?
So, for most prefetching techniques,
it's, after a cache miss, you've prefetched
a certain number of query results,
or a fixed range of data bound,
but if the queries are being issued at a very high rate,
but cover a larger data bound in a shorter time
compared to queries being issued at slower rate,
so for high-speed interactions,
you should ideally be prefetching larger data bounds.
Similarly, when the user is issuing queries
at a very high rate, so, like,
the case of range slider,
the initial interaction, the user is basically
just zipping through a very large portion of data,
so they are probably not interested in it,
and they are not waiting enough
to observe the feedback from the system.
So, that could probably mean
that you can relax the accuracy constraint
for those queries.
And finally, the physics-aware
prefetching and approximation.
Any widget which has this dataministic physics
associated with it, and you can datamine the entire motion,
at the initiation of user action.
You can generate the entire workload,
the query workload for the session at the very start,
and issue it to the back end, and that's what we do.
So this is an overview, a simplified overview
of flux capacitor.
A query comes in from the UI,
it is annotated with its motion characteristics,
basically what speed the interaction rate is at that point,
and then we have a client-side query processor,
which basically keeps checking the front end cache
for, it's a semantic data cache,
so it checks what data bounds it is currently maintaining,
and if the front end cache doesn't have
the required data extent,
to answer the query,
it would issue a partial data query to the server
and this is all aggregated at the front end
and then it issues the result to the UI.
The motion analyzer part it is clubbed
with the de-bouncing and throttling logic
of the interface - so basically
that's something that you are doing anyway,
so there is no additional cost to it.
I present the performance evaluation that we did for this.
The dataset is the 3D Road Network
from UCI machine learning repository.
We used this because the work that we used for
performance evaluation,
those are traces from one of the previous works by my group,
so we already had range slider query tracers
from a lot of users,
and the metrics used for evaluation are data stalls,
which is basically the time when the UI is stalled
waiting for a feedback from the back end
and how many times the UI stalls,
so whenever the UI stalls for data,
that basically shows up as lag for the user
and how long are those data stalls?
And the second, the latency,
the average query response time.
So, the first workload is a timestamped sequence
of queries generated from the selection of specified
latitude and longitude range,
and, the front end cache is an R-tree,
and the baseline setup we use for evaluating
our interaction rate strategy
is a simple directional prefetching strategy.
Now, with most directional prefetching strategies,
you prefetch a certain fixed range of data on a cache miss.
Here we chose to prefetch five percent
of the entire data range on every cache miss.
Now, that's not exactly arbitrary,
we tried out multiple fixed ranges,
and longer ranges would lead to longer data stalls,
because those are larger data bounds
and it would take more time -
the network latency would be higher,
and if we reduced that data range,
it would just lead into more stalls.
So, the interaction-rate aware prefetching strategy
basically leads to fewer stalls, two,
compared to the baseline setup of five,
and the stall time is almost half of the baseline setup,
which leads to the overall interaction time being shorter.
Now, for the physics awareness study,
we did not exactly have traces from users
and that's also because we are starting
this arbitrary flick of the slider handle,
it's not a specified range selection.
So we have three different setups.
The first one is exact caching,
where we are not approximating the results,
so this is basically the interaction rate
of our prefetching cache from the previous results.
The second one is the approximate caching setup
where we process the queries
on different sample-rate,
so for queries which are issued during high-speed regions,
they are processed at a lower sampling rate
and queries which are really close to the goal query
they are processed on the entire data,
and lastly, the physics-aware prefetching
basically generates the entire query workload at the start
and uses sampling and prefetching,
so basically same as the last one,
but you know the entire workload
at the start of the session.
So, if you notice, the physics-aware caching
basically performs the best of all three setups,
and it has the least (inaudible) ability
in query response time for individual queries,
and each of the queries pretty much under 100 millisecond,
which is generally considered
to be interactive response time.
So, takeaways from this work:
interactivity in visualizations is preferred,
even when it doesn't really help the users
in performing the task.
In fact, it might even take them longer.
Interaction-rate based directional prefetching
generally performs better than
fixed-range directional prefetching,
and you can use this with other prefetching techniques too,
like it does not have to be directional prefetching.
If you knew how the interaction pattern is,
you can still use the query rate,
and UX widgets with certain Physics-metaphors
have deterministic behavior,
enabling generating the entire workload
at the start of the user action.
Future work - so, we have quite a few
approximate query processing systems now,
where you can specify the error bounds
and the latency bounds,
and Flux Capacitor can be used
to model those constraints for those systems,
and there are quite a few data summaries
which support incremental addition, refinement
and deletion, which can be used as the cache
instead of the of the R-Tree
or sampling techniques that we use,
and some of these of these characteristics or strategies
that we used for range slider,
the results that we presented,
they would directly translate
to other interaction techniques
such as panning on a map,
and since we are using approximation techniques,
if we were to include this
in a visualization stack,
we need uncertainty visualization techniques,
which there are a lot of available,
and finally, this is something which is under review,
a data platform for shared augmented reality.
It basically has a local hindsight cache,
and we use prefetching based on localization
and path prediction,
so, some of these would also apply to that.
So, that was it, thank you for coming,
and if you have any questions I can answer them now.
(crowd applause)
- [Host] We have about a couple of minutes
for questions, so, wanna do quick ones?
Right, I can start again:
So, not sure I, maybe you said this I missed it,
what was the platform
on which you performed the experiments?
- Oh, so these are all web visualizations,
so basically the entire code is JavaScript.
- [Host] Oh, no, so it's not in terms of code.
As an end-user, was the end-user,
or the participants, were they using a mouse?
- They were using a mouse. - OK.
- [Host] So, especially because you're talking
about physics-based, you know, features,
are you, how do you think it changes
when you actually use touch,
where it's much more prevalent
in terms of how the inertia works
or how the velocity works?
- Yes, so, I actually do have preliminary results
from panning a map on touch screen.
I haven't included it in the paper,
because I'm still working on it, but...
It basically,
so this is the directional prefetching strategy
that I'm using, so it is basically
what you would expect it to be,
because the physics does not actually affect
how you are approximating the speed bands,
so the prefetching region,
it doesn't matter if you have inertial motion
or if it's just on the basis of the user's interaction.
- [Host] OK, we can talk more about it offline,
but I think... - I'm just checking if I've...
- [Host] Are there any other questions?
I just want to make sure I give the audience a chance.