Department of Computer Science & Engineering

University of Ioannina

Department Seminars, “Efficient Indexes for Data Queries Combining Geometry with Query Processing”


Department Seminars: Lecture from Stavros Sintos, Assistant Professor, Department of Computer Science, University of Illinois Chicago,  will be held on Friday 16/12/2022 at 12:00 in Seminar Hall of Computer Science and Engineering Department.


Query processing is an important problem in many research fields, including database systems, data mining, and geometric computing. The goal is to preprocess input data into an index to efficiently answer queries. With the data sets becoming increasingly large and complex, queries are also becoming complex, therefore new challenging problems have emerged in query processing. In this presentation, I show how to use techniques and notions from computational geometry to design efficient indexes for practical and complex data queries over big data.

The first part of the talk is on designing efficient indexes for Approximate Query Processing (AQP). I present PASS, an efficient dynamic index for answering range aggregation queries by combining hierarchical spatial partitioning and stratified sampling. PASS provides theoretical guarantees on the confidence intervals, it uses low space and answers queries with low latency. Interestingly, it outperforms the state-of-the-art AQP systems on aggregation queries. In the second part of the talk, I briefly describe how various complex queries, such as top-k queries and join queries, can benefit from the design of geometric indexes. In this presentation, I mostly focus on top-k queries under certain practical constraints, like diverse top-k, durable top-k, and uncertain top-k, with various applications in online stores, recommendation systems, and computational journalism. I will conclude the talk with some future research directions.