Database Seminar Series (2005-2006)

While the Web has become the ultimate information repository, several major barriers have hindered today's search engines from unleashing the Web's promise. Toward tackling the dual challenges for accessing both the deep and the surface Web, I will present our "trilogy" of pursuit:

To begin with, from search to integration: As the Web has deepened dramatically, much information is now hidden on the "deep Web," behind the query interfaces of numerous searchable databases. Our 2004 survey estimated 450,000 online databases and 1,258,000 query interfaces. We thus believe that search much resort to integration: To enable access to the deep Web, we are building the MetaQuerier at UIUC for both finding and querying such online databases.

Further, from integration to mining: Toward large scale integration, to tackle the critical issue of dynamic semantics discovery, we observe our key insight that-- while the deep Web challenges us for its large scale, the challenge itself presents a unique opportunity: We believe that integration must resort to mining, to tackle the deep semantics by exploring shallow syntactic and statistic regularities hidden across large scale of sources, holistically.

Finally, from mining back to search? Beyond the MetaQuerier, such holistic mining is equally crucial for the dual challenge of semantics discovery on the surface Web. We believe such mining must resort to search, and propose to build holistic analysis into a next generation search engine by demonstrating our initial solutions.

Project URL: http://metaquerier.cs.uiuc.edu

In the second part of the talk, we describe how the knowledge gleaned by LEO is exploited consistently in a query optimizer, by adjusting the optimizer's model and by maximzing information entropy.

From January 1997 to December 2000, Dr. Markl worked for the Bavarian Research Center for Knowledge-Based Systems (FORWISS) in Munich, Germany as deputy research group manager, leading the MISTRAL and MDA projects, thereby cooperating with SAP AG, NEC, Hitachi, Teijin Systems Technology, GfK, and Microsoft Research. His MDA project, jointly with TransAction Software, developed the relational database management system TransBase HyperCube, which was awarded the European IST Prize 2001 by EUROCASE and the European Commission.

Dr. Markl also initiated and co-ordinated the EDITH EU IST project investigating the physical clustering of multiple hierarchies and its applications to GIS and Data Warehousing that now is being carried out by FORWISS and several partners from Germany, Italy, Greece, and Poland.

Volker Markl is a graduate of the Technische Universität München, where he earned a Masters degree in Computer Science in 1995. He completed his PhD in 1999 under the supervision of Rudolf Bayer. His dissertation on "Relational Query Processing Using a Multidimensional Access Technique" was honored "with distinction" by the German Computer Society (Gesellschaft für Informatik). He also earned a degree in Business Administration from the University Hagen, Germany in 1995. Since 1996, Volker Markl has published more than 30 reviewed papers at prestigious scientific conferences and journals, filed more than 10 patents and has been invited speaker at many universities and companies. Dr. Markl is member of the German Computer Society (GI) as well as the Special Interest Group on Management of Data of the Assosication for Computing Machinery (ACM SIGMOD). He also serves as program committee member and reviewer for several international conferences and journals, including SIGMOD, ICDE, VLDB, TKDE, TODS, IS, and the Computer Journal. His main research interests are on autonomic computing, query processing, and query optimization, but also include applications like data warehousing, electronic commerce and pervasive computing.

Dr. Markl's earlier professional experience include software engineer for a virology laboratory, as part of his military service; lecturer for software-engineering courses at the University of Applied Sciences in Augsburg, Germany and for programming and communications at the Technische Universität München; and consultant for a forwarding agency. He was awarded a fellowship by Siemens AG, Munich and also worked as an international intern with Benefit Panel Services, Los Angeles.

The quality of the data residing in information repositories and databases gets degraded due to a multitude of reasons. In the presence of data quality errors, a central problem is to identify all pairs of entities (tuples) in two sets of entities that are approximately the same. This operation has been studied through the years and it is known under various names, including record linkage, entity identification, entity reconciliation and approximate join, to name a few. The objective of this talk is to provide an overview of key research results and techniques used for approximate joins.

