Large Language Models (LLMs) have demonstrated remarkable factual accuracy in producing human-like and AI-generated texts across a wide range of natural language tasks, including question answering. Despite these advances, their tendency to hallucinate and produce fabricated, false or incorrect responses is a persistent limitation. This limitation undermines their reliability and remains a critical challenge, especially in areas where high precision and trustworthiness are required. To address this challenge, we investigate whether the features derived from Knowledge Graphs (KGs) align with the accuracy of answers produced by the LLMs. In particular, we focus on entropy-based KG features, which capture diversity and uncertainty within structured knowledge. By analyzing the correlation between the entropy-based KG features and the accuracy of LLM responses, we are able to identify “blind spots” where LLMs are prone to hallucination. This provides insights not only into when an LLM is correct, but also into the conditions under which it fails. We present results across several datasets, including two developed for this study, demonstrating that entropy-based KG features can effectively align with the accuracy of LLM responses. Motivated by these findings, we propose a probing strategy for assessing LLM accuracy by focusing on areas where LLM accuracy is weak. The experimental results confirm that KG features can guide the probing effectively, highlighting the importance of using structured features from KGs in building more reliable and hallucination-free AI based systems.

Sliding-window aggregation is important in analyzing data streams, but it seriously suffers from out-of-order streams, which contain late events. The existing approaches are not efficient because they are dependent on the window size. They ignore the past windows affected by the late records. This paper proposes two solutions: (1) CMiX for computing the current window, and (2) PWiX for updating the past windows. Experiments show that CMiX and PWiX can deal with out-of-order streams significantly better than other approaches.

Abstract In data stream applications, a query is created using a series of operators connected by unidirectional pipelines. Since those operators may be deployed in a shared-nothing distributed environment, it is necessary to have a valid restore point in case an operator fails. This ensures consistency of the states among operators after recovering from failures. Typical fault-tolerant approaches periodically capture global snapshots, encompassing all operator states. In the recovery process, all operators must be reinstated to the most recent global snapshot. This global dependency affects the recovery performance and the required computational costs for recovery. We propose fault-tolerant schemes for stateful stream processing that localizes recovery to a subset of operators. Additionally, we introduce a partial snapshot mechanism to capture the states required for local recovery efficiently. This snapshot records only a subset of operator states instead of global states. Our implemented recovery schemes in Apache Flink show improved recovery times by up to more than 50 percent.

Stream processing enables real-time data analysis. Recent stream processing engines (SPEs) execute stream processing in a distributed manner for real-time analysis of massive amounts of data produced by IoT devices and sensors. It has been widely adopted in various applications that support critical decision making. To explain the results of stream processing, ensuring provenance is indispensable. Provenance clarifies the relationship between input data and output data in the processing. With provenance, we can understand what input data contributed to the output. Existing frameworks for providing provenance for stream processing generate provenance or additional information to construct provenance at runtime. However, these approaches impose substantial overhead in ordinary stream processing. In this paper, we propose a new framework, named LPStream, for fine-grained lazy provenance. LPStream is the first framework to support lazy provenance for stream processing. In the ordinary execution mode, LPStream executes stream processing with checkpointing but without provenance generation. If provenance is necessary for some target output tuples, it replays the processing from an appropriate checkpoint and generates the provenance for the target tuple. We explain the design and implementation of LPStream and evaluate its performance by comparing LPStream with stream processing without provenance and with eager provenance. The experimental results demonstrate the effectiveness of our proposal.

As an factor influencing data quality, out-of-distribution (OOD) data detection plays a critical role in AI quality assurance. This paper presents an advanced OOD detection method based on Granular Computing (GrC) and dictionary learning, specifically designed for detecting textual OOD in natural language processing (NLP) systems. First, informative data structure descriptors (information granules) are generated through GrC, which are aimed to reduce the computation overhead in big data analysis. Next, granular dictionary is constructed from these granules and used to represent original data through dictionary learning and data reconstruction. Finally, OOD detection is formalized by analyzing differences between original and reconstructed data. Finally, the proposed method formulate OOD detection via the difference between original and reconstructed data. Experiments conducted on a sentiment analysis system based on a large language model (LLM) and three OOD datasets are implemented. The constructed granular dictionary is firstly demonstrated to have good representation ability supporting effective OOD detection. Furthermore, the proposed method’s effectiveness, efficiency and scalability in textual OOD detection are validated through comprehensive comparative analysis.

Sliding-window aggregation is one of the core operations in processing and analyzing data streams, but it seriously suffers from the unordered events or elements from data streams. Unordered streams or out-of-order data streams contain events whose order based on their timestamps (called event time) is different from the order based on their arriving times to the system (called ingestion time). Out-of-order data streams typically occur in a distributed environment due to many factors, such as network disruptions and delays. Out-of-order data streams drastically make the processing speed slower and existing works, that can handle out-of-order streams, do not address this problem well and can be further improved. The time complexities of existing approaches are not efficient because they are dependent on$n$, which is the number of slides in the window. In addition, they ignore the past windows affected by the late-arrival records. In many applications, updating and reporting the results of the past windows affected by the late-arrival records in real time is strongly needed. This paper proposes two solutions: (1) A Maximum-allowed lateness-based IndeXing algorithm with a Constant time complexity (CMiX) for computing the current window, and (2) A Past Window Indexing algorithm (PWiX) for efficient updating the past windows. Experimental results show that CMiX and PWiX can deal with out-of-order data streams significantly better than other existing approaches. CMiX is about 3.21 times faster than the state-of-the-art approach by significantly using less memory. It is important to emphasize that all approaches mentioned in the paper have the following limitations: (1) Aggregation can be both distributive and algebraic, which must be commutative due to the out-of-order of data streams, and (2) The window and slide sizes are assumed to be fixed, and if they are changed, the indices must be reconstructed.

