Instruction Tuning (IT) is crucial for enhancing Large Language Models (LLMs), but training on all available instructions is often unnecessary and computationally costly. Recent studies show that small, well-chosen subsets can match or exceed full dataset performance, motivating efficient data selection techniques. While gradient-based methods like LESS estimate sample influence effectively, they are expensive due to per-sample gradient computation. We propose Approx-LESS, a scalable alternative that computes LoRA-based gradient features for a small fraction of the samples and trains regression models to predict influence scores for the rest. This enables selection and tuning on the most impactful samples. On three validation sets with a fixed 270K instruction corpus, Approx-LESS outperforms applicable baselines and closely matches LESS, reducing gradient extraction time by over 3x. It also shows high sample selection overlap with LESS, making it an effective, low-cost method for influence-based instruction tuning.

This paper introduces the novel concept of cost-sensitive data acquisition (CDA), a desirable addition to the data preparation process in a data science pipeline that focuses on strategically acquiring data from various priced sources, such as data markets, under budget constraints. CDA improves data quality by identifying the best set of values to acquire and integrating them into incomplete datasets, optimizing a particular objective defined in the resulting tables (data products). This paper focuses on CDA for a single relational table while also exploring possible extensions to multi-table contexts. First, we introduce an algorithm that utilizes conformal risk control to select rows likely to be included in the data product with probabilistic guarantees. We then investigate ways to acquire data to complete these rows under various CDA scenarios. We start with a scenario where data records are available on a row-wise basis, which proves to be an NP-hard problem. To solve this problem, we introduce an efficient row-wise greedy algorithm (RGreedy), which approaches an approximation ratio of 1. Subsequently, we explore a more generic scenario where each unit of data for acquisition may involve multiple records with a subset of the attributes. We propose a coverage minimum option selection (CMOS) algorithm for its solution, focusing on scalability. Through empirical evaluations on three real-world datasets and one synthetic dataset, we demonstrate that our methods yield performance improvements of 20 % to 40 % over applicable baselines.

High-accuracy object detection on resource-constrained devices is becoming increasingly important for applications in autonomous systems, smart surveillance, and mobile computing. However, deploying high-performance object detection models on these devices is impractical due to computational limitations, and transmitting and processing all data on a much more powerful remote server running significantly more complex and accurate models, known as full cloud offloading, incurs high latency and is constrained by network bandwidth. In this paper, we propose a selective cloud offloading framework that provides users with control over the tradeoff between prediction accuracy and processing cost. Our approach employs a lightweight object detection model on the edge to make initial predictions, leveraging conformal prediction to quantify uncertainty. Only high-uncertainty regions are offloaded to the cloud, where more powerful models refine predictions, improving overall detection accuracy. To further optimize efficiency, multiple uncertain regions are combined into a single image before offloading, reducing transmission and processing costs. We present the architecture of our system and evaluate its performance on real datasets, demonstrating that it achieves cloud-level accuracy while significantly reducing offloading overhead.

The exponential growth of video data highlights the necessity of exploring large-scale video repositories to extract valuable insights. Querying video clips based on content and temporal attributes is a critical task. However, existing solutions face two major challenges: insufficient flexibility in handling complex query conditions involving statistical reasoning and temporal constraints, and low efficiency under high query quality requirements and resource constraints.

Large language models (LLMs) have revolutionized natural language interfaces for databases, particularly in text-to-SQL conversion. However, current approaches often generate unreliable outputs when faced with ambiguity or insufficient context. We present Reliable Text-to-SQL (RTS), a novel framework that enhances query generation reliability by incorporating abstention and human-in-the-loop mechanisms. RTS focuses on the critical schema linking phase, which aims to identify the key database elements needed for generating SQL queries. It autonomously detects potential errors during the answer generation process and responds by either abstaining or engaging in user interaction. A vital component of RTS is the Branching Point Prediction (BPP) which utilizes statistical conformal techniques on the hidden layers of the LLM model for schema linking, providing probabilistic guarantees on schema linking accuracy. We validate our approach through comprehensive experiments on the BIRD benchmark, demonstrating significant improvements in robustness and reliability. Our findings highlight the potential of combining transparent-box LLMs with human-in-the-loop processes to create more robust natural language interfaces for databases. For the BIRD benchmark, our approach achieves near-perfect schema linking accuracy, autonomously involving a human when needed. Combined with query generation, we demonstrate that near-perfect schema linking and a small query generation model can almost match SOTA accuracy achieved with a model orders of magnitude larger than the one we use.

Visual analysis of large time-series data often requires transformations over multivariate time series. Existing methods struggle to meet interactive response time requirements, relying on full transformations that incur high computation costs. We propose a visualization-oriented transformation system PIVOT that incrementally generates accurate visualizations by selectively transforming only essential data samples. At its core is a transformation-aware query mechanism that efficiently computes point-wise transformations by leveraging cached hierarchical data on the server. To support responsive interaction, we introduce a pixel-based error-bound guarantee that estimates the accuracy of intermediate visualizations without requiring a reference, enabling a balance between latency and visual fidelity. Experiments show that PIVOT achieves highly accurate visualizations with interactive response times, outperforming existing error-free methods by up to an order of magnitude on billion-scale datasets.

With the rise of Large Language Models (LLMs), tourists increasingly use it for route planning by entering keywords for attractions, instead of relying on traditional manual map services. LLMs provide generally reasonable suggestions, but often fail to generate optimal plans that account for detailed user requirements, given the vast number of potential POIs and possible routes based on POI combinations within a real-world road network. In this case, a route-planning API could serve as an external tool, accepting a sequence of keywords and returning the top-k best routes tailored to user requests. To address this need, this paper introduces the Keyword-Aware Top-k Routes (KATR) query that provides a more flexible and comprehensive semantic to route planning that caters to various user's preferences including flexible POI visiting order, flexible travel distance budget, and personalized POI ratings. Subsequently, we propose an explore-and-bound paradigm to efficiently process KATR queries by eliminating redundant candidates based on estimated score bounds from global to local levels. Extensive experiments demonstrate our approach's superior performance over existing methods across different scenarios.

This paper introduces DAMOCRO, a data migration framework using online classification and tuple reordering to improve throughput and decrease the costs of data migration. The DAMOCRO workflow consists of four main steps. First, it classifies records into subgroups to maximize the similarity within each group. Next, it reorders tuples within these groups, ensuring that similar tuples are adjacent. Subsequently, column-wise compression is applied to each group. Finally, the compressed data is transferred from the source to the target machine. The initial two steps enhance the compression ratio, thereby boosting throughput and reducing costs. Our evaluations on five real-world datasets and two benchmark datasets, show that the online classification process in DAMOCRO improves throughput by more than 24% and reduces costs by over 19% compared to baselines. Besides, implementing reordering based on functional dependencies brings an additional cost reduction ranging from 10% to 60%, while also enhancing throughput.

The recent surge in learned index algorithms, along-side traditional indexes, has greatly diversified indexing options to support query processing in databases. Despite the rapid expansion of learned indexes, there remains a significant gap in tools for index algorithm selection. Traditional research on index selection has largely focused on recommending which columns to index, as the choice between algorithms like B+tree or hash index was once straightforward. This was managed through basic rules or experiential judgment, given the historically limited options. However, this approach is inadequate today, due to the growing diversity and complexity of index algorithms. In this paper, we introduce a Learned INDex Algorithm Selector, LINDAS. Taking a learned approach, LINDAS uniquely focuses on automatically selecting the most suitable index algorithm for a specific column, that satisfies diverse performance objectives in a wide range of applications. We explore the design space of LINDAS, employing a carefully designed featurization approach to capture both data-and workload-specific characteristics with attention mechanisms, as well as the meta-features of index algorithms. Two variants of LINDAS are designed to cater to diverse scenarios and adapt readily to new datasets, workloads, and emerging index algorithms. Comprehensive evaluations of LINDAS across various datasets and workloads demonstrate its effectiveness and superiority compared to applicable baselines.

