Retrieving unusual temporal trends effectively and efficiently with trend surfing

Abstract Locating unusual temporal trends in data is a recurrent task in various application domains. We consider a version of this problem in which it is important to understand which dimensions of the dataset are correlated with the given unusual trend. That is, given a fact table whose dimensions include a temporal dimension and whose dependent attribute of interest is numeric or categorical, we seek to locate unusual temporal trends in the data cube induced by the fact table, via user-driven or automatic navigation. Our goal in this paper is to make such navigation in search of unusual temporal trends more effective and efficient. Challenges in achieving this goal arise from the rarity of the temporal trends to be located, and from the combinatorics involved in finding nodes with unusual trends in the data cube. We show that exhaustive solutions to the trend-retrieval problems are worst-case intractable, and address the challenges by presenting a suite of tractable heuristic approaches that enable effective and efficient navigation of the data cube. Our algorithms expose temporal trends in data cubes in a strategic manner, which we call trend surfing . The proposed approaches can be used in their automated or (fully or partially) user-driven form, and involve criteria for helping users determine which temporal trends could be unusual for their purposes. We report the results of testing our trend-surfing algorithms on three real-life datasets and one synthetic dataset; these results showcase the effectiveness and efficiency of the proposed approaches against the exhaustive baseline.