Donghui Zhang's Talks

[abstract]
PrivacyPreserving Data Publishing
 CCIS Ph.D. seminar, February 28, 2008.

[abstract]
PCCSC: Profilebased and Constrained Compressed Skycube, extended from a SIGMOD'06 paper.
 UMass Lowell, October 26, 2007.

[abstract]
Algorithms in Spatial Databases (a short course)
 Renmin University, China, May 26  June 1, 2007.

[abstract]
The Skyline Query in Databases: Which Objects are the Most Important?
 CCIS Ph.D. seminar, March 22, 2007.

[abstract]
The MinDist OptimalLocation Query, extended from a VLDB'06 paper.
 UMass Boston, October 17, 2006.
 CCIS Ph.D. Seminar, November 30, 2006.
 UMass Lowell, December 6, 2006.

[abstract]
Introduction to Spatial Database Research (30 min)
 CCIS Ph.D. Open House, Mar 23, 2007.

[abstract]
Introduction to Spatial Databases
 NEU ACM Talk, Feburary 21, 2007.

[abstract]
The optimallocation query, extended from an SSTD'05 paper.
 CCIS Ph.D. seminar, November 3, 2005.
 Boston University, April 19, 2006.
 WPI, April 28, 2006.

[abstract]
Spatial Database Query Processing using Indices.
 CCIS Ph.D. seminar, October 21, 2004.

[abstract]
On SpatialRange ClosestPair Query, extended from an SSTD'03 paper.
 UMass Boston, March 12, 2003.

[abstract]
ERMiner: A New Method to Mine Essential Rules and
Constrained Essential Rules.
 CCIS Ph.D. seminar, 2003.
Talk Abstracts

PrivacyPreserving Data Publishing
Data publishing has a widespread need. For instance, a medical
institute may need to publish its medical data, so as to enable
the public researchers to ask queries such as: "what fraction of
males in Massachusetts have lung cancer?" However, at the same
time the privacy of the individuals needs to be preserved. The
first attempt, of simply removing the name attributes before
publishing
the data, does not work. The values of the remaining attributes, if
unique, may reveal the identities of some individuals. This talk
discusses some existing and ongoing work on this topic.

