TopKube: A Rank-Aware Data Cube for Real-Time Exploration of Spatiotemporal Data

IEEE Trans Vis Comput Graph. 2018 Mar;24(3):1394-1407. doi: 10.1109/TVCG.2017.2671341. Epub 2017 Feb 17.

Abstract

From economics to sports to entertainment and social media, ranking objects according to some notion of importance is a fundamental tool we humans use all the time to better understand our world. With the ever-increasing amount of user-generated content found online, "what's trending" is now a commonplace phrase that tries to capture the zeitgeist of the world by ranking the most popular microblogging hashtags in a given region and time. However, before we can understand what these rankings tell us about the world, we need to be able to more easily create and explore them, given the significant scale of today's data. In this paper, we describe the computational challenges in building a real-time visual exploratory tool for finding top-ranked objects; build on the recent work involving in-memory and rank-aware data cubes to propose TOPKUBE: a data structure that answers top-k queries up to one order of magnitude faster than the previous state of the art; demonstrate the usefulness of our methods using a set of real-world, publicly available datasets; and provide a new set of benchmarks for other researchers to validate their methods and compare to our own.