Predicting missing attribute values in data is extremely important in improving the accuracy in many applications. Existing algorithms ignore the difference between the records used for learning and predicting. The accuracy is not good enough and can be further improved. This paper proposes two solutions: (1) Maximization-based approach (MP) and (2) Distance-ratio-based approach (DP). MP and DP ensure that the incomplete records with the missed values are similar to the records used to learn the parameters as much as possible. MP and DP learn all possible parameters not only from the k nearest neighboring set (k-NN) but from the k-Sets, which are all possible combinations of k complete records. The parameters learnt from the records that are most similar to the repaired candidates of the incomplete records are chosen. Experimentally, MP and DP significantly outperform the existing approaches.

In the rapidly evolving landscape of cybersecurity, the accurate identification and classification of cybersecurity-related entities within textual data have gained paramount importance. This paper presents a novel Cybersecurity Entity Recognition (CSER) model that addresses the distinct challenges posed by the cybersecurity domain. Unlike conventional Named Entity Recognition (NER) methods, the cybersecurity context introduces domain-specific features, such as specialized patterns, keywords, and linguistic structures. Moreover, the presence of out-of-vocabulary words and domain-specific symbols further complicates entity recognition. To tackle these challenges, our CSER model integrates contextual, semantic, and morphological features, leveraging recurrent neural networks, convolutional neural networks, and conditional random fields. We investigate various embeddings, model architectures, and configurations, analyzing their influence on benchmark performance metrics. The outcomes of our experiments demonstrate a consistent superiority of our proposed CSER models over existing ones in terms of diverse performance metrics. This underscores the efficacy of our models in precisely recognizing cybersecurity-related entities. This research contributes to the advancement of entity recognition in the cybersecurity domain, shedding light on the pivotal role of domain-specific features and sophisticated architectures in enhancing accuracy and reliability.

In this paper, we address the problem of mapping identifiers in non-RDF data to URIs. Virtual knowledge graphs (VKGs), where non-RDF data, such as relational databases, CSV files, etc., are published as RDF data, allowing users to access them using a standard query language (SPARQL), has been gaining much attention to integrating heterogeneous data. There have been several VKG systems, but there has been a problem of assigning an appropriate URI to an entity included in a record, and existing systems only support simple methods to generate a URI by adding a URI prefix to the ID value in a record. However, in practice, more complex mappings are needed to meet the demands of real applications. To address this problem, we proposed to extend the relation-to-RDF mapping rules where users are allowed to specify how entities in relations are mapped to URIs in terms of a user-defined URI function. More precisely, we integrate this method into our relation-to-RDF mapping framework. We conduct a set of experiments to assess the feasibility of the proposed method.

Stream processing is used in various fields. In the field of big data, stream aggregation is a popular processing technique, but it suffers serious setbacks when the order of events (e.g., stream elements) occurring is different from the order of events arriving to the systems. Such data streams are called "non-FIFO steams". This phenomenon usually occurs in a distributed environment due to many factors, such as network disruptions, delays, etc. Many analyzing scenarios require efficient processing of such non-FIFO streams to meet various data processing requirements. This paper proposes an efficient scalable checkpoint-based bidirectional indexing approach, called CPiX , for faster real-time analysis over non-FIFO streams. CPiX maintains the partial aggregation results in an on-demand manner. CPiX needs less time and space than the state-of-the-art approach. Extensive experiments confirm that CPiX can deal with out-of-order streams very efficiently and is, on average, about 3.8 times faster than the state-of-the-art approach while consuming less memory. CPiX and the existing approaches support the distributive and algebraic aggregation functions, such as min, average, standard deviation, etc. Holistic aggregation is beyond the scope.

Entity Matching (EM) involves identifying different data representations referring to the same entity from multiple data sources and is typically formulated as a binary classification problem. It is a challenging problem in data integration due to the heterogeneity of data representations. State-of-the-art solutions have adopted NLP techniques based on pre-trained language models (PrLMs) via the fine-tuning paradigm, however, sequential fine-tuning of overparameterized PrLMs can lead to catastrophic forgetting, especially in low-resource scenarios. In this study, we propose a parameter-efficient paradigm for fine-tuning PrLMs based on adapters, small neural networks encapsulated between layers of a PrLM, by optimizing only the adapter and classifier weights while the PrLMs parameters are frozen. Adapter-based methods have been successfully applied to multilingual speech problems achieving promising results, however, the effectiveness of these methods when applied to EM is not yet well understood, particularly for generalized EM with heterogeneous data. Furthermore, we explore using (i) pre-trained adapters and (ii) invertible adapters to capture token-level language representations and demonstrate their benefits for transfer learning on the generalized EM benchmark. Our results show that our solution achieves comparable or superior performance to full-scale PrLM fine-tuning and prompt-tuning baselines while utilizing a significantly smaller computational footprint of the PrLM parameters.

Abstract Data points situated near a cluster boundary are called boundary points and they can represent useful information about the process generating this data. The existing methods of boundary points detection cannot differentiate boundary points from outliers as they are affected by the presence of outliers as well as by the size and density of clusters in the dataset. Also, they require tuning of one or more parameters and prior knowledge of the number of outliers in the dataset for tuning. In this research, a boundary points detection method called BPF is proposed which can effectively differentiate boundary points from outliers and core points. BPF combines the well-known outlier detection method Local Outlier Factor (LOF) with Gravity value to calculate the BPF score. Our proposed algorithm StaticBPF can detect the top-m boundary points in the given dataset. Importantly, StaticBPF requires tuning of only one parameter i.e. the number of nearest neighbors $$(k)$$ ( k ) and can employ the same $$k$$ k used by LOF for outlier detection. This paper also extends BPF for streaming data and proposes StreamBPF. StreamBPF employs a grid structure for improving k-nearest neighbor computation and an incremental method of calculating BPF scores of a subset of data points in a sliding window over data streams. In evaluation, the accuracy of StaticBPF and the runtime efficiency of StreamBPF are evaluated on synthetic and real data where they generally performed better than their competitors.