In recent years, there has been a growing recognition that high-quality training data is crucial for the performance of machine learning models. This awareness has catalyzed both research endeavors and industrial initiatives dedicated to data acquisition to enhance diverse dimensions of model performance. Among these dimensions, model confidence holds paramount importance; however, it has often been overlooked in prior investigations into data acquisition methodologies. To address this gap, our work focuses on improving the data acquisition process with the goal of enhancing the confidence of Machine Learning models. Specifically, we operate within a practical context where limited samples can be obtained from a large data pool. We employ well-established model confidence metrics as our foundation, and we propose two methodologies, Bulk Acquisition (BA) and Sequential Acquisition (SA), each geared towards identifying the sets of samples that yield the most substantial gains in model confidence. Recognizing the complexity of BA and SA, we introduce two efficient approximate methods, namely kNN-BA and kNN-SA, restricting data acquisition to promising subsets within the data pool. To broaden the applicability of our solutions, we introduce a Distribution-based Acquisition approach that makes minimal assumption regarding the data pool and facilitates the data acquisition across various settings. Through extensive experimentation encompassing diverse datasets, models, and parameter configurations, we demonstrate the efficacy of our proposed methods across a range of tasks. Comparative experiments with alternative applicable baselines underscore the superior performance of our proposed approaches.

Video Database Management Systems (VDBMS) leverage advancements in computer vision and deep learning for efficient video data analysis and retrieval. This paper introduces the concept of user-specified Clues, allowing users to incorporate domain-specific knowledge, referred to as Clues, into query optimization. Clues are expressed as Clue types, each associated with optimization rules, and applied to queries through Clue instances. The extensible ClueVQS system we present to incorporate these ideas, optimizes queries automatically, utilizing Clues to improve processing efficiency. We also introduce algorithms to optimize queries using Clues allowing for trade-offs between speed and query accuracy. Our proposals and system address challenges such as data-dependent Clue effectiveness, limiting search space, and accuracy-efficiency trade-offs. Detailed experimental results demonstrate query speedups of up to two orders of magnitude compared to other applicable approaches, and a reduction of the query optimizer time by up to 95% while respecting user-specified accuracy constraints, showcasing the effectiveness of the proposed framework.

The problem of identifying thek-shortest paths (KSPs for short) in a dynamic road network is essential to many location-based services. Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Very often such services have to process numerous KSP queries over large road networks at the same time, thus there is a pressing need to identify distributed solutions for this problem. However, most existing approaches are designed to identify KSPs on a static graph in a sequential manner (i.e., the$(i+1)^{th}$shortest path is generated based on the$i^{th}$shortest path), restricting their scalability and applicability in a distributed setting. We therefore propose KSP-DG, a distributed algorithm for identifyingk-shortest paths in a dynamic graph. It is based on partitioning the entire graph into smaller subgraphs, and reduces the problem of determining KSPs into the computation of partial KSPs in relevant subgraphs, which can execute in parallel on a cluster of servers. A distributed two-level index called DTLP is developed to facilitate the efficient identification of relevant subgraphs. A salient feature of DTLP is that it indexes a set of virtual paths that are insensitive to varying traffic conditions in an efficient and compact fashion, leading to very low maintenance cost in dynamic road networks. This is the first treatment of the problem of processing KSP queries over dynamic road networks. Extensive experiments conducted on real road networks confirm the superiority of our proposal over baseline methods.

We study the problem of processing continuous$k$nearest neighbor (C$k$NN) queries over moving objects on road networks, which is an essential operation in a variety of applications. We are particularly concerned with scenarios where the object densities in different parts of the road network evolve over time as the objects move. Existing methods on C$k$NN query processing are ill-suited for such scenarios as they utilize index structures with fixed granularities and are thus unable to keep up with the evolving object densities. In this paper, we directly address this problem and propose an object density aware index structure called ODIN that is an elastic tree built on a hierarchical partitioning of the road network. It is equipped with the unique capability of dynamically folding/unfolding its nodes, thereby adapting to varying object densities. We further present the ODIN-KNN-Init and ODIN-KNN-Inc algorithms for the initial identification of the$k$NNs and the incremental update of query result as objects move. Thorough experiments on both real and synthetic datasets confirm the superiority of our proposal over several baseline methods.

The widespread use of positioning devices has given rise to many trajectories, with each having three explicit attributes: user ID, location ID, and time-stamp and an implicit attribute: activity type (akin to "topic" in text mining). To model these trajectories, existing works learn different attribute representations by either introducing latent activity types based on topic models or transforming the location and time context into a low-dimensional space via embedding techniques. In this paper, we propose a holistic approach named Human Mobility Representation Model (HMRM) to simultaneously produce the vector representations of all four (explicit and implicit) attributes. We evaluate HMRM on two real check-in datasets collected from Foursquare. Experimental results show that HMRM could not only improve the performance of capturing latent activity types, but also learn better trajectory embeddings.

Video analysis frameworks supporting declarative queries are actively researched in recent years. A major prerequisite in executing such queries is the ability to accurately extract metadata at the frame level utilizing various computer vision algorithms, including object tracking models. Tracking models are of profound importance as they establish unique identifiers for the objects across frames.Despite the maturity of tracking algorithms, they still face challenges (such as occlusions, object glaze etc.) which diminish their quality and accuracy. This gives rise to the track fragmentation problem in which a single track is fragmented into multiple smaller tracks. This impacts downstream temporal querying applications degrading query accuracy.In this paper, we propose an algorithm, TMerge for identifying and merging fragmented tracks that constitutes a pre-processing step during data ingestion for video query processing. The algorithm exploits the properties of the problem and utilizes a sampling methodology that significantly reduces the time required to pre-process and ingest the video sequence.We comprehensively describe and analyze our proposals utilizing real data sets and also present the results of a detailed experimental evaluation varying parameters of interest. We demonstrate performance savings of up to two orders of magnitude without loss in accuracy.

Numerous cloud platforms are available to deploy and train deep models as well as process data, such as Amazon Rekognition and Azure custom Vision Service, which have made it easy for companies to adopt deep learning technologies in their operations. Commonly such services price usage per image or frame in typical applications that consume video streams and as a result the costs rapidly accumulate. In this paper we introduce a model, named EventHit, that is able to marshal model inference requests in such services by making predictions over the video stream about events of interest. As such only relevant video segments are sent for analysis to the cloud infrastructure and irrelevant parts are filtered from further processing. We introduce the architecture and fully describe its components. We present two novel optimizations in this context that aim to provide control over the trade-off between prediction accuracy (especially regarding the probability of missing an event of interest) and processing cost at the cloud infrastructure. We fully describe and analyze our proposals in the context of real datasets. We also present the results of a detailed experimental evaluation varying parameters of interest and demonstrate the practical utility of our proposals.

