We consider the problem of building an organizational directory of data lakes to support effective user navigation. The organization directory is defined as an acyclic graph that contains nodes representing sets of attributes and edges indicating subset relationships between nodes. A probabilistic model is constructed to model user navigational behaviour. The model also predicts the likelihood of users finding relevant tables in a data lake given an organization. We formulate the data lake organization problem as an optimization over the organizational structure in order to maximize the expected likelihood of discovering tables by navigating. An approximation algorithm is proposed with an analysis of its error bound. The effectiveness and efficiency of the algorithm are evaluated on both synthetic and real data lakes. Our experiments show that our algorithm constructs organizations that outperform many existing organizations including an existing hand-curated taxonomy, a linkage graph, and a common baseline organization. We have also conducted a formal user study which shows that navigation can help users discover relevant tables that are not easily accessible by keyword search queries. This suggests that keyword search and navigation using an organization are complementary modalities for data discovery in data lakes.

There is a large growth in hardware and software systems capable of producing vast amounts of image and video data. These systems are rich sources of continuous image and video streams. This motivates researchers to build scalable computer vision systems that utilize data-streaming concepts for processing of visual data streams. However, several challenges exist in building large-scale computer vision systems. For example, computer vision algorithms have different accuracy and speed profiles depending on the content, type, and speed of incoming data. Also, it is not clear how to adaptively tune these algorithms in large-scale systems. These challenges exist because we lack formal frameworks for building and optimizing large-scale visual processing. This paper presents formal methods and algorithms that aim to overcome these challenges and improve building and optimizing large-scale computer vision systems. We describe a formal algebra framework for the mathematical description of computer vision pipelines for processing image and video streams. The algebra naturally describes feedback control and provides a formal and abstract method for optimizing computer vision pipelines. We then show that a general optimizer can be used with the feedback-control mechanisms of our stream algebra to provide a common online parameter optimization method for computer vision pipelines.

Dataset discovery can be performed using search (with a query or keywords) to find relevant data. However, the result of this discovery can be overwhelming to explore. Existing navigation techniques mostly focus on linkage graphs that enable navigation from one data set to another based on similarity or joinability of attributes. However, users often do not know which data set to start the navigation from. RONIN proposes an alternative way to navigate by building a hierarchical structure on a collection of data sets: the user navigates between groups of data sets in a hierarchical manner to narrow down to the data of interest. We demonstrate RONIN, a tool that enables user exploration of a data lake by seamlessly integrating the two common modalities of discovery: data set search and navigation of a hierarchical structure. In RONIN, a user can perform a keyword search or joinability search over a data lake, then, navigate the result using a hierarchical structure, called an organization , that is created on the fly. While navigating an organization, the user may switch to the search mode, and back to navigation on an organization that is updated based on search. This integration of search and navigation provides great power in allowing users to find and explore interesting data in a data lake.

We consider the problem of creating an effective navigation structure over a data lake. We define an organization as a navigation graph that contains nodes representing sets of attributes within a data lake and edges indicating subset relationships among nodes. We propose the data lake organization problem as the problem of finding an organization that allows a user to most effectively navigate a data lake. We present a new probabilistic model of how users interact with an organization and propose an approximate algorithm for the data lake organization problem. We show the effectiveness of the algorithm on both a real data lake containing data from open data portals and on a benchmark that contains rich metadata emulating the observed characteristics of real data lakes. Through a formal user study, we show that navigation can help users find relevant tables that cannot be found by keyword search.

The ubiquity of data lakes has created fascinating new challenges for data management research. In this tutorial, we review the state-of-the-art in data management for data lakes. We consider how data lakes are introducing new problems including dataset discovery and how they are changing the requirements for classic problems including data extraction, data cleaning, data integration, data versioning, and metadata management.

