A Survey on Matching Problems in Spatial Databases

PhD Qualifying Examination


Title: "A Survey on Matching Problems in Spatial Databases"

by

Mr. Cheng LONG


Abstract:

Matching is a traditional topic in computer science. Given two sets of 
objects, we want to match the objects from one set with those from the 
other set according to some appropriate objectives.

Many matching problems have been proposed in the literature. Some examples 
are Stable Marriage, Optimal Matching Problem and Generalized Assignment 
Problem. Furthermore, many algorithms have been designed for these 
matching problems. Nevertheless, most of them are not efficient enough for 
large datasets. For instance, the lower bound of the time complexity for 
Stable Marriage is quadratic and that for Optimal Matching Problem is even 
worse, cubic. Fortunately,as some researchers discovered,some of these 
performance limitations do not occur any more when the matching problems 
are studied in the context of spatial databases.

Recently, considerable research has been conducted on the matching 
problems in the community of spatial databases. Because the objects 
involved in many applications of matching are actually spatial entities. 
Some examples include emergence resource allocation, profile matching and 
facility location allocation. In this survey, we first review different 
variants of traditional matching problems and introduce some relevant 
spatial databases techniques. We then study the matching problems in 
spatial databases that have been studied recently. Besides, some variants 
of the matching problems in spatial databases are introduced. Finally, we 
conclude this survey by giving some future research directions related to 
matching problems in spatial databases.


Date:                   Friday, 13 January 2012

Time:                   10:00am - 12noon

Venue:                  Room 3501
                         lifts 25/26

Committee Members:	Dr. Raymond Wong (Supervisor)
                         Prof. Dimitris Papadias (Chairperson)
 			Prof. Dik-Lun Lee
 			Dr. Qiong Luo


**** ALL are Welcome ****