This is joint work with Nick Koudas.

Divesh Srivastava is the head of the Database Research Department at AT&T Labs-Research. He received his B.Tech. in Computer Science & Engineering from the Indian Institute of Technology, Bombay, India, and his Ph.D. in Computer Sciences from the University of Wisconsin, Madison, USA. His current research interests include XML databases and IP network data management. 

A key benefit of XML is its ability to represent a mix of structured and text data. We discuss the interplay of structured information and keyword search in three aspects of XML search: query design, scoring methods and query evaluation. In query design, existing languages for XML evolved from simple keyword search to queries combining sophisticated conditions on structure ala XPath and XQuery and complex full-text search primitives, such as the use of ontologies and keyword proximity distance, ala XQuery Full-Text. In XML scoring, methods range from a pure IR tf*idf to approximating and scoring both structure and keyword conditions. In evaluating XML search, document structure has been used to identify meaningful XML fragments to be returned as answers to keyword queries and, is
currently being explored to optimize full-text search queries.

This discussion is based on published and ongoing work between AT&T Labs and UBC, The U. of Toronto, Cornell U., Rutgers U., the U. of Waterloo and UCSD.

With the growing popularity and availability of mobile communications, our ability to stay connected while on the move is becoming a reality instead of science fiction just a decade ago. An important research challenge for modern location-based services is the scalable processing of location monitoring requests on a large collection of mobile objects. The centralized architecture, though studied extensively in literature, would create intolerable performance problems as the number of mobile objects grows significantly.

In this talk, we present a distributed architecture and a suite of optimization techniques for scalable processing of continuously moving location queries. Moving location queries can be viewed as standing location tracking requests that continuously monitors the locations of mobile objects of interests and return a subset of mobile objects when a certain conditions are met. We describe the design of a distributed location monitoring architecture through MobiEyes, a distributed real time location monitoring system in a mobile environment. The main idea behind the MobiEyes distributed architecture is to promote a careful partition of a real time location monitoring task into an optimal coordination of server-side processing and client-side processing. Such a partition allows the location of a moving object to be computed with a high degree of precision using a small number of location updates or no updates at all, thus providing highly scalable and more cost-effective location monitoring services. Concretely, the MobiEyes distributed architecture not only encourages a careful utilization of the rapidly growing computational power available at various mobile devices, such as cell phones, hand helds, GPS devices, but also endorses a strong coordination agreement between the mobile objects and the server. Such an agreement supports varying location update rates for different mobile users at different times, and advocates the exploitation of location predication and location inference to further constrain the resource/bandwidth consumption while maintaining the satisfactory precision of location information. A set of optimization techniques are used to further limit the amount of computations to be handled by the mobile objects and enhance the overall performance and system utilization of MobiEyes. Important metrics to validate the proposed architecture and optimizations include messaging cost, server load, and amount of computation at individual mobile objects. Our experimental results show that the MobiEyes approach can lead to significant savings in terms of server load and messaging cost when compared to solutions relying on central processing of location information at the server. If time permits, at the end of my talk, I will also give an overview of the location privacy protection in LBS.

XQuery 1.0 and its sister language XPath 2.0 have set a fire underneath database vendors and researchers alike. More than thirty commercial and research XQuery implementations are listed on the XML Query working group home page. Galax (www.galaxquery.org) is an open-source, general-purpose XQuery engine, designed to be complete, efficient, and extensible. During Galax's development, we have focused on each of these three requirements in turn, while never losing sight of the other two.

In this talk, I will describe how these requirements have impacted Galax's evolution and our own research interests. Along the way, I will show how Galax's architecture supports these three requirements.

Galax is joint work with Jérôme Siméon, IBM T.J. Watson Research Center.

Discovering Interesting Subsets of Data in Cube Space

