Spreadsheets are one of the most popular data analysis tools, wherein users can express computation as formulae alongside data. The ensuing dependencies are tracked as formula graphs. Efficiently querying and maintaining these formula graphs is critical for interactivity across multiple settings. Unfortunately, formula graphs are often large and complex such that querying and maintaining them is time-consuming, reducing interactivity. We propose TACO, a framework for efficiently compressing formula graphs, thereby reducing the time for querying and maintenance. The efficiency of TACO stems from a key spreadsheet property: tabular locality, which means that cells close to each other are likely to have similar formula structures. We leverage four such tabular locality-based patterns, and develop algorithms for compressing formula graphs using these patterns, directly querying the compressed graph without decompression, and incrementally maintaining the graph during updates. We integrate TACO into an open-source spreadsheet system and show that TACO can significantly reduce formula graph sizes. For querying formula graphs, the speedups of TACO over a baseline implemented in our framework and a commercial spreadsheet system are up to 34,972 × and 632 ×, respectively.

LSM-trees are widely adopted as the storage backend of key-value stores. However, optimizing the system performance under dynamic workloads has not been sufficiently studied or evaluated in previous work. To fill the gap, we present RusKey, a key-value store with the following new features: (1) RusKey is a first attempt to orchestrate LSM-tree structures online to enable robust performance under the context of dynamic workloads; (2) RusKey is the first study to use Reinforcement Learning (RL) to guide LSM-tree transformations; (3) RusKey includes a new LSM-tree design, named FLSM-tree, for an efficient transition between different compaction policies -- the bottleneck of dynamic key-value stores. We justify the superiority of the new design with theoretical analysis; (4) RusKey requires no prior workload knowledge for system adjustment, in contrast to state-of-the-art techniques. Experiments show that RusKey exhibits strong performance robustness in diverse workloads, achieving up to 4x better end-to-end performance than the RocksDB system under various settings.

Spreadsheets are a ubiquitous data analysis tool, empowering non-programmers and programmers alike to easily express their computations by writing formulae alongside data. The dependencies created by formulae are tracked as formula graphs, which play a central role in many spreadsheet applications and are critical to the interactivity and usability of spreadsheet systems. Unfortunately, as formula graphs become large and complex, it becomes harder for end-users to make sense of formula graphs and trace the dependents or precedents of cells to check the accuracy of individual formulae and identify sources of errors. In this paper, we demonstrate a spreadsheet formula graph visualization tool, TACO-Lens, developed as a plugin for Microsoft Excel. Our plugin leverages TACO, our framework for compactly and efficiently representing formula graphs. TACO compresses formula graphs using a key spreadsheet property: tabular locality, which means that cells close to each other are likely to have similar formula structures. This compact representation enables end-users to more easily consume complex dependencies and reduces the response time for tracing dependents and precedents. TACO-Lens, our visualization plugin, depicts the compact representation of TACO and supports users in visually tracing dependents and precedents. In this demonstration, attendees can compare the visualizations of different formula graphs using TACO, Excel's built-in dependency tracing tool, and an approach that does not compress formula graphs, and quantitatively compare the different response time of different approaches.