While selecting the execution plan for a given query based on a single estimated cost is a generally-adopted strategy, it is usually error-prone and fails to comprehensively profile the plan performance. In this work, we complement existing plan selection methods by proposing a new approach named ET, which produces execution time distributions for query plans utilizing conformal predictions. We develop dbET, a framework that integrates ET into an existing DBMS, requiring no modification to the DBMS and only incurring minor overhead to query processing. Based on the execution time distribution, we design several intuitive yet fundamental query execution objectives and devise the corresponding plan selection strategies. Our experiments on several widely-adopted benchmarks showcase that our design significantly improves the capability of DBMSs in achieving the designated objectives.

We present a novel multi-level representation of time series called OM3 that facilitates efficient interactive progressive visualization of large data stored in a database and supports various interactions such as resizing, panning, zooming, and visual query. Based on our proposed line-segment aggregation, this representation can produce error-free line visualizations that preserve the shape of a time series in windows of arbitrary sizes. To reduce the interaction latency, we develop an incremental tree-based query strategy to support progressive visualizations, allowing a finer control on the accuracy-time tradeoff. We quantitatively compare OM3 with state-of-the-art methods, including a method implemented on a leading time-series database InfluxDB, in two settings with databases residing either in the local area network or on the cloud. Results show that OM^3 maintains a low latency within 300~ms on the web browser and a high data reduction ratio regardless of the data size (ranging from millions to billions of records), achieving around 1,000 times faster than the state-of-the-art methods on the largest dataset experimented with.

The markets for data and AI models are rapidly emerging and increasingly significant in the realm and the practices of data science and artificial intelligence. These markets are being studied from diverse perspectives, such as e-commerce, economics, machine learning, and data management. In light of these developments, there is a pressing need to present a comprehensive and forward-looking survey on the subject to the database and data management community. In this tutorial, we aim to provide a comprehensive and interdisciplinary introduction to data and AI model markets. Unlike a few recent surveys and tutorials that concentrate only on the economics aspect, we take a novel perspective and examine data and AI model markets as grand opportunities to address the long-standing problem of data and model sharing, discovery, and integration. We motivate the importance of data and model markets using practical examples, present the current industry landscape of such markets, and explore the modules and options of such markets from multiple dimensions, including assets in the markets (e.g., data versus models), platforms, and participants. Furthermore, we summarize the latest advancements and examine the future directions of data and AI model markets as mechanisms for enabling and facilitating sharing, discovery, and integration.

The prevalence of location-based services has generated a deluge of check-ins, enabling the task of human mobility understanding. Among the various types of information associated with the check-in venues, categories (e.g., Bar and Museum ) are vital to the task, as they often serve as excellent semantic characterization of the venues. Despite its significance and importance, a large portion of venues in the check-in services do not have even a single category label, such as up to 30% of venues in the Foursquare system lacking category labels. We, therefore, address the problem of semantic venue annotation, i.e., labeling the venue with a semantic category. Existing methods either fail to fully exploit the contextual information in the check-in sequences, or do not consider the semantic correlations across related categories. As such, we devise a Tree-guided Multi-task Embedding model (TME for short) to learn effective representations of venues and categories for the semantic annotation. TME jointly learns a common feature space by modeling multi-contexts of check-ins and utilizes the predefined category hierarchy to regularize the relatedness among categories. We evaluate TME over the task of semantic venue annotation on two check-in datasets. Experimental results show the superiority of TME over several state-of-the-art baselines.

Recent advances in Computer Vision have contributed to solid accuracy and efficiency improvements in many tasks such as object detection and tracking, enabling new opportunities for video analytics. In this paper, we initiate the study of ranked window queries that aim to retrieve clips from large video repositories in which objects co-occur in a query-specified fashion. For example, ranked window queries allow retrieval of clips of a set duration (e.g., 10 seconds) with the highest score from a long video, where at least the same 3 cars (with matching conditions based on suitably defined metadata) appear jointly. To answer such queries, we propose a two-phased approach, which builds indexes for all desired objects of the given videos during an Ingestion Phase and evaluates query answers efficiently in the Query Phase. During the Ingestion Phase, the proposed Partition-Based Index Construction (PBIC) algorithm builds indexes on partitions obtained by splitting each given video. Leveraging such indexes, queries are answered in the Query Phase using the Partition-Based Query Processing (PBQP) algorithm, which efficiently produces the desired (query-specified) number of results with the highest scores. We present the outcome of a thorough performance study on real videos that evaluates the performance of the proposed algorithms by varying parameters of interest. Our results indicate that the proposed set of techniques are capable of processing queries efficiently at scale, demonstrating multiple orders of magnitude speedups over other applicable approaches.

Recent advances in Computer Vision (CV) algorithms have improved accuracy and efficiency, making video annotations possible with high accuracy. In this paper, we utilize the annotated data provided by such algorithms and construct graph representations to capture both object labels and spatial-temporal relationships of objects in videos. We define the problem of Spatial and Temporal Constrained Ranked Retrieval (STAR Retrieval) over videos. Based on the graph representation, we propose a two-phase approach, consisting of the ingestion phase, where we construct and materialize the Graph Index (GI), and the query phase, where we compute the top ranked windows (video clips) according to the window matching score efficiently. We propose two algorithms to perform Spatial Matching (SMA) and Temporal Matching (TM) separately with an early-stopping mechanism. Our experiments demonstrate the effectiveness of the proposed methods, achieving orders of magnitude speedups on queries with high selectivity.

As modern applications generate data at an unprecedented speed and often require the querying/analysis of data spanning a large duration, it is crucial to develop indexing techniques that cater to larger-than-memory databases, where data reside on heterogeneous storage devices (such as memory and disk), and support fast data insertion and query processing. In this paper, we propose FILM, a F ully learned I ndex for L arger-than- M emory databases. FILM is a learned tree structure that uses simple approximation models to index data spanning different storage devices. Compared with existing techniques for larger-than-memory databases, such as anti-caching, FILM allows for more efficient query processing at significantly lower main-memory overhead. FILM is also designed to effectively address one of the bottlenecks in existing methods for indexing larger-than-memory databases that is caused by data swapping between memory and disk. More specifically, updating the LRU (for Least Recently Used) structure employed by existing methods for cold data identification (determining the data to be evicted to disk when the available memory runs out) often incurs significant delay to query processing. FILM takes a drastically different approach by proposing an adaptive LRU structure and piggybacking its update onto query processing with minimal overhead. We thoroughly study the performance of FILM and its components on a variety of datasets and workloads, and the experimental results demonstrate its superiority in improving query processing performance and reducing index storage overhead (by orders of magnitudes) compared with applicable baselines.

Next location prediction is of great importance for many location-based applications and provides essential intelligence to various businesses. In previous studies, a common approach to next location prediction is to learn the sequential transitions with massive historical trajectories based on conditional probability. Nevertheless, due to the time and space complexity, these methods (e.g., Markov models) only utilize the just passed locations to predict next locations, neglecting earlier passed locations in the trajectory. In this work, we seek to enhance the prediction performance by incorporating the travel time from all the passed locations in the query trajectory to each candidate next location. To this end, we propose a novel prediction method, namely the Travel Time Difference Model, which exploits the difference between the shortest travel time and the actual travel time to predict next locations. Moreover, we integrate the Travel Time Difference Model with a Sequential and Temporal Predictor to yield a joint model. The joint prediction model integrates local sequential transitions, temporal regularity, and global travel time information in the trajectory for the next location prediction problem. We have conducted extensive experiments on two real-world datasets: the vehicle passage record data and the taxi trajectory data. The experimental results demonstrate significant improvements in prediction accuracy over baseline methods.

