Summarizing Topological Relations in Large Spatial Datasets
Speaker: Dr. Xuemin Lin, Department of Computer Science and Engineering, The University of New South Wales
When: 2003-10-27 13:30:00
Venue: 78-420
Host: Professor Maria Orlowska
Abstract:Summarizing topological relations is fundamental to many spatial
applications including spatial query optimization. In this talk, we
present several novel techniques to effectively construct cell
density based spatial histograms for range (window) summarizations
restricted to the four most important topological relations:
contains, contained, overlap, and disjoint.
We first present a novel framework to construct a multiscale
histogram composed of multiple Euler histograms with the guarantee
of the exact summarization results for aligned windows in constant
time.
Then we present an approximate algorithm, with the approximate ratio
19/12, to minimize the storage spaces of such multiscale Euler
histograms, although the problem is generally NP-hard. To conform to
a limited storage space where only k Euler histograms are allowed,
an effective algorithm is presented to construct multiscale
histograms to achieve high accuracy.
Finally, we present a new approximate algorithm to query an Euler
histogram that cannot guarantee the exact answers; it runs in
constant time.
Our extensive experiments against both synthetic and real world
datasets demonstrated that the approximate multiscale histogram
techniques may improve the accuracy of the existing techniques by
several orders of magnitude while retaining the cost efficiency, and
the exact multiscale histogram technique requires only a storage
space linearly proportional to the number of cells for the real
datasets.
(A joint work with Qing Liu - UNSW, Yidong Yuan -UNSW, and Xiaofang
Zhou - UQ)
Biography:Dr. Xuemin Lin is a senior lecturer in the school of Computer
Science (CSE) and Engineering at the University of New South
Wales. Currently, he is leading the database research group in CSE
at UNSW. His research interests lie in database systems and graph
visualization. In the last 10 years, Xuemin has published about 70
papers in highly prestigious journals and conferences, and received
a number of research grants from the government and industry.
Type: ITEE Seminar
Contact:Professor Maria Orlowska, seminar host (maria@itee.uq.edu.au)
or Guido Governatori (ITEE seminar co-ordinator)
(guido@itee.uq.edu.au)