Text-to-visualization (text-to-vis) models for tabular data have become essential tools in the era of big data, enabling users to generate visualizations and make data-driven decisions through natural language queries (NLQs). Despite their growing adoption, the security vulnerabilities of these models remain largely unexplored. To address this gap, we propose VisPoison, a backdoor attack framework that realistically simulates three types of attacks on text-to-vis models via data poisoning: data exposure, misleading visualizations, and denial-of-service (DoS). Specifically, VisPoison introduces two types of stealthy triggers to enable both proactive and passive backdoor activations. Proactive triggers are deliberately inserted by attackers using rare-word patterns to extract sensitive information, whereas passive triggers are unintentionally activated by users through first-word prompts, resulting in visualization errors or DoS failures. To support these triggers, we craft specialized payloads for visualization queries that allow compromised models to function normally on benign inputs while producing malicious outputs in the presence of triggers. Extensive evaluations on both trainable and in-context learning (ICL)-based text-to-vis models show that VisPoison achieves attack success rates exceeding 90\%, exposing serious vulnerabilities. Additionally, existing defense strategies reveal limited effectiveness against VisPoison, underscoring the urgent need for more robust and security-aware text-to-vis systems to safeguard human-data interaction.

Bridging natural language and structured query languages is a long-standing challenge in the database community. While recent advances in language models have shown promise in this direction, existing solutions often rely on large-scale closed-source models that suffer from high inference costs, limited transparency, and lack of adaptability for lightweight deployment. In this paper, we present OsmT, an open-source tag-aware language model specifically designed to bridge natural language and Overpass Query Language (OverpassQL), a structured query language for accessing large-scale OpenStreetMap (OSM) data. To enhance the accuracy and structural validity of generated queries, we introduce a Tag Retrieval Augmentation (TRA) mechanism that incorporates contextually relevant tag knowledge into the generation process. This mechanism is designed to capture the hierarchical and relational dependencies present in the OSM database, addressing the topological complexity inherent in geospatial query formulation. In addition, we define a reverse task, OverpassQL-to-Text, which translates structured queries into natural language explanations to support query interpretation and improve user accessibility. We evaluate OsmT on a public benchmark against strong baselines and observe consistent improvements in both query generation and interpretation. Despite using significantly fewer parameters, our model achieves competitive accuracy, demonstrating the effectiveness of open-source pre-trained language models in bridging natural language and structured query languages within schema-rich geospatial environments.

Causality has been integrated with machine learning in uncovering and understanding the causal relationship between variables and observed outcomes. However, the centralized training setting of causal machine learning is not adaptable to most practical scenarios, where datasets are distributed, stored, and unsharable due to privacy concerns. Federated learning (FL), a distributed learning framework that allows collaborative training across multiple devices without raw data sharing, emerges as a potential solution to this problem. By integrating FL into causal problems, the discovery and inference of causal relationships across dispersed datasets can be achieved. On the other hand, causality can also enhance FL models in various dimensions, including model interpretability and explainability, generalizability, adversarial robustness, and fairness and bias mitigation. In this article, we provide a comprehensive review of the above two directions and summarize the interplays between causality and FL (short for Causal-FL ) by organizing our discussion around two key questions: (1) how FL enable decentralized causal analysis; and (2) how causality tackles FL challenges. The potential applications of these methods are also introduced, including healthcare, recommendation, economics, social equity, and so on. Moreover, we discuss promising future directions and future challenges to be explored.

The prevalence of computer graphics technology boosts the development of point clouds, which offer advantages over T riangular I rregular N etworks , i.e., TIN s, in proximity queries. All existing on-the-fly shortest path query algorithms and oracles on a TIN are expensive, and no algorithms can answer shortest path queries on a point cloud directly. Thus, we propose two types of efficient shortest path oracles on a point cloud. They answer the shortest path query between (1) a pair of P oints- O f- I nterests ( POIs ), and (2) any point and a POI, respectively. We propose four adaptations of them to answer the query between any point and a POI (or any point if no POIs are given). We also propose two efficient proximity query algorithms using these oracles. Our two oracles and their proximity query algorithms outperform the best-known adapted oracle by 12 to 42,000 times in terms of the oracle construction time, oracle size and proximity query time, respectively 1 .

Data visualization (DV) is of significance to the data analysis applications, exploring the hidden patterns and showing the insightful data. The task of Text-to-Vis, which takes text as input and generates data visualizations, was proposed to lower the threshold for generating DVs. However, the existing methods only view this problem as a one-shot mapping problem, directly outputting the final DVs without considering any user feedback for refining the generated DVs. Motivated by this, a more interactive scenario is investigated, where users could provide natural language feedback to refine the generated DVs. The scenario is formulated as the Text-to-Vis with Feedback problem. A new dataset is also created to further study the problem, which contains the user utterance, database schema, generated DVs, the natural language feedback and the refined DVs. A large language model (LLM) based framework named Vis-Edit is designed for handling this task, including schema linking, clause location, clause generation, merger and self-consistency. Eventually, extensive experiments reveal the effectiveness of Vis-Edit.

Text-to-Vis is an emerging task in the data engineering and mining area that aims to automatically generate data visualizations from natural language questions (NLQs). Despite their progress, existing text-to-vis models often heavily rely on lexical matching between words in the questions and tokens in data schemas. This overreliance on lexical matching may lead to a diminished level of model robustness against input variations. In this study, we thoroughly examine the robustness of current text-to-vis models, an area that has not previously been explored. In particular, we construct the first robustness dataset nvBench-Rob, which contains diverse lexical and phrasal variations based on the original text-to-vis benchmark nvBench. Then, we found that the performance of existing text-to-vis models on this new dataset dramatically drops, implying that these methods exhibit inadequate robustness overall. Finally, we propose a novel framework based on Retrieval-Augmented Generation (RAG) technique, named GRED, specifically designed to address input perturbations in these two variants. The framework consists of three parts: NLQ-Retrieval Generator, Visualization Query-Retrieval Retuner and Annotation-based Debugger, which are used to tackle the challenges posed by natural language variants, programming style differences and data schema variants, respectively. Extensive experimental evaluations show that, compared to the state-of-the-art model Prompt4Vis in the Text-to-Vis field, GRED performs better in terms of model robustness, with a 40% increase in accuracy on the proposed nvBench-Rob dataset.

Given a massive dataset, data visualization (DV) could efficiently express the insights and summaries behind the massive raw data by employing vivid visual representations. To create suitable DVs, users are required to get a comprehensive understanding of the raw data and then transfer their ideas into DVs by composing a suitable and accurate specification in some declarative visualization languages (DVLs, e.g., Vega-Lite). A specification is a JSON object defining the properties of the DVs, like the selected data, the transformations, the visual details, and so on. Due to its complicated grammar and details, DV has quite a steep learning curve, even for data analysts. In this paper, we propose a new task named FeVisQA, referring to Free-form Question Answering over data Visualizations. More specifically,-given a raw dataset, a related DV (in the form of a specification), and a question, FeVisQA aims to predict a textual answer automatically. As a particular case of the general CodeQA (i.e., QA over general programming code like Python and Java) task, FeVisQA enables people to better comprehend data and its DVs by conducting logical reasoning when answering these questions. Since FeVisQA has not been studied in the literature, we first construct a benchmark dataset containing 152 datasets, 14,406 DVs, and 83,890 QA pairs. To tackle this new task, we design a novel neural network named FeVisQANet with advanced multi-modal encoder and adaptive decoder structures, and we also design a novel multi-step framework called VisQA for Multi-modal Large Language Models (MLLMs) based on Retrieval-augmented Generation (RAG) technology. Extensive experiments on our constructed datasets validate the rationale and effectiveness of this proposed FeVisQA task and the proposed model. While research on QA over text and table, machine reading comprehension, and CodeQA develops rapidly, prior works have yet to draw attention to question-answering over DVs. This study connects two important subareas, QA from the natural language process area and DV from the data engineering area. We hope this new dataset and model can serve as a helpful benchmark that would benefit the development of both fields.

Data visualization (DV) is the fundamental and premise tool to improve the efficiency in conveying the insights behind the big data, which has been widely accepted in existing data-driven world. Task automation in DV, such as converting natural language queries to visualizations (i.e., text-to-vis), gener-ating explanations from visualizations (i.e., vis-to-text), answering DV-related questions in free form (i.e. Fe VisQA), and explicating tabular data (i.e., table-to-text), is vital for advancing the field. Despite their potential, the application of pre-trained language models (PLMs) like T5 and BERT in DV has been limited by high costs and challenges in handling cross-modal information, leading to few studies on PLMs for DV. We introduce Data VisT5, a novel PLM tailored for DV that enhances the T5 architecture through a hybrid objective pre-training and multi-task fine-tuning strategy, integrating text and DV datasets to effectively interpret cross-modal semantics. Extensive evaluations on public datasets show that Data VisT5 consistently outperforms current state-of-the-art models and higher-parameter Large Language Models (LLMs) on various DV-related tasks. We anticipate that Data VisT5 will not only inspire further research on vertical PLMs but also expand the range of applications for PLMs.

The pervasiveness of shortest path queries is evident in real life, particularly in online mapping applications. However, in practice, the travel times of road segments can be uncertain due to various reasons, such as traffic congestion, which leads to the shortest path not to be the fastest, resulting in an unreliable path. The Reliable Shortest Path (RSP) query has been developed to fulfill individuals' reliability requirements by considering travel times as random variables. Extensive solutions have been proposed to efficiently find RSPs in stochastic road networks. However, they are either unscalable to large networks or incapable of handling rapid streams of routing queries. In this paper, we propose an efficient index-based solution for RSP queries, called Non-dominated Reliable Path (NRP). It stores partial path answers to support fast query processing and utilizes several tailored pruning techniques that can significantly reduce the query time. Experiments conducted on large city road networks verified the superiority of our solution, which can answer each query in around 100 microseconds and beat competitors by orders of magnitude.

The top-k query is a representative multi-criteria decision-making operator that assists users in finding the best$k$tuples based on their criteria. However, it has certain limitations in the query process and the final output. First, the query process requires users to specify their criteria explicitly and accurately in advance, which may be difficult for some users. Second, the final output often lacks diversity, which potentially leads to user dissatisfaction. To address these limitations, in this paper, we propose an enhanced top-k query by incorporating an interactive learning framework and a diversity mechanism, expecting to return a diverse output that aligns with the user's criterion, even if the criterion is not specified in advance. We study our problem progressively. Initially, we examine a special case where tuples are described by two scoring attributes. We present the TDIA algorithm that is asymptotically optimal regarding the user effort needed for interaction. Then, we move on to the general case where tuples are described by multiple scoring attributes. We propose the HDIA algorithm which is asymptotically optimal w.r.t. the number of questions asked in expectation. Experiments were conducted on synthetic and real datasets. The results show that our algorithms can return a diverse output while requiring less user effort than existing ones.

Natural Language Interfaces (NLIs) have transformed data interaction by enabling natural language querying and visualization of tabular data. Despite the growing importance of NLIs, prior research has examined querying and visualization tasks separately, lacking a unified perspective, especially in the era of Large Language Models (LLMs). To fill this gap, this survey provides a comprehensive analysis of NLIs for tabular data, examining their evolution and fundamental components: datasets, evaluation metrics, and architectural designs. By analyzing over 60 approaches and 38 datasets, we explore recent advancements in Text-to-SQL and Text-to-Vis tasks, focusing on semantic parsing techniques for natural language translation to SQL queries and visualization specifications. We evaluate the impact of LLMs on these systems, discussing their capabilities and limitations. Our systematic review serves as a roadmap for developing NLIs in the foundation model era.

As multimedia content continues to grow on the web, the integration of visual and textual data has become a crucial challenge for web applications, particularly in recommendation systems. Large Vision Language Models (LVLMs) have demonstrated considerable potential in addressing this challenge across various tasks that require such multimodal integration. However, their application in multimodal sequential recommendation (MSR) has not been extensively studied. To bridge this gap, we introduce MSRBench, the first comprehensive benchmark designed to systematically evaluate different LVLM integration strategies in web-based recommendation scenarios. We benchmark three state-of-the-art LVLMs, i.e., GPT-4 Vision, GPT-4o, and Claude-3-Opus, on the next item prediction task using the constructed Amazon Review Plus dataset, which includes additional item descriptions generated by LVLMs. Our evaluation examines five integration strategies: using LVLMs as recommender, item enhancer, reranker, and various combinations of these roles. The benchmark results reveal that 1) using LVLMs as rerankers is the most effective strategy, significantly outperforming others that rely on LVLMs to directly generate recommendations or only enhance items; 2) GPT-4o consistently achieves the best performance across most scenarios, particularly when employed as a reranker; 3) the computational inefficiency of LVLMs presents a major barrier to their widespread adoption in real-time multimodal recommendation systems. Our code and datasets are available at https://github.com/PALIN2018/MSRBench.

Data cleaning is a long-standing challenge in data management. While powerful logic and statistical algorithms have been developed to detect and repair data errors in tables, existing algorithms predominantly rely on domain-experts to first manually specify data-quality constraints specific to a given table, before data cleaning algorithms can be applied. In this work, we observe that there is an important class of data-quality constraints that we call Semantic-Domain Constraints, which can be reliably inferred and automatically applied to any tables, without requiring domain-experts to manually specify on a per-table basis. We develop a principled framework to systematically learn such constraints from table corpora using large-scale statistical tests, which can further be distilled into a core set of constraints using our optimization framework, with provable quality guarantees. Extensive evaluations show that this new class of constraints can be used to both (1) directly detect errors on real tables in the wild, and (2) augment existing expert-driven data-cleaning techniques as a new class of complementary constraints. Our code and data are available at https://github.com/qixuchen/AutoTest for future research.

Approximate nearest neighbor (ANN) query in high-dimensional Euclidean space is a key operator in database systems. For this query, quantization is a popular family of methods developed for compressing vectors and reducing memory consumption. Among these methods, a recent algorithm called RaBitQ achieves the state-of-the-art performance and provides an asymptotically optimal theoretical error bound. RaBitQ uses 1 bit per dimension for quantization and compresses vectors with a large compression rate. In this paper, we extend RaBitQ to compress vectors with flexible compression rates - it achieves this by using B bits per dimension for quantization with B = 1, 2, ... It inherits the theoretical guarantees of RaBitQ and achieves the asymptotic optimality in terms of the trade-off between space and error bounds as to be proven in this study. Additionally, we present efficient implementations of the extended RaBitQ, enabling its application to ANN queries to reduce both space and time consumption. Extensive experiments on real-world datasets confirm that our method consistently outperforms the state-of-the-art baselines in both accuracy and efficiency when using the same amount of memory.

