This category includes problems that
(i) arise in resource allocation applications,
(ii) have a spatial nature (i.e., their optimization criteria involve the notion of distance), and
(iii) are of a large scale (thus, typically requiring disk-based storage).
Although such problems have been dealt with in the operations research literature,
the solutions proposed there are targeted to in-memory processing and are suitable
for small size datasets. Our work enables efficient processing in cases where scale
is several times (or orders) larger than considered before.
Emerging Ideas and Initiatives
Suppose that a franchise plans to open k branches in a city, so that the average
distance from each residential block to the closest branch is minimized. This is an instance
of the k-medoids problem, where residential blocks constitute the input dataset and the k
branch locations correspond to the medoids, i.e., the blocks we chose to open the branches at.
In [1] we solve the k-medoid problem, assuming the existence of a spatial index on the input dataset.
Our study in this area also includes spatial versions of the optimal matching problem, one of the
oldest problems in operations research. Consider a set of customers (e.g., WiFi receivers) and
a set of service providers (e.g., wireless access points), where each provider has a capacity and
the quality of service offered to its customers is anti-proportional to their distance. Our task is to
compute a matching between the two sets such that (i) the maximum possible number of customers
are served, and (ii) the average Euclidean distance between assigned provider-customer pairs is minimized.
Although textbook algorithms exist for the general optimal matching problem, they cannot scale to medium
or large scale databases. We develop new algorithms that exploit the geometric nature of the problem, and
successfully scale to input sizes in the order of millions [2, 3]. We also study the continuous version of the problem where
(i) each service provider has a coverage region (i.e., it can only serve customers within a specific area), and
(ii) the customers move frequently and arbitrarily. The task of the processing server in this scenario is to
continuously report the optimal assignment (subject to the customers' most recent locations) in an online fashion [4].
We also consider multi-criteria decision making issues in the context of road networks (e.g., city maps).
In the context of large such networks, we take into account the co-existence of multiple distance notions in
transportation decisions. For example, the different cost notions associated with a road segment could be its
Euclidean length, the driving time, the walking time, possible toll fee, etc. The relative significance of these
proximity notions may vary from user to user, yielding different location-based preferences over the facilities
reachable via the network. In [5] we formalize preference queries over facilities located in a multi-cost road network,
and design algorithms for their efficient processing.
Selected Publications
[1] Kyriakos Mouratidis, Dimitris Papadias, Spyros Papadimitriou. Tree-based Partition Querying: A Methodology for Computing Medoids in Large Spatial Datasets. Very Large Data Bases Journal (VLDBJ), 17(4), 923-945, 2008.
[2] Leong Hou U, Man Lung Yiu, Kyriakos Mouratidis, Nikos Mamoulis. Capacity Constrained Assignment in Spatial Databases. ACM Conference on Management of Data (SIGMOD), 2008.
[3] Leong Hou U, Kyriakos Mouratidis, Man Lung Yiu, Nikos Mamoulis. Optimal Matching between Spatial Datasets under Capacity Constraints. ACM Transactions on Database Systems (TODS), 35(2), 2010.
[4] Leong Hou U, Kyriakos Mouratidis, Nikos Mamoulis. Continuous Spatial Assignment of Moving Users. Very Large Data Bases Journal (VLDBJ), 19(2), 141-160, 2010.
[5] Kyriakos Mouratidis, Yimin Lin, Man Lung Yiu. Preference Queries in Large Multi-Cost Transportation Networks. IEEE International Conference on Data Engineering (ICDE), 2010.
Projects, Presentations and Posters
- Mouratidis, K. Medoid Queries. Presentation slides of [1].
- Mouratidis, K. Spatial Optimization Problems.. Presentation slides of [2, 3, 4].
- Mouratidis, K. Preference Queries in Large Multi-Cost Transportation Networks.
Poster of [5] at ICDE 2010.
External Collaborations
-
Collaborator: Nikos MAMOULIS, Associate Professor, Department of Computer Science, University of Hong Kong
-
Visiting PhD Student: Leong Hou U, currently Assistant Professor, Faculty of Science and technology, University of Macau