We define the table union search problem and present a probabilistic solution for finding tables that are unionable with a query table within massive repositories. Two tables are unionable if they share attributes from the same domain. Our solution formalizes three statistical models that describe how unionable attributes are generated from set domains, semantic domains with values from an ontology, and natural language domains. We propose a data-driven approach that automatically determines the best model to use for each pair of attributes. Through a distribution-aware algorithm, we are able to find the optimal number of attributes in two tables that can be unioned. To evaluate accuracy, we created and open-sourced a benchmark of Open Data tables. We show that our table union search outperforms in speed and accuracy existing algorithms for finding related tables and scales to provide efficient search over Open Data repositories containing more than one million attributes.

We developed T oronto O pen D ata S earch to support the ad hoc , interactive discovery of connections or linkages between datasets. It can be used to efficiently navigate through the open data cloud. Our system consists of three parts: a user-interface provided by a Web application; a scalable backend infrastructure that supports navigational queries; and a dynamic repository of open data tables. Our system uses LSH Ensemble, an efficient index structure, to compute linkages (attributes in two datasets with high containment score) in real time at Internet scale. Our application allows users to navigate along these linkages by joining datasets. LSH Ensemble is scalable, providing millisecond response times for linkage discovery queries even over millions of datasets. Our system offers users a highly interactive experience making unrelated (and unlinked) dynamic collections of datasets appear as a richly connected cloud of data that can be navigated and combined easily in real time.

When working with a high volume relational database, is it possible to effectively provide a compact visualization of the tuples in that database? Data visualization techniques very often scale poorly with input volume, hindering attempts at providing a responsive, full picture of the relationships within data. We introduce a method of efficiently visualizing millions of tuples in a two-dimensional constrained space, providing a method for data to be visually analyzed at the tuple level. We achieve this by applying a physics simulation on an embedded network, positioning tuples according to their representative node.

We study the problem of domain search where a domain is a set of distinct values from an unspecified universe. We use Jaccard set containment score, defined as | Q ∩ X |/| Q |, as the measure of relevance of a domain X to a query domain Q . Our choice of Jaccard set containment over Jaccard similarity as a measure of relevance makes our work particularly suitable for searching Open Data and data on the web, as Jaccard similarity is known to have poor performance over sets with large differences in their domain sizes. We demonstrate that the domains found in several real-life Open Data and web data repositories show a power-law distribution over their domain sizes. We present a new index structure, Locality Sensitive Hashing (LSH) Ensemble, that solves the domain search problem using set containment at Internet scale. Our index structure and search algorithm cope with the data volume and skew by means of data sketches using Minwise Hashing and domain partitioning. Our index structure does not assume a prescribed set of data values. We construct a cost model that describes the accuracy of LSH Ensemble with any given partitioning. This allows us to formulate the data partitioning for LSH Ensemble as an optimization problem. We prove that there exists an optimal partitioning for any data distribution. Furthermore, for datasets following a power-law distribution, as observed in Open Data and Web data corpora, we show that the optimal partitioning can be approximated using equi-depth, making it particularly efficient to use in practice. We evaluate our algorithm using real data (Canadian Open Data and WDC Web Tables) containing up over 262 million domains. The experiments demonstrate that our index consistently outperforms other leading alternatives in accuracy and performance. The improvements are most dramatic for data with large skew in the domain sizes. Even at 262 million domains, our index sustains query performance with under 3 seconds response time.

Central to many applications involving moving objects is the task of processing k-nearest neighbor (k-NN) queries. Most of the existing approaches to this problem are designed for the centralized setting where query processing takes place on a single server; it is difficult, if not impossible, for them to scale to a distributed setting to handle the vast volume of data and concurrent queries that are increasingly common in those applications. To address this problem, we propose a suite of solutions that can support scalable distributed processing of k-NN queries. We first present a new index structure called Dynamic Strip Index (DSI), which can better adapt to different data distributions than exiting grid indexes. Moreover, it can be naturally distributed across the cluster, therefore lending itself well to distributed processing. We further propose a distributed k-NN search (DKNN) algorithm based on DSI. DKNN avoids having an uncertain number of potentially expensive iterations, and is thus more efficient and more predictable than existing approaches. DSI and DKNN are implemented on Apache S4, an open-source platform for distributed stream processing. We perform extensive experiments to study the characteristics of DSI and DKNN, and compare them with three baseline methods. Experimental results show that our proposal scales well and significantly outperforms the alternative methods.