He is Chair of ACM SIGMOD, on the Board of Directors of ACM SIGKDD and the Board of Trustees of the VLDB Endowment, an associate editor of ACM Transactions on Database Systems, and was previously editor-in-chief of the Journal of Data Mining and Knowledge Discovery and the Database area editor of the Journal of Logic Programming. Dr. Ramakrishnan is a Fellow of the Association for Computing Machinery (ACM), and has received several awards, including a Packard Foundation Fellowship, an NSF Presidential Young Investigator Award, and an ACM SIGMOD Contributions Award. He has authored over 100 technical papers and written the widely-used text "Database Management Systems" (WCB/McGraw-Hill), now in its third edition (with J. Gehrke).

In February 2004 the Web Ontology Language (OWL) was adopted by the W3C as a recommendation and emerged as a core standard for knowledge representation in the web. The sublanguage OWL-DL is a notational variant of the well-known description logic SHOIN(Dn-), which has decidable inference problems but is also known to be NexpTime-complete. The availability of OWL-DL caused a significant interest in OWL-compliant assertional description logic reasoners. Racer was the first highly optimized assertional reasoner for the very expressive (ExpTime-complete) description logic SHIQ(D-), which covers most parts of OWL-DL with the exception of so-called nominals.

In this talk I will briefly introduce description logics / OWL-DL and associated inferences services. Afterward I will discuss the architecture of the description logic reasoner Racer and highlight selected tableau optimization techniques, especially on assertional reasoning and its relationship to database technology. Several recently devised optimization techniques were introduced due to requirements from semantic web applications relating huge amounts of (incomplete) data to ontological information. I will conclude my presentation with an outlook on OWL 1.1 and ongoing and future description logic research such as explanation of reasoning and adding uncertainty as well as database support in Racer Pro.

The research on Racer is joint work with Ralf Moeller, Hamburg University of Technology.

Dr. Haarslev obtained his doctoral degree from the University of Hamburg, Germany, specializing in user interface design. His early research work was in compilers, interfaces and visual languages. His current work is in automated reasoning, especially description logics, which play important roles in database technology and Internet technology. For databases, description logics allow the integration of heterogeneous data sources. For Internet technology, description logics are the logical foundation of the web ontology language (OWL) and form the basis of the semantic web, the emerging next generation of the World Wide Web.

Dr. Haarslev is internationally regarded for his substantial research contributions in the fields of visual language theory and description logics. He is a principal architect of the description logic and OWL reasoner Racer, which can be considered as a key component for the emerging semantic web. Dr. Haarslev holds the position of Associate Professor in the Department of Computer Science and Software Engineering in Concordia University. He leads a research group working on automated reasoning and related database technology in the context of the semantic web. Dr. Haarslev is also cofounder of the company Racer Systems, which develops and distributes Racer Pro, the commercial successor of Racer.

In this talk, I'll begin with a short overview of this newly emerging research area. Then, I will describe some of my group's recent work on link-based classification and entity resolution in relational domains. I'll spend the majority of time describing our work on entity resolution. I'll describe the framework and algorithms that we have developed, present results on several real world datasets and our work on making the algorithms scalable.

Joint work with students: Indrajit Bhattacharya, Mustafa Bilgic, Louis Licamele and Prithviraj Sen.

Emerging data streaming applications pose new challenges to database management systems. In this talk, I will focus on two applications, namely mobile objects and phenomena detection and tracking applications. I will highlight new challenges that these applications raise and how we address them in the context of Nile, a data stream management system being developed at Purdue. In particular, I will present new features of Nile, including incremental evaluation of continuous queries, supporting "predicate windows" using views, and stream query processing with relevance feedback. I will demonstrate the use and performance gains of these features in the context of the above two applications. Finally, I will talk about ongoing research in Nile and directions for future research.

Self-similarity, fractals and power laws are extremely successful in describing real datasets (coast-lines, rivers basins, stockprices, brain-surfaces, communication-line noise, to name a few). We show some old and new successes, involving modeling of graph topologies (internet, web and social networks); modeling galaxy and video data; dimensionality reduction; and more.

Trio web site: http://www-db.stanford.edu/trio/