Low visibility events due to fog cause an adverse impact on transportation in North India during the winter season. In this study, in-situ visibility (METAR) observations and satellite (INSAT -3D) fog product are used to detect the fog for 7 North Indian cities from 2013–2021. Both fog products have a different spatial scale and theoretical background. One should have an idea of an agreement between these two fog data sources before making a combined use. Hence, equivalent visibility for the satellite fog is found out, keeping overall accuracy and Kohen's Kappa coefficient as measures of the agreement. The equivalent visibility for INSAT -3D fog product is 306 m, with an overall accuracy of 0.96 and Kohen's Kappa coefficient of 0.29. The non-fog observations outnumber fog observations and make the dataset imbalanced, leading to a smaller value of Kohen's Kappa coefficient despite a large overall accuracy. The equivalent visibility varies between 161 to 998 m for different cities, indicating some spatial variability altering the agreement.

More and more companies are running Big Data workloads on cloud platforms. Configuration tuning of these data engines continues to be an essential but difficult undertaking. Cloud platforms further add to this complexity due to elasticity of compute resources and availability of different machine types. Data engineers have to choose the machine type and the cluster size in addition to the other configuration options. In this paper, we address the problem of automatically determining good configuration parameters for SQL workloads on SQL-On-Hadoop Engines like Hive and Spark, with the goal of optimizing resource usage and cost. We chose to focus on SQL workloads because SQL or SQL-like languages continue to be the most popular choice of ETL engineers and analysts. We propose a model based approach that relies on simple rules and insights into SQL Data Engine behavior and evaluate its effectiveness on both synthetic and real workloads. We show that very simple models can provide very good recommendations compared to the default configuration. In fact, we found that these were often better than those chosen by experts on real customer workloads. A somewhat surprising result is that more expensive machines with larger RAMs often do not lead to significant improvements in query execution times. The principles behind our model based approach are generic and can be adopted for any big data engine.

Prior solutions for securely handling SQL range predicates in outsourced Cloud-resident databases have primarily focused on passive attacks in the Honest-but-Curious adversarial model, where the server is only permitted to observe the encrypted query processing. We consider here a significantly more powerful adversary, wherein the server can launch an active attack by clandestinely issuing specific range queries via collusion with a few compromised clients. The security requirement in this environment is that data values from a plaintext domain of size N should not be leaked to within an interval of size $$H$$ . Unfortunately, all prior encryption schemes for range predicate evaluation are easily breached with only $$O(\log _2\psi )$$ range queries, where $$\psi = N{/}H$$ . To address this lacuna, we present SPLIT, a new encryption scheme where the adversary requires exponentially more— $${\mathbf{O}}(\psi )$$ —range queries to breach the interval constraint and can therefore be easily detected by standard auditing mechanisms. The novel aspect of SPLIT is that each value appearing in a range-sensitive column is first segmented into two parts. These segmented parts are then independently encrypted using a layered composition of a secure block cipher with the order-preserving encryption and prefix-preserving encryption schemes, and the resulting ciphertexts are stored in separate tables. At query processing time, range predicates are rewritten into an equivalent set of table-specific sub-range predicates, and the disjoint union of their results forms the query answer. A detailed evaluation of SPLIT on benchmark database queries indicates that its execution times are well within a factor of two of the corresponding plaintext times, testifying its efficiency in resisting active adversaries.

Time-travel text search over a temporally evolving document collection is useful in various applications. Supporting a wide range of query classes demanded by these applications require different index layouts optimized for their respective query access patterns. The problem we tackle is how to efficiently handle different query classes using the same index layout.

Quantifying the similarity between two trajectories is a fundamental operation in analysis of spatio-temporal databases. While a number of distance functions exist, the recent shift in the dynamics of the trajectory generation procedure violates one of their core assumptions; a consistent and uniform sampling rate. In this paper, we formulate a robust distance function called Edit Distance with Projections (EDwP) to match trajectories under inconsistent and variable sampling rates through dynamic interpolation. This is achieved by deploying the idea of projections that goes beyond matching only the sampled points while aligning trajectories. To enable efficient trajectory retrievals using EDwP, we design an index structure called TrajTree. TrajTree derives its pruning power by employing the unique combination of bounding boxes with Lipschitz embedding. Extensive experiments on real trajectory databases demonstrate EDwP to be up to 5 times more accurate than the state-of-the-art distance functions. Additionally, TrajTree increases the efficiency of trajectory retrievals by up to an order of magnitude over existing techniques.