The widespread use of positioning devices has given rise to many trajectories, with each having three explicit attributes:user ID,location ID, andtime-stampand an implicit attribute:activity type(akin to “topic” in text mining). To model these trajectories, existing works learn different attribute representations by either introducing latent activity types based on topic models or transforming the location and time context into a low-dimensional space via embedding techniques. In this paper, we propose a holistic approach named Human Mobility Representation Model (HMRM) to simultaneously produce the vector representations of all four (explicit and implicit) attributes. The merits of HMRM lie in that: (1) it models the latent activity types and learns trajectory attribute embeddings in an integrated manner, and (2) it connects the activity-related distributions and these attributes embeddings by adding a newly designed collaborative learning component, and makes them mutually exchanged to take the best of both worlds. We apply HMRM to both unsupervised and supervised tasks including two activity evaluation tasks and two embedding evaluation tasks, on two real check-in datasets collected from Foursquare. Experimental results show that HMRM could not only improve the performance of capturing latent activity types, but also learn better trajectory embeddings.

Venue categories used in location-based social networks often exhibit a hierarchical structure, together with the category sequences derived from users’ check-ins. The two data modalities provide a wealth of information for us to capture the semantic relationships between those categories. To understand the venue semantics, existing methods usually embed venue categories into low-dimensional spaces by modeling the linear context (i.e., the positional neighbors of the given category) in check-in sequences. However, the hierarchical structure of venue categories, which inherently encodes the relationships between categories, is largely untapped. In this article, we propose a venue C ategory E mbedding M odel named Hier-CEM , which generates a latent representation for each venue category by embedding the Hier archical structure of categories and utilizing multiple types of context. Specifically, we investigate two kinds of hierarchical context based on any given venue category hierarchy and show how to model them together with the linear context collaboratively. We apply Hier-CEM to three tasks on two real check-in datasets collected from Foursquare. Experimental results show that Hier-CEM is better at capturing both semantic and sequential information inherent in venues than state-of-the-art embedding methods.

Machine Learning (ML) applications are proliferating in the enterprise. Relational data which are prevalent in enterprise applications are typically normalized; as a result, data has to be denormalized via primary/foreign-key joins to be provided as input to ML algorithms. In this paper, we study the implementation of popular nonlinear ML models, Gaussian Mixture Models (GMM) and Neural Networks (NN), over normalized data addressing both cases of binary and multiway joins over normalized relations. For the case of GMM, we show how it is possible to decompose computation in a systematic way both for binary joins and for multi-way joins to construct mixture models. We demonstrate that by factoring the computation, one can conduct the training of the models much faster compared to other applicable approaches, without any loss in accuracy. For the case of NN, we propose algorithms to train the network taking normalized data as the input. Similarly, we present algorithms that can conduct the training of the network in a factorized way and offer performance advantages. The redundancy introduced by denormalization can be exploited for certain types of activation functions. However, we demonstrate that attempting to explore this redundancy is helpful up to a certain point; exploring redundancy at higher layers of the network will always result in increased costs and is not recommended. We present the results of a thorough experimental evaluation, varying several parameters of the input relations involved and demonstrate that our proposals for the training of GMM and NN yield drastic performance improvements typically starting at 100%, which become increasingly higher as parameters of the underlying data vary, without any loss in accuracy.

Fuel-efficient route recommendation has been increasingly valuable for both energy conservation and environmental protection. Most existing methods analyze fuel consumption factors from the short-distance trajectories. However, due to the differences in the road network structure and route composition between long-distance and short-distance trajectories, directly using these methods to recommend fuel-efficient routes for long-distance drivers is less effective. In addition, previous works usually adopt heuristic algorithms due to efficiency, but empirically set the heuristic functions, which makes it difficult to integrate various influencing factors appropriately. In this paper, we propose a novel fuel-efficient route recommendation model for long-distance driving, LDFeRR. We first identify the potential factors that affect fuel consumption over long distances based on historical trajectories. To fully exploit these factors to estimate fuel consumption and further provide reliable recommendations, we propose to integrate deep learning methods with heuristic algorithm. Specially, we use a multi-layer perceptron (MLP) to predict the fuel consumption of a single road segment. We also employ an attention-based bidirectional gated recurrent unit (Att-BiGRU) to estimate the fuel consumption between two locations connected by routes. In this way, the two cost functions of the classic heuristic algorithm, i.e., A* algorithm, are automatically learned. Extensive experiments on the large real-world dataset demonstrate the effectiveness of our proposed model.

Recent advances in Computer Vision and Deep Learning have made possible the efficient extraction of structured information from frames of video feeds. As such, a stream of objects and their associated classes along with unique object identifiers derived via object tracking can be generated, providing unique objects as they are captured across frames. In this paper we initiate a study of temporal queries involving objects and their co-occurrences in video feeds. For example, queries that identify video segments during which the same two red cars and the same two humans appear jointly for five minutes are of interest to many applications ranging from law enforcement to security and safety. We take the first step and define such queries in a way that they incorporate certain physical aspects of video capture such as object occlusion. We present an architecture consisting of three layers, namely object detection/tracking, intermediate data generation, and query evaluation. We propose two techniques, Marked Frame Set (MFS) and Sparse State Graph (SSG), to organize all detected objects in the intermediate data generation layer, which effectively, given the queries, minimizes the number of objects and frames that have to be considered during query evaluation. We also introduce an algorithm called SSG-CM that processes incoming frames against the SSG and efficiently prunes objects and frames unrelated to query evaluation, while maintaining all states required for succinct query evaluation. We present the results of a thorough experimental evaluation utilizing both real and synthetic data, establishing the trade-offs between MFS and SSG. We stress various parameters of interest in our evaluation and demonstrate that the proposed query evaluation methodology coupled with the proposed algorithms is capable to evaluate temporal queries over video feeds efficiently, achieving orders of magnitude performance benefits.

Set similarity search is a problem of central interest to a wide variety of applications such as data cleaning and web search. Past approaches on set similarity search utilize either heavy indexing structures, incurring large search costs or indexes that produce large candidate sets. In this paper, we design a learning-based exact set similarity search approach, LES 3 . Our approach first partitions sets into groups, and then utilizes a light-weight bitmap-like indexing structure, called token-group matrix (TGM), to organize groups and prune out candidates given a query set. In order to optimize pruning using the TGM, we analytically investigate the optimal partitioning strategy under certain distributional assumptions. Using these results, we then design a learning-based partitioning approach called L2P and an associated data representation encoding, PTR, to identify the partitions. We conduct extensive experiments on real and synthetic datasets to fully study LES 3 , establishing the effectiveness and superiority over other applicable approaches.

The vast advances in Machine Learning (ML) over the last ten years have been powered by the availability of suitably prepared data for training purposes. The future of ML-enabled enterprise hinges on data. As such, there is already a vibrant market offering data annotation services to tailor sophisticated ML models. In this paper, inspired by the recent vision of online data markets and associated market designs, we present research on the practical problem of obtaining data in order to improve the accuracy of ML models. We consider an environment in which consumers query for data to enhance the accuracy of their models and data providers who possess data make them available for training purposes. We first formalize this interaction process laying out the suitable framework and associated parameters for data exchange. We then propose two data acquisition strategies that consider a trade-off betweenexplorationduring which we obtain data to learn about the distribution of a provider's data andexploitationduring which we optimize our data inquiries utilizing the gained knowledge. In the first strategy,Estimation and Allocation(EA), we utilize queries to estimate the utilities of various predicates while learning about the distribution of the provider's data; then we proceed to the allocation stage in which we utilize those learned utility estimates to inform our data acquisition decisions. The second algorithmic proposal, namedSequential Predicate Selection(SPS), utilizes a sampling strategy to explore the distribution of the provider's data, adaptively investing more resources to parts of the data space that are statistically more promising to improve overall model accuracy. We present a detailed experimental evaluation of our proposals utilizing a variety of ML models and associated real data sets exploring all applicable parameters of interest. Our results demonstrate the relative benefits of the proposed algorithms. Depending on the models trained and the associated learning tasks we identify trade-offs and highlight the relative benefits of each algorithm to further optimize model accuracy.