A basic step in integration is the identification of linkage points, i.e., finding attributes that are shared (or related) between data sources, and that can be used to match records or entities across sources. This is usually performed using a match operator, that associates attributes of one database to another. However, the massive growth in the amount and variety of unstructured and semi-structured data on the Web has created new challenges for this task. Such data sources often do not have a fixed pre-defined schema and contain large numbers of diverse attributes. Furthermore, the end goal is not schema alignment as these schemas may be too heterogeneous (and dynamic) to meaningfully align. Rather, the goal is to align any overlapping data shared by these sources. We will show that even attributes with different meanings (that would not qualify as schema matches) can sometimes be useful in aligning data. The solution we propose in this paper replaces the basic schema-matching step with a more complex instance-based schema analysis and linkage discovery. We present a framework consisting of a library of efficient lexical analyzers and similarity functions, and a set of search algorithms for effective and efficient identification of linkage points over Web data. We experimentally evaluate the effectiveness of our proposed algorithms in real-world integration scenarios in several domains.

This paper presents a new approach for automatic road detection in traffic cameras. The technique proposed here detects the dominant road boundary and estimates the vanishing point in images captured by traffic cameras under a wide range of lighting and environmental conditions, e.g., in images of unlit highways captured at night, etc. The approach starts by segmenting the traffic scene into a number of superpixel regions. The contours of these regions are used to generate a large number of edges which are organized into clusters of co-linearly similar sets using hierarchical bottom up clustering. A confidence level is assigned to each cluster using a statistical approach and the best clusters are chosen. Pairs of clusters with high confidence levels are then ranked and filtered according to image perspective and activity. The top ranked pair is selected as the road boundary. The proposed technique is tested on a real world dataset collected from the Ontario 401 traffic surveillance system. Experimental results demonstrate a distinct speedup and improvement in accuracy of the proposed technique in detecting the dominant road boundary in challenging scenarios compared to the state of the art Gabor filter based technique.

We propose a framework and algorithm for annotating unbounded text streams with entities of a structured database. The algorithm allows one to correlate unstructured and dirty text streams from sources such as emails, chats and blogs, to entities stored in structured databases. In contrast to previous work on entity extraction, our emphasis is on performing entity annotation in a completely online fashion. The algorithm continuously extracts important phrases and assigns to them top-k relevant entities. Our algorithm does so with a guarantee of constant time and space complexity for each additional word in the text stream, thus infinite text streams can be annotated. Our framework allows the online annotation algorithm to adapt to changing stream rate by self-adjusting multiple run-time parameters to reduce or improve the quality of annotation for fast or slow streams, respectively. The framework also allows the online annotation algorithm to incorporate query feedback to learn the user preference and personalize the annotation for individual users.

We introduce a statistical technique of inferring the position of RFID tags by means of computation on multiple data streams from distributed RFID receivers. Using a single statistical model that describes the detection rate between tags and receivers, we are able to perform Bayesian inference on the positions of the observed tags. If permitted by the receivers, our method can optimally coordinate the signal strength of multiple receivers to improve the time response of our positional inference system.

Keyword search provides a simple yet effective way for the users to query and explore the underlying documents. In the recent years, there have been a great deal of research and development activities on extending keyword search capabilities to handle relational data, the dominant form in which business data are stored. Algorithms and prototype systems, such as Discover, DBXplorer, BANKS, and SPARK, have been developed to support retrieving relevant information from relational databases using keyword queries.