Many of the ETL products in the market today provide tools for design of ETL workflows, with very little or no support for opti-mization of such workflows. Optimization of ETL workflows pose several new challenges compared to traditional query optimization in database systems. There have been many attempts both in the industry and the research community to support cost-based opti-mization techniques for ETL Workflows, but with limited success. Non-availability of source statistics in ETL is one of the major chal-lenges that precludes the use of a cost based optimization strategy. However, the basic philosophy of ETL workflows of design once and execute repeatedly allows interesting possibilities for determin-ing the statistics of the input. In this paper, we propose a frame-work to determine various sets of statistics to collect for a given workflow, using which the optimizer can estimate the cost of any alternative plan for the workflow. The initial few runs of the work-flow are used to collect the statistics and future runs are optimized based on the learned statistics. Since there can be several alterna-tive sets of statistics that are sufficient, we propose an optimization framework to choose a set of statistics that can be measured with the least overhead. We experimentally demonstrate the effective-ness and efficiency of the proposed algorithms.

We address the problem of mining targeted association rules over multidimensional market-basket data. Here, each transaction has, in addition to the set of purchased items, ancillary dimension attributes associated with it. Based on these dimensions, transactions can be visualized as distributed over cells of an n-dimensional cube. In this framework, a targeted association rule is of the form {X → Y}R, where R is a convex region in the cube and X → Y is a traditional association rule within region R. We first describe the TOARM algorithm, based on classical techniques, for identifying targeted association rules. Then, we discuss the concepts of bottom-up aggregation and cubing, leading to the Cell Union technique. This approach is further extended, using notions of cube-count interleaving and credit-based pruning, to derive the Ice Cube algorithm. Our experiments demonstrate that Ice Cube consistently provides the best execution time performance, especially for large and complex data cubes.

Master data management (MDM) integrates data from multiple structured data sources and builds a consolidated 360-degree view of business entities such as customers and products. Today's MDM systems are not prepared to integrate information from unstructured data sources, such as news reports, emails, call-center transcripts, and chat logs. However, those unstructured data sources may contain valuable information about the same entities known to MDM from the structured data sources. Integrating information from unstructured data into MDM is challenging as textual references to existing MDM entities are often incomplete and imprecise and the additional entity information extracted from text should not impact the trustworthiness of MDM data. In this paper, we present an architecture for making MDM text-aware and showcase its implementation as IBM Info-Sphere MDM Extension for Unstructured Text Correlation, an add-on to IBM InfoSphere Master Data Management Standard Edition. We highlight how MDM benefits from additional evidence found in documents when doing entity resolution and relationship discovery. We experimentally demonstrate the feasibility of integrating information from unstructured data sources into MDM.

Customer satisfaction (CSAT) is the key driver for retention and growth in retail banking and several techniques have been applied by banks to achieve this. For instance, banks in emerging markets with high footfall in branches have gone beyond the traditional approach of segmenting customers and services to optimizing the wait time for customers visiting the bank's branch. While this approach has significantly improved service quality, it has also added a new dimension in the service quality metric : pro-actively identify and address customer needs for (i) efficient banking experience and (ii) enhancing profit by selling additional services to existing customer. In this paper we present a system that addresses the challenge involved in providing better service to retail banking customer while ensuring that a larger share of customer's wallet comes to the branch. We do this by combining predictive analytics, scheduling and process optimization techniques.

A Reverse Skyline query returns all objects whose skyline contains the query object. In this paper, we consider Reverse Skyline query processing where the distance between attribute values are not necessarily metric. We outline real world cases that motivate Reverse Skyline processing in such scenarios. We consider various optimizations to develop efficient algorithms for Reverse Skyline processing. Firstly, we consider block-based processing of objects to optimize on IO costs. We then explore pre-processing to re-arrange objects on disk to speed-up computational and IO costs. We then present our main contribution, which is a method of using group-level reasoning and early pruning to micro-optimize processing by reducing attribute level comparisons. An extensive empirical evaluation with real-world datasets and synthetic data of varying characteristics shows that our optimization techniques are indeed very effective in dramatically speeding Reverse Skyline processing, both in terms of computational costs and IO costs.