The point-to-point shortest path query is widely used in many spatial applications, e.g., navigation systems. However, the returned shortest path minimizing only one objective fails to satisfy users' various routing requirements in practice. For example, the user may specify the order of using several transportation modes in the planned route. The Label-Constrained Shortest Path (LCSP) query under regular languages is powerful enough to express diversified routing demands in a labeled road network where each edge is associated with a label to denote its road type. The complex routing demand can be formulated by a regular language, and the edge labels along each path should be a word under the given regular language. Previous LCSP solutions were either inefficient in query processing or inflexible in their use of the languages since they made some assumptions about the given language. In this paper, we propose an efficient index-based solution called Border-based State Move (BSM), which can answer LCSP queries quickly with flexible use of the language constraint. Specifically, our BSM builds indexes to skip the exploration between a vertex and its border vertices during query processing. Our experiments conducted on real road networks demonstrated the superiority of our proposed BSM. It can reduce the query time over state-of-the-art solutions by two orders of magnitude.

Multimodal recommender systems utilize a variety of information types to model user preferences and item properties, aiding in the discovery of items that align with user interests. Rich multimodal information alleviates inherent challenges in recommendation systems, such as data sparsity and cold start problems. However, multimodal information further introduces challenges in terms of robustness and generalization capability. Regarding robustness, multimodal information magnifies the risks associated with information adjustment and inherent noise, posing severe challenges to the stability of recommendation models. For generalization capability, multimodal recommender systems are more complex and difficult to train, making it harder for models to handle data beyond the training set, posing significant challenges to model generalization capability. In this paper, we analyze the shortcomings of existing robustness and generalization capability enhancement strategies in the multimodal recommendation field. We propose a sharpness-aware minimization strategy focused on batch data (BSAM), which effectively enhances the robustness and generalization capability of multimodal recommender systems without requiring extensive hyper-parameter tuning. Furthermore, we introduce a mixed loss variant strategy (BSAM+), which accelerates convergence and achieves remarkable performance improvement. We provide rigorous theoretical proofs and conduct experiments with nine advanced models on five widely used datasets to validate the superiority of our strategies. Moreover, our strategies can be integrated with existing robust training and data augmentation strategies to achieve further improvement, providing a superior training paradigm for multimodal recommendations.

The booming of computer graphics technology facilitates the growing use of terrain data. Notably, shortest path querying on a terrain surface is central in a range of applications and has received substantial attention from the database community. Despite this, computing the shortest paths on-the-fly on a terrain surface remains very expensive, and all existing oracle-based algorithms are only efficient when the terrain surface is fixed. They rely on large data structures that must be re-constructed from scratch when updates to the terrain surface occur, which is very time-consuming. To advance the state-of-the-art, we propose an efficiently updatable$(1+\epsilon )$-approximate shortest path oracle for a set ofPoints-Of-Interests(POIs) on an updated terrain surface, and it can be easily adapted to the case if POIs are not given as input. Our experiments show that when POIs are given (resp. not given), our oracle is up to 88 times, 12 times, and 3 times (resp. 15 times, 50 times, and 100 times) better than the best-known oracle on terrain surfaces in terms of the oracle update time, output size, and shortest path query.

Abstract Due to the growth of the 3D technology, digital 3D models represented in the form of point clouds have attracted a lot of attention from both industry and academia. In this paper, due to a variety of applications, we study a fundamental problem called the 3D object retrieval, which is to find a set of 3D point clouds stored in a database that are similar to a given query 3D point cloud. To the best of our knowledge, solving the problem of 3D object retrieval efficiently remains unexplored in the research community. In this paper, we propose a framework called C $$_2$$ 2 O to find the answer efficiently with the help of an index built on the database. In most of our experiments, C $$_2$$ 2 O performs up to 2 orders of magnitude faster than all adapted algorithms in the literature. In particular, when the database size scales up to 100 million points, C $$_2$$ 2 O answers the 3D object retrieval within 10 s but all adapted exact algorithms need more than 1000 s.

The traditional top-k query was proposed to obtain a small subset from the database according to the user preference, which is explicitly expressed as a ranking scheme (i.e., utility function). However, a poorly-designed utility function may create discrimination, which in turn may cause harm to minority groups, e.g., women and ethnic minorities, and thus, fairness is becoming increasingly important in many situations, e.g., hiring and admission decisions. Motivated by this, we study fair ranking to alleviate discrimination. We design a fairness model, called α-fairness, to quantify the fairness of utility functions. We propose an efficient exact framework with a basic implementation and an improved implementation to find the fairest utility function with the minimum modification penalty. We conducted extensive experiments on both real and synthetic datasets to demonstrate our effectiveness and efficiency compared with the prior studies.

Question Answering (QA) systems playa vital role in knowledge acquisition. CodeQA refers to question answering (QA) over source code for code comprehension purpose. However, existing CodeQA studies mainly focus on questions related to general-purpose programming languages (GPLs) (e.g., Java and Python), and no study has been conducted on QA over declarative visualization languages (DVLs) (e.g., Vega-Lite), a kind of programming languages used for creating data visualization (DV). DVLs enjoys specific grammars that are instinct different from GPLs. This demonstration presents the first neural-based QA system for DVL, FeVisQASystem. FeVisQASystem is based on a new task named Fevisqa, short for Free-form QA over data Visualization, which takes natural language questions and DV specification as inputs to predict the answers to the questions. As a particular case of the CodeQA task, Fe VisQA enables people to better comprehend data and its DV s by conducting logical reasoning when answering these questions. Although research on question-answering and machine reading comprehension is progressing quickly, little attention has previously been paid to FeVisQA. This new system and the task can serve as a helpful pioneering study for DV comprehension. The video can be accessed via https://ldrv.ms/f/s!Ah2vhboIPBFMhk6jTYOtaIRnLC2K?e=OkJqOq

Vehicular traffic congestion is a recurring and widespread societal phenomenon. Since drivers increasingly rely on routing services, we consider how to enhance such services to provide routes that mitigate congestion. Specifically, we propose the Congestion-mitigating Spatiotemporal Routing (CSR) problem that considers the congestion caused by vehicles following the routes provided. This problem is challenging because vehicles that follow recommended routes appear on different road segments at different times. We propose two solutions, Spatiotemporal Oblivious Routing (SOR) and Spatiotemporal Routing with History (SRH), which return routes based on the current and anticipated future traffic statuses, respectively, while offering theoretical guarantees. We also propose an update procedure for handling traffic dynamics. Extensive evaluations on real data provide insight into the properties of the solutions, indicating that SRH can reduce the number of vehicles on the most congested road segments by nearly 33 % and can process a query in less than 10 ms.

Reverse operators have lately gained much attention within the realm of multi-criteria decision-making. While forward operators, such as skyline, seek to identify products that may interest a customer, reverse operators identify prospective customers who are likely to be attracted to a particular product. Specifically, for each customer, they assign scores to all products w.r.t. the customer's preference and then rank the products based on these scores. If the particular product ranks high, the customer is considered a prospective customer for that product. However, relying purely on rankings might cause misleading results, as rankings emphasize the products' relative positions without accounting for their score differences. In a competitive market, a comparatively low-ranked product may have a score that is nearly indistinguishable from that of the top-tier product(s), and thus, may still be interesting to the customer. In this paper, we directly utilize scores to evaluate products, enabling more accurate identification of prospective customers. We refer to our problem as the reverse regret query (RRQ) and make several contributions. First, for the special case in which each product is described by two attributes, we propose an algorithm Sweeping that only takes linear time. Second, for the general case in which each product can be described by multiple attributes, we present two algorithms: an exact algorithm E-PT and a faster approximate algorithm A-PC. We conducted experiments on synthetic and real datasets. The results confirm that evaluating products via scores provides a sound and insightful way of identifying prospective customers. Under typical settings, our proposed algorithms execute faster than existing ones by 1–3 orders of magnitude.

Identifying the best tuples in a large database for users has been a longstanding challenge in database community. Many interactive methods have been proposed to help users search for their best tuples in the database. Specifically, each user undergoes rounds of interaction. In each round, the user is presented with two tuples and is asked to pick the one s/he prefers more. Based on the user feedback, the user preference can be learned implicitly. Eventually, the best tuple w.r.t. the learned user preference is returned. Many systems have been designed for conducting interactive methods. However, they mainly restrict their settings on databases with numerical attributes, neglecting that in reality, databases can also be described by categorical attributes. Although there are some strategies to convert categorical attributes to numerical attributes, the conversion not only incurs poor efficiency, but also requires heavy interactive effort. In light of this, we developed an interactive system, called MixedSearch, and demonstrated that the system could find the best tuples for users in the database described by mixed attributes.

Session-based recommendation, aiming at making the prediction of the user's next item click based on the information in a single session only, even in the presence of some random user's behavior, is a complex problem. This complex problem requires a high-capability model of predicting the user's next action. Most (if not all) existing models follow the encoder-predictor paradigm where all studies focus on how to optimize the encoder module extensively in the paradigm, but they overlook how to optimize the predictor module. In this paper, we discover the critical issue of the low-capability predictor module among existing models. Motivated by this, we propose a novel framework called Session-based Recommendation with Predictor Add-On (SR-PredictAO). In this framework, we propose a high-capability predictor module which could alleviate the effect of random user's behavior for prediction. It is worth mentioning that this framework could be applied to any existing models, which could give opportunities for further optimizing the framework. Extensive experiments on two real-world benchmark datasets for three state-of-the-art models show that SR-PredictAO outperforms the current state-of-the-art model by up to 2.9% in HR@20 and 2.3% in MRR@20. More importantly, the improvement is consistent across almost all the existing models on all datasets, and is statistically significant, which could be regarded as a significant contribution in the field.

Data visualization (DV) has become the prevailing tool in the market due to its effectiveness into illustrating insights in vast amounts of data. To lower the barrier of using DVs, automatic DV tasks, such as natural language question (NLQ) to visualization translation (formally called text-to-vis), have been investigated in the research community. However, text-to-vis assumes the NLQ to be well-organized and expressed in a single sentence. However, in real-world settings, complex DV is needed through consecutive exchanges between the DV system and the users. In this paper, we propose a new task named CoVis, short for Conversational text-to-Visualization, aiming at constructing DVs through a series of interactions between users and the system. Since it is the task which has not been studied in the literature, we first build a benchmark dataset named Dial-NVBench, including dialogue sessions with a sequence of queries from a user and responses from the system. The ultimate goal of each dialogue session is to create a suitable DV. However, this process can contain diverse dialogue queries, such as seeking information about the dataset, manipulating parts of the data, and visualizing the data. Then, we propose a multi-modal neural network named MMCoVisNet to answer these DV-related queries. In particular, MMCoVisNet first fully understands the dialogue context and determines the corresponding responses. Then, it uses adaptive decoders to provide the appropriate replies: (i) a straightforward text decoder is used to produce general responses, (ii) an SQL-form decoder is applied to synthesize data querying responses, and (iii) a DV-form decoder tries to construct the appropriate DVs. We comparatively evaluate MMCoVisNet with other baselines over our proposed benchmark dataset. Experimental results validate that MMCoVisNet performs better than existing baselines and achieves a state-of-the-art performance.

Studying the shortest path query for moving objects on a terrain surface has aroused widespread concern in industry and academia. In this paper, we study the weighted region problem, which aims at finding the shortest path between two points passing different regions on a 3D weighted terrain surface and different regions are assigned different weights. We propose an efficient (1 + ϵ)-approximate on-the-fly algorithm to solve it. Our experimental results show that our algorithm is up to 1630 times and 40 times better than the best-known algorithm in terms of running time and memory usage in realistic settings1.

The prevalence of computer graphics technology boosts the developments of point clouds in recent years, which offer advantages over terrain surfaces (represented by Triangular Irregular Networks, i.e., TINs) in proximity queries, including the shortest path query, the k-Nearest Neighbor (kNN) query and the range query. Since (1) all existing on-the-fly and oracle-based shortest path query algorithms on a TIN are very expensive, (2) all existing on-the-fly shortest path query algorithms on a point cloud are still not efficient, and (3) there are no oracle-based shortest path query algorithms on a point cloud, we propose an efficient (1+ε)-approximate shortest path oracle that answers the shortest path query for a set of Points-Of-Interests (POIs) on the point cloud, which has a good performance (in terms of the oracle construction time, oracle size and shortest path query time) due to the concise information about the pairwise shortest paths between any pair of POIs stored in the oracle. Our oracle can be easily adapted to answering the shortest path query for any points on the point cloud if POIs are not given as input, and also achieve a good performance. Then, we propose efficient algorithms for answering the (1+ε)-approximate kNN and range query with the assistance of our oracle. Our experimental results show that when POIs are given (resp. not given) as input, our oracle is up to 390 times, 30 times and 6 times (resp. 500 times, 140 times and 50 times) better than the best-known oracle on a TIN in terms of the oracle construction time, oracle size and shortest path query time, respectively. Our algorithms for the other two proximity queries are both up to 100 times faster than the best-known algorithms.

The task of finding a user's utility function (representing the user's preference) by asking them to compare pairs of points through a series of questions, each requiring him/her to compare 2 points for choosing a more preferred one, to find the best point in the database is a common problem in the database community. However, in real-world scenarios, users may provide unreliable answers due to two major types of errors, namely persistent errors and random errors. Existing interaction algorithms either simply assume that all answers provided by the user are reliable, or are capable of handling random errors only, which can lead to finding undesirable points, ignoring persistent errors. To address this challenge, we propose more generalized algorithms that are robust to both persistent and random errors made by the user. Specifically, we propose (1) an algorithm that asks an asymptotically optimal number of questions, and (2) an algorithm that asks an even smaller number of questions empirically, with provable performance guarantee. Our experiments on both real and synthetic datasets demonstrate that our algorithms outperform existing methods in terms of accuracy, even with a small number of questions asked.