Abstract Data lineage allows information to be traced to its origin in data analysis by showing how the results were derived. Although many methods have been proposed to identify the source data from which the analysis results are derived, analysis is becoming increasingly complex both with regard to the target (e.g., images, videos, and texts) and technology (e.g., AI and machine learning (ML)). In such complex data analysis, simply showing the source data may not ensure traceability. For example, ML analysts building image classifier models often need to know which parts of images are relevant to the output and why the classifier made a decision. Recent studies have intensively investigated interpretability and explainability in the AI/ML domain. Integrating these techniques into the lineage framework will help analysts understand more precisely how the analysis results were derived and how the results are trustful. In this paper, we propose the concept of augmented lineage for this purpose, which is an extended lineage, and an efficient method to derive the augmented lineage for complex data analysis. We express complex data analysis flows using relational operators by combining user-defined functions (UDFs). UDFs can represent invocations of AI/ML models within the data analysis. Then, we present a method taking UDFs into consideration to derive the augmented lineage for arbitrarily chosen tuples among the analysis results. We also experimentally demonstrate the efficiency of the proposed method.

Human and machine interaction is shaping the future of work in a growing body of applications ranging from big data analysis to healthcare. While many employer-centered solutions have emerged in recent years in areas such as crowd-sourcing and big-data analysis, worker-centered approaches have received less attention. In this work, we explore a worker-centered application of Human-Robot Interaction (HRI) for improving human well-being at work through actively sensing and recognising sitting posture habits. We present a platform for data-driven human sitting posture training based on adaptive HRI feedback using a novel robot called Owro. Owro is an owl-shaped emotive desktop robot that connects with the LifeChair, which is an IoT cushion for sitting posture training. The robot displays various emotive feedback to correct poor sitting habits based on the actively recognised human sitting posture. Our results demonstrated that the HRI feedback was effective in improving sitting posture by significantly increasing the percentage of time spent sitting upright from 15.62% to 47.96%, significantly reducing the percentage of amount of time spent slouching from 84.38% to 52.04%, and promoting a healthier back pressure distribution. We also show preliminary survey results on the human perception of the HRI feedback using Owro.

Edge-labeled directed graphs are commonly used to represent various information in different applications, such as social networks, knowledge graphs, etc., and regular path queries (RPQs) allow us to extract pairs of nodes that are reachable from one to another through a labeled path matching with the query pattern represented as a regular expression. It is useful for us to extract complicated or semantically meaningful information from a graph, but it gives rise to a challenge when dealing with large graphs. This is due to the long execution time caused by the explosive growth of intermediate results, but, on the other hand, some applications require fast query executions. To address this problem, we propose an FPGA-based RPQ accelerator. The idea is to exploit FPGA’s parallelism in traversing the target graph and matching the regular path expression in parallel with the pipeline manner. To validate the performance of the proposed method, we conducted a set of experiments. From the results, we observed that the proposed method achieves shorter elapsed times for RPQs against social graphs extracted from the real world, up to three orders of magnitude compared with baseline methods.

Capturing a global snapshot is the most common mechanism in distributed stream processing systems (DSPSs) to create a checkpoint, which can be used to rollback a system to a consistent state after a failure. Recording such a global snapshot requires long chain synchronization of pipelined tasks, adversely affecting the system’s performance. To improve performance, herein a fine-tailored p artial s napshot a lgorithm f or D SPSs is proposed to create separated snapshot regions from a subset of the global checkpointing mechanism. The synchronization space of the snapshotting process can be narrowed into several independently executed sub-snapshots. The frequency of checkpoint intervals varies by region. To minimize the impact on the whole system, regions containing critical tasks have a higher frequency to provide timely restore points, while those with lightweight tasks can be detached to a different region. As a proof of concept, we present RegSnap implemented on top of Apache Flink. In general, our scheme outperforms existing global snapshots in terms of the number of affected tasks, checkpoint duration, and recovery latency.

Stream processing is used in various fields. In the field of big data, stream aggregation is a popular processing technique, but it suffers serious setbacks when the order of events (e.g., stream elements) occurring is different from the order of events arriving to the systems. Such data streams are called “non-FIFO steams”. This phenomenon usually occurs in a distributed environment due to many factors, such as network disruptions, delays, etc. Many analyzing scenarios require efficient processing of such non-FIFO streams to meet various data processing requirements. This paper proposes an efficient scalable checkpoint-based bidirectional indexing approach, called$CPiX$, for faster real-time analysis over non-FIFO streams. CPiX maintains the partial aggregation results in an on-demand manner per checkpoint. CPiX needs less time and space than the state-of-the-art approach. Extensive experiments confirm that CPiX can deal with out-of-order streams very efficiently and is, on average, about 3.8 times faster than the state-of-the-art approach while consuming less memory.

We propose a document search method using knowledge bases (KBs) to explore documents through mentioned entities and their relationship. Documents are one of the most popular media to accumulate and transmit information. People often want to search for necessary documents or explore necessary information across multiple documents. However, it is generally difficult to find the target documents (or information) in particular when the search conditions are complicated, or the conditions are implicitly represented. Thus, users cannot represent their information needs in terms of a query, such as keywords. To address this problem, we exploit knowledge bases (KBs). More precisely, we extract entities mentioned in the documents and link them with the KBs, allowing users to explore the documents through the entities and their relationships. Furthermore, we propose a user-friendly interface to query documents and the relevant information. We experimentally show the proposed system performs better than the search system with a popular full-text search engine in some search tasks.

