K-NN Queries with Operating Time Constraints in Time-Dependent Road Networks”

Speaker:        Professor Mario A. Nascimento
                Department of Computing Science
                University of Alberta

Title:          "K-NN Queries with Operating Time Constraints in
                 Time-Dependent Road Networks”

Date:           Friday, 16 May 2014

Time:           4:00pm - 5:00pm

Venue:          Lecture Theater H (near lifts 27/28), HKUST

Abstract:

We consider the problem of finding the k nearest points of interest from a
given location in time-dependent road networks, i.e., one where travel
time along each edge is a function of the departure time, and where the
operating times of the points of interest are also taken into
consideration. More specifically, we address the following query: find the
k points of interest in which a user can start to be served in the minimum
amount of time, accounting for both the travel time to the point of
interest and the waiting time, if the point(s) of interest is (are)
closed. Previous works have proposed solutions to answer kNN queries
considering the time dependency of the network but not the operating times
of the points of interest. We propose and discuss three solutions to this
type of query which are based on the previously proposed incremental
network expansion and use the A* search algorithm equipped with suitable
heuristic functions. We also present experimental results comparing the
number of disk access required by each solution with respect to a few
different parameters. (Work done in collaboration with C.F. Costa, J.A.F.
Macêdo and J. Machado.)

*******************
Biography:

Mario A. Nascimento is a professor at the Department of Computing Science
of the University of Alberta, and has served as the CS/UofA Department's
Associate Chair (2010-2013).  Before joining the University of Alberta, he
was a researcher with the Brazilian Agency for Agricultural Research
(1989-1999) and also an adjunct faculty member with the Institute of
Computing of the University of Campinas (1997-1999).  In addition, Mario
has been a (sabbatical) visiting professor at the National University of
Singapore's School of Computing (Fall/2005) and Aalborg University's
Department of Computer Science (Winter/2006).  Currently he is spending
his sabbatical leave (2013-2014) at LMU Munich and is also an Adjunct
Professor at the Federal University of Ceara in Brazil.  According to
Google Scholar (as of May, 2014) his publications have been cited 2,300+
times, earning him an H-index of 25.   Besides often serving as a program
committee member for the main database conferences, and as (co) chair of
several workshops and symposia, Mario has also served as ACM SIGMOD's
Information Director (2002-2005) and ACM SIGMOD Record's Editor-In-Chief
(2005-2007).  He is currently a member of the VLDB Journal's Editorial
Board, the SSTD Endowment's Board of Directors, and has been a senior
member of the ACM since 2007.  Finally, his main research interests lie in
the areas of Spatio-Temporal Data Management and Data Management for
Wireless Sensor Networks.  (Further information can be found at
http://www.cs.ualberta.ca/~mn.)