In a peer-to-peer overlay network, the phenomenon of multiple overlay links sharing bottleneck physical links leads to correlation of overlay link capacities. We are able to more accurately model the overlay by incorporating these linear capacity constraints (LCCs). We formulate the problem of maximizing bandwidth in overlay multicast using our LCC model. We show that finding a maximum bandwidth multicast tree in an overlay network with LCC is NP-complete. Therefore, an efficient heuristics algorithm is designed to solve the problem. Extensive simulations show that our algorithm is able to construct multicast trees that are optimal or extremely close to optimal, with significantly higher bandwidth than trees formed in overlays with no LCC. Furthermore, we develop a fully distributed algorithm for obtaining near-optimal multicast trees, by means of gossip-based algorithms and a restricted but inherently distributed class of LCC (node-based LCC). We demonstrate that the distributed algorithm converges quickly to the centralized optimal and is highly scalable.

In this paper, we revisit the problem of multicast tree construction in overlay peer-to-peer networks. We present an iterative online multicast tree construction algorithm for multi-session multicasting of elastic content. Our framework allows receivers to request multiple sessions from possibly different servers. Each receiver expresses a quality-of-service requirement using a utility function. We propose an online algorithm which constructs multicast trees to maximize the overall receiver utility functions in an iterative fashion, allowing it to adapt to changes in network topology and cross-traffic.

Unlike traditional database queries, keyword queries do not adhere to predefined syntax and are often dirty with irrelevant words from natural languages. This makes accurate and efficient keyword query processing over databases a very challenging task. In this paper, we introduce the problem of query cleaning for keyword search queries in a database context and propose a set of effective and efficient solutions. Query cleaning involves semantic linkage and spelling corrections of database relevant query words, followed by segmentation of nearby query words such that each segment corresponds to a high quality data term. We define a quality metric of a keyword query, and propose a number of algorithms for cleaning keyword queries optimally. It is demonstrated that the basic optimal query cleaning problem can be solved using a dynamic programming algorithm. We further extend the basic algorithm to address incremental query cleaning and top- k optimal query cleaning. The incremental query cleaning is efficient and memory-bounded, hence is ideal for scenarios in which the keywords are streamed. The top- k query cleaning algorithm is guaranteed to return the best k cleaned keyword queries in ranked order. Extensive experiments are conducted on three real-life data sets, and the results confirm the effectiveness and efficiency of the proposed solutions.

