Anil Pacaci, M. Tamer Özsu, colleague Angela Bonifati receive best paper award at ICDE 2022

PhD student Anil Pacaci, University Professor M. Tamer Özsu, and their colleague Professor Angela Bonifati from Claude Bernard Lyon 1 University in France have received a best paper award at ICDE 2022, the 38^th IEEE International Conference on Data Engineering. 

Their paper, “Evaluating Complex Queries on Streaming Graphs,” introduced a foundational model to efficiently query streaming graphs, a complex type of data structure that evolves over time and is ubiquitous in today’s big data era.

L to R: University Professor M. Tamer Özsu and his PhD student, Anil Pacaci. Professor Angela Bonifati’s photo is inset in the article.

Anil’s research focuses on scalable systems to manage fast streaming data, with a primary focus on graph-structured data. He works on online query processing over streaming graphs, exploring new algorithms and system architectures for persistent query execution on large streaming graphs.

Graphs model complex interactions in applications that range as widely as analyzing relationships and interactions in social media networks to monitoring data flows in communication networks to recommending consumer purchases on ecommerce platforms. 

Many applications produce and process enormous amounts of data that can be modelled naturally as a streaming graph. Twitter’s recommendation system, for example, processes some 12 thousand events per second to determine which tweets appear in a person’s feed at any given time. 

Efficient querying of streaming graphs is a crucially important task for applications that monitor complex patterns and relationships. Querying over static graphs is difficult and the subject of much research, but querying over a streaming graph is considerably more challenging.

Existing systems have failed to support streaming graph workloads because of the complexity of graph queries and the nearly boundless growth of real-world streaming graphs. Many applications have relied on specialized solutions tailored to their specific needs, and the approach used typically either maps queries to well-known relational primitives, or requires the design of one-off execution algorithms for different query types. A comprehensive, generalizable solution requires combining two exceedingly difficult problems — graph querying with streaming data processing. 

“We introduced a foundational model for efficient querying of streaming graphs,” explains Anil. “The diverse requirements of real-world applications required our rethinking the components of the well-established query processor architecture.”

To address these requirements in a principled manner, the research team first designed a formal model to express streaming graph queries, then developed an algebraic framework as the basis of a general-purpose query system. 

Streaming is difficult because the entire graph is never fully available, and the arrival rate of graph edges may be extremely high, requiring fast incremental operators, explains University Professor Özsu. 

“We solved this by developing a formal query model, an algebraic basis for graph query systems, then implemented a prototype of it — an extensive experimental analysis over real and synthetic datasets, demonstrating both the proposed approach’s feasibility and its performance gains,” University Professor Özsu said. “To the best of our knowledge, this is the first research that investigates the design of a streaming graph query processor, and introduces an end-to-end solution to evaluate streaming graph queries with complex constructs.”