Neural attention, an emerging technique used to identify important inputs within neural networks, have become increasingly popular in the area of recommender systems. Not only allowing to better identify what defines users and items, attention-based recommender systems are further able to provide accompanying explanations. However, these representations usually capture only part of users' preferences and items' attributes, resulting in limited reasoning and accuracy. We therefore propose Dual Attention Recommender with Items and Attributes (DARIA), a novel approach able to combine two dependable neural attention mechanisms to better justify its suggestions. Utilizing the personalized history of users, DARIA identifies the most relevant past activities while considering the real-world features that contributed to the similarity. In addition, we adopt the novel approach of self-attention and introduce Self-Attention Recommender based on Attributes and History (SARAH). As a variation to DARIA, SARAH utilizes two self-attention components to describe users by their most characteristic past activities and items by their best depicting attributes. Various experiments establish the significant improvement of SARAH and DARIA over seven key baselines in diverse recommendation settings. By comparing our two proposed frameworks, we demonstrate the potential benefit of applying self-attention in different scenarios.

We present TQVS, a system capable of conducting efficient evaluation of declarative temporal queries over real-time video streams. Users may issue queries to identify video clips in which the same two cars and the same three persons appear jointly in the frames for say 30 seconds. In real-world videos, some of the objects may disappear in frames due to reasons such as occlusion, which introduces challenges to query evaluation. Our system, aiming to address such challenges, consists of two main components: the Object Detection and Tracking (ODT) module and the Query Evaluation module. The ODT module utilizes state-of-art Object Detection and Tracking algorithms to produce a list of identified objects for each frame. Based on these results, we maintain select object combinations through the current window during query evaluation. Those object combinations contain sufficient information to evaluate queries correctly. Since the number of possible combinations could be very large, we introduce a novel technique to structure the possible combinations and facilitate query evaluation. We demonstrate that our approach offers significant performance benefits compared to alternate approaches and constitutes a fundamental building block of the TQVS system.

The problem of identifying the k -shortest paths (KSPs for short) in a dynamic road network is essential to many location-based services. Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Very often such services have to process numerous KSP queries over large road networks at the same time, thus there is a pressing need to identify distributed solutions for this problem. However, most existing approaches are designed to identify KSPs on a static graph in a sequential manner (i.e., the (i+1)-th shortest path is generated based on the i-th shortest path), restricting their scalability and applicability in a distributed setting. We therefore propose KSP-DG, a distributed algorithm for identifying k-shortest paths in a dynamic graph. It is based on partitioning the entire graph into smaller subgraphs, and reduces the problem of determining KSPs into the computation of partial KSPs in relevant subgraphs, which can execute in parallel on a cluster of servers. A distributed two-level index called DTLP is developed to facilitate the efficient identification of relevant subgraphs. A salient feature of DTLP is that it indexes a set of virtual paths that are insensitive to varying traffic conditions, leading to very low maintenance cost in dynamic road networks. This is the first treatment of the problem of processing KSP queries over dynamic road networks. Extensive experiments conducted on real road networks confirm the superiority of our proposal over baseline methods.

Next location prediction is of great importance for many location-based applications and provides essential intelligence to business and governments. In existing studies, a common approach to next location prediction is to learn the sequential transitions with massive historical trajectories based on conditional probability. Unfortunately, due to the time and space complexity, these methods (e.g., Markov models) only use the just passed locations to predict next locations, without considering all the passed locations in the trajectory. In this paper, we seek to enhance the prediction performance by considering the travel time from all the passed locations in the query trajectory to a candidate next location. In particular, we propose a novel method, called Travel Time Difference Model (TTDM), which exploits the difference between the shortest travel time and the actual travel time to predict next locations. Further, we integrate the TTDM with a Markov model via a linear interpolation to yield a joint model, which computes the probability of reaching each possible next location and returns the top-rankings as results. We have conducted extensive experiments on two real datasets: the vehicle passage record (VPR) data and the taxi trajectory data. The experimental results demonstrate significant improvements in prediction accuracy over existing solutions. For example, compared with the Markov model, the top-1 accuracy improves by 40% on the VPR data and by 15.6% on the Taxi data.

Recent advances in social and mobile technology have enabled an abundance of digital traces (in the form of mobile check-ins, association of mobile devices to specific WiFi hotspots, etc.) revealing the physical presence history of diverse sets of entities (e.g., humans, devices, and vehicles). One challenging yet important task is to identify k entities that are most closely associated with a given query entity based on their digital traces. We propose a suite of indexing techniques and algorithms to enable fast query processing for this problem at scale. We first define a generic family of functions measuring the association between entities, and then propose algorithms to transform digital traces into a lower-dimensional space for more efficient computation. We subsequently design a hierarchical indexing structure to organize entities in a way that closely associated entities tend to appear together. We then develop algorithms to process top-k queries utilizing the index. We theoretically analyze the pruning effectiveness of the proposed methods based on a mobility model which we propose and validate in real life situations. Finally, we conduct extensive experiments on both synthetic and real datasets at scale, evaluating the performance of our techniques both analytically and experimentally, confirming the effectiveness and superiority of our approach over other applicable approaches across a variety of parameter settings and datasets.

In many surveillance applications, capture devices are set on fixed locations to track entities, leading to valuable spatio-temporal trajectories. However, sometimes the IDs of the entities in these trajectories are incorrectly identified due to various reasons (e.g., illumination conditions and partial occlusion). Since very often the movements of the entities are constrained by certain restrictions imposed by the application (e.g., vehicles must move along the given road network), we consider how to repair the erroneous IDs using transition graphs derived from such restrictions. Roughly speaking, the occurrence of erroneous IDs can cause a valid trajectory to be broken into trajectory fragments that violate some movement constraints imposed by the transition graph, and we aim to repair them by rewriting the IDs and merging the fragments. This problem is practically challenging since it is not easy to judge which IDs in the dataset are correct, and also there may be multiple candidates as the correct value for a single error. We formulate the repair process as an optimization problem and propose a two-phase repair paradigm, which includes candidate repair generation and compatible repair selection, to maximize the quality improvement estimated by a designed objective function. Though both phases are intractable, we propose effective algorithms to solve them through exploiting the locality and sparsity of trajectories. We further devise an index structure, as well as a pruning method to make the repair process more efficient. Experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of the proposed methods. © 2018 Copyright held by the owner/author(s)

Short text stream clustering has become an increasingly important problem due to the explosive growth of short text in diverse social medias. In this paper, we propose a model-based short text stream clustering algorithm (MStream) which can deal with the concept drift problem and sparsity problem naturally. The MStream algorithm can achieve state-of-the-art performance with only one pass of the stream, and can have even better performance when we allow multiple iterations of each batch. We further propose an improved algorithm of MStream with forgetting rules called MStreamF, which can efficiently delete outdated documents by deleting clusters of outdated batches. Our extensive experimental study shows that MStream and MStreamF can achieve better performance than three baselines on several real datasets.

