Hippo in Action: Scalable Indexing of a Billion New York City Taxi Trips and Beyond

Abstract

The paper demonstrates Hippo a lightweight database indexing scheme that significantly reduces the storage and maintenance overhead without compromising much on the query execution performance. Hippo stores disk page ranges instead of tuple pointers in the indexed table to reduce the storage space occupied by the index. It maintains simplified histograms that represent the data distribution and adopts a page grouping technique that groups contiguous pages into page ranges based on the similarity of their index key attribute distributions. When a query is issued, Hippo leverages the page ranges and histogram-based page summaries to recognize those pages such that their tuples are guaranteed not to satisfy the query predicates and then inspects the remaining pages. We demonstrate Hippo using a billion NYC taxi trip records.

Publication
In IEEE International Conference on Data Engineering, ICDE
Jia Yu
Jia Yu
Assistant Professor (from Fall 2020)

Jia Yu obtained his PhD from Arizona State University in Summer 2020. His research interests include database systems, distributed data systems and geospatial data management.

Mohamed Sarwat
Mohamed Sarwat
Assistant Professor

Mohamed Sarwat is an assistant professor of computer science at Arizona State University. His general research interest lies in developing robust and scalable data systems for spatial and spatiotemporal applications.

Related