Shortest path queries are ubiquitous in many spatial applications. Existing solutions assign numerical weights to edges and compute the path with the minimum sum of edge weights. However, in practice, the road categories associated with edges (e.g., toll) can make shortest paths undesirable, e.g., they may use unfavorable toll roads. Augmenting each edge with a label to denote its category, we study the Label-Constrained Shortest Path (LCSP) query that finds the shortest path under the constraint that the edge labels along the path should follow a pattern expressed by a formal language. There have been extensive LCSP solutions, but they are either inefficient in query processing or limited to special languages with low expressiveness capacity. In this paper, we propose the index called Partially Constrained Shortest Path (PCSP), which answers each query quickly by concatenating two shortest paths that partially satisfy the constraint and support more general regular languages. We also present pruning techniques that further optimize query efficiency. Experimental comparison with the state-of-the-art index demonstrates the superiority of PCSP. It can answer each LCSP query in around 100 microseconds and runs faster than the best-known solution by up to two orders of magnitude.

Co-location patterns, which capture the phenomenon that objects with certain labels are often located in close geographic proximity, are defined based on a support measure which quantifies the prevalence of a pattern candidate in the form of a label set. Existing support measures share the idea of counting the number of instances of a given label set$C$as its support, where an instance of$C$is an object set whose objects collectively carry all labels in$C$and are located close to one another. However, they suffer from various weaknesses, e.g., fail to capture all possible instances, or overlook the cases when multiple instances overlap. In this paper, we propose a new measure called Fraction-Score which counts instancesfractionallyif they overlap. Fraction-Score captures all possible instances, and handles the cases where instances overlap appropriately (so that the supports defined are more meaningful and anti-monotonic). We develop efficient algorithms to solve the co-location pattern mining problem defined with Fraction-Score. Furthermore, to obtain representative patterns, we develop an efficient algorithm for mining the maximal co-location patterns, which are those patterns without proper superset patterns. We conduct extensive experiments using real and synthetic datasets, which verified the superiority of our proposals.

Given a source node$s$and a target node$t$, the hitting probability tells us how likely an$\alpha$-terminating random walk (which stops with probability$\alpha$at each step) starting from$s$can hit$t$before it stops. This concept originates from the hitting time, a classic concept in random walks. In this paper, we focus on the group hitting probability (GHP) where the target is a set of nodes, measuring the node-to-group structural proximity. For this group version of the hitting probability, we present efficient algorithms for two types of GHP queries: the pairwise query which returns the GHP value of a target set$T$with respect to (w.r.t.) a source node$s$, and the top-$k$query which returns the top-$k$target sets with the largest GHP value w.r.t. a source node$s$. We first develop an efficient algorithm named SAMBA for the pairwise query, which is built on a group local push algorithm tailored for GHP, with rigorous analysis for correctness. Next, we show how to speed up SAMBA by combining the group local push algorithm with the Monte Carlo approach, where GHP brings new challenges as it might need to consider every hop of the random walk. We tackle this issue with a new formulation of the GHP and show how to provide approximation guarantees with a detailed theoretical analysis. With SAMBA as the backbone, we develop an iterative algorithm for top-$k$queries, which adaptively refines the bounds for the candidate target sets, and terminates as soon as it meets the stopping condition, thus saving unnecessary computational costs. We further present an optimization technique to accelerate the top-$k$query, improving its practical performance. Extensive experiments show that our solutions are orders of magnitude faster than their competitors.

With the advance of the geo-positioning technology, the terrain surface data has become increasingly popular and has drawn much research attention from both academia and industry. Answering a shortest-path query for a given source and a given destination on a terrain surface is a fundamental problem and has many applications including Geographical Information System and 3D virtual games. We observe that all existing exact algorithms are only aware of the position of the source point and is unaware of the information of the destination point. Motivated by this, in this paper, we propose an efficient algorithm, namelydirection-oriented algorithm (DIO Algorithm), for answering shortest-path queries on a terrain surface. The algorithm properly guides the search along a direction towards the destination instead of blindly searching all possible directions from the source point. To this end, we convert the geodesic shortest path problem to a shortest obstacle-free euclidean path problem in the 2D planar unfolding of the terrain surface. Based on this conversion, we derive for each part of the terrain surface a lower bound on the length of the shortest path from the source to the destination passing through the part with a novel method. The lower bounds provide useful information that can be used to decide the visiting order of the parts on the terrain surface and guides the search of finding the destination quickly. Our experiments verified that our algorithm runs faster than the state-of-the-art by more than one order of magnitude.

The emergence of natural language processing has revolutionized the way users interact with tabular data, enabling a shift from traditional query languages and manual plotting to more intuitive, language-based interfaces. The rise of large language models (LLMs) such as ChatGPT and its successors has further advanced this field, opening new avenues for natural language processing techniques. This survey presents a comprehensive overview of natural language interfaces for tabular data querying and visualization, which allow users to interact with data using natural language queries. We introduce the fundamental concepts and techniques underlying these interfaces with a particular emphasis on semantic parsing, the key technology facilitating the translation from natural language to SQL queries or data visualization commands. We then delve into the recent advancements in Text-to-SQL and Text-to-Vis problems from the perspectives of datasets, methodologies, metrics, and system designs. This includes a deep dive into the influence of LLMs, highlighting their strengths, limitations, and potential for future improvements. Through this survey, we aim to provide a roadmap for researchers and practitioners interested in developing and applying natural language interfaces for data interaction in the era of large language models.

Mining causal relationships within co-location patterns is a crucial aspect of knowledge discovery, with broad applications spanning across ecosystems, praxiology, and epidemiology. However, existing approaches to solving this problem still have limitations. Some causality models assume rigid definitions of causation that may not generalize or do not fully leverage spatial-temporal information. Moreover, how to differentiate direct causes and indirect causes is also challenging. To address them, this paper proposes a generalized model for mining causality from co-location patterns. Our approach, rooted at Granger causality, integrates an algorithm that approximates direct causes from Granger causes by leveraging unique linear causal information. We conducted extensive experiments on real-world datasets to evaluate the effectiveness of our method and compared it with two baselines.

In the literature of the database community, there are a lot of studies about finding a utility function from a user (representing the user’s preference), via interaction with the user by asking a number of questions each requiring him/her to compare 2 points for choosing a more preferred point, in order to find the best tuple in the database containing a lot of tuples. In the real world, the user may make mistakes (carelessly), which means that s/he may answer some of the questions wrongly. Unfortunately, existing interaction algorithms may find the undesirable point based on the wrongly learnt utility function because they assume that all answers from the user are 100% correct. In particular, even if the user answers only 1 wrong answer, the output of the existing algorithms may be far away from the users’ real need. Motivated by this, in this paper, we propose a new problem of finding the most interesting point via interaction which is robust to possible mistakes made by a user. Besides, we propose (1) an algorithm that asks an asymptotically optimal number of questions when the dataset contains 2 dimensions and (2) two algorithms with provable performance guarantee when the dataset contains d dimensions where d≥ 2. Experiments on real and synthetic datasets show that our algorithms outperform the existing ones with a higher accuracy with only a small number of questions asked.

Public transport contributes significantly to addressing some city issues such as air pollution and traffic congestion. As the public transport demand changes in urban development, we need to plan new routes to match the demand. Existing methods of planning new bus routes either are inefficient in using the path’s cost or use other inaccurate cost measurements. This paper focuses on finding a new bus route efficiently on road networks. Specifically, we first propose the Bus Routing on Roads (BRR) problem which combines two common goals of minimizing the walking costs of passengers and maximizing the connectivity of the new route to the existing transit network. They are consistent with matching the demand and facilitating the transfer. We first show the NP-hardness of the BRR and design an approximation algorithm called Efficient Bus Routing on Roads (EBRR). We theoretically analyzed its approximation ratio and time complexity. Extensive evaluations with state-of-the-art solutions on three real-world datasets validate the effectiveness and efficiency of EBRR. It could recommend a new bus route with high quality in around 10 seconds, 60x faster than the baselines.

The problem of extracting the user’s favorite tuple from a large dataset attracts a lot of attention in the database community. Existing studies attempt to search for the target tuple with the help of user interaction. Specifically, they ask a user several questions, each of which consists of two tuples and asks the user to indicate which one s/he prefers. Based on the feedback, the user preference is learned implicitly and the target tuple w.r.t. the learned preference is returned. However, they mainly consider datasets with numerical attributes (e.g., price). In practice, tuples can also be described by categorical attributes (e.g., color), where there is no trivial order in the attribute values. Even if the categorical attributes can be reduced into numerical ones using conventional strategies (e.g., one-hot encoding), existing methods do not work well. In this paper, we study how to find the user’s favorite tuple from datasets with mixed attributes (including both numerical and categorical attributes) by interacting with the user.We study our problem progressively. Firstly, we inquiry a special case in which tuples are only described by categorical attributes. We present algorithm SP-Tree that asks an asymptotically optimal number of questions. Secondly, we explore the general case in which tuples are described by numerical and categorical attributes. We propose algorithm GE-Graph that performs well theoretically and empirically. Experiments are conducted on synthetic and real datasets. The results show that our algorithms outperform existing ones on both the execution time and the number of questions asked. Under typical settings, we reduce dozens of questions asked and speed up by several orders of magnitude.

Given a set of spatio-temporal objects, a top-k window aggregate query reports top-k tuples that are ordered with respect to the number of objects during a given time interval and within a spatial range. For example, when analyzing traffic density in a city, one wishes to retrieve top-k time intervals in a certain area that are decreasingly ordered according to the number of vehicles passing by. As simply performing sequential scan over all objects is a costly procedure, an index structure is typically built to enhance the query performance. A crucial step during the evaluation is to determine the number of objects in an arbitrary node, called coverage number sequence. This is a challenging task since objects appear and disappear at different time points such that the number of objects in the query node changes over time. Also, as a hierarchical index structure, the value of a node at high level is achieved by performing the aggregation over its child nodes. Simply enumerating all objects rooted in the query node suffers from performance issues mainly due to (i) traversing the sub-tree to retrieve a large number of time points and (ii) repeatedly performing the aggregation at certain time points. We propose an efficient approach to solve the performance issue for both R-tree and Octree and support updating for new arrival data objects being inserted into the index. Our approach outperforms alternative methods in general according to a thorough analysis on the complexity. Coverage number sequences as well as proposed optimization techniques are utilized to enhance the performance of window aggregate queries. We confirm the superiority of our approach over alternative methods by performing a comprehensive experimental evaluation over large real datasets in a database system.

Data visualizations (DVs) refer to the methodologies and tools where visual elements like charts, bars and scatters are used to convey summaries behind the raw data. However, it usually takes much effort to master DV, even for data scientists and experts, not to mention beginners. Hence, a popular task named Text-to-Vis, focusing on automatically generating data visualizations (DVs) from natural language questions (NLQs), has been introduced and has recently been gaining great attention from both the database and the data mining communities. In this paper, we propose the reversed task Vis-to-Text, which aims to generate human-readable descriptions to explain complicated DVs for educational purposes. Intuitively, text-to-vis and vis-to-text are strongly correlated to one another, i.e., the input of text-to-vis is the output of vis-to-text, and vice versa. This relationship is generally known as duality and has been validated to be important for improving the performances of both tasks in machine translation, question answering, and dialogue systems. However, its effectiveness in text-to-vis and vis-to-text is under-explored. In this paper, we make use of the duality to optimize both tasks. We first design a Transformer-based network to tackle the vis-to-text task. Then, we further explore a dual training framework to simultaneously optimize the two tasks. More specifically, we analyze the duality and finally convert it into a corresponding regularization term to constrain the loss function to guide the model training process. Finally, we evaluate our approach on a public dataset, and the experimental results validate the rationale of this new proposed vis-to-text task and also show that this dual framework can boost the performance of the vis-to-text task over existing baselines.

The computation of a group Steiner tree (GST) in various types of graph networks, such as social network and transportation network, is a fundamental graph problem in graphs, with important applications. In these graphs, time is a common and necessary dimension, for example, time information in social network can be the time when a user sends a message to another user. Graphs with time information can be called temporal graphs. However, few studies have been conducted on GST in terms of temporal graphs. This study analyzes the computation of GST for temporal graphs, i.e., the computation of temporal GST (TGST), which is shown to be an NP‐hard problem. We propose an efficient solution based on a dynamic programming algorithm for our problem. This study adopts new optimization techniques, including graph simplification, state pruning, and A∗ search, are adopted to dramatically reduce the algorithm search space. Moreover, we consider three extensions for our problem, namely the TGST with unspecified tree root, the progressive search of TGST, and the top‐N search of TGST. Results of the experimental study performed on real temporal networks verify the efficiency and effectiveness of our algorithms.

Due to the advancement of geo-positioning technology, the terrain data has become increasingly popular and has drawn a lot of research effort from both academia and industry. The distance computation on the terrain surface is a fundamental and important problem that is widely applied in geographical information systems and 3D modeling. As could be observed from the existing studies, online computation of the distance on the terrain surface is very expensive. All existing index-based methods are only efficient under the case where the distance query must be performed among a small set of predefined points-of-interest known apriori. But, in general cases, they could not scale up to sizable datasets due to their intolerable oracle building time and space consumption. In this paper, we studied the arbitrary point-to-arbitrary point distance query on the terrain surface in which no assumption is imposed on the query points, and the distance query could be performed between any two arbitrary points. We propose an indexing structure, namely Efficient Arbitrary Point-to-Arbitrary Point Distance Oracle (EAR-Oracle), with theoretical guarantee on the accuracy, oracle building time, oracle size and query time. Our experiments demonstrate that our oracle enjoys excellent scalability and it scales up to enormous terrain surfaces but none of the existing index-based methods could be able to. Besides, it significantly outperforms all existing online computation methods by orders of magnitude in terms of the query time.