Question answering (QA) is a fundamental task whose aim is to answer natural language questions. Several embedding based methods that capture semantic similarity between the natural language question and the given answer have been proposed. While these methods achieve good results on the QA task, the high dimensional representations of embeddings comes at a high memory and computational cost. In this work, we propose a scheme where embedding dimensions are reconstructed with a low dimension for solving the question answering task. To be specific, we apply an autoencoder that learns the low dimension properties of the input embedding representations which we then use for measuring similarity between the natural language question and the given answer. We demonstrate through our analysis that with dimensionality reduction, computation time, and memory requirements can be reduced all the while achieving a reasonable performance. Experiments and analysis on insuaranceQA benchmark, show that our proposed method can obtain performance comparable to standard baselines while remaining cost efficient on both time and memory.

This paper proposes a method for multi-query optimization for distributed RDF stream processing systems. Due to the recent advances of IoT (internet of things) and CPS (cyber-physical systems), the edge computing environment becomes rich in computational resources, and the popularity of RDF stream has been increasing due to its high expressivity. To deal with massive RDF streams on the server-side, distributed RDF stream systems have been intensively studied, where many user queries are processed simultaneously using multiple computing nodes. For making query processing more efficient, it is important to cope with the changes of RDF streams in data rate and data distribution. However, the state-of-the-art methods cannot cope with it. To this problem, we propose a cost model for distributed RDF query processing and a dynamic load-balancing method based on the model. The experimental study shows that the proposed method outperforms the existing method even when the data rate and data distribution of RDF stream changes.

Recently, knowledge bases, which represent general knowledge as graphs, have attracted much attention and are used in various fields. As a consequence, the number of knowledge bases have been growing and more than 600,000 datasets exist with different targets in wide spectrum of domains. Thus, it is desirable to make it possible to process queries over different knowledge bases in order for the users to get more integrated information. However, it is still difficult because one needs to cope with different vocabularies. Besides, there is another problem in knowledge bases that new facts tend to be missing, while we can get latest information from text documents, e.g., new sites. In this paper, we propose a method for query processing over multiple knowledge bases and text documents. We apply open information extraction (OIE) over text documents to extract knowledge graphs. To deal with the heterogeneity of vocabulary and schema, we perform distributed queries to multiple knowledge bases using mediator/wrapper approach. Besides, we introduce different strategies to join triples retrieved from different knowledge graphs of different RDF vocabulary. The evaluations show that our approach can improve the coverage of query results by using information from multiple knowledge bases and information from texts.

We propose a relation-oriented faceted search method for knowledge bases (KBs) that allows users to explore relations between entities. KBs store a wide range of knowledge about real-world entities in a structured form as (subject, predicate, object). Although it is possible to query entities and relations among entities by specifying appropriate query expressions of SPARQL or keyword queries, the structure and the vocabulary are complicated and it is hard for non-expert users to get the desired information. For this reason, many researchers have proposed faceted search interfaces for KBs. Nevertheless, existing ones are designed for finding entities and are insufficient for finding relations. To this problem, we propose a novel "relation facet" to find relations between entities. To generate it, we apply clustering over predicates based on the Jaccard similarity. We experimentally show the proposed scheme performs better than existing ones in the task of searching relations.

The most typical approach today to data processing which does not have proven algorithms is to first request humans to provide labels to a small set of data and then develop artificial intelligences (AIs) with the data to perform all the remaining tasks. This development is sometimes crowdsourced through platforms such as Kaggle. The approach, however, is not always effective; if the AI does not meet the quality requirement, we may have to give up the development and all the data items have to be done manually. In order to avoid this all-or-nothing situation, “selective” AI programs that perform tasks which they are confident to do will be effective. This study addresses the problem of designing an incentive structure for crowdsourcing the development of such selective AI programs. This paper shows the results of our real-world experiment with a stair-step incentive structure and the behavior of a worker who developed the AI agent under the incentive. This paper also discusses the limitations of the proposed incentive design.

At times, a composite dataflow needs rerunning in crowdsourcing for various reasons, even when the dataflow may be half complete. Rerunning the dataflow requires more time and incurs monetary costs for the additional work that would need to be completed by crowd workers. This time and cost may be reduced by reusing complete or intermediate results in the previous run. However, at times, such results cannot be used as is (e.g., when the dataflow has been changed), and some additional tasks need to be completed in the old dataflow in order to make them reusable in the new dataflow. The benefit of reusing these results in the previous run may or may not be worth the cost of these additional tasks. This paper gives a general framework for formulating this problem, and proposed a method to estimate the additional costs. The simulation result shows that it is worth devising optimization techniques to identify feasible (namely, cost-effective) plans.

This paper addresses the pipeline processing of sequential workflows in crowdsourcing. Sequential workflows consisting of several subtasks are ubiquitous in crowdsourcing. Our approach is to control the budget distribution to subtasks in order to balance the execution speed of the subtasks and to improve throughput of overall sequential workflows. As we cannot control the price for earlier steps retrospectively in the stepwise batch execution, we explore pipeline processing schemes. Our experimental results show that our pipeline processing scheme with price control achieves significantly higher throughput of sequential workflows.