Logical constraints, (e.g., `phone numbers in Toronto can have prefixes 416, 647, 905 only'), are ubiquitous in relational databases. Traditional integrity constraints, such as functional dependencies, are examples of such logical constraints as well. However, under frequent database updates, schema evolution and transformations, they can be easily violated. As a result, tables become inconsistent and data quality is degraded. In this paper we study the problem of validating collections of user defined constraints on a number of relational tables. Our primary goal is to quickly identify which tables violate such constraints. Logical constraints are potentially complex logical formuli, and we demonstrate that they cannot be efficiently evaluated by SQL queries. In order to enable fast identification of constraint violations, we propose to build and maintain specialized logical indices on the relational tables. We choose Boolean Decision Diagrams (BDD) as the index structure to aid in this task. We first propose efficient algorithms to construct and maintain such indices in a space efficient manner. We then describe a set of query re-write rules that aid in the efficient utilization of logical indices during constraint validation. We have implemented our approach on top of a relational database and tested our techniques using large collections of real and synthetic data sets. Our results indicate that utilizing our techniques in conjunction with logical indices during constraint validation offers very significant performance advantages.

We study the problem of indexing continuous data streams in which data are heterogeneous in structure. Such data streams arise naturally in many real-life scenarios such as sensor networks. Our index structure uses bitmap based techniques to efficiently sketch the structures to allow space-efficient lossless archiving of the data stream. It also allows very fast query processing on the archived data stream. Furthermore, our index structure adapts to structural evolutions of the stream to ensure good indexing and querying performance both in space and time. We developed a cost-based optimization framework so the indexing engine adjusts its configuration at run-time to adapt to changes in the data stream. By means of linear feedback controllers, structural clustering and steepest gradient ascent optimization, our indexing engine can achieve excellent performance without any human intervention.

This paper studies a problem of web service composition from a syntactic approach. In contrast with other approaches on enriched semantic description such as statetransition description of web services, our focus is in the case when only the input-output type information from the WSDL specifications is available. The web service composition problem is formally formulated as deriving a given desired type from a collection of available types and web services using a prescribed set of rules with costs. We show that solving the minimal cost composition is NP-complete in general, and present a practical solution based on dynamic programming. Experiements using a mixture of synthetic and real data sets show that our approach is viable and produces good results.

We present a framework for functionally modeling query languages and data models. Data and queries are uniformly represented by first-order functions, and query-language constructs by polymorphic higher-order functions. The functions are typed by a database-oriented type system that supports polymorphism and nesting of types, thus one can perform static type-checking and type-inferencing of query-expressions. The query language can be freely extended by introducing new querying constructs as polymorphic higher-order functions.While type information gives the input-output description of the functions, the semantic information is captured by equational specifications. Knowledge about the functions is represented as equalities of functional expressions in the form of equations. By equational axiomatization of the query language, database problems of query equivalence and answering-query with views can be posed as equational word-problems and equational matching.

We propose a new functional framework for modeling, querying and reasoning about OLAP databases. The framework represents data (data cubes and dimensional hierarchies) and querying constructs as first-order and second-order functional symbols respectively. A polymorphic attribute-based type system is used to annotate the functional symbols with proper type information. Furthermore, semantic knowledge about the functional symbols, such as the properties of dimensional hierarchical structures and algebraic identities among query constructs, can be specified by equations which permits equational reasoning on equivalence of OLAP queries and generalized summarizability of aggregate views.

Many location-based applications require constant monitoring of k-nearest neighbor (k-NN) queries over moving objects within a geographic area. Existing approaches to this problem have focused on predictive queries, and relied on the assumption that the trajectories of the objects are fully predictable at query processing time. We relax this assumption, and propose two efficient and scalable algorithms using grid indices. One is based on indexing objects, and the other on queries. For each approach, a cost model is developed, and a detailed analysis along with the respective applicability is presented. The object-indexing approach is further extended to multi-levels to handle skewed data. We show by experiments that our grid-based algorithms significantly outperform R-tree-based solutions. Extensive experiments are also carried out to study the properties and evaluate the performance of the proposed approaches under a variety of settings.

We study the problem of economical representation of subsets of structured sets, which are sets equipped with a set cover or a family of preorders. Given a structured set U , and a language L whose expressions define subsets of U , the problem of minimum description length in L (L-MDL) is: “given a subset V of U , find a shortest string in L that defines V .” Depending on the structure and the language, the MDL-problem is in general intractable. We study the complexity of the MDL-problem for various structures and show that certain specializations are tractable. The families of focus are hierarchy, linear order, and their multidimensional extensions; these are found in the context of statistical and OLAP databases. In the case of general OLAP databases, data organization is a mixture of multidimensionality, hierarchy, and ordering, which can also be viewed naturally as a cover-structured ordered set. Efficient algorithms are provided for the MDL-problem for hierarchical and linearly ordered structures, and we prove that the multidimensional extensions are NP-complete. Finally, we illustrate the application of the theory to summarization of large result sets and (multi) query optimization for ROLAP queries.

We study the problem of economical representation of subsets of structured sets, that is, sets equipped with a set cover. Given a structured set U, and a language L whose expressions define subsets of U, the problem of Minimum Description Length in L (L-MDL) is: "given a subset V of U, find a shortest string in L that defines V".We show that the simple set cover is enough to model a number of realistic database structures. We focus on two important families: hierarchical and multidimensional organizations. The former is found in the context of semistructured data such as XML, the latter in the context of statistical and OLAP databases. In the case of general OLAP databases, data organization is a mixture of multidimensionality and hierarchy, which can also be viewed naturally as a structured set. We study the complexity of the L-MDL problem in several settings, and provide an efficient algorithm for the hierarchical case.Finally, we illustrate the application of the theory to summarization of large result sets, (multi) query optimization for ROLAP queries, and XML queries.