Route planning is fundamental in our daily life. However, existing mapping applications focus on recommending routes by optimizing one single objective, which is inconsistent with some scenarios where users prefer the optimal route under a constraint. The constrained shortest path (CSP) query matches this requirement, but the query efficiencies of previous solutions are often low due to CSP's NP-hardness. In the era of big data, state-of-the-art indexes are getting larger to support faster query processing. Recent attempts to preprocess more intermediate results and reduce the number of table lookups have proved successful in solving the CSP. However, the best-known algorithm ignores some information in the CSP queries and tries to solve a more general problem before tackling the exact CSP. In this paper, we propose by far the fastest algorithm called QHL, which fully utilizes the pruning power of the CSP query information. Specifically, we preprocess our index by generating pruning conditions that can improve query efficiency. We also conducted extensive experiments on real-world datasets to demonstrate the superiority of our proposed algorithm. QHL could answer each CSP query in around 50 μs and run faster than the best-known algorithm by orders of magnitude.

Image retrieval keeps attracting a lot of attention from both academic and industry over past years due to its variety of useful applications. Due to the rapid growth of deep learning approaches, more better feature vectors of images could be discovered for improving image retrieval. However, most (if not all) existing deep learning approaches consider the similarity between two images locally without considering the similarity among a group of similar images globally , and thus could not return accurate results. In this article, we study the image retrieval with manifold ranking (MR) which considers both the local similarity and the global similarity, which could give more accurate results. However, existing best-known algorithms have one of the following issues: (1) they require to build a bulky index, (2) some of them do not have any theoretical bound on the output, and (3) some of them are time-consuming. Motivated by this, we propose two algorithms, namely Monte Carlo-based MR ( MCMR ) and MCMR+ , for image retrieval, which do not have the above issues. We are the first one to propose an index-free manifold ranking image retrieval with the output theoretical bound. More importantly, our algorithms give the first best-known time complexity result of \(O(n \log n)\) where \(n\) is the total number of images in the database compared with the existing best-known result of \(O(n^2)\) in the literature of computing the exact top- \(k\) results with quality guarantee. Lastly, our experimental result shows that MCMR+ outperforms existing algorithms by up to four orders of magnitude in terms of query time.