Data integration is still laboursome task when integrating data are not consistently managed. Such inconsistency can happen easily in real-world situations, such as properties of objects are managed by a central organization and trajectories (or logs) of the objects are recorded by other peripheral organizations. This paper deals with a case of missing ordering information. Integrating property data and log data without ordering information causes duplicated results. In order to solve this problem, this paper proposes a join algorithm, called implicit order join, which discovers implicit ordering information from both property data and log data with help of partial true integrated results from human assistance. With the discovered ordering information, the implicit order join enables to integrate the property data and log data. In order to discover the implicit ordering information, ordering correlation between attribute sequences of property data and log data should be found from comprehensive examination of possible attribute sequence pairs. The potential number of sequence pairs is as high as factorial order of the number of attributes. Therefore, this paper develops a heuristic approach to prune unnecessary examinations based on ordering dependency between attribute sequences. Experimental evaluation in this paper indicates that implicit order join can reduce 77% labouring tasks for integration and the pruning method reduces the number of attribute sequences in orders of magnitude.

Analyzing and feeding back the results on real-world services are important missions in the Big Data era to realize smart city. However, analyzing real-world data is still challenging because of dirtiness of data and large variety of analytic requirements. To cope with the challenges, this paper proposes and develops an analytical toolbox for smart city applications. The analytical toolbox consists of three phases: preparation, analysis, and visualization. The preparation phase deals with the dirtiness of the data by including fundamental data cleansing techniques and data integration techniques. The analysis phase is responsible for ETL (extract, transform and load) process and analytical query processing from the next phase. The visualization phase deals with analytical requirements from users and visualization of analytical results. This paper showcases a real-world use case of the proposed analytical toolbox. The use case is now open in public with help of Fujisawa city, Japan, and this fact indicates that the proposed analytical toolbox is feasible for real-world data analysis and feeding back to citizens.

Graph clustering has recently attracted much attention as a technique to extract community structures from various kinds of graph data. Since available graph data becomes increasingly large, the acceleration of graph clustering is an important issue for handling large-scale graphs. To this end, this paper proposes a fast graph clustering method using GPUs. The proposed method is based on parallelization of label propagation, one of the fastest graph clustering algorithms. Our method has the following three characteristics: (1) efficient parallelization: the algorithm of label propagation is transformed into a sequence of data-parallel primitives; (2) load balance: the method takes into account load balancing by adopting the primitives that make the load among threads and blocks well balanced; and (3) out-of-core processing: we also develop algorithms to efficiently deal with large-scale datasets that do not fit into GPU memory. Moreover, this GPU out-of-core algorithm is extended to simultaneously exploit both CPUs and GPUs for further performance gain. Extensive experiments with real-world and synthetic datasets show that our proposed method outperforms an existing parallel CPU implementation by a factor of up to 14.3 without sacrificing accuracy.

This paper proposes an index-based approach for secure query processing. Due to the rapid proliferation of cloud computing services in diverse applications, such as database as a service (DBaaS), and encrypted database systems (EDBSs) have been gaining much attentions as a way to construct secure databases in DBaaS. However, most of the existing works suffer from poor performance when dealing with large data. Some works proposed index-based query processing schemes, but they have a privacy problem that the order of attribute values may be revealed from the index structure on the server. To this problem, we propose a novel secure index-based query processing scheme where the order of attribute values is not disclosed. In the scheme, the index is maintained in such a way that the structural information regarding the index and the values (or index entries) are maintained separately, and only the latter is stored in a cloud server. When searching, a client uses the structural information (without entries) to traverse the index by cooperating with cloud servers, thereby securing the order among the index entries. We prove that, in our scheme, the order among the index entries would not be disclosed even though the data and the query log are disclosed. In addition, our experimental results show that the proposed scheme significantly outperforms existing state-of-the-art schemes.

Similarity joins are important database operations that can identify pairs of roughly similar records. Due to their many applications (e.g., duplicate elimination and plagiarism detection), a number of algorithms have been created to enhance similarity joins, especially in terms of performance. However, in some cases, the privacy of the data being joined also becomes an important aspect to consider, as leaking sensitive information can result in grave consequences for individuals, enterprises and governmental organizations. We propose a protocol for secure execution of similarity joins that is based on fully homomorphic cryptosystems, which are resistant to a number of attacks and provide flexibility to calculate the similarity between encrypted records. We also consider the adaptation of filter techniques to improve the efficiency of the protocol by reducing the number of record pairs that are compared. In addition, we exploit modern hardware to parallelize the solution and evaluate the performance of the proposal using real datasets.

Searching over Linked Data requires large efforts to users, which include knowing locations of suitable SPARQL endpoints and writing appropriate SPARQL queries in terms of language standards as well as the underlying structure of Linked Data. This situation degrades usability of Linked Data, thus is highly problematic. To resolve this problem, this paper proposes CROISSANT which is a centralized view management system for SPARQL endpoints on the Web. CROISSANT stores pre-defined view definitions, and provides a searchable interface for the views to users. To realize CROISSANT, query processing performance is a big issue, because CROISSANT has to communicate with remote SPARQL endpoints and it takes time to receive results. To cope with this issue, this paper proposes four optimization techniques, namely, view materialization, selection push-down, projection push-down, and view query merge. Experimental evaluation demonstrates these optimizations improve query processing performance.

This paper proposes a scheme of detecting topic evolutions in bibliographic databases. There have been a lot of scientific bibliographies, such as DBLP, CiteSeerX, MEDLINE/PubMed, ADS, arXiv, etc., and hence it has been extremely important to extract useful information from these databases. It should be noticed that, in such databases, citations play crucial role to represent relationships among different publications. To make the best use of citation information as well as textual features for extracting topic evolutions in a bibliographic database, we propose a scheme based on non-negative matrix factorization (NMF). More precisely, we first partition the set of publications in a database according to their publication years, and apply NMF to extract clusters of publications. Notice that we take into account citation information to perform NMF for better clustering. Having obtained sets of publications for each time span, we associate similar clusters in consecutive time spans according to their similarity. Thus we can obtain time evolution of topics and clusters of publications. In the experiments we demonstrate the proposed scheme can successfully extract topic evolutions in real bibliographic databases, CiteSeerX and arXiv.

