Seminars

The DKE weekly seminar

All full-time students and visiting students will be required to attend DKE weekly seminars. The attendance will be recorded. You can talk a research paper recently published in the top conferences and journals such as SIGMOD, VLDB, ICDE, or you can talk your own work.

Seminar in coming weeks

Date	Speaker	Title
...	...	...
12 May, 2010	Prof. Peter Scheuerma (Northwestern University, USA)	Continuous Queries and Reactive Behavior Management in Moving Object Databases, or Multi-Path + Multiple Trees Routing and Aggregation in Sensor Networks
...	...	...
27 Apr. 2010 (Tue)	Dr. Xing Xie (Microsoft Research Asia)	...
...	...	...
24 Mar. 2010	Kevin Zhneg, Felix Xie and Shou Shang	PhD Confirmation Practise
17 Mar. 2010	Ke Deng	Active Duplicate Detection (DASFAA Best Paper Award Runner Up)
8 Mar. 2010	Henry Ye	Approaches to Web Service Composition - A survey
3 Mar. 2010	Zaiben Chen	Searching Trajectories by Locations - An Efficiency Study (Accepted SIGMOD'2010 Paper)
24 Feb. 2010	Henning, Ke Deng	Practise for DASFAA, APWEB presentation
17 Feb. 2010	Kevin Zheng	K-Nearest Neighbor Search for Fuzzy Objects (Accepted SIGMOD 2010 Paper)
10 Feb. 2010	Henning	Sampling Dirty Data for Matching Attributes s (Accepted SIGMOD 2010 Paper)

Candidate Speaker List

Name	Degree	Mode	Advisor
Andri Setiawan	PhD	Full	Sadiq
Eunjung Chin	PhD	Full	Zhou
Henry Ye	PhD	Full	Zhou
Felix Xie	PhD	Full	Zhou
Jafaar Al Abodi	PhD	Full	Xue Li
Jia Jun Liu	PhD	Full	Shen
Joe Lin	PhD	Full	Orlowska
Kelvin Cheng	PhD	Full	Shen
Kevin Zheng	PhD	Full	Zhou
Kexin Xie	PhD	Full	Zhou
Mandy Singh	PhD	Full	Xue Li
Naiem Khodabandehloo	PhD	Full	Sadiq
Shang Shuo	PhD	Full	Zhou
Simon Raboczi	PhD	Full	Governatori
Syed Norris Abdullah	PhD	Full	Sadiq
Thien Au	PhD	Full	Sadiq
Yang Yang	PhD	Full	Shen
Zaiben Chen	PhD	Full	Shen
Zhixu Li	PhD	Full	Sadiq
Yingying Zhu	PhD	Full	.
Jing Yang	visiting-student	.	.
Ke Deng	PDF	.	.
Henning	PDF	.	.
Helen Huang	PDF	.	.

attendance record

Biographical Sketch:

Professor Peter Scheuermann is a Professor of Electrical Engineering and Computer Science at Northwestern University. He has held visiting professor positions with the Free University of Amsterdam, the University of Hamburg, the Technical University of Berlin and the Swiss Federal Institute of Technology, Zurich. During 1997-1998 he served as Program Director for Operating Systems at the NSF. Dr. Scheuermann has served on the editorial board of the Communications of ACM, The VLDB Journal, IEEE Transactions on Knowledge and Data Engineering and is currently an associate editor of Data and Knowledge Engineering and the International Journal of Next-Generation Computing. Among his professional activities, he has served as General chair of the ACM-SIGMOD Conference in 1988, General chair of the ER ¡®2003 Conference and more recently as Program Co-Chair of the ACM-SIGPATIAL conference in 2009. He was a member of the ACM-SIGMOD advisory board, and prior to this he chaired the ACM-SIGMOD awards committee His research interests are in distributed database systems, mobile computing, sensor networks and data mining. He has published more than 120 journal and conference papers. His research has been funded by NSF, NASA, HP, Northrop Grumman, and BEA, among others. Peter Scheuermann is a Fellow of IEEE and AAAS (American Association for the Advancement of Science).

Abstracts:

Continuous Queries and Reactive Behavior Management in Moving Object Databases

Unlike traditional applications where queries are instantaneous, many queries of interest in moving object databases (MOD) are continuous in nature and require constant re-evaluation over the history of the objects. We assume that that the motion of objects is represented by trajectories, which consists of a sequence of 3D points. We present first a comprehensive set of techniques, both static and dynamic, for minimizing the costs involved in reevaluating continuous queries in response to bulk updates. The static techniques correspond to specifying the values of various semantic dimensions of trigger execution. The dynamic techniques include an in-memory shared reevaluation algorithm, adapting query indexing techniques to trajectory data, and utilizing ordering based on space-filling curves to improve the I/O efficiency.

We next address the problem of handling event notification in MOD, by introducing a class of dynamic topological predicates, such moving along and moving towards. We show that traditional triggers are inadequate for handling the reactive behavior of these topological predicates since they repeatedly evaluate the conditions on the entire past trajectory.

Motivated by this we introduce a new paradigm for expressing reactive behavior in distributed environments in which data continuously changes over time and which allows users to explicitly specify how the triggers should be (self) modified. We call this paradigm Evolving and Context-Aware Event Condition Action (ECA) 2. Our model combines reactive behavior with proactive impact by modifying dynamically the event/conditions and actions monitored. Since both the monitored event and the condition part of the trigger can be continuous in nature, we introduce the concept of metatriggers to coordinate the detection of events and the evaluation of conditions.

*******

Multi-Path + Multiple Trees Routing and Aggregation in Sensor Networks

Multi-path routing approaches in wireless sensor networks have received considerable attention since they can achieve two complimentary goals: (1) increase the reliability of the transmission in the network and (2) provide for better load balancing, which in turn affects the operational lifetime of the network. However, most multi-path routing protocols exhibit a number of drawbacks, such as path merging due to decrease in available next-hop neighbors and to overload of the nodes in the vicinity of the source/sink.

We present two approaches to multi-path routing that alleviate these problems substantially. The first approach is based on the concept of Busier curves that have been used extensively in computer graphics. Bezier curves are a class of polynomial parametric curves that have a high degree of flexibility in the construction of their shape, which is achieved with a set of control points. By carefully selecting the control points, Bezier curves provide soft Quality of Service guarantees in terms of latency of delivery of the sensed data. In addition, they also provide a better distribution of the energy consumption which is especially relevant for the nodes in the vicinity of the source and sink.

The second approach is inspired by the analogy of multi-path routing to the gradient vectors of an electric field. We introduce our Discrepancy Adaptive Multipole Routing (DA-MPR) protocol that adapts to the spatial distribution of the nodes in order to improve the distribution of the energy reserve and the lifetime of the network. DA-MPR also includes a heuristic based on the method of images from physics which provides a distributed solution to the problem of path-merging effects near the physical boundary of the network.

In the last portion of the talk we will discuss how tree-based routing can be combined with multi-path routing in order to process constrained range queries that are restricted to a subset of the field covered by a given sensor network. Tree-based routing is the strategy of choice when in-network aggregation needs to be performed We show how alternating among multiple trees or using disjoint trees (tributaries) can be achieved inside the region of interest and then combined with multi-path routing (deltas) that are employed to transmit the results from the query region to a sink residing outside of it.

******

Searching Trajectories by Locations-An Efficiency Study

Trajectory search has long been an attractive and challenging topic which blooms various interesting applications in spatial-temporal databases. In this work, we study a new problem of searching trajectories by locations, in which context the query is only a small set of locations with or without an order specified, while the target is to find the k Best-Connected Trajectories (k-BCT) from a database such that the k-BCT best connect the designated locations geographically. Different from the conventional trajectory search that looks for similar trajectories w.r.t. shape or other criteria by using a sample query trajectory, we focus on the goodness of connection provided by a trajectory to the specified query locations. This new query can benefit users in many novel applications such as trip planning.

In our work, we firstly define a new similarity function for measuring how well a trajectory connects the query locations, with both spatial distance and order constraint being considered. Upon the observation that the number of query locations is normally small (e.g. 10 or less) since it is impractical for a user to input too many locations, we analyze the feasibility of using a general-purpose spatial index to achieve efficient k-BCT search, based on a simple Incremental k-NN based Algorithm (IKNN). The IKNN effectively prunes and refines trajectories by using the devised lower bound and upper bound of similarity. Our contributions mainly lie in adapting the best-first and depth-first k-NN algorithms to the basic IKNN properly, and more importantly ensuring the efficiency in both search effort and memory usage. An in-depth study on the adaption and its efficiency is provided. Further optimization is also presented to accelerate the IKNN algorithm. Finally, we verify the efficiency of the algorithm by extensive experiments.

*******

Approaches to Web Service Composition - A survey
Our world has been evoled from a Data-Oriented to Service- Oriented as the maturation of Web service techniques. During the last ten years or more, the early standardization work has helped the fast deployment of Web service infrastructures. However, much more research is needed to reach its full potential. Web service composition is one of the salient research topics within this area. In last ten years, many approaches and frameworks have been proposed to solve Web service composition. Here we provide a survey on these approaches and give an outlook to essential future research work.

*******

Active Duplicate Detection
The aim of duplicate detection is to group records in a relation which refer to the same entity in the real world such as a person or business. Most existing works require user specified parameters such as similarity threshold in order to conduct duplicate detection. These methods are called user-first in this paper. However, in many scenarios, pre-specification from the user is very hard and oftenunreliable, thus limiting applicability of user-first methods. In this paper, we propose a user-last method, called Active Duplicate Detection (ADD), where an initial solution is returned without forcing user to specify such parameters and then user is involved to refine the initial solution. Different from user-first methods where user makes decision before any processing, ADD allows user to make decision based on an initial solution. The identified initial solution in ADD enjoys comparatively high quality and is easy to be refined in a systematic way (at almost zero cost).

10 March 2010 Last Edited