Most of the traditional top- k algorithms are based on a single-server setting. They may be highly inefficient and/or cause huge communication overhead when applied to a distributed system environment. Therefore, the problem of top- k monitoring in distributed environments has been intensively investigated recently. This paper studies how to monitor the top- k data objects with the largest aggregate numeric values from distributed data streams within a fixed-size monitoring window W , while minimizing communication cost across the network. We propose a novel algorithm, which adaptively reallocates numeric values of data objects among distributed nodes by assigning revision factors when local constraints are violated and keeps the local top- k result at distributed nodes in line with the global top- k result. We also develop a framework that combines a distributed data stream monitoring architecture with a sliding window model. Based on this framework, extensive experiments are conducted on top of Apache Storm to verify the efficiency and scalability of the proposed algorithm.

This paper studies privacy-preserving reachability query services under the paradigm of data outsourcing. Specifically, graph data have been outsourced to a third-party service provider (SP), query clients submit their queries to the (SP), and the (SP) returns the query answers to the clients. However, the (SP) may not always be trustworthy. Hence, this paper investigates protecting the structural information of the graph data and the query answers from the (SP). Existing techniques are either insecure or not scalable. This paper proposes a privacy-preserving labeling, called ppTopo. To our knowledge, ppTopo is the first work that can produce reachability index on massive networks and is secure against known plaintext attacks (KPA). Specifically, we propose a scalable index construction algorithm by employing the idea of topological folding, recently proposed by Cheng et al. We propose a novel asymmetric scalar product encryption in modulo 3 (ASPE3). It allows us to encrypt the index labels and transforms the queries into scalar products of encrypted labels. We perform an experimental study of the proposed technique on the SNAP networks. Compared with the existing methods, our results show that our technique is capable of producing the encrypted indexes at least 5 times faster for massive networks and the client's decryption time is 2-3 times smaller for most graphs.

Graph coloring is a fundamental NP-hard problem in graph theory. It has a wide range of real applications, such as Operations Research, Communication Network, Computational Biology and Compiler Optimization. Notable efforts have been spent on designing its approximation algorithms. Halldrsson proposed the algorithm (denoted as SampleIS) with the current best known approximation ratio. However, its time complexity is O(|G|3), where |G| is the number of vertices of a graph G. It is clear that SampleIS is not practical for large graphs. In this paper, we propose a practical vertex-cut based coloring technique (VColor) for coloring large graphs. First, we partition G into k connected components (CCs) of a small size s by removing a vertex-cut component (VCC). For each CC, we apply our novel coloring algorithm, based on maximal independent set enumeration. The approximation ratio and the time complexity for coloring the k CCs are log s + 1 and O(ks23s/3), respectively, whereas those of SampleIS are ks(log log ks)2/ log3 ks and O(k3s3). For the VCC, we simply apply SampleIS. To combine the colorings of the CCs and the VCC, we propose a maximum matching based algorithm. Second, in the context of a database of graphs, users may color many graphs. We propose an optimization technique, inspired by multi-query optimization, for coloring a set of graphs. We design a VP hierarchy (VPH) to represent the common subgraphs as the common CCs. Third, we propose techniques for determining the optimal values of the parameters of VColor. Our extensive experimental evaluation on real-world graphs confirms the efficiency and/or effectiveness of our proposed techniques. In particular, VColor is more than 500 times faster than SampleIS, and the number of colors used are comparable on real graphs Yeast and LS.

This paper studies the problem of mining frequent co-occurrence patterns across multiple data streams, which has not been addressed by existing works. Co-occurrence pattern in this context refers to the case that the same group of objects appear consecutively in mul-tiple streams over a short time span, signaling tight correlations be-tween these objects. The need for mining such patterns in real-time arises in a variety of applications ranging from crime prevention to location-based services to event discovery in social media. Since the data streams are usually fast, continuous, and unbounded, existing methods on mining frequent patterns requiring more than one pass over the data cannot be directly applied. Therefore, we propose DIMine and CooMine, two algorithms to discover fre-quent co-occurrence patterns across multiple data streams. DIMine is an Apriori-style algorithm based on an inverted index, while CooMine uses an in-memory data structure called the Seg-tree to compactly index the data that are already seen but have not expired yet. CooMine employs a one-pass algorithm that uses the filter-and-refine strategy to obtain the co-occurrence patterns from the Seg-tree as updates to the streams arrive. Extensive experiments on two real datasets demonstrate the superiority of the proposed approaches over a baseline method, and show their respective ap-plicability in different senarios. 1.

Keyword search over relational databases offers an alternative way to SQL to query and explore databases that is effective for lay users who may not be well versed in SQL or the database schema. This becomes more pertinent for databases with large and complex schemas. An answer in this context is a join tree spanning tuples containing the query's keywords. As there are potentially many answers to the query, and the user is often only interested in seeing the top-k answers, how to rank the answers based on their relevance is of paramount importance. We focus on the relevance of join as the fundamental means to rank answers. We devise means to measure relevance of relations and foreign keys in the schema over the information content of the database. This can be done offline with no need for external models. We compare the proposed measures against a gold standard we derive from a real workload over TPC-E and evaluate the effectiveness of our methods. Finally, we test the performance of our measures against existing techniques to demonstrate a marked improvement, and perform a user study to establish naturalness of the ranking of the answers.

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.

The explosive growth of user-generated contents in social networking websites necessitates the recommendation functionality that can push to the user the content that he/she is most likely to be interested in. Such recommendation should happen in real-time as new contents become available, because "freshness" is an important consideration in people's content-consumption behavior. Representing users and contents as feature vectors in a high-dimensional space, we can essentially cast the problem of real-time recommendations as the problem of computing the list of k nearest neighbors of each user, which we call kNN join. Given the vast volume of contents and users, the biggest challenge is how to continuously update the kNN join results as new contents arrive. Existing methods for incremental kNN join on data streams suffer from the "curse of dimensionality" and high in-memory search cost. In this paper, we present a solution that first identifies the users whose kNN's might be affected by the newly arrived content, and then update their kNN's respectively. We propose a new index structure named HDR-tree in order to support the efficient search of affected users. HDR-tree performs dimensionality reduction through clustering and principle component analysis (PCA) in order to improve the search effectiveness. To further reduce response time, we propose a variant of HDR-tree, called HDR-tree, that supports more efficient but approximate solutions. The results of extensive experiments show that our methods significantly outperform baseline methods.

Existing work on collaborative filtering (CF) is often based on the overall ratings the items have received. However, in many cases, understanding how a user rates each aspect of an item may reveal more detailed information about her preferences and thus may lead to more effective CF. Prior work has studied extracting/quantizing sentiments on different aspects from the reviews, based on which the unknown overall ratings are inferred. However, in that work, all the aspects are treated equally; while in reality, different users tend to place emphases on difference aspects when reaching the overall rating. For example, users may give a high rating to a movie just for its plot despite its mediocre performances. This emphasis on aspects varies for different users and different items. In this paper, we propose a method that uses tensor factorization to automatically infer the weights of different aspects in forming the overall rating. The main idea is to learn, through constrained optimization, a compact representation of a weight tensor indexed by three dimensions for user, item, and aspect, respectively. Overall ratings can then be predicted using the obtained weights. Experiments on a movie dataset show that our method compares favorably with three baseline methods.