Association rule mining is an indispensable tool for discovering insights from large databases and data warehouses.The data in a warehouse being multi-dimensional, it is often useful to mine rules over subsets of data defined by selections over the dimensions.Such interactive rule mining over multi-dimensional query windows is difficult since rule mining is computationally expensive.Current methods using pre-computation of frequent itemsets require counting of some itemsets by revisiting the transaction database at query time, which is very expensive.We develop a method (RMW) that identifies the minimal set of itemsets to compute and store for each cell, so that rule mining over any query window may be performed without going back to the transaction database.We give formal proofs that the set of itemsets chosen by RMW is sufficient to answer any query and also prove that it is the optimal set to be computed for 1 dimensional queries.We demonstrate through an extensive empirical evaluation that RMW achieves extremely fast query response time compared to existing methods, with only moderate overhead in pre-computation and storage.

A R k NN query returns all objects whose nearest k neighbors contain the query object. In this paper, we consider R k NN query processing in the case where the distances between attribute values are not necessarily metric. Dissimilarities between objects could then be a monotonic aggregate of dissimilarities between their values, such aggregation functions being specified at query time. We outline real world cases that motivate R k NN processing in such scenarios. We consider the AL-Tree index and its applicability in R k NN query processing. We develop an approach that exploits the group level reasoning enabled by the AL-Tree in R k NN processing. We evaluate our approach against a Naive approach that performs sequential scans on contiguous data and an improved block-based approach that we provide. We use real-world datasets and synthetic data with varying characteristics for our experiments. This extensive empirical evaluation shows that our approach is better than existing methods in terms of computational and disk access costs, leading to significantly better response times.

A skyline query returns a set of objects that are not dominated by other objects. An object is said to dominate another if it is closer to the query than the latter on all factors under consideration. In this paper, we consider the case where the similarity measures may be arbitrary and do not necessarily come from a metric space. We first explore middleware algorithms, analyze how skyline retrieval for non-metric spaces can be done on the middleware backend, and lay down a necessary and sufficient stopping condition for middleware-based skyline algorithms. We develop the Balanced Access Algorithm, which is provably more IO-friendly than the state-of-the-art algorithm for skyline query processing on middleware and show that BAA outperforms the latter by orders of magnitude. We also show that without prior knowledge about data distributions, it is unlikely to have a middleware algorithm that is more IO-friendly than BAA. In fact, we empirically show that BAA is very close to the absolute lower bound of IO costs for middleware algorithms. Further, we explore the non-middleware setting and devise an online algorithm for skyline retrieval which uses a recently proposed value space index over non-metric spaces (AL-Tree [10]). The AL-Tree based algorithm is able to prune subspaces and efficiently maintain candidate sets leading to better performance. We compare our algorithms to existing ones which can work with arbitrary similarity measures and show that our approaches are better in terms of computational and disk access costs leading to significantly better response times.

The top-k retrieval problem requires finding k objects most similar to a given query object. Similarities between objects are most often computed as aggregated similarities of their attribute values. We consider the case where the similarities between attribute values are arbitrary (non-metric), due to which standard space partitioning indexes cannot be used. Among the most popular techniques that can handle arbitrary similarity measures is the family of threshold algorithms. These were designed as middleware algorithms that assume that similarity lists for each attribute are available and focus on efficiently merging these lists to arrive at the results. In this paper, we explore multi-dimensional indexing of non-metric spaces that can lead to efficient pruning of the search space utilizing inter-attribute relationships, during top-k computation. We propose an indexing structure, the AL-Tree and an algorithm to do top-k retrieval using it in an online fashion. The ALTree exploits the fact that many real world attributes come from a small value space. We show that our algorithm performs much better than the threshold based algorithms in terms of computational cost due to efficient pruning of the search space. Further, it out-performs them in terms of IOs by upto an order of magnitude in case of dense datasets.

Document analysis research typically focuses on document image understanding or classic problems in text classification, clustering, summarization and discovery. While that is an important aspect of document management, in practice, documents lifecycles are often determined by the context of the business process that they are relevant to. It therefore becomes necessary for the document analysis techniques to recognize and leverage the contextual information provided by a supporting schema and business process. This paper presents an intelligent document management framework with relevant document analysis, metadata extraction, and business process association algorithms and methodology. The architecture supporting this framework seamlessly integrates a runtime environment with an authoring environment by combining relational data modeling tools with document classification techniques. The runtime environment accepts incoming documents, classifies the document, extracts metadata and executes customized business logic. The authoring environment supports the association of a class of documents with a relational document schema, identification of attribute values that must be extracted automatically, generation of relevant business logic, and deployment of authoring artifacts into the runtime architecture. We demonstrate the use of this framework with representative real-world document transformative applications.