Analyzing vehicle recorder data of electric vehicles (EVs) reveals how the EVs are used. This paper proposes an OLAP framework to support analyzing trajectories in vehicle recorder data and applies the framework to vehicle recorder data of EVs. The framework consists of ETL (extract, transform, and load) process for trajectory data and visualization for analyzing the data. The ETL process includes hierarchy definitions for spatial and temporal dimensions, as well as aggregation functions for trajectory data. In the subsequent visualization phase, the framework displays results of OLAP operations on map interface. To ensure the applicability of the framework for real applications, we apply the framework to vehicle recorder data of micro-sized EVs (or μEVs), which are smaller EVs with one or two passengers including one driver and can drive at most 100km distance without charging on the way. The application realizes that the framework successfully enables analyses on the trajectory data for real analytic requirements.

Explosive increase of real-time data sources, so-called "data streams" (or just "steams") and increasing demands for real-time analysis over streams give rise to realtime analysis over streams. However, developing tailor-made systems for such applications is not always desirable due to high developing costs and long developing periods. To cope with this problem, this paper proposes a novel architecture for online analytical processing (OLAP) over streams exploiting off-the-shelf stream processing engine (SPE) combined with OLAP engine. It allows users to perform OLAP analysis over streams for the latest time period, called Interval of Interest (Iol). The system in the meantime processes multiple continuous query language (CQL) queries corresponding to different aggregation levels in cube lattice. To cover arbitrary aggregation levels using limited system's memory, we propose to partially deploy CQL queries for those with higher reference frequencies, whereas the results are dynamically calculated using existing aggregation results with the help of OLAP engine. For optimal CQL query deployment, we propose a cost-based optimization method that maximizes the performance. The experimental results show that the proposed architecture is feasible enough to realize stream OLAP by combining an SPE and an OLAP engine. Also, the proposed system significantly outperforms other comparative methods by generating optimized query deployment plans.

We propose in this paper a social reading system for EPUB3 publications (SRS4ePub), whereby users can share bookmarks and annotations among users. One of the features of this system is that it fully exploits EPUB and its related open standards to make social reading system possible. Besides, the system can record users' operational records so that we can analyse users' behavior while reading e-books. We first overview the proposed system and client, followed by its technical details. Next, we describe the user experiment and discuss how we can extract useful information from the collected data. As a result, we successfully extract various kinds of users' data, which are useful in many applications.

Linked Data (or LD) has promoted publishing information, and links published information (e.g., vocabularies and facts) for utilization. There are increasing number of LD datasets containing numerical data such as statistics. Analyses using such data require dedicated programs to extract, transform, and load (or ETL) for preparation. Thus, a large effort of developers is required. Also, the LD datasets tend to be large and the dumps (or snapshots) for the datasets easily become not up-to-date due to update frequency of the datasets. Hence, downloading dumps of LD datasets to ETL for OLAP can miss latest records. This paper proposes a framework called SPOOL, which attempts to reduce the effort and to ETL latest numerical records data from LD datasets for OLAP through SPARQL endpoints without downloading whole datasets. SPOOL provides series of SPARQL queries extracting objects and attributes from LD datasets, and converts them into star/snowflake schemas, and materialize relevant triples as fact and dimension tables for OLAP. The applicability of SPOOL is evaluated using exiting LD datasets on the Web, and SPOOL successfully processes the LD datasets to ETL for OLAP.

The location profiles of social media users are valuable for various applications, such as marketing and real-world analysis. As most users do not disclose their home locations, the problem of inferring home locations has been well studied in recent years. In fact, most existing methods perform batch inference using static (i.e., pre-stored) social media contents. However, social media contents are generated and delivered in real-time as social streams. In this situation, it is important to continuously update current inference results based on the newly arriving contents to improve the results over time. Moreover, it is effective for location inference to use the spatiotemporal correlation between contents and locations. The main idea of this paper is that we can infer the locations of users who simultaneously post about a local event (e.g., earthquakes). Hence, in this paper, we propose an online location inference method over social streams that exploits the spatiotemporal correlation, achieving 1) continuous updates with low computational and storage costs, and 2) better inference accuracy than that of existing methods. The experimental results using a Twitter dataset show that our method reduces the inference error to less than 68% of existing methods. The results also show that the proposed method can update inference results in constant time regardless of the amount of accumulated contents.

Due to the rapid proliferation of ontology-based information systems and networks, there are strong demands for ontology-mapping in a privacy-aware way. To this problem, in this paper, we propose Privacy-Preserving Quick Ontology Mapping (P2QOM), a privacy-preserving ontology mapping scheme based on Quick Ontology Mapping (QOM). The idea is to implement QOM, a well-known ontology-mapping scheme, in a privacy-preserving setting. More precisely, we assume a (untrusted) third party. In each client, the ontology being matched is converted into a set of features, and they are transmitted to the third party after obfuscation. The schema mapping is performed in the third party by exploiting some techniques for computing the similarity between the obfuscated features. The experimental results reveal that the proposed scheme is comparable to the original (non-privacy preserving) QOM in terms of both accuracy and performance, though the proposed scheme involves some extra overheads.

Applying faceted search for XML data enables users to search XML data in an interactive manner. However, applying faceted search is challenging, because faceted search requires target subtrees (objects) and facets to be defined before-hand. To this problem, existing works assume that such objects and/or facets are defined manually, but it is infeasible to manually specify objects and facets in particular when the XML data are huge and/or its structure is quite complicated. To address this problem, this paper proposes an automatic extraction scheme of objects and facets from XML data. We propose two approaches, namely frequency-based approach and semantic-based approach, and also hybrid approach of them. The basic ideas of these approaches are that the frequently occurring XML elements seem to be objects and facets, and such XML elements may have semantically meaningful name. Although the proposed approaches are rather simple, the experiments using real world XML data show that the proposed approaches can automatically extract objects and facets from the XML data.