Keyword search in relational databases was introduced in the last decade to assist users who are not familiar with a query language, the schema of the database, or the content of the data. An answer is a join tree of tuples that contains the query keywords. When searching a database with a complex schema, there are potentially many answers to the query. Therefore, ranking answers based on their relevance is crucial in this context. Prior work has addressed relevance based on the size of the answer or the IR scores of the tuples. However, this is not sufficient when searching a complex schema. We demonstrate MeanKS, a new system for meaningful keyword search over relational databases. The system first captures the user's interest by determining the roles of the keywords. Then, it uses schema-based ranking to rank join trees that cover the keyword roles. This uses the relevance of relations and foreign-key relationships in the schema over the information content of the database. In the demonstration, attendees can execute queries against the TPC-E warehouse and compare the proposed measures against a gold standard derived from a real workload over TPC-E to test the effectiveness of our methods.

Keyword search over a graph searches for a subgraph that contains a set of query keywords. A problem with most existing keyword search methods is that they may produce duplicate answers that contain the same set of content nodes (i.e., nodes containing a query keyword) although these nodes may be connected differently in different answers. Thus, users may be presented with many similar answers with trivial differences. In addition, some of the nodes in an answer may contain query keywords that are all covered by other nodes in the answer. Removing these nodes does not change the coverage of the answer but can make the answer more compact. The answers in which each content node contains at least one unique query keyword are called minimal answers in this paper. We define the problem of finding duplication-free and minimal answers, and propose algorithms for finding such answers efficiently. Extensive performance studies using two large real data sets confirm the efficiency and effectiveness of the proposed methods.

As highly centralized storage facilities are gaining popularity, duplicate detection becomes a critical problem. Traditional methods focus on reducing the storage space consumption; however, for network storage system with remote clients, the network overhead cannot be ignored, especially when the system is accessed over WAN. We propose a new duplicate detection method and implement a network file system prototype called DDSN based on this new method. It can reach the same performance in terms of storage space consumption as the state-of-the-art sliding blocking method. Meanwhile, our method overcomes its drawback that the whole file needs to be transmitted over the network, and therefore saves massive bandwidth for duplicate data. Experiments confirm the effectiveness of the proposed method.

The last few years have witnessed a meteoric rise of microblogging platforms, such as Twitter and Tumblr. The sheer volume of the microblog data and its highly dynamic nature present unique technical challenges for the platforms that provide search services. In particular, the search service must provide real-time response to queries, and continuously update the results as new microblogs are posted. Conventional approaches either cannot keep up with the high update rate, or cannot scale well to handle the large volume of data.

Keyword search over databases, popularized by keyword search in WWW, allows ordinary users to access database information without the knowledge of structured query languages and database schemas. Most of the previous studies in this area use IR-style ranking, which fail to consider the importance of the query answers. In this paper, we propose CI-RANK, a new approach for keyword search in databases, which considers the importance of individual nodes in a query answer and the cohesiveness of the result structure in a balanced way. CI-RANK is built upon a carefully designed model call Random Walk with Message Passing that helps capture the relationships between different nodes in the query answer. We develop a branch and bound algorithm to support the efficient generation of top-k query answers. Indexing methods are also introduced to further speed up the run-time processing of queries. Extensive experiments conducted on two real data sets with a real user query log confirm the effectiveness and efficiency of CI-RANK.

Collaborative filtering (CF) aims to produce user specific recommendations based on other users' ratings of items. Most existing CF methods rely only on users' overall ratings of items, ignoring the variety of opinions users may have towards different aspects of the items. Using the movie domain as a case study, we propose a framework that is able to capture users' opinions on different aspects from the textual reviews, and use that information to improve the effectiveness of CF. This framework has two components, an opinion mining component and a rating inference component. The former extracts and summarizes the opinions on multiple aspects from the reviews, generating ratings on the various aspects. The latter component, on the other hand, infers the overall ratings of items based on the aspect ratings, which forms the basis for item recommendation. Our core contribution is in the proposal of a tensor factorization approach for the rating inference. Operating on the tensor composed of the overall and aspect ratings, this approach is able to capture the intrinsic relationships between users, items, and aspects, and provide accurate predictions on unknown ratings. Experiments on a movie dataset show that our proposal significantly improves the prediction accuracy compared with two baseline methods.

Posting reviews online has become an increasingly popular way for people to express opinions and sentiments toward the products bought or services received. Analyzing the large volume of online reviews available would produce useful actionable knowledge that could be of economic values to vendors and other interested parties. In this paper, we conduct a case study in the movie domain, and tackle the problem of mining reviews for predicting product sales performance. Our analysis shows that both the sentiments expressed in the reviews and the quality of the reviews have a significant impact on the future sales performance of products in question. For the sentiment factor, we propose Sentiment PLSA (S-PLSA), in which a review is considered as a document generated by a number of hidden sentiment factors, in order to capture the complex nature of sentiments. Training an S-PLSA model enables us to obtain a succinct summary of the sentiment information embedded in the reviews. Based on S-PLSFA, we propose ARSA, an Autoregressive Sentiment-Aware model for sales prediction. We then seek to further improve the accuracy of prediction by considering the quality factor, with a focus on predicting the quality of a review in the absence of user-supplied indicators, and present ARSQA, an Autoregressive Sentiment and Quality Aware model, to utilize sentiments and quality for predicting product sales performance. Extensive experiments conducted on a large movie data set confirm the effectiveness of the proposed approach.

Keyword search over relational databases has recently received significant attention. Many solutions and prototypes have been developed. However, due to large memory consumption requirements and unpredictable running time, most of them cannot be applied directly to situations where memory is limited and quick response is required, such as when performing keyword search over databases in mobile devices as part of the OLAP funtionalities. In this paper, we attack the keyword search problem from a new perspective, and propose a cascading top-k keyword search algorithm, which generates supernodes in each step of search instead of computing the Steiner trees as done in many existing approaches. This new algorithm consumes less memory and significantly reduces the response time. Experiments show that the method can achieve high search efficiency compared with the state-of-the-art approaches.

Analyzing the large volume of online reviews would produce useful knowledge that could be of economic values to vendors and other interested parties. In particular, the sentiments expressed in the online reviews have been shown to be strongly correlated with the sales performance of products. In this paper, we present an adaptive sentiment analysis model called S-PLSA+, which aims to capture the hidden sentiment factors in the reviews with the capability to be incrementally updated as more data become available. We show how S-PLSA+ can be applied to sales performance prediction using an ARSA model developed in previous literature. A case study is conducted in the movie domain, and results from preliminary experiments confirm the effectiveness of the proposed model.

Online reviews, which are getting increasingly prevalent with the rapid growth of Web 2.0, have been shown to be second only to "word-of-mouth" in terms of influencing purchase decisions. It is therefore imperative to analyze them and distill useful knowledge that could be of economic values to vendors and other interested parties. Previous studies have confirmed that the sentiments expressed in the online reviews are strongly correlated with the sales performance of products. In particular, a model called ARSA has been proposed for predicting sales performance using a model called S-PLSA. In this paper, we build upon that work, and present an adaptive sentiment analysis model called S-PLSA+, which not only can capture the hidden sentiment factors in the reviews, but has the capability to be incrementally updated as more data become available. We show how the proposed S-PLSA+model can be applied to sales performance prediction using the ARSA model. A case study is conducted in the movie domain, and results from preliminary experiments confirm the effectiveness of the proposed model.