The daily use of Internet-based services is involved with hundreds of different tasks being performed by multiple users. A single task is typically involved with a sequence of Web URLs invocation. We study the problem of pattern detection in Web logs to identify tasks performed by users, and analyze task trends over time using a grammar-based framework. Our results are demonstrated on a corporate Intranet portal application with 7000 users over a 6 week period and demonstrate compelling business value from this high-level task analysis.

Association rule mining is a valuable decision support technique that can be used to analyze customer preferences, buying patterns, and product correlations.Current systems are however handicapped by the long processing times required by mining algorithms that make them unsuitable for interactive use.In this paper, we propose the use of a knowledge cache that can reduce the response time by several orders of magnitude.Most of the performance gain comes from the idea of guaranteed support that allows us to completely eliminate database accesses in a large number of cases.Using this cache, the time taken to answer a query is proportional to just the size of the result, rather than to the size of the database.Cache replacement is best done by a benefit-metric based strategy that can easily adapt to changing query patterns.We show that our caching scheme is quite robust, providing good performance on a wide variety of data distributions even for small cache sizes.We also compare algorithms that use precomputation to those that use caching and show that the best performance is obtained by combining both these techniques.Finally, we illustrate how the idea of caching can be readily extended to a broader class of problems such as the mining of generalized association rules.

Caching has been proposed (and implemented) by OLAP systems in order to reduce response times for multidimensional queries. Previous work on such caching has considered table level caching and query level caching. Table level caching is more suitable for static schemes. On the other hand, query level caching can be used in dynamic schemes, but is too coarse for “large” query results. Query level caching has the further drawback for small query results in that it is only effective when a new query is subsumed by a previously cached query. In this paper, we propose caching small regions of the multidimensional space called “chunks”. Chunk-based caching allows fine granularity caching, and allows queries to partially reuse the results of previous queries with which they overlap. To facilitate the computation of chunks required by a query but missing from the cache, we propose a new organization for relational tables, which we call a “chunked file.” Our experiments show that for workloads that exhibit query locality, chunked caching combined with the chunked file organization performs better than query level caching. An unexpected benefit of the chunked file organization is that, due to its multidimensional clustering properties, it can significantly improve the performance of queries that “miss” the cache entirely as compared to traditional file organizations.

Database researchers have made significant progress on several research issues related to multidimensional data analysis, including the development of fast cubing algorithms, efficient schemes for creating and maintaining precomputed group-bys, and the design of efficient storage structures for multidimensional data. However, to date there has been little or no work on multidimensional query optimization. Recently, Microsoft has proposed “OLE DB for OLAP” as a standard multidimensional interface for databases. OLE DB for OLAP defines Multi-Dimensional Expressions (MDX), which have the interesting and challenging feature of allowing clients to ask several related dimensional queries in a single MDX expression. In this paper, we present three algorithms to optimize multiple related dimensional queries. Two of the algorithms focus on how to generate a global plan from several related local plans. The third algorithm focuses on generating a good global plan without first generating local plans. We also present three new query evaluation primitives that allow related query plans to share portions of their evaluation. Our initial performance results suggest that the exploitation of common subtask evaluation and global optimization can yield substantial performance improvements when relational database systems are used as data sources for multidimensional analysis.

Computing multiple related group-bys and aggregates is one of the core operations of On-Line Analytical Processing (OLAP) applications. Recently, Gray et al. [GBLP95] proposed the “Cube” operator, which computes group-by aggregations over all possible subsets of the specified dimensions. The rapid acceptance of the importance of this operator has led to a variant of the Cube being proposed for the SQL standard. Several efficient algorithms for Relational OLAP (ROLAP) have been developed to compute the Cube. However, to our knowledge there is nothing in the literature on how to compute the Cube for Multidimensional OLAP (MOLAP) systems, which store their data in sparse arrays rather than in tables. In this paper, we present a MOLAP algorithm to compute the Cube, and compare it to a leading ROLAP algorithm. The comparison between the two is interesting, since although they are computing the same function, one is value-based (the ROLAP algorithm) whereas the other is position-based (the MOLAP algorithm). Our tests show that, given appropriate compression techniques, the MOLAP algorithm is significantly faster than the ROLAP algorithm. In fact, the difference is so pronounced that this MOLAP algorithm may be useful for ROLAP systems as well as MOLAP systems, since in many cases, instead of cubing a table directly, it is faster to first convert the table to an array, cube the array, then convert the result back to a table.