With the proliferation of location-based services, geo-textual data is becoming ubiquitous. Objects involved in geo-textual data include geospatial locations, textual descriptions or keywords, and various attributes (e.g., a point-of-interest has its expenses and users' ratings). One prominent type of spatial keyword queries is to find, for a query consisting of a location and keywords, a set of objects that covers all the keywords and is of good quality according to some criteria. Existing studies define the criteria either based on the geospatial information of the objects solely or simply treat the geospatial and attribute information of the objects together without differentiation. As a result, they cannot provide users flexibility to express finer grained preferences on the objects. In this paper, we propose a new criterion which is to find a set of objects where the distance (defined based on the geospatial information) is at most a threshold specified by users and the cost (defined based on the attribute information) is optimized. We develop a suite of three algorithms including an exact algorithm and two approximation algorithms with provable guarantees for the problem. We conducted extensive experiments on real datasets which verified the efficiency and effectiveness of proposed algorithms.

Session-based recommendation aims to predict the next item in an anonymous session. Recent advances have shown the importance of exploiting inter-session dependencies, such as item-item transitions and session-session similarities. However, the existing methods either ignore the relative order of item co-occurrences or assign the same importance to co-occurrence patterns at all distances. Besides, they are prone to extracting wrong signals to learn user preferences from dependencies between sessions. To solve these problems, we propose a model called FOCOL to better exploit the intersession dependencies by considering Fine-grained item co-Occurrences and applying the COntrastive Learning framework. Specifically, to capture inter-session item-item dependencies, we propose a component called FOGCN (Fine-grained co-Occurrence Graph Convolution Network) to automatically learn the importance of item co-occurrence patterns from a global graph that encodes the detailed information about item co-occurrences such as relative order and distance. To directly capture dependencies between sessions, we view the recommendation task as a clustering problem, and propose a component called CSRL (Contrastive Session Representation Learning) to implicitly group similar sessions (i.e., sessions with the same next item) into the same cluster and push apart sessions at different clusters. Extensive experiments conducted on three public datasets show that the proposed model is superior to the state-of-the-art methods and the proposed two components can learn more informative item and session representations by considering the fine-grained item co-occurrences and directly capturing dependencies between sessions.

With the proliferation of location-based services, geo-textual data is becoming ubiquitous. Objects involved in geo-textual data include geospatial locations, textual descriptions or keywords, and various attributes (e.g., a point-of-interest has its expenses and users' ratings). Many types of spatial keyword queries have been proposed on geo-textual data. Among them, one prominent type is to find, for a query consisting of a query location and some query keywords, a set of multiple objects such that the objects in the set collectively cover all the query keywords, and the object set is of good quality according to some criterion. Existing studies define the criterion either based on the geospatial information of the objects solely, or simply treat the geospatial information and the attribute information of the objects together without differentiation though they may have different semantics and scales. As a result, they cannot provide users flexibility to express finer grained preferences on the objects. In this paper, we propose a new criterion which is to find a set of objects where the distance (defined based on the geospatial information) is at most a threshold specified by users and the cost (defined based on the attribute information) is optimized. We develop a suite of two algorithms including an exact algorithm and an approximation algorithm with provable guarantees for the problem. We conducted extensive experiments on both real and synthetic datasets, which verified the efficiency and effectiveness of proposed algorithms.

Recent years have witnessed the burgeoning of data visualization (DV) systems in both the research and the industrial communities since they provide vivid and powerful tools to convey the insights behind the massive data. A necessary step to visualize data is through creating suitable specifications in some declarative visualization languages (DVLs, e.g., Vega-Lite, ECharts). Due to the steep learning curve of mastering DVLs, automatically generating DVs via natural language questions, or text-to-vis, has been proposed and received great attention. However, existing neural network-based text-to-vis models, such as Seq2Vis or ncNet, usually generate DVs from scratch, limiting their performance due to the complex nature of this problem. Inspired by how developers reuse previously validated source code snippets from code search engines or a large-scale codebase when they conduct software development, we provide a novel hybrid retrieval-generation framework named RGVisNet for text-to-vis. It retrieves the most relevant DV query candidate as a prototype from the DV query codebase, and then revises the prototype to generate the desired DV query. Specifically, the DV query retrieval model is a neural ranking model which employs a schema-aware encoder for the NL question, and a GNN-based DV query encoder to capture the structure information of a DV query. At the same time, the DV query revision model shares the same structure and parameters of the encoders, and employs a DV grammar-aware decoder to reuse the retrieved prototype. Experimental evaluation on the public NVBench dataset validates that RGVisNet can significantly outperform existing generative text-to-vis models such as ncNet, by up to 74.28% relative improvement in terms of overall accuracy. To the best of our knowledge, RGVisNet is the first framework that seamlessly integrates the retrieval- with the generative-based approach for the text-to-vis task.

With recent development in natural language processing (NLP) and automatic speech recognition (ASR), voice-based interfaces have become a necessity for applications such as chatbots, search engines, and databases. In this demonstration, we introduce VoiceQuerySystem, a voice-based database querying system that enables users to conduct data operations with natural language questions (NLQs). Different from existing voice-based interfaces such as SpeakQL or EchoQuery, which restricts the voice input to be an exact SQL or follow a pre-defined template, VoiceQuerySystem attempts to achieve data manipulation via common NLQs, and thus does not require the user's technical background in SQL language.

There are various queries proposed to assist users in finding their favorite tuples from a dataset with the help of user interaction. Specifically, they interact with a user by asking questions. Each question presents two tuples, which are selected from the dataset based on the user's answers to the previous questions, and asks the user to select the one s/he prefers. Following the user feedback, the user preference is learned implicitly, and the best tuple w.r.t. the learned preference is returned. However, existing queries only consider datasets with ordered attributes (e.g., price), where there exists a trivial order on the attribute values. In practice, a dataset can also be described by unordered attributes, where there is no consensus about the order of the attribute values. For example, the size of a laptop is an unordered attribute. One user might favor a large size because s/he could enjoy a large screen, while another user may prefer a small size for portability. In this paper, we study how to find a user's favorite tuple from the dataset that has both ordered and unordered attributes by interacting with the user. We study our problem progressively. First, we look into a special case in which the dataset is described by one ordered and one unordered attributes. We present algorithm DI that is asymptotically optimal in terms of the number of questions asked. Then, we dig into the general case in which the dataset has several ordered and unordered attributes. We propose two algorithms BS and EDI that have provable performance guarantees and perform well empirically. Experiments were conducted on synthetic and real datasets, showing that our algorithms outperform existing algorithms in the number of questions asked and the execution time. Under typical settings, our algorithms ask up to 10 times fewer questions and take several orders of magnitude less time than existing algorithms.

Due to the advance of the geo-spatial positioning and the computer graphics technology, digital terrain data has become increasingly popular nowadays. Query processing on terrain data has attracted considerable attention from both the academic and the industry communities. Proximity queries such as the shortest path/distance query, k nearest/farthest neighbor query, and top- k closest/farthest pairs query are fundamental and important queries in the context of the terrain surfaces, and they have a lot of applications in Geographical Information System, 3D object feature vector construction, and 3D object data mining. In this article, we first study the most fundamental type of query, namely, shortest distance and path query, which is to find the shortest distance and path between two points of interest on the surface of the terrain. As observed by existing studies, computing the exact shortest distance/path is very expensive. Some existing studies proposed ϵ -approximate distance and path oracles, where ϵ is a non-negative real-valued error parameter. However, the best-known algorithm has a large oracle construction time, a large oracle size, and a large query time. Motivated by this, we propose a novel ϵ -approximate distance and path oracle called the S pace E fficient distance and path oracle (SE), which has a small oracle construction time, a small oracle size, and a small distance and path query time, thanks to its compactness of storing concise information about pairwise distances between any two points-of-interest. Then, we propose several algorithms for the k nearest/farthest neighbor and top- k closest/farthest pairs queries with the assistance of our distance and path oracle SE . Our experimental results show that the oracle construction time, the oracle size, and the distance and path query time of SE are up to two, three, and five orders of magnitude faster than the best-known algorithm, respectively. Besides, our algorithms for other proximity queries including k nearest/farthest neighbor queries and top- k closest/farthest pairs queries significantly outperform the state-of-the-art algorithms by up to two orders of magnitude.

Traffic forecasting is an important and challenging problem for intelligent transportation systems due to the complex spatial dependencies among neighboring roads and changing road conditions in different time periods. Spatio-temporal graph convolutional networks (STGCNs) are usually adopted to forecast traffic features in a road network. Some STGCN models involves spatial layers first and then temporal layers and some other models involves these layers in a reverse order. This creates an interesting research question on whether the ordering of the spatial layers (or temporal layers) first in an existing STGCN model could improve the forecasting performance. To the best of our knowledge, we are the first to study this interesting research problem, which creates a deep insight as a guideline to the research community on how to design STGCN models. We conducted extensive experiments to study a number of representative STCGN models for this research problem. We found that these models with spatial layers constructed before temporal layers has a higher chance to outperform that with temporal layers constructed first, which suggests the future design principle of STGCN models.

Selecting a small set of representatives from a large database is important in many applications such as multi-criteria decision making, web search, and recommendation. The k-regret minimizing set (k-RMS) problem was recently proposed for representative tuple discovery. Specifically, for a large database P of tuples with multiple numerical attributes, the k-RMS problem returns a size-r subset Q of P such that, for any possible ranking function, the score of the top-ranked tuple in Q is not much worse than the score of the kth-ranked tuple in P. Although the k-RMS problem has been extensively studied in the literature, existing methods are designed for the static setting and cannot maintain the result efficiently when the database is updated. To address this issue, we propose the first fully-dynamic algorithm for the k-RMS problem that can efficiently provide the up-to-date result w.r.t. any tuple insertion and deletion in the database with a provable guarantee. Experimental results on several real-world and synthetic datasets demonstrate that our algorithm runs up to four orders of magnitude faster than existing k-RMS algorithms while providing results of nearly equal quality.

N-best list rescoring, an essential step in hybrid automatic speech recognition (ASR), aims to re-evaluate the N-best hypothesis list decoded by the acoustic model (AM) and language model (LM), and selects the top-ranked hypotheses as the final ASR results. This paper explores the performance of neural rescoring models in scenarios where large-scale training labels are not available. We propose a weakly supervised neural rescoring method, WSNeuRescore, where a listwise multimodal neural rescoring model is pre-trained using labels automatically obtained without human annotators. Specifically, we employ the output of an unsupervised rescoring model, the weighted linear combination of the AM score and the LM score, as a weak supervision signal to pre-train the neural rescoring model. Our experimental evaluations on a public dataset validate that the pre-trained rescoring model based on weakly supervised data leads to an impressive performance. In the extreme scenario without any high-quality labeled data, it achieves up to an 11.90% WER reduction and a 15.56% NDCG@10 improvement over the baseline method in Kaldi, a well-known open-source toolkit in the ASR community.

When a large dataset is given, it is not desirable for a user to read all tuples one-by-one in the whole dataset to find satisfied tuples. The traditional top-k query finds the best k tuples (i.e., the top-k tuples) w.r.t. the user's preference. However, in practice, it is difficult for a user to specify his/her preference explicitly. We study how to enhance the top-k query with user interaction. Specifically, we ask a user several questions, each of which consists of two tuples and asks the user to indicate which one s/he prefers. Based on the feedback, the user's preference is learned implicitly and one of the top-k tuples w.r.t. the learned preference is returned. Here, instead of directly following the top-k query to return all the top-k tuples, since it requires heavy user effort during the interaction (e.g., answering many questions), we reduce the output size to strike for a trade-off between the user effort and the output size.

In many applications of session-based recommendation, social networks are usually available. Since users' interests are influenced by their friends, recommender systems can leverage social networks to better understand their users' preferences and thus provide more accurate recommendations. However, existing methods for session-based social recommendation are not efficient. To predict the next item of a user's ongoing session, the methods need to process many additional sessions of the user's friends to capture social influences, while non-social-aware methods (i.e., those without using social networks) only need to process one single session. To solve the efficiency issue, we propose an efficient framework for session-based social recommendation. In the framework, first, a heterogeneous graph neural network is used to learn user and item representations that integrate the knowledge from social networks. Then, to generate predictions, only the user and item representations relevant to the current session are passed to a non-social-aware model. During inference, since the user and item representations can be precomputed, the overall model runs as fast as the original non-social-aware model, while it can achieve better performance by leveraging the knowledge from social networks. Apart from being efficient, our framework has two additional advantages. First, the framework is flexible because it is compatible with any existing non-social-aware models and can easily incorporate more knowledge other than social networks. Second, our framework can capture cross-session item transitions while existing methods can only capture intra-session item transitions. Extensive experiments conducted on three public datasets demonstrate the effectiveness and efficiency of the proposed framework. Our code is available at https://github.com/twchen/SEFrame.

The shortest path in both the two dimensional (2D) plane and the three dimensional (3D) terrain is extensively used both in industry and academia. Although there are some map visualization tools for viewing the shortest path in 2D and 3D views, we find two limitations: (1) they are not applicable for map applications with obstacles (such as the wall in a building), and (2) they look unrealistic and strange when a road network approach is blindly adopted. Motivated by this, we developed a web-based multi-functional campus map tool called Path Advisor , which allows users to visualize the shortest path in the 2D view, the bird's eye view and the virtual reality view (VR view). Path Advisor uses Dijkstra's shortest path algorithm and breadth-first tree in the 2D view, and the weighted shortest surface path algorithm in the bird's eye view and the VR view. We shot a video for demonstrating Path Advisor at https://youtu.be/ZgdjyXXHwqg.

Due to the prevalence of graph data, graph analysis is very important nowadays. One popular analysis on graph data is Random Walk with Restart (RWR) since it provides a good metric for measuring the proximity of two nodes in a graph. Although RWR is important, it is challenging to design an algorithm for RWR. To the best of our knowledge, there are no existing RWR algorithms which, at the same time, (1) are index-free, (2) return answers with a theoretical guarantee and (3) are efficient. Motivated by this, in this paper, we propose an index-free algorithm called Residue-Accumulated approach (ResAcc) which returns answers with a theoretical guarantee efficiently. Our experimental evaluations on large-scale real graphs show that ResAcc is up to 4 times faster than the best-known previous algorithm, guaranteeing the same accuracy. Under typical settings, the best-known algorithm ran around 1000 seconds on a large dataset containing 41.7 million nodes, which is too time-consuming, while ResAcc finished in 275 seconds with the same accuracy. Moreover, ResAcc is up to 6 orders of magnitude more accurate than the best-known algorithm in practice with the same execution time, which is considered as a substantial improvement.

Geo-textual data is ubiquitous nowadays, where each object has a location and is associated with some keywords. Many types of queries based on geo-textual data, termed as spatial keyword queries, have been proposed, and are to find optimal object(s) in terms of both its (their) location(s) and keywords. In this paper, we propose a new type of query called nearby-fit spatial keyword query (NSKQ), where an optimal object is defined based not only on the location and the keywords of the object itself, but also on those of the objects nearby. For example, in an application of finding a hotel, not only the location of a hotel but also the objects near the hotel (e.g., shopping malls, restaurants and bus stops nearby) might need to be taken into consideration.The query is proved to be NP-hard, and in order to perform the query efficiently, we developed two approximate algorithms with small constant approximation factors equal to 1.155 and 1.79. We conducted extensive experiments based on both real and synthetic datasets, which verified our algorithms.

When faced with a database containing millions of products, a user may be only interested in a (typically much) smaller representative subset. Various approaches were proposed to create a good representative subset that fits the user's needs which are expressed in the form of a utility function (e.g., the top-k and diversification query). Recently, a regret minimization query was proposed: it does not require users to provide their utility functions and returns a small set of tuples such that any user's favorite tuple in this subset is guaranteed to be not much worse than his/her favorite tuple in the whole database. In a sense, this query finds a small set of tuples that makes the user happy (i.e., not regretful) even if s/he gets the best tuple in the selected set but not the best tuple among all tuples in the database. In this paper, we study the min-size version of the regret minimization query; that is, we want to determine the least tuples needed to keep users happy at a given level. We term this problem as the α-happiness query where we quantify the user's happiness level by a criterion, called the happiness ratio, and guarantee that each user is at least α happy with the set returned (i.e., the happiness ratio is at least α) where α is a real number from 0 to 1. As this is an NP-hard problem, we derive an approximate solution with theoretical guarantee by considering the problem from a geometric perspective. Since in practical scenarios, users are interested in achieving higher happiness levels (i.e., α is closer to 1), we performed extensive experiments for these scenarios, using both real and synthetic datasets. Our evaluations show that our algorithm outperforms the best-known previous approaches in two ways: (i) it answers the α-happiness query by returning fewer tuples to users and, (ii) it answers much faster (up to two orders of magnitude times improvement for large α).

Topic modeling has been intensively studied and widely applied in both academia and industry in the last decade. In the literature, topic models usually need to be trained from scratch for each individual corpus. Hence, the wisdom of the crowd (i.e., topic models previously trained based upon other corpora) is abandoned. Since a massive amount of in-domain data, considerable computational cost, and human labour are involved in obtaining a high-quality topic model, training from scratch for each new corpus is a huge waste of resources. In this paper, we propose the novel TopicOcean framework, which aims to integrate well-trained topic models and transfer the knowledge of accumulated topics to new corpora in order to improve the quality of their topic models. We first propose a method of constructing the ever-increasing TopicOcean, and then propose a meta-learning mechanism that transfers the meta-level knowledge (i.e., topics) in TopicOcean to the scenario of topic modeling on new corpora. Comprehensive experiments validate that the TopicOcean framework can significantly outperform the state-of-the-art (53.77% perplexity improvement on a temporal-shift corpus and 29.24% improvement on a domain-shift corpus). The well-trained high-quality topic models used to construct TopicOcean have been opensourced to promote further research.11The well-trained topic models can be accessed at Github (https://github.com/baidu/Familia/blob/master/model/download_model.sh).

Recently, graph neural networks (GNNs) have gained increasing popularity due to their convincing performance in various applications. Many previous studies also attempted to apply GNNs to session-based recommendation and obtained promising results. However, we spot that there are two information loss problems in these GNN-based methods for session-based recommendation, namely the lossy session encoding problem and the ineffective long-range dependency capturing problem. The first problem is the lossy session encoding problem. Some sequential information about item transitions is ignored because of the lossy encoding from sessions to graphs and the permutation-invariant aggregation during message passing. The second problem is the ineffective long-range dependency capturing problem. Some long-range dependencies within sessions cannot be captured due to the limited number of layers. To solve the first problem, we propose a lossless encoding scheme and an edge-order preserving aggregation layer based on GRU that is dedicatedly designed to process the losslessly encoded graphs. To solve the second problem, we propose a shortcut graph attention layer that effectively captures long-range dependencies by propagating information along shortcut connections. By combining the two kinds of layers, we are able to build a model that does not have the information loss problems and outperforms the state-of-the-art models on three public datasets.

Given two vertices of interest (POIs) s and t on a spatial network, a distance (path) query returns the shortest network distance (shortest path) from s to t. This query has a variety of applications in practice and is a fundamental operation for many database and data mining algorithms. In this paper, we propose an efficient distance and path oracle on dynamic road networks using the randomization technique. Our oracle has a good performance in practice and remarkably, and at the same time, it has a favorable theoretical bound. Specifically, it has O(n log2 n) (resp. O(n log2n)) preprocessing time (resp. space) and O(log4n log log n) (resp. O(log4n log log n+l)) distance query time (resp. shortest path query time) as well as O(log3n) update time with high probability (w.h.p.), where n is the number of vertices in the spatial network and l is the number of edges on the shortest path. Our experiments show that the existing oracles suffer from a huge updating time that renders them impractical and our oracle enjoys a negligible updating time and meanwhile has comparable query time and indexing cost with the best existing oracle.

Geo-textual data is ubiquitous nowadays, where each object has a location and is associated with some keywords. Many types of queries based on geo-textual data, termed as spatial keyword queries, have been proposed, and are to find optimal object(s) in terms of both its (their) location(s) and keywords. In this paper, we propose a new type of query called nearby-fit spatial keyword query (NSKQ), where an optimal object is defined based not only on the location and the keywords of the object itself, but also on those of the objects nearby. For example, in an application of finding a hotel, not only the location of a hotel but also the objects near the hotel (e.g., shopping malls, restaurants, and bus stops nearby) might need to be taken into consideration. The query is proved to be NP-hard, and in order to perform the query efficiently, we developed two approximate algorithms with small constant approximation factors equal to 1.155 and 1.79. We conducted extensive experiments based on both real and synthetic datasets, which verified our algorithms.

We consider the following secure data retrieval problem: a client outsources encrypted data blocks to a semi-trusted cloud server and later retrieves blocks without disclosing access patterns. Existing PIR and ORAM solutions suffer from serious performance bottlenecks in terms of communication or computation costs. To help eliminate this void, we introduce "access pattern unlinkability'' that separates access pattern privacy into short-term privacy at individual query level and long-term privacy at query distribution level. This new security definition provides tunable trade-offs between privacy and query performance. We present an efficient construction, called SBR protocol, using PIR and Oblivious Shuffling to enable secure data retrieval while satisfying access pattern unlinkability. Both analytical and empirical analysis show that SBR exhibits flexibility and usability in practice.

With the proliferation of spatial-textual data such as location-based services and geo-tagged websites, spatial keyword queries are ubiquitous in real life. One example of spatial-keyword query is the so-called collective spatial keyword query (CoSKQ) which is to find, for a given query consisting a query location and several query keywords, a set of objects which covers the query keywords collectively and has the smallest cost wrt the query location. Quite a few cost functions have been proposed for CoSKQ and correspondingly, different approaches have been developed. However, given these cost functions in different forms and approaches in different structures, one could hardly compare existing cost functions systematically and needs to implement all approaches in order to tackle the CoSKQ problem with different cost functions, which is effort-consuming. In this paper, we design a unified cost function which generalizes the majority of existing cost functions for CoSKQ and develop a unified approach which works as well as (and sometimes better than) best-known approaches based on different cost functions. Experiments were conducted on both real and synthetic datasets which verified our proposed approach.

Co-location patterns are well-established on spatial objects with categorical labels, which capture the phenomenon that objects with certain labels are often located in close geographic proximity. Similar to frequent itemsets, co-location patterns are defined based on a support measure which quantifies the popularity (or prevalence) of a pattern candidate (a label set). Quite a few support measures exist for defining co-location patterns and they share an idea of counting the number of instances of a given label set C as its support, where an instance of C is an object set whose objects carry all the labels in C and are located close to one another. Unfortunately, these measures suffer from various weaknesses, e.g., some fail to capture all possible instances while some others overlook the cases when multiple instances overlap. In this paper, we propose a new measure called Fraction-Score whose idea is to count instances fractionally if they overlap. Compared to existing measures, Fraction-Score not only captures all possible instances, but also handles the cases where instances overlap appropriately (so that the supports defined are more meaningful and consistent with the desirable anti-monotonicity property). To solve the co-location pattern mining problem based on Fraction-Score, we develop efficient algorithms which are significantly faster than a baseline that adapts the state-of-the-art. We conduct extensive experiments using both real and synthetic datasets, which verified the superiority of Fraction-Score and also the efficiency of our developed algorithms.

Selecting a certain number of data points (or records) from a database which "best" satisfy users' expectations is a very prevalent problem with many applications. One application is a hotel booking website showing a certain number of hotels on a single page. However, this problem is very challenging since the selected points should "collectively" satisfy the expectation of all users. Showing a certain number of data points to a single user could decrease the satisfaction of a user because the user may not be able to see his/her favorite point which could be found in the original database. In this paper, we would like to find a set of k points such that on average, the satisfaction (ratio) of a user is maximized. This problem takes into account the probability distribution of the users and considers the satisfaction (ratio) of all users, which is more reasonable in practice, compared with the existing studies that only consider the worst-case satisfaction (ratio) of the users, which may not reflect the whole population and is not useful in some applications. Motivated by this, in this paper, we propose algorithms for this problem. Finally, we conducted experiments to show the effectiveness and the efficiency of the algorithms.

Session-based recommendation is a task to predict users' next actions given a sequence of previous actions in the same session. Existing methods either encode the previous actions in a strict order or completely ignore the order. However, sometimes the order of actions in a short sub-sequence, called the detailed order, may not be important, e.g., when a user is just comparing the same kind of products from different brands. Nevertheless, the high-level ordering information is still useful because the data is sequential in nature. Therefore, a good session-based recommender should pay different attention to the sequential information in different levels of granularity. To this end, we propose a novel model to automatically ignore the insignificant detailed ordering information in some sub-sessions, while keeping the high-level sequential information of the whole sessions. In the model, we first use a full self-attention layer with Gaussian weighting to extract features of sub-sessions, and then we apply a recurrent neural network to capture the high-level sequential information. Extensive experiments on two real-world datasets show that our method outperforms or matches the state-of-the-art methods.

Image retrieval keeps attracting a lot of attention from both academic and industry over past years due to its variety of useful applications. Due to the rapid growth of deep learning approaches, more better feature vectors of images could be discovered for improving image retrieval. However, most (if not all) existing deep learning approaches consider the similarity between 2 images locally without considering the similarity among a group of similar images globally, and thus could not return accurate results. In this paper, we study the image retrieval with manifold ranking (MR) which considers both the local similarity and the global similarity, which could give more accurate results. However, existing best-known algorithms have one of the following issues: (1) They require a bulky index, (2) some of them do not have any theoretical bound on the output, and (3) some of them are time-consuming. Motivated by this, we propose an algorithm, namely Monte Carlo-based MR (MCMR) for image retrieval, which does not have the above issues. We are the first one to propose an index-free manifold ranking-based image retrieval with the output theoretical bound. Lastly, our experiments show that MCMR outperforms existing algorithms by up to 4 orders of magnitude in terms of query time.

Optimal location querying (OLQ) in road networks is important for various applications. Existing work assumes no labels for servers and that a client only visits the nearest server. These assumptions are not realistic and it renders the existing work not useful in many cases. In this paper, we introduce the KOLQ problem which considers the k nearest servers of clients and labeled servers. We also proposed algorithms for the problem. Extensive experiments on the real road networks illustrate the efficiency of our proposed solutions.

When faced with a database containing millions of tuples, an end user might be only interested in finding his/her favorite tuple in the database. In this paper, we study how to help an end user to find such a favorite tuple with a few user interactions. In each interaction, a user is presented with a small number of tuples (which can be artificial tuples outside the database or true tuples inside the database) and s/he is asked to indicate the tuple s/he favors the most among them. Different from the previous work which displays artificial tuples to users during the interaction and requires heavy user interactions, we achieve a stronger result. Specifically, we use a concept, called the utility hyperplane, to model the user preference and an effective pruning strategy to locate the favorite tuple for a user in the whole database. Based on these techniques, we developed an interactive system, called FindYourFavorite, and demonstrate that the system could identify the favorite tuple for a user with a few user interactions by always displaying true tuples in the database.

When faced with a database containing millions of tuples, an end user might be only interested in finding his/her (close to) favorite tuple in the database. Recently, a regret minimization query was proposed to obtain a small subset from the database that fits the user's needs, which are expressed through an unknown utility function. Specifically, it minimizes the "regret'' level of a user, which we quantify as the regret ratio if s/he gets the best tuple in the selected subset but not the best tuple among all tuples in the database. We study how to enhance the regret minimization query with user interactions : when presented with a small number of tuples (which can be artificial tuples or true tuples inside the database), a user is asked to indicate the tuple s/he favors the most among them. In particular, we are also interested in the special case of determining the favorite tuple for a user in the entire database with a small amount of interaction, measured by the number of questions we ask the user. Different from the previous work which displays artificial tuples to users, we achieve a stronger result in this paper by always displaying true tuples in the database. Specifically, we present a generic framework for interactive regret minimization, under which we propose algorithms that ask an asymptotically optimal number of questions in 2-dimensional spaces and algorithms with provable performance guarantees in d-dimensional spaces ($d \geq 2$) where each dimension corresponds to a description of a tuple. Experiments on real and synthetic datasets showed that our algorithms outperform the existing one by locating the favorite tuple and guaranteeing a small regret ratiowith much fewer questions.

Extracting interesting tuples from a large database is an important problem in multi-criteria decision making. Two representative queries were proposed in the literature: top- k queries and skyline queries. A top- k query requires users to specify their utility functions beforehand and then returns k tuples to the users. A skyline query does not require any utility function from users but it puts no control on the number of tuples returned to users. Recently, a k-regret query was proposed and received attention from the community because it does not require any utility function from users and the output size is controllable, and thus it avoids those deficiencies of top- k queries and skyline queries. Specifically, it returns k tuples that minimize a criterion called the maximum regret ratio .

In many commercial campaigns, we observe that there exists a tradeoff between the number of customers satisfied by the company and the profit gained. Merely satisfying as many customers as possible or maximizing the profit is not desirable. To this end, in this article, we propose a new problem called k - Satisfiability Assignment for Maximizing the Profit ( k -SAMP), where k is a user parameter and a non-negative integer. Given a set P of products and a set O of customers, k -SAMP is to find an assignment between P and O such that at least k customers are satisfied in the assignment and the profit incurred by this assignment is maximized. Although we find that this problem is closely related to two classic computer science problems, namely maximum weight matching and maximum matching, the techniques developed for these classic problems cannot be adapted to our k -SAMP problem. In this work, we design a novel algorithm called Adjust for the k -SAMP problem. Given an assignment A , Adjust iteratively increases the profit of A by adjusting some appropriate matches in A while keeping at least k customers satisfied in A . We prove that Adjust returns a global optimum. Extensive experiments were conducted that verified the efficiency of Adjust .

With the proliferation of spatial-textual data such as location-based services and geo-tagged websites, spatial keyword queries are ubiquitous in real life. One example of spatial-keyword query is the so-called collective spatial keyword query (CoSKQ) which is to find for a given query consisting a query location and several query keywords a set of objects which covers the query keywords collectively and has the smallest costwrt the query location. In the literature, many different functions were proposed for defining the cost and correspondingly, many different approaches were developed for the CoSKQ problem. In this paper, we study the CoSKQ problem systematically by proposing a unified cost function and a unified approach for the CoSKQ problem (with the unified cost function). The unified cost function includes all existing cost functions as special cases and the unified approach solves the CoSKQ problem with the unified cost function in a unified way. Experiments were conducted on both real and synthetic datasets which verified our proposed approach.

We study the k-regret minimizing query (k-RMS), which is a useful operator for supporting multi-criteria decision-making. Given two integers k and r, a k-RMS returns r tuples from the database which minimize the k-regret ratio, defined as one minus the worst ratio between the k-th maximum utility score among all tuples in the database and the maximum utility score of the r tuples returned. A solution set contains only r tuples, enjoying the benefits of both top-k queries and skyline queries. Proposed in 2012, the query has been studied extensively in recent years. In this paper, we advance the theory and the practice of k-RMS in the following aspects. First, we develop efficient algorithms for k-RMS (and its decision version) when the dimensionality is 2. The running time of our algorithms outperforms those of previous ones. Second, we show that k-RMS is NP-hard even when the dimensionality is 3. This provides a complete characterization of the complexity of k-RMS, and answers an open question in previous studies. In addition, we present approximation algorithms for the problem when the dimensionality is 3 or larger.

Due to the advance of the geo-spatial positioning and the computer graphics technology, digital terrain data become more and more popular nowadays. Query processing on terrain data has attracted considerable attention from both the academic community and the industry community. One fundamental and important query is the shortest distance query and many other applications such as proximity queries (including nearest neighbor queries and range queries), 3D object feature vector construction and 3D object data mining are built based on the result of the shortest distance query. In this paper, we study the shortest distance query which is to find the shortest distance between a point-of-interest and another point-of-interest on the surface of the terrain due to a variety of applications. As observed by existing studies, computing the exact shortest distance is very expensive. Some existing studies proposed ε-approximate distance oracles where ε is a non-negative real number and is an error parameter. However, the best-known algorithm has a large oracle construction time, a large oracle size and a large distance query time. Motivated by this, we propose a novel ε-approximate distance oracle called the Space Efficient distance oracle (SE) which has a small oracle construction time, a small oracle size and a small distance query time due to its compactness storing concise information about pairwise distances between any two points-of-interest. Our experimental results show that the oracle construction time, the oracle size and the distance query time of SE are up to two orders of magnitude, up to 3 orders of magnitude and up to 5 orders of magnitude faster than the best-known algorithm.

Similarity among entities in graphs plays a key role in data analysis and mining. SimRank is a widely used and popular measurement to evaluate the similarity among the vertices. In real-life applications, graphs do not only grow in size, requiring fast and precise SimRank computation for large graphs, but also change and evolve continuously over time, demanding an efficient maintenance process to handle dynamic updates. In this paper, we propose a random walk based indexing scheme to compute SimRank efficiently and accurately over large dynamic graphs. We show that our algorithm outperforms the state-of-the-art static and dynamic SimRank algorithms.

We propose "average regret ratio" as a metric to measure users' satisfaction after a user sees k selected points of a database, instead of all of the points in the database. We introduce the average regret ratio as another means of multi-criteria decision making. Unlike the original k-regret operator that uses the maximum regret ratio, the average regret ratio takes into account the satisfaction of a general user. While assuming the existence of some utility functions for the users, in contrast to the top-k query, it does not require a user to input his or her utility function but instead depends on the probability distribution of the utility functions. We prove that the average regret ratio is a supermodular function and provide a polynomial-time approximation algorithm to find the average regret ratio minimizing set for a database.

Graph keyword search is the process of extracting small subgraphs that contain a set of query keywords from a graph. This problem is challenging because there are many constraints, including distance constraint, keyword constraint, search time constraint, index size constraint, and memory constraint, while the size of data is inflating at a very high speed nowadays. Existing greedy algorithms guarantee good performance by sacrificing the accuracy to generate approximate answers, and exact algorithms promise exact answers but require a high memory consumption for loading indices and advanced knowledge about the maximum distance constraint. For big data applications, existing techniques are inefficient and impractical due to huge memory consumption and varied distance constraint. We propose a new keyword search algorithm that finds exact answers with low memory consumption and without advanced knowledge of maximum distance constraint. This algorithm builds a compact index structure offline based on a recent labeling index for shortest path queries. At the query time, it finds the answer efficiently by examining a small portion of the index related to a query.

Non-independent reasoning (NIR) allows the information about one record in the data to be learnt from the information of other records in the data. Most posterior/prior based privacy criteria consider NIR as a privacy violation and require to smooth the distribution of published data to avoid sensitive NIR. The drawback of this approach is that it limits the utility of learning statistical relationships. The differential privacy criterion considers NIR as a non-privacy violation, therefore, enables learning statistical relationships, but at the cost of potential disclosures through NIR. A question is whether it is possible to (1) allow learning statistical relationships, yet (2) prevent sensitive NIR about an individual. We present a data perturbation and sampling method to achieve both (1) and (2). The enabling mechanism is a new privacy criterion that distinguishes the two types of NIR in (1) and (2) with the help of the law of large numbers. In particular, the record sampling effectively prevents the sensitive disclosure in (2) while having less effect on the statistical learning in (1).

Top-k nearest keyword search has been of interest because of applications ranging from road network location search by keyword to search of information on an RDF repository. We consider the evaluation of a query with a given vertex and a keyword, and the problem is to find a set of $k$ nearest vertices that contain the keyword. The known algorithms for handling this problem only give approximate answers. In this paper, we propose algorithms for top-k nearest keyword search that provide exact solutions and which handle networks of very large sizes. We have also verified the performance of our solutions compared with the best-known approximation algorithms with experiments on real datasets.

Multi-criteria decision making problem has been well studied for many years. One popular query for multi-criteria decision making is top-k queries which require each user to specify an exact utility function. In many cases, the utility function of a user is probabilistic and finding the distribution on the utility functions has been widely explored in the machine learning areas, such as user's recommender systems, Bayesian learning models and user's preference elicitation, for improving user's experience. Motivated by this, we propose a new type of queries called k-hit queries, which has not been studied before. Given a set D of tuples in the database, the distribution θ on utility functions and a positive integer k, we would like to select a set of k tuples from D in order to maximize the probability that at least one of tuples in the selection set is the favorite of a user. All applications for top-k queries can naturally be used in k-hit queries. In this paper, we present various interesting properties of k-hit queries. Besides, based on these properties, we propose a novel algorithm called k-hit_Alg for k-hit queries. Finally, we conducted comprehensive experiments to show that the performance of our proposed method, k hit_Alg, is superior compared with other existing algorithms which were originally used to answer other existing queries.

The increasing availability of massive and accurate laser data enables the processing of spatial queries on terrains. As shortest-path computation, an integral element of query processing, is inherently expensive on terrains, a key approach to enabling efficient query processing is to reduce the need for exact shortest-path computation in query processing. We develop new lower and upper bounds on terrain shortest distances that are provably tighter than any existing bounds. Unlike existing bounds, the new bounds do not rely on the quality of the triangulation. We show how use of the new bounds speeds up query processing by reducing the need for exact distance computations. Speedups of of nearly an order of magnitude are demonstrated empirically for well-known spatial queries.

In this article, we study an optimal location query based on a road network. Specifically, given a road network containing clients and servers, an optimal location query finds a location on the road network such that when a new server is set up at this location, a certain cost function computed based on the clients and servers (including the new server) is optimized. Two types of cost functions, namely, MinMax and MaxSum, have been used for this query. The optimal location query problem with MinMax as the cost function is called the MinMax query, which finds a location for setting up a new server such that the maximum cost of a client being served by his/her closest server is minimized. The optimal location query problem with MaxSum as the cost function is called the MaxSum query, which finds a location for setting up a new server such that the sum of the weights of clients attracted by the new server is maximized. The MinMax query and the MaxSum query correspond to two types of optimal location query with the objectives defined from the clients' perspective and from the new server's perspective, respectively. Unfortunately, the existing solutions for the optimal query problem are not efficient. In this article, we propose an efficient algorithm, namely, MinMax-Alg ( MaxSum-Alg ), for the MinMax (MaxSum) query, which is based on a novel idea of nearest location component . We also discuss two extensions of the optimal location query, namely, the optimal multiple-location query and the optimal location query on a 3D road network. Extensive experiments were conducted, showing that our algorithms are faster than the state of the art by at least an order of magnitude on large real benchmark datasets. For example, in our largest real datasets, the state of the art ran for more than 10 (12) hours while our algorithm ran within 3 (2) minutes only for the MinMax (MaxSum) query, that is, our algorithm ran at least 200 (600) times faster than the state of the art.

Returning tuples that users may be interested in is one of the most important goals for multi-criteria decision making. Top-k queries and skyline queries are two representative queries. A top-k query has its merit of returning a limited number of tuples to users but requires users to give their exact utility functions. A skyline query has its merit that users do not need to give their exact utility functions but has no control over the number of tuples to be returned. In this paper, we study a k-regret query, a recently proposed query, which integrates the merits of the two representative queries. We first identify some interesting geometry properties for the k-regret query. Based on these properties, we define a set of candidate points called happy points for the k-regret query, which has not been studied in the literature. This result is very fundamental and beneficial to not only all existing algorithms but also all new algorithms to be developed for the k-regret query. Since it is found that the number of happy points is very small, the efficiency of all existing algorithms can be improved significantly. Furthermore, based on other geometry properties, we propose two efficient algorithms each of which performs more efficiently than the best-known fastest algorithm. Our experimental results show that our proposed algorithms run faster than the best-known method on both synthetic and real datasets. In particular, in our experiments on real datasets, the best-known method took more than 3 hours to answer a k-regret query but one of our proposed methods took about a few minutes and the other took within a second.

Trajectory data is becoming more and more popular nowadays and extensive studies have been conducted on trajectory data. One important research direction about trajectory data is the anomaly detection which is to find all anomalies based on trajectory patterns in a road network. In this paper, we introduce a road segment-based anomaly detection problem, which is to detect the abnormal road segments each of which has its “real” traffic deviating from its “expected” traffic and to infer the major causes of anomalies on the road network. First, a deviation-based method is proposed to quantify the anomaly of reach road segment. Second, based on the observation that one anomaly from a road segment can trigger other anomalies from the road segments nearby, a diffusion-based method based on a heat diffusion model is proposed to infer the major causes of anomalies on the whole road network. To validate our methods, we conduct intensive experiments on a large real-world GPS dataset of about 23,000 taxis in Shenzhen, China to demonstrate the performance of our algorithms.

In the literature of supervised learning, most existing studies assume that the labels provided by the labelers are deterministic, which may introduce noise easily in many real-world applications. In many applications like crowdsourcing, however, many labelers may simultaneously label the same group of instances and thus the label of each instance is associated with a probability. Motivated by this observation, we propose a new framework where each label is enriched with a probability. In this paper, we study an interactive sampling strategy, namely, selective sampling, in which each selected instance is labeled with a probability. Specifically, we flip a coin every time when we read a new instance and decide whether it should be labeled according to the flipping result. We prove that in our setting the label complexity can be reduced dramatically. Finally, we conducted comprehensive experiments in order to verify the effectiveness of our proposed labeling framework.

Classification is a fundamental topic in the literature of data mining and all recent hot topics like active learning and transfer learning all rely on the concept of classification. Probabilistic information becomes more prevalent nowadays and can be found easily in many applications like crowdsourcing and pattern recognition. In this paper, we focus on a dataset which contains probabilistic information for classification. Based on this probabilistic dataset, we propose a classifier and give a theoretical bound linking the error rate of our classifier and the number of instances needed for training. Interestingly, we find that our theoretical bound is asymptotically at least no worse than the previously best-known bounds developed based on the traditional dataset. Furthermore, our classifier guarantees a fast rate of convergence compared with traditional classifiers. Experimental results show that our proposed algorithm has a higher accuracy than the traditional algorithm. We believe that this work is influential since it opens a new topic on the probabilistic dataset, allowing researchers to study all topics related to classification like active learning and transfer learning under this new probabilistic setting.

In this paper, we study the optimal location query problem based on road networks. Specifically, we have a road network on which some clients and servers are located. Each client finds the server that is closest to her for service and her cost of getting served is equal to the (network) distance between the client and the server serving her multiplied by her weight or importance. The optimal location query problem is to find a location for setting up a new server such that the maximum cost of clients being served by the servers (including the new server) is minimized. This problem has been studied before, but the state-of-the-art is still not efficient enough. In this paper, we propose an efficient algorithm for the optimal location query problem, which is based on a novel idea of \emph{nearest location component}. We also discuss three extensions of the optimal location query problem, namely the optimal multiple-location query problem, the optimal location query problem on 3D road networks, and the optimal location query problem with another objective. Extensive experiments were conducted which showed that our algorithms are faster than the state-of-the-art by at least an order of magnitude on large real benchmark datasets. For example, on our largest real datasets, the state-of-the-art ran for more than 10 hours but our algorithm ran within 3 minutes only (i.e., >200 times faster).

Hyperspheres are commonly used for representing uncertain objects (in uncertain databases) and for indexing spatial objects (in spatial databases). An interesting operator on hyperspheres called dominance is to decide for two given hyperspheres whether one dominates (or is closer than) the other wrt a given query hypersphere. In this paper, we propose an approach called Hyperbola which is optimal in the sense that it gives neither false positives nor false negatives and runs in linear time wrt the dimensionality. To the best of our knowledge, Hyperbola is the first optimal approach for the dominance problem on hyperespheres with any dimensionality. We also study an application of the dominance problem which relies on the dominance operator as the core component. We conducted extensive experiments on both real and synthetic datasets which verified our approaches.

We study the problem of point-to-point distance querying for massive scale-free graphs, which is important for numerous applications. Given a directed or undirected graph, we propose to build an index for answering such queries based on a novel hop-doubling labeling technique. We derive bounds on the index size, the computation costs and I/O costs based on the properties of unweighted scale-free graphs. We show that our method is much more efficient and effective compared to the state-of-the-art techniques, in terms of both querying time and indexing costs. Our empirical study shows that our method can handle graphs that are orders of magnitude larger than existing methods.

Trajectory data is central to many applications with moving objects. Raw trajectory data is usually very large, and so is simplified before it is stored and processed. Many trajectory simplification notions have been proposed, and among them, the direction-preserving trajectory simplification (DPTS) which aims at protecting the direction information has been shown to perform quite well. However, existing studies on DPTS require users to specify an error tolerance which users might not know how to set properly in some cases (e.g., the error tolerance could only be known at some future time and simply setting one error tolerance does not meet the needs since the simplified trajectories would usually be used in many different applications which accept different error tolerances). In these cases, a better solution is to minimize the error while achieving a pre-defined simplification size. For this purpose, in this paper, we define a problem called Min-Error and develop two exact algorithms and one 2-factor approximate algorithm for the problem. Extensive experiments on real datasets verified our algorithms.

Terrain data is becoming increasingly popular both in industry and in academia. Many tools have been developed for visualizing terrain data. However, we find that (1) they usually accept very few data formats of terrain data only; (2) they do not support terrain simplification well which, as will be shown, is used heavily for query processing in spatial databases; and (3) they do not provide the surface distance operator which is fundamental for many applications based on terrain data. Motivated by this, we developed a tool called Terrain-Toolkit for terrain data which accepts a comprehensive set of data formats, supports terrain simplification and provides the surface distance operator.

Dominance analysis is important in many multi-criteria decision making applications. Most previous works assume that the price of a service is given and study how to select "best" services according to multiple given attributes including attribute Price. In this paper, we propose an interesting data mining problem, finding competitive price, which has not been studied before. Given a set of existing services, for a new service, we want to find a price of the new service such that the new service is not worse than any existing services. The price found refers to a competitive price. We propose a spatial approach which makes use of some spatial properties and thus runs efficiently. Finally, we conducted experiments to show the efficiency of our proposed method.

There are a bulk of studies on proposing algorithms for composing the melody of a song automatically with algorithms, which is known as algorithmic composition. To the best of our knowledge, none of them took the lyric into consideration for melody composition. However, according to some recent studies, within a song, there usually exists a certain extent of correlation between its melody and its lyric. In this demonstration, we propose to utilize this type of correlation information for melody composition. Based on this idea, we design a new melody composition algorithm and develop a melody composer called T-Music which employs this composition algorithm.

Peer review has become the most common practice for judging papers submitted to a conference for decades. An extremely important task involved in peer review is to assign submitted papers to reviewers with appropriate expertise which is referred to as paper-reviewer assignment. In this paper, we study the paper-reviewer assignment problem from both the goodness aspect and the fairness aspect. For the goodness aspect, we propose to maximize the topic coverage of the paper-reviewer assignment. This objective is new and the problem based on this objective is shown to be NP-hard. To solve this problem efficiently, we design an approximate algorithm which gives a 1/3-approximation. For the fairness aspect, we perform a detailed study on conflict-of-interest (COI) types and discuss several issues related to using COI, which, we hope, can raise some open discussions among researchers on the COI study. Finally, we conducted experiments on real datasets which verified the effectiveness of our algorithm and also revealed some interesting results of COI.

Recently, spatial keyword queries become a hot topic in the literature. One example of these queries is the collective spatial keyword query (CoSKQ) which is to find a set of objects in the database such that it covers a set of given keywords collectively and has the smallest cost. Unfortunately, existing exact algorithms have severe scalability problems and existing approximate algorithms, though scalable, cannot guarantee near-to-optimal solutions. In this paper, we study the CoSKQ problem and address the above issues.

Bichromatic reverse nearest neighbor (BRNN) queries have been studied extensively in the literature of spatial databases. Given a set P of service-providers and a set O of customers, a BRNN query is to find which customers in O are "interested" in a given service-provider in P. Recently, it has been found that this kind of queries lacks the consideration of the capacities of service-providers and the demands of customers. In order to address this issue, some spatial matching problems have been proposed, which, however, cannot be used for some real-life applications like emergency facility allocation where the maximum matching cost (or distance) should be minimized. In this paper, we propose a new problem called Spatial Matching for Minimizing Maximum matching distance (SPM-MM). Then, we design two algorithms for SPM-MM, Threshold-Adapt and Swap-Chain. Threshold-Adapt is simple and easy to understand but not scalable to large datasets due to its relatively high time/space complexity. Swap-Chain, which follows a fundamentally different idea from Threshold-Adapt, runs faster than Threshold-Adapt by orders of magnitude and uses significantly less memory. We conducted extensive empirical studies which verified the efficiency and scalability of Swap-Chain.

We study the problem of computing shortest path or distance between two query vertices in a graph, which has numerous important applications. Quite a number of indexes have been proposed to answer such distance queries. However, all of these indexes can only process graphs of size barely up to 1 million vertices, which is rather small in view of many of the fast-growing real-world graphs today such as social networks and Web graphs. We propose an efficient index, which is a novel labeling scheme based on the independent set of a graph. We show that our method can handle graphs of size orders of magnitude larger than existing indexes.

With the increasing availability of terrain data, e.g., from aerial laser scans, the management of such data is attracting increasing attention in both industry and academia. In particular, spatial queries, e.g., k -nearest neighbor and reverse nearest neighbor queries, in Euclidean and spatial network spaces are being extended to terrains. Such queries all rely on an important operation, that of finding shortest surface distances. However, shortest surface distance computation is very time consuming. We propose techniques that enable efficient computation of lower and upper bounds of the shortest surface distance, which enable faster query processing by eliminating expensive distance computations. Empirical studies show that our bounds are much tighter than the best-known bounds in many cases and that they enable speedups of up to 43 times for some well-known spatial queries.

Trajectories of moving objects are collected in many applications. Raw trajectory data is typically very large, and has to be simplified before use. In this paper, we introduce the notion of direction-preserving trajectory simplification, and show both analytically and empirically that it can support a broader range of applications than traditional position-preserving trajectory simplification. We present a polynomial-time algorithm for optimal direction-preserving simplification, and another approximate algorithm with a quality guarantee. Extensive experimental evaluation with real trajectory data shows the benefit of the new techniques.

Sequence analysis is very important in our daily life. Typically, each sequence is associated with an ordered list of elements. For example, in a movie rental application, a customer's movie rental record containing an ordered list of movies is a sequence example. Most studies about sequence analysis focus on subsequence matching which finds all sequences stored in the database such that a given query sequence is a subsequence of each of these sequences. In many applications, elements are associated with properties or attributes. For example, each movie is associated with some attributes like "Director" and "Actors". Unfortunately, to the best of our knowledge, all existing studies about sequence analysis do not consider the attributes of elements. In this paper, we propose two problems. The first problem is: given a query sequence and a set of sequences, considering the attributes of elements, we want to find all sequences which are matched by this query sequence. This problem is called attribute-based subsequence matching (ASM). All existing applications for the traditional subsequence matching problem can also be applied to our new problem provided that we are given the attributes of elements. We propose an efficient algorithm for problem ASM. The key idea to the efficiency of this algorithm is to compress each whole sequence with potentially many associated attributes into just a triplet of numbers. By dealing with these very compressed representations, we greatly speed up the attribute-based subsequence matching. The second problem is to find all frequent attribute-based subsequence. We also adapt an existing efficient algorithm for this second problem to show we can use the algorithm developed for the first problem. Empirical studies show that our algorithms are scalable in large datasets. In particular, our algorithms run at least an order of magnitude faster than a straightforward method in most cases. This work can stimulate a number of existing data mining problems which are fundamentally based on subsequence matching such as sequence classification, frequent sequence mining, motif detection and sequence matching in bioinformatics.

The importance of dominance and skyline analysis has been well recognized in multicriteria decision-making applications. Most previous studies focus on how to help customers find a set of “best” possible products from a pool of given products. In this paper, we identify an interesting problem, finding top-k preferable products, which has not been studied before. Given a set of products in the existing market, we want to find a set of k “best” possible products such that these new products are not dominated by the products in the existing market. We study two problem instances of finding top-k preferable products. In the first problem instance, we need to set the prices of these products such that the total profit is maximized. We refer such products as top-k profitable products. In the second problem instance, we want to find k products such that these k products can attract the greatest number of customers. We refer these products as top-k products. In both problem instances, a straightforward solution is to enumerate all possible subsets of size k and find the subset which gives the greatest profit (for the first problem instance) or attracts the greatest number of customers (for the second problem instance). However, there are an exponential number of possible subsets. In this paper, we propose solutions to find the top-k profitable products and the top-k popular products efficiently. An extensive performance study using both synthetic and real data sets is reported to verify the effectiveness and efficiency of proposed algorithms.

Given a set S of servers and a set C of clients, an optimal-location query returns a location where a new server can attract the greatest number of clients. Optimal-location queries are important in a lot of real-life applications, such as mobile service planning or resource distribution in an area. Previous studies assume that a client always visits its nearest server, which is too strict to be true in reality. In this paper, we relax this assumption and propose a new model to tackle this problem. We further generalize the problem to finding top-k optimal locations. The main challenge is that, even the fastest approach in existing studies needs to take hours to answer an optimal-location query on a typical real world dataset, which significantly limits the applications of the query. Using our relaxed model, we design an efficient grid-based approximation algorithm called FILM (Fast Influential Location Miner) to the queries, which is orders of magnitude faster than the best-known previous work and the number of clients attracted by a new server in the result location often exceeds 98% of the optimal. The algorithm is extended to finding k influential locations. Extensive experiments are conducted to show the efficiency and effectiveness of FILM on both real and synthetic datasets.

The importance of dominance and skyline analysis has been well recognized in multi-criteria decision making applications. Most previous studies focus on how to help customers find a set of “best” possible products from a pool of given products. In this paper, we identify an interesting problem, finding top-k profitable products, which has not been studied before. Given a set of products in the existing market, we want to find a set of k “best” possible products such that these new products are not dominated by the products in the existing market. In this problem, we need to set the prices of these products such that the total profit is maximized. We refer such products as top-k profitable products. A straightforward solution is to enumerate all possible subsets of size k and find the subset which gives the greatest profit. However, there are an exponential number of possible subsets. In this paper, we propose solutions to find the top-k profitable products efficiently. An extensive performance study using both synthetic and real datasets is reported to verify its effectiveness and efficiency.

Viral marketing has attracted considerable concerns in recent years due to its novel idea of leveraging the social network to propagate the awareness of products. Specifically, viral marketing is to first target a limited number of users (seeds) in the social network by providing incentives, and these targeted users would then initiate the process of awareness spread by propagating the information to their friends via their social relationships. Extensive studies have been conducted for maximizing the awareness spread given the number of seeds. However, all of them fail to consider the common scenario of viral marketing where companies hope to use as few seeds as possible yet influencing at least a certain number of users. In this paper, we propose a new problem, called J-MIN-Seed, whose objective is to minimize the number of seeds while at least J users are influenced. J-MIN-Seed, unfortunately, is proved to be NP-hard in this work. In such case, we develop a greedy algorithm that can provide error guarantees for J-MIN-Seed. Furthermore, for the problem setting where J is equal to the number of all users in the social network, denoted by Full-Coverage, we design other efficient algorithms. Extensive experiments were conducted on real datasets to verify our algorithm.

Finding shortest paths is a fundamental operator in spatial databases. Recently, terrain datasets have attracted a lot of attention from both industry and academia. There are some interesting issues to be studied in terrain datasets which cannot be found in a traditional two-dimensional space. In this paper, we study one of the issues called a slope constraint which exists in terrain datasets. In this paper, we propose a problem of finding shortest paths with the slope constraint. Then, we show that this new problem is more general than the traditional problem of finding shortest paths without considering the slope constraint. Since finding shortest paths with the slope constraint is costly, we propose a new framework called surface simplification so that we can compute shortest paths with the slope constraint efficiently. Under this framework, the surface is "simplified" such that the complexity of finding shortest paths on this simplified surface is lower. We conducted experiments to show that the surface simplification is very efficient and effective not only for the new problem with the slope constraint but also the traditional problem without the slope constraint.

Group based anonymization is the most widely studied approach for privacy-preserving data publishing. Privacy models/definitions using group based anonymization includes k -anonymity, l -diversity, and t -closeness, to name a few. The goal of this article is to raise a fundamental issue regarding the privacy exposure of the approaches using group based anonymization. This has been overlooked in the past. The group based anonymization approach by bucketization basically hides each individual record behind a group to preserve data privacy. If not properly anonymized, patterns can actually be derived from the published data and be used by an adversary to breach individual privacy. For example, from the medical records released, if patterns such as that people from certain countries rarely suffer from some disease can be derived, then the information can be used to imply linkage of other people in an anonymized group with this disease with higher likelihood. We call the derived patterns from the published data the foreground knowledge. This is in contrast to the background knowledge that the adversary may obtain from other channels, as studied in some previous work. Finally, our experimental results show such an attack is realistic in the privacy benchmark dataset under the traditional group based anonymization approach.

Abstract — While previous works on privacy-preserving serial data publishing consider the scenario where sensitive values may persist over multiple data releases, we find that no previous work has sufficient protection provided for sensitive values that can change over time, which should be the more common case. In this work, we propose to study the privacy guarantee for such transient sensitive values, which we call the global guarantee. We formally define the problem for achieving this guarantee. We show that the data satisfying the global guarantee also satisfies a privacy guarantee commonly adopted in the privacy literature called the local guarantee. I.

Temporal data are time-critical in that the snapshot at each timestamp must be made available to researchers in a timely fashion. However, due to the limited data, each snapshot likely has a skewed distribution on sensitive values, which renders classical anonymization methods not possible. In this work, we propose the “reposition model” to allow a record to be published within a close proximity of original timestamp. We show that reposition over a small proximity of timestamp is sufficient for reducing the skewness of a snapshot, therefore, minimizing the impact on window queries. We formalize the optimal reposition problem and present a linear-time solution. The contribution of this work is that it enables classical methods on temporal data.

Background knowledge is an important factor in privacy preserving data publishing. Probabilistic distribution-based background knowledge is a powerful kind of background knowledge which is easily accessible to adversaries. However, to the best of our knowledge, there is no existing work that can provide a privacy guarantee under adversary attack with such background knowledge. The difficulty of the problem lies in the high complexity of the probability computation and the non-monotone nature of the privacy condition. The only solution known to us relies on approximate algorithms with no known error bound. In this paper, we propose a new bounding condition that overcomes the difficulties of the problem and gives a privacy guarantee. This condition is based on probability deviations in the anonymized data groups, which is much easier to compute and which is a monotone function on the grouping sizes.

A highly skewed microdata contains some sensitive attribute values that occur far more frequently than others. Such data violates the “eligibility condition” assumed by existing works for limiting the probability of linking an individual to a specific sensitive attribute value. Specifically, if the frequency of some sensitive attribute value is too high, publishing the sensitive attribute alone would lead to linking attacks. In many practical scenarios, however, this eligibility condition is violated. In this paper, we consider how to publish microdata under this case. A natural solution is “minimally” suppressing “dominating” records to restore the eligibility condition. We show that the minimality of suppression may lead to linking attacks. To limit the inference probability, we propose a randomized suppression solution. We show that this approach has the least expected suppression in a large family of randomized solutions, for a given privacy requirement. Experiments show that this solution approaches the lower bound on the suppression required for this problem.

Given a set P of products, a set O of customers, and a product p ε P, a bichromatic reverse skyline query retrieves all the customers in O that do not find any other product in P to be absolutely better than p. More specifically, a customer o ε O is in the reverse skyline of p ε P if and only no other product in P better matches the preference of o on all dimensions.

Existing approaches on privacy-preserving data publishing rely on the assumption that data can be divided into quasi-identifier attributes (QI) and sensitive attribute (SA). This assumption does not hold when an attribute has both sensitive values and identifying values, which is typically the case. In this paper, we study how such attributes would impact the privacy model and data anonymization. We identify a new form of attacks, called "freeform attacks", that occur on such data without explicit QI attributes and SA attributes. We present a framework for modeling identifying/sensitive information at the value level, define a problem to eliminate freeform attacks, and outline an efficient solution.

The importance of dominance and skyline analysis has been well recognized in multi-criteria decision making applications. Most previous works study how to help customers find a set of "best" possible products from a pool of given products. In this paper, we identify an interesting problem, creating competitive products, which has not been studied before. Given a set of products in the existing market, we want to study how to create a set of "best" possible products such that the newly created products are not dominated by the products in the existing market. We refer such products as competitive products. A straightforward solution is to generate a set of all possible products and check for dominance relationships. However, the whole set is quite large. In this paper, we propose a solution to generate a subset of this set effectively. An extensive performance study using both synthetic and real datasets is reported to verify its effectiveness and efficiency.

Bichromatic reverse nearest neighbor (BRNN) has been extensively studied in spatial database literature. In this paper, we study a related problem called MaxBRNN: find an optimal region that maximizes the size of BRNNs. Such a problem has many real life applications, including the problem of finding a new server point that attracts as many customers as possible by proximity. A straightforward approach is to determine the BRNNs for all possible points that are not feasible since there are a large (or infinite) number of possible points. To the best of our knowledge, the fastest known method has exponential time complexity on the data size. Based on some interesting properties of the problem, we come up with an efficient algorithm called MaxOverlap. Extensive experiments are conducted to show that our algorithm is many times faster than the best-known technique.

The importance of skyline analysis has been well recognized in multi-criteria decision making applications. All of the previous studies assume a fixed order on the attributes in question. However, in some applications, users may be interested in skylines with respect to various total or partial orders on nominal attributes. In this paper, we identify and tackle the problem of online skyline analysis with dynamic preferences on nominal attributes. We investigate how changes of orders in attributes lead to changes of skylines. We address two novel types of interesting queries: a viewpoint query returns with respect to which orders a point is (or is not) in the skylines and an order-based skyline query retrieves the skyline with respect to a specific order. We develop two methods systematically and report an extensive performance study using both synthetic and real data sets to verify their effectiveness and efficiency.

Data publishing generates much concern over the protection of individual privacy. Recent studies consider cases where the adversary may possess different kinds of knowledge about the data. In this article, we show that knowledge of the mechanism or algorithm of anonymization for data publication can also lead to extra information that assists the adversary and jeopardizes individual privacy. In particular, all known mechanisms try to minimize information loss and such an attempt provides a loophole for attacks. We call such an attack a minimality attack. In this article, we introduce a model called m -confidentiality which deals with minimality attacks, and propose a feasible solution. Our experiments show that minimality attacks are practical concerns on real datasets and that our algorithm can prevent such attacks with very little overhead and information loss.

Previous works about privacy preserving serial data publishing on dynamic databases have relied on unrealistic assumptions of the nature of dynamic databases. In many applications, some sensitive values changes freely while others never change. For example, in medical applications, the disease attribute changes with time when patients recover from one disease and develop another disease. However, patients do not recover from some diseases such as HIV. We call such diseases permanent sensitive values. To the best of our knowledge, none of the existing solutions handle these realistic issues. We propose a novel anonymization approach called HD-composition to solve the above problems. Extensive experiments with real data confirm our theoretical results.

Current skyline evaluation techniques assume a fixed ordering on the attributes. However, dynamic preferences on nominal attributes are more realistic in known applications. In order to generate online response for any such preference issued by a user, one obvious solution is to enumerate all possible preferences and materialize all results of these preferences. However, the pre-processing and storage requirements of a full materialization are typically prohibitive. Instead, we propose a semi-materialization method called the IPO-tree Search which stores partial useful results only. With these partial results, the result of each possible preference can be returned efficiently. We have also conducted experiments to show the efficiency of our proposed algorithm.

Individual privacy will be at risk if a published data set is not properly deidentified. k-anonymity is a major technique to de-identify a data set. Among a number of k-anonymization schemes, local recoding methods are promising for minimizing the distortion of a k-anonymity view. This paper addresses two major issues in local recoding k-anonymization in attribute hierarchical taxonomies. First, we define a proper distance metric to achieve local recoding generalization with small distortion. Second, we propose a means to control the inconsistency of attribute domains in a generalized view by local recoding. We show experimentally that our proposed local recoding method based on the proposed distance metric produces higher quality k-anonymity tables in three quality measures than a global recoding anonymization method, Incognito, and a multidimensional recoding anonymization method, Multi. The proposed inconsistency handling method is able to balance distortion and consistency of a generalized view.

The importance of dominance and skyline analysis has been well recognized in multi-criteria decision making applications. Most previous studies assume a fixed order on the attributes. In practice, different customers may have different preferences on nominal attributes. In this paper, we identify an interesting data mining problem, finding favorable facets, which has not been studied before. Given a set of points in a multidimensional space, for a specific target point p we want to discover with respect to which combinations of orders (e.g., customer preferences) on the nominal attributes p is not dominated by any other points. Such combinations are called the favorable facets of p.

Individual privacy will be at risk if a published data set is not properly de-identified. k -anonymity is a major technique to de-identify a data set. A more general view of k -anonymity is clustering with a constraint of the minimum number of objects in every cluster. Most existing approaches to achieving k -anonymity by clustering are for numerical (or ordinal) attributes. In this paper, we study achieving k -anonymity by clustering in attribute hierarchical structures. We define generalisation distances between tuples to characterise distortions by generalisations and discuss the properties of the distances. We conclude that the generalisation distance is a metric distance. We propose an efficient clustering-based algorithm for k -anonymisation. We experimentally show that the proposed method is more scalable and causes significantly less distortions than an optimal global recoding k -anonymity method. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Privacy preservation is an important issue in the release of data for mining purposes. The k-anonymity model has been introduced for protecting individual identification. Recent studies show that a more sophisticated model is necessary to protect the association of individuals to sensitive information. In this paper, we propose an (α, k)-anonymity model to protect both identifications and relationships to sensitive information in data. We discuss the properties of (α, k)-anonymity model. We prove that the optimal (α, k)-anonymity problem is NP-hard. We first presentan optimal global-recoding method for the (α, k)-anonymity problem. Next we propose a local-recoding algorithm which is more scalable and result in less data distortion. The effectiveness and efficiency are shown by experiments. We also describe how the model can be extended to more general case.

Privacy consideration has much significance in the application of data mining. It is very important that the privacy of individual parties will not be exposed when data mining techniques are applied to a large collection of data about the parties. In many scenarios such as data warehousing or data integration, data from the different parties form a many-to-many schema. This paper addresses the problem of privacy-preserving frequent pattern mining in such a schema across two dimension sites. We assume that sites are not trusted and they are semi-honest. Our method is based on the concept of semi-join and does not involve data encryption which is used in most previous work. Experiments are conducted to study the efficiency of the proposed models. 1

Frequent pattern discovery in data streams can be very useful in different applications. In time critical applications, a sliding window model is needed to discount stale data. In this paper, we adopt this model to mine the K most interesting itemsets, or to estimate the K most frequent itemsets of different sizes in a data stream. In our method, the sliding window is partitioned into buckets. We maintain the statistics of the frequency counts of the itemsets for the transactions in each bucket. We prove that our algorithm guarantees no false negatives for any data distributions. We also show that the number of false positives returned is typically small according to Zipfian Distribution. Our experiments on synthetic data show that the memory used by our method is tens of times smaller than that of a naive approach, and the false positives are negligible.

Recent research suggests that clustering for high-dimensional data should involve searching for "hidden" subspaces with lower dimensionalities, in which patterns can be observed when data objects are projected onto the subspaces. Discovering such interattribute correlations and location of the corresponding clusters is known as the projective clustering problem. We propose an efficient projective clustering technique by histogram construction (EPCH). The histograms help to generate "signatures", where a signature corresponds to some region in some subspace, and signatures with a large number of data objects are identified as the regions for subspace clusters. Hence, projected clusters and their corresponding subspaces can be uncovered. Compared to the best previous methods to our knowledge, this approach is more flexible in that less prior knowledge on the data set is required, and it is also much more efficient. Our experiments compare behaviors and performances of this approach and other projective clustering algorithms with different data characteristics. The results show that our technique is scalable to very large databases, and it is able to return accurate clustering results.

In the literature of data mining, many different algorithms for association rule mining have been proposed. However, there is relatively little study on how association rules can aid in more specific targets. One of the applications for association rules - maximal-profit item selection with cross-selling effect (MPIS) problem - is investigated. The problem is about selecting a subset of items, which can give the maximal profit with the consideration of cross-selling. We prove that a simple version of this problem is NP-hard. We propose a new approach to the problem with the consideration of the loss rule - a kind of association rule to model the cross-selling effect. We show that the problem can be transformed to a quadratic programming problem. In case quadratic programming is not applicable, we also propose a heuristic approach. Experiments are conducted to show that both of the proposed methods are highly effective and efficient.