With the rise of Web search engines, processing keyword search over XML and XML streams has drawn much attention from many researchers. Compared to conventional query methods, keyword search has several benefits for its simplicity and its user-friendliness in querying XML databases. Therefore, a great deal of effort has been put on this search paradigm by trying to improve the quality of search result of pure keyword search, where only keywords are allowed as a query. However, due to the vagueness of keyword search, it is hard to accurately express real search intention with just keyword search. We observe that there are many cases where the combination of path-based query and keyword search is a better choice and can deal with such challenge. To address this problem, we propose a method to integrate XPath and keyword search so that users can accurately express their search demands. The experimental results show that the proposed scheme can process queries over XML streams practically.

Faceted search for XML data is one of the promising exploration methods with high usability to find desired subtrees from a given XML data. This paper proposes improved approach of faceted search over XML data by utilizing facets containing unique and longer textual values, like titles of papers in bibliographic database. Our approach is to extract suitable terms which categorize the current results into several groups. Also we propose a task designing method for evaluating exploratory search by defining specificity of tasks called specification level, and we introduce how to generate tasks with given specification level as well. With this task design, we evaluate our proposed approach and the results show our proposed approach improves search performance comparing with the previous approaches, especially when tasks have low specification levels.

This paper proposes a system for social reading based on EPUB3, a standardized format for EPUB publications. The system is to collect and manage reading-related information, such as EPUB publications' metadata, bookmarks, and annotations, as well as users' behavioral information, such as the time and the location at which the users read the e-books, the timing when they turned the pages, etc. The system not only allows the users to share the reading-related information with each other, but also enables them to extract useful information out of the stored data. We present an overview of the proposed social reading system based on EPUB3, followed by the prototype implementation using Readium, a reference implementation of EPUB3 reader.

ObjectRank is a method of link structure analysis to evaluate the importance of objects in a database. ObjectRank is known to be computationally expensive, because it requires iterative computations over a large graph. However, in many real applications, it is sufficient to compute the ObjectRank scores for only small fraction of objects. To address this problem, this paper proposes a novel method for estimating ObjectRank scores for specific objects by applying local computation over partial graphs, thereby allowing us to maintain low computational cost even for large graphs. Our basic idea is that, for a given target node, we induce a local graph by checking the edge weights and pruning the edges with considering their weights. We conduct experiments to compare our method with some comparative methods. The experimental results show that our method can reduce the computational cost while maintaining the accuracy.

This paper proposes a scheme of detecting "Intensive Bookmarking using Multiple Accounts" (IBMA), where many social bookmark accounts are used to create bookmark entries linking to the target web resources with the aim of increasing site visitors or optimizing search result ranking. To efficiently detect IBMA, we propose to use clustering social bookmark user accounts according to the similarity with respect to the book marked web resources or web sites. Specifically, we cluster users who create bookmarks linking to similar set of web resources or web sites. For this, we propose three similarity measurements over two sets of bookmarks. We experimentally show that the proposed scheme successfully detects IBMA spammers in a real dataset. We also evaluate the accuracy of the proposed scheme with varying the similarity measurements, and characterize them.

Uncertain databases have been widely developed to deal with the vast amount of data that contain uncertainty. To extract valuable information from the uncertain databases, several methods of frequent itemset mining, one of the major data mining techniques, have been proposed. However, their performance is not satisfactory because handling uncertainty incurs high processing costs. In order to address this problem, we utilize GPGPU (General-Purpose computation on GPU). GPGPU implies using a GPU (Graphics Processing Unit), which is originally designed for processing graphics, to accelerate general purpose computation. In this paper, we propose a method of frequent itemset mining from uncertain databases using GPGPU. The main idea is to speed up probability computations by making the best use of GPU's high parallelism and low-latency memory. We also employ an algorithm to manipulate a bitstring and data-parallel primitives to improve performance in the other parts of the method. Extensive experiments show that our proposed method is up to two orders of magnitude faster than existing methods.

In this paper, we address the problem of tagging users in Twitter, one of the most popular micro-blogging services. There are growing needs to get useful information from Twitter, because an enormous amount of information is transmitted in real time. Twitter users, who play an important role as information sources, typically transmit information about some particular topics which they are interested in. Therefore, to identify useful information, it is very important to know which topics a user tends to transmit. In this paper, we propose a method to discover appropriate topics for a user by using Twitter list. Twitter list is an official functionality to make a"user list, " list members tend to transmit information about the topic represented in the name of the list. From this observation, our idea is to extract tags from list names, and exploit the relationship among lists, tags extracted from the list names, and list members. Experimental results show the effectiveness of the proposed method.

In this paper, we propose a framework of faceted navigation over XML data. General faceted navigation schemes are used to browse objects (or records) containing multiple properties. However, because XML is semi-structured in nature, it is not straightforward to apply faceted navigation to XML data. Specifically, we need to cope with three major technical issues: 1) objects in XML data are not predetermined, 2) objects may have flexible and/or recursive structure, and 3) properties of an object need to be automatically detected and extracted. To these problems, in this paper, we formulate faceted navigation over XML data by giving definitions of class, property, object, and facet in XML data. We then formulate typical user interactions in faceted navigation as operations over aforementioned concepts (class, object, and facet). We also propose a framework based on these definitions and operations, and construct a prototype system based on the framework. Finally, we show experimental evaluations using the prototype system to show the effectiveness of our proposed scheme.