PCCSC: Profilebased and Constrained Compressed Skycube
This talk introduces the SIGMOD'06 paper on the Compressed Skycube, and
then raises the algorithmic question on how to choose a set of CSCs to
build given a query profile and a resource constraint. In more
detail, the CSC (built on all attributes) supports the skyline queries on
an arbitrary set of attributes, e.g. considering (#points, #rebounds,
#assists), who are the best NBA players? Here a player is one of the
best NBA players if there does not exist another player who is better in
all dimensions. With a high dimensional dataset, the complete CSC may be
too large. It may be better to build a set of CSCs, each on a subset of
attributes. Given a query profile such as the percentage of queries on
every subset of attributes, and a constraint such as storage size, the
open question is what CSCs to build which satisfy the constraint and
which covers the maximal number of queries.

Algorithms in Spatial Databases (a short course)
Spatial databases have many practical applications, and have close relationship with GIS, Computational Geometry, and Operations Research. The spatial database research community has produced many interesting algorithms for solving various spatial queries. This course covers some of these algorithms. It discusses spatial index structures such as the Rtree. It introduces the concepts and algorithms of the range query, nearest neighbor query, reverse nearest neighbor query, aggregation query, fastestpath query, optimal location query, skyline query, and join query. By learning the stateoftheart algorithms for processing these spatial queries, the students are expected to develop a foundational understanding of the spatial database research field.

The Skyline Query in Databases: Which Objects are the Most Important?
Recently, the database research community has witnessed a strong interest in the skyline operator. This operator can be used to suggest important objects among a set of multiattribute objects where different attributes may not be comparable. Given a set of ddimensional objects, the skyline is the set of objects that are not dominated by any other object. An object O1 dominates another object O2 if O1 is better than or equal to O2 in all dimensions, and is strictly better than O2 in at least one dimension. A classic example is to find important hotels in Nassau, Bahamas. A user wants to find hotels which are both cheap and close to beach. The traditional topk query requires the user to provide a preference function which converts a pair of price and distance to a single numeric score.
However, this requirement may not be reasonable for some applications, since different attributes may not be comparable. The skyline concept provides a way of suggesting important objects, without requiring comparison among different attributes. This talk introduces the skyline concept and describes the progressive and optimal BBS algorithm. It also presents the Compressed Skycube developed by the Database Lab at NEU.

The MinDist OptimalLocation Query
This paper proposes and solves the mindist optimallocation
query in spatial databases. Given a set S of sites, a set O
of weighted objects, and a spatial region Q, the mindist
optimallocation query returns a location in Q which, if a
new site is built there, minimizes the average distance from
each object to its closest site. This query can help a franchise
(e.g. McDonaldâ€™s) decide where to put a new store in or
der to maximize the benefit to its customers. To solve this
problem is challenging, for there are theoretically infinite
number of locations in Q, all of which could be candidates.
This paper first provides a theorem that limits the number
of candidate locations without losing the power to find ex
act answers. Then it provides a progressive algorithm that
quickly suggests a location, tells the maximum error it may
have, and keeps refining the result. When the algorithm
finishes, the exact answer can be found. The intermediate
result of early runs can be used to prune the search space
for later runs. Crucial to the pruning technique are novel
lowerbound estimators. The proposed algorithm, the effect
of several optimizations, and the progressiveness are exper
imentally evaluated.

Introduction to Spatial Database Research (30 min)
The spatial database research is an interesting subfield of
database research. It has close relationship with GIS, Computational
Geometry, and Operations Research. And it has practical applications.
This talk introduces the spatial database research field by discussing
several crucial spatial queries.
In particular, the talk will introduce the concepts of the fastestpath query,
range query, aggregation query,
nearest neighbor query, reverse nearest neighbor query, optimal
location query, and skyline query.
The paper then discusses one query processing scheme: the compressed skycube.

Introduction to Spatial Databases
The spatial database research is an interesting subfield of
database research. It has close relationship with GIS, Computational
Geometry, and Operations Research. And it has practical applications.
This talk introduces the spatial database research field by discussing
several crucial spatial queries and their efficient processing algorithms.
In particular, the talk will introduce the range query, aggregation query,
nearest neighbor query, reverse nearest neighbor query, optimal
location query, and skyline query.

The OptimalLocation Query
We propose and solve the optimallocation query in spatial
databases. Given a set S of sites, a set O of weighted objects, and a
spatial region Q, the optimallocation query returns a location in Q with
maximum influence. Here the influence of a location l is the total weight
of its RNNs, i.e. the total weight of objects in O that are closer to l than
to any site in S. This new query has practical applications, but is very
challenging to solve. Existing work on computing RNNs assumes a single
query location, and thus cannot be used to compute optimal locations.
The reason is that there are infinite candidate locations in Q. If we
check a finite set of candidate locations, the result can be inaccurate,
i.e. the revealed location may not have maximum influence. This paper
proposes three methods that accurately compute optimal locations. The
first method uses a standard R*tree. To compute an optimal location,
the method retrieves certain objects from the R*tree and sends them as
a stream to a planesweep algorithm, which uses a new data structure
called the aSBtree to ensure query efficiency. The second method is
based on a new index structure called the OLtree, which novelly extends
the kdBtree to store segmented rectangular records. The OLtree is
only of theoretical usage for it is not space efficient. The most practical
approach is based on a new index structure called the Virtual OLtree.
These methods are theoretically and experimentally evaluated.

Spatial Database Query Processing using Indices
This talk first introduces the concept of spatial databases and points some
of its applications. Then it describes two representative spatial index structures:
the Rtree and kdBtree. Finally, efficient indexbased algorithms are discussed
to solve the selection query, aggregation query, and nearest neighbor query.

On SpatialRange ClosestPair Query
An important query in spatial database research is to find the closest pair of objects in a given space. Existing work assumes two different data sets are both indexed by Rtrees, and finds the closest pair in the whole space via an optimized Rtree join technique. However, this technique does not perform well when the two data sets are identical. In this paper, we address the closest pair problem within the same data set. Furthermore, we consider an extended version of the query, which involves a spatial range. We now are interested in finding the closest pair of objects among those inside a given range. We first extend existing techniques to solve the new problem. We then propose two index structures based on augmenting the Rtree and show that in both cases, the augmented information is easy to maintain. Experimental results show that our structures are more robust than earlier approaches.

ERMiner: A New Method to Mine Essential Rules and
Constrained Essential Rules
One fundamental task in the data mining area is to find strong
association rules. That is, association rules whose support and
confidence are both beyond given minimum thresholds. Recent
research has shown that certain rules can ``imply'' others. We describe
efficient algorithm to mine
``essential'' rules, i.e. strong rules which cannot be implied by
any other strong rule. The result size is very compact, and the set of
strong rules can be derived from the essential rules without accessing
the transactional database.
Home