Writing and publishing reviews online has become an increasingly popular way for people to express opinions and sentiments. Analyzing the large volume of online reviews available can produce useful knowledge that are of interest to vendors and other parties. Prior studies in the literature have shown that online reviews have a significant correlation with the sales of products, and therefore mining the reviews could help predict the sales performance of relevant products. However, those studies fail to consider one important factor that may significantly affect the accuracy of the prediction, i.e., the quality of the reviews. In this paper, we propose a regression model that explicitly takes into account the quality factor, and discusses how this quality information can be predicted when it is not readily available. Experimental results on a movie review dataset confirm the effectiveness of the proposed model.

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.

Online reviews provide a valuable resource for potential customers to make purchase decisions. However, the sheer volume of available reviews as well as the large variations in the review quality present a big impediment to the effective use of the reviews, as the most helpful reviews may be buried in the large amount of low quality reviews. The goal of this paper is to develop models and algorithms for predicting the helpfulness of reviews, which provides the basis for discovering the most helpful reviews for given products. We first show that the helpfulness of a review depends on three important factors: the reviewerpsilas expertise, the writing style of the review, and the timeliness of the review. Based on the analysis of those factors, we present a nonlinear regression model for helpfulness prediction. Our empirical study on the IMDB movie reviews dataset demonstrates that the proposed approach is highly effective.

With the flourish of the Internet, online review mining has attracted a lot of attention from the research community. However, compared to various well-studied sentiment analysis and opinion summarization problems, less effort has been made to analyze the quality of online reviews. The objective of this paper is to fill in this gap by automatically evaluating the "helpfulness" of reviews and consequently developing novel models to identify the most helpful reviews for a particular product. In particular, based on a thorough analysis of various factors that may affect the review quality, we propose HelpMeter, a nonlinear regression model for helpfulness prediction. Some preliminary experiments were conducted on a movie review data set, and the performance results confirm the superiority of the proposed method.

In many text retrieval tasks, it is highly desirable to obtain a "similarity profile" of the document collection for a given query. We propose sampling-based techniques to address this need, using calibration techniques to improve the accuracy. Experimental results confirm the effectiveness of the proposed approaches.

We study selectivity estimation techniques for set similarity queries. A wide variety of similarity measures for sets have been proposed in the past. In this work we concentrate on the class of weighted similarity measures (e.g., TF/IDF and BM25 cosine similarity and variants) and design selectivity estimators based on a priori constructed samples. First, we study the pitfalls associated with straightforward applications of random sampling, and argue that care needs to be taken in how the samples are constructed; uniform random sampling yields very low accuracy, while query sensitive realtime sampling is more expensive than exact solutions (both in CPU and I/O cost). We show how to build robust samples a priori, based on existing synopses for distinct value estimation. We prove the accuracy of our technique theoretically, and verify its performance experimentally. Our algorithm is orders of magnitude faster than exact solutions and has very small space overhead.

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.

Due to its high popularity, Weblogs (or blogs in short) present a wealth of information that can be very helpful in assessing the general public's sentiments and opinions. In this paper, we study the problem of mining sentiment information from blogs and investigate ways to use such information for predicting product sales performance. Based on an analysis of the complex nature of sentiments, we propose Sentiment PLSA (S-PLSA), in which a blog entry is viewed as a document generated by a number of hidden sentiment factors. Training an S-PLSA model on the blog data enables us to obtain a succinct summary of the sentiment information embedded in the blogs. We then present ARSA, an autoregressive sentiment-aware model, to utilize the sentiment information captured by S-PLSA for predicting product sales performance. Extensive experiments were conducted on a movie data set. We compare ARSA with alternative models that do not take into account the sentiment information, as well as a model with a different feature selection method. Experiments confirm the effectiveness and superiority of the proposed approach.

In this paper, we propose a novel index structure, the CSR+-tree, to support efficient high-dimensional similarity search in main memory. We introduce quantized bounding spheres (QBSs) that approximate bounding spheres (BSs) or data points. We analyze the respective pros and cons of both QBSs and the previously proposed quantized bounding rectangles (QBRs), and take the best of both worlds by carefully incorporating both of them into the CSR+-tree. We further propose a novel distance computation scheme that eliminates the need for decompressing QBSs or QBRs, which results in significant cost savings. We present an extensive experimental evaluation and analysis of the CSR+-tree, and compare its performance against that of other representative indexes in the literature. Our results show that the CSR+-tree consistently outperforms other index structures.

Join techniques deploying approximate match predicates are fundamental data cleaning operations. A variety of predicates have been utilized to quantify approximate match in such operations and some have been embedded in a declarative data cleaning framework. These techniques return pairs of tuples from both relations, tagged with a score, signifying the degree of similarity between the tuples in the pair according to the specific approximate match predicate. In this paper, we consider the problem of estimating various parameters on the output of declarative approximate join algorithms for planning purposes. Such algorithms are highly time consuming, so precise knowledge of the result size as well as its score distribution is a pressing concern. This knowledge aids decisions as to which operations are more promising for identifying highly similar tuples, which is a key operation for data cleaning. We propose solution strategies that fully comply with a declarative framework and analytically reason about the quality of the estimates we obtain as well as the performance of our strategies. We present the results of a detailed performance evaluation of all strategies proposed. Our experimental results validate our analytical expectations and shed additional light on the quality and performance of our estimation framework. Our study offers a set of simple, fully declarative techniques for this problem, which can be readily deployed in data cleaning systems.

Accurate estimation of the sizes of intermediate query results (cardinality estimation) is of critical importance to plan costing in query optimization. The common practice in current commercial database systems such as IBM DB2 Universal Database (DB2 UDB) is to derive the cardinality estimates from base-table statistics. However, this approach often suffers from simplifying yet unrealistic assumptions that have to be made about the underlying data (for example, different attributes are independently distributed).Ways for exploiting statistics on query expressions (or, statistics on views, or SITs) have been proposed to improve the accuracy of cardinality estimation. We propose a novel method for efficient computation of SITs for joins. In particular, we are concerned with statistics on join queries involving large fact tables and relatively small dimension tables. Rather than materializing the views, we make use of the frequency statistics that are available on the fact tables to obtain an approximate estimate of the statistics on various attributes in the join results. The dimension tables are generally much smaller than the fact table, and therefore we can afford to closely examine the dimension table, while at the same time avoid accessing the fact table. By closely examining the dimension table, we are able to capture the correlations between the attributes in the dimension table as well as the skew and domain range of the fact table join column values. This leads to reasonably accurate statistics on the join result. We prototyped this idea as a module on top of DB2 UDB, and our experience shows that employment of this technique results in a very significant speed-up in the computation of SITs, at the expense of only slight degradation in accuracy compared with the full-materialization method.

Accurately and efficiently estimating the number of distinct values for some attribute(s) or sets of attributes in a data set is of critical importance to many database operations, such as query optimization and approximation query answering. Previous work has focused on the estimation of the number of distinct values for a single attribute and most existing work adopts a data sampling approach. This paper addresses the equally important issue of estimating the number of distinct value combinations for multiple attributes which we call COLSCARD (for COLumn Set CARDinality). It also takes a different approach that uses existing statistical information (e.g., histograms) available on the individual attributes to assist estimation. We start with cases where exact frequency information on individual attributes is available, and present a pair of lower and upper bounds on COLSCARD that are consistent with the available information, as well as an estimator of COLSCARD based on probability. We then proceed to study the case where only partial information (in the form of histograms) is available on individual attributes, and show how the proposed estimator can be adapted to this case. We consider two types of widely used histograms and show how they can be constructed in order to obtain optimal approximation. An experimental evaluation of the proposed estimation method on synthetic as well as two real data sets is provided.

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.