When querying RDF and RDFS data, for improving the performance, it is common to derive all triples according to RDFS entailment rules before query processing. An undesirable drawback of this approach is that a large number of triples are generated by the RDFS reasoning, and hence considerable amount of storage space is required if we materialize the RDFS closure. In this paper, we propose RDF packages, which is a time and space efficient format for RDF data. In an RDF package, a set of triples of the same class or triples having the same predicate are grouped into a dedicated node named Package. Using Packages, we can represent any metadata that can be expressed by RDF. An important feature of the RDF packages is that, when performing RDFS reasoning, the same rules can be applied without any modification, thereby allowing us to use existing RDFS reasoners. In this paper, we discuss the model of RDF packages and its rules, followed by the transformation between RDF and RDF packages. We also discuss the implementation RDF packages using an existing RDF framework. Finally, we demonstrate the performance of the proposed scheme in triple size, reasoning speed, and querying speed.

Information Extraction (IE) is a technique to extract structured information (record) from unstructured documents such as Web pages. However, existing techniques are basically aiming at extracting simple records, such as binary relationships like (company, location) or named entities like (organization). In this paper, we propose an algorithm for extracting complex records like XML by utilizing an existing IE technique. Given a set of seed records in the form of XML data (XML records), we firstly infer the schema information from the XML records. Then, we transform the XML records to a set of relational records consisting of several tables. The obtained relational tables are decomposed into a set of binary relations, and they are forwarded to a record extraction system. We reconstruct XML data from the results obtained from the record of the extraction system. We point out a naive implementation docs not work well, and propose an improved scheme for more efficient XML record extraction. We evaluate the effectiveness of our proposed algorithm in some experiments.

Database security has become a vital issue in modern Web applications. Critical business data in databases is an evident target for attack. Therefore, ensuring the confidentiality, privacy and integrity of data is a major issue for the security of database systems. Recent high profile data thefts have shown that perimeter defenses are insufficient to secure sensitive data. This paper studies security of the databases shared between many parties from a cryptographic perspective. We propose mixed cryptography database (MCDB), a novel framework to encrypt databases over untrusted networks in a mixed form using many keys owned by different parties. The encryption process is based on a new data classification according to the data owner. The proposed framework is very useful in strengthening the protection of sensitive data even if the database server is attacked at multiple points from the inside or outside.

The advancement of multi-core processors technology has led to changing course of computing and enabled us to maximize the computing performance. In this study, we present a parallel TwigStack algorithm executed on a shared-memory multi-core system for achieving scalable query performance against large XML data. Our proposed scheme explores the following features. Firstly, we perform on-the-fly partitioning on input streams of XML nodes for subsequent parallel execution and, thereby, ensure that query solutions in a partition can be obtained by the TwigStack algorithm without being dependent on other partitions. Secondly, we propose a scheme for estimating the optimal partition size for a given system configuration by taking L2-cache size into account. Finally, we introduce a partition prefetching technique to alleviate the overheads of performing the on-the-fly partitions. The experimental results demonstrate that our proposed parallel algorithm works effectively and efficiently. The parallel speedup scales up to the number of available CPU-cores.

This paper discusses algorithms that efficiently compute structural grouping over XML data, which is a core operation in the interactive analysis of XML data, called "XML-OLAP". XML-OLAP allows interactive analysis over XML data to discover important information, and aggregation computation according to XML's tree hierarchy or TOPOLOGICAL ROLLUP, which plays a key role in XML structure-based grouping. We propose several variations of algorithms for efficient TOPOLOGICAL ROLLUP computation. Initially, these are basic algorithms: Top-Down and Bottom-Up, which are based on well-known Structural Join algorithms. We then propose a modified Bottom-Up algorithm to improve applicability, and the Single-Scan algorithms that make use of dedicated data structures. We finally perform comparative experimental analysis over the proposed algorithms, and demonstrate efficiency.

As traditional partitioning strategies do not serve well for semistructured data, partitioning and distributing heterogeneous XML documents onto a parallel cluster system have lead to such an intricacy issue for maintaining good query processing performance. In this paper, we propose a grid metadata model for XML that gives a conceptual view to partition XML data, specifically for holistic twig joins processing. The proposed model adopts a cost-based model and facilitates a set of partition refinement methods for workload balancing purpose. The model has features of reducing the workload variance significantly on the cluster system, duplicating XML data necessarily to avoid data dependency among cluster nodes, and exploiting inter query parallelism and intra query parallelism. We evaluate the effectiveness of our proposed model in the experiment that our data partitioning method has better workload balance and has an impact on better parallel speed up performance as well.

Recent developments in network and sensor device technologies enable us to easily obtain real-world information, such as locations of moving objects and environment information including brightness and temperature. These data are continuously supplied as they change over time, and they are regarded as data streams. The requirements for online processing of such data streams are increasing. In this demonstration, we present location-based information delivery using StreamSpinner, our stream processing engine. StreamSpinner achieves efficient stream data processing based on novel multiple continuous query optimization techniques. Using the StreamSpinner API, we built a location-based information delivery system for exhibition visitors. Locations of exhibition visitors are continuously monitored and supplied as data streams. Useful information about nearby exhibits and the availability of exhibition hall facilities is provided by the system to visitor terminals. Online integration of streams and database contents is achieved in the demonstration system.

Update management of XML documents is an increasingly important research issue in XML databases, because contents of XML documents evolve as time goes by. Even though, XML databases should be able to effectively process XML queries as well as updates on the documents. We propose a robust node-numbering scheme for XML documents named QRS (quartering-regions scheme). In QRS, reefs (regions expressed by floating-point numbers), a variant of regions, are used for expressing node-numbers. Reefs are almost compatible to regions, and thus they can be used for detecting ancestor-descendant relationship among nodes for the purpose of efficient query processing. Moreover, reefs can cope with updates by utilizing gaps between reefs in terms of floating-point numbers. Consequently, we can avoid node renumbering as much as possible.