In 2011, I was traveling on the Kolkata Metro when I made an interesting observation. Nearly every passenger around me was using a computing device of some sort. Some were playing with their smartphones, some with their tablets, some listening to music on their iPod Touches. Each was a consumer of structured data of some sort; interacting with their email, Facebook, or music catalog. Weeks later, while on a flight, this pattern came up again — every seat in the plane was equipped with a touch-driven entertainment system, some used while sifting through book pages on e-Readers. Clearly, the notion of a “computer” for the future generation looks very different from the past!

Over time, we seem to be converging to a vision where we are surrounded by computing devices of varying capacities, with users performing both simple and complex tasks, with a common attribute — these devices do not possess keyboards. In 2011, smartphones and tablets outsold workstations and portable computers by 1.5x. In 2013, this ratio is projected to reach 4x. Based on this trend, non-keyboard interaction (typically in the form of gestures) is on-track to be the dominant mode of data interaction.

Gesture-driven applications pose a very different workload to underlying databases than traditional ones. Consider the idea of scrolling through a page of text, which is typically implemented as a SELECT / LIMIT query for each page, with page transitions implemented as successive queries. Most touch and gestural interfaces now implement inertial scrolling, where the speed of transitions can be superlinear. With a few successive swipes, the frontend could easily overload the query queue with successive SELECT / LIMIT queries, one for each page. Ironically, due to the high speed of scrolling, most of these results are moving too fast, and are hence ignored by the user. So, the question arises: Are today’s databases capable of handling gestural workloads? If not, what parts of the database should we fix? Should we devise a new query scheduler that can rapidly reprioritize / kill queries? (e.g., pages that the user has skipped no longer need to be queried or returned) Should we investigate bounded-latency execution? (e.g., the application needs results within Xms) Or should we change the query paradigm altogether? (e.g., query for a preview of results while scrolling is in motion, and then detailed results as the view stabilizes)

Another example of an interesting gestural interaction is that of the Interactive Join. As part of the GestureDB system we are developing in my group, the GestureQuery multitouch interface lets you compose two relations into an equijoin by simply dragging them together on the specific attributes:

In the interactive join, assuming all attributes are of the same data type, there could be M x N possible JOIN combinations, but only one is the correct intended query. We model this gesture as a query intent, a probability distribution over the space of possible queries(i.e. the M x N possible joins). Initially, the likelihood of each query is uniform, but while the user articulates the gesture, we can use the distance between attributes to compute the probability of each query.

The following interactive demo lets you play around with a real multitouch interaction trace from one of our user studies, collected from interactions with our GestureQuery iPad prototype². The subject was asked to perform an equijoin Album.ArtistId with Artist.ArtistId, dragging the two tables close to each other. Dragging the slider left to right lets you step through the recorded trace. Notice how rapidly the “Proximity Score” changes during the interaction.

This interaction is an great example of query intent transition. As the gesture is being articulated, the distribution changes rapidly. The “Proximity Score” is the score for Album.ArtistId ⋈= Artist.ArtistId, the inverse of the distance between the two tables, which can be considered the likelihood for the intent — there is a score for each pair of attributes. Thus, in order to provide a preview for the intended join, this would involve quickly executing and displaying results while the user is articulating the gesture, basing the priority on these scores.

Just like the previous example, challenges arise here. Can a database provide join results at such low latency for such a diverse number of queries being fired at the same time, given such rapidly changing probabilities? It is not practical for the database to execute them all in parallel. Given that we know the domain of possible queries, is there scope for multiquery optimization? Second, given an interactive threshold of say 100ms for the results, is it feasible (or even useful) to generate full results for all queries? Should we consider partial query execution? Or can we simply sample the tables to provide interactive (albeit inaccurate) results? Third, feedback for a query is useful only for a fleeting moment during the gesture articulation. How could we show parts (i.e. rank tuples) of the result that are most useful?

Clearly, when working with gesture-driven interfaces and application layers, the gestural workloads of database queries pose a smorgasbord of challenges, that might require rethinking of the entire database stack. As these interfaces evolve, the underlying database systems will have to keep up with changes in user expectations and demands. With the explosion of new and novel gestural interfaces, natural interfaces and casual computing lately, it’s an exciting time for database research!

References:
1. Arnab Nandi: Querying Without Keyboards: CIDR 2013 (Vision Track)
2. Lilong Jiang, Arnab Nandi, Michael Mandel: GestureQuery: A Multitouch Database Query Interface: VLDB 2013 (demo)

Blogger’s Profile:
Arnab Nandi is an Assistant Professor of Computer Science & Engineering at The Ohio State University. Arnab’s research is in the area of database systems, focusing on challenges in big data analytics and data interaction. The goal of his group’s work is to allow end-users to explore and interact with semi-structured and structured data. Prior to joining Ohio State, Arnab did his Ph.D. at the University of Michigan, Ann Arbor, with stints at Google, Yahoo! Research, and Microsoft Research.