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 38th 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.
![photo of M. Tamer Özsu and Anil Pacaci](/sites/default/files/uploads/images/m-tamer-ozsu-anil-pacaci-1500-pixels.jpg)
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.
![photo of Professor Angela Bonifati](/sites/default/files/uploads/images/angela-bonifati.jpg)
“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.”