Explanation techniques such as local interpretable model-agnostic explanation (LIME) provide reasons behind decisions made by machine-learning models. These methods typically use a set of features and their values as inputs and identify those that significantly influence the final decision. However, machine-learning models for entity matching operate on two sets of tokens or records, each representing an entity, to determine whether they refer to the same real-world entity. Explanations for entity-matching decisions are more convincing when they highlight contributing pairs of tokens within the pair of records, rather than focusing on individual tokens alone. In this sense, existing explanation techniques are insufficient for entity matching. Therefore, we propose a new method, Pair INterpretation for Entity matching (PINE), which takes two records as input, and outputs correlated token pairs as an explanation for an entity-matching decision. Our extensive experiments on public datasets demonstrate that the extracted token pairs exhibit strong correlations and serve as interpretable evidence for matching records.

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.

With the rising awareness of the critical role sleep plays in both health and social well-being, the demand for sleep studies is rapidly increasing.Automatic sleep stage classification is a fundamental part of sleep measurement, and machine learning models have been developed to assist in this process. These models achieve accuracy comparable to that of technicians when using data from healthy individuals. However, sleep patterns in individuals with sleep disorders, such as sleep apnea syndrome (SAS), one of the most common sleep disorders, differ from those of healthy individuals. As a result, existing models trained on healthy individuals’ data do not achieve sufficient accuracy when applied to SAS patients. This is a barrier to clinical application.A recent study using in-home EEG devices showed that technicians can accurately classify sleep stages in SAS cases by considering surrounding epochs. Based on this, we developed a model dedicated to SAS patients that incorporates the temporal context of relevant epochs.We found that this context-aware model significantly improved classification accuracy compared to models that only focused on the target epoch. In the training process using data from 76 severe SAS cases, the model based solely on single-epoch data achieved an accuracy of 71.5%, while the model considering the surrounding epochs achieved an accuracy of 73.7%. The classification accuracy improved across all stages except N3.This approach appears to capture the frequent sleep stage transitions characteristic of SAS.

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.

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.

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.

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.

Recent advances in location-aware devices have resulted in an exponential increase in the trajectory data streams. A number of applications require real-time processing and analysis of massive moving objects' trajectories. For instance, route guidance in emergency evacuation, patients tracking, etc. Existing scalable trajectory management systems lack support for real-time processing, while the real-time systems do not natively support spatial trajectory processing. This work presents TStream, a real-time and scalable trajectory stream processing and analysis framework. TStream utilizes grid index to support efficient processing of continuous range, kNN and join queries.

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.

Apache Flink is an open-source system for scalable processing of batch and streaming data. Flink does not natively support efficient processing of spatial data streams, which is a requirement of many applications dealing with spatial data. Besides Flink, other scalable spatial data processing platforms including GeoSpark, Spatial Hadoop, etc. do not support streaming workloads and can only handle static/batch workloads. To fill this gap, we present GeoFlink, which extends Apache Flink to support spatial data types, indexes and continuous queries over spatial data streams. To enable efficient processing of spatial continuous queries and for the effective data distribution across Flink cluster nodes, a gird-based index is introduced. GeoFlink currently supports spatial range, spatial kNN and spatial join queries on point data type. An experimental study on real spatial data streams shows that GeoFlink achieves significantly higher query throughput than ordinary Flink processing.

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.

As the popularity of SNS and the number of GPS-equipped mobile devices increases, a large number of web users frequently change their location (spatial attribute) and interesting keywords (keyword attribute) in real-time. An example of such would be when a user watches the news, videos, and blogs while moving. Many location-based web applications can benefit from continuously searching for these dynamic spatial keyword objects. In this paper, we define a novel query problem to continuously search for dynamic spatial keyword objects. To the best of our knowledge, this is the first work to consider dynamic spatial keyword objects. We employ a novel grid-based index to manage both queries and dynamic spatial keyword objects. With the proposed index, we develop a buffer named partial cell list to reduce the computation cost in the top-k reevaluation. The experiments confirm the superiorities of our proposed methods.

How can the most appropriate community be found given an attributed graph and a user-specified query node? The community search algorithm is currently an essential graph data management tool to find a community suited to a user-specified query node. Although community search algorithms are useful in various web-based applications and services, they have trouble handling attributed graphs due to the strict topological constraints of traditional algorithms. In this paper, we propose an accurate community search algorithm for attributed graphs. To overcome current limitations, we define a new attribute-driven community search problem class called the Flexible Attributed Truss Community (F-ATC). The advantage of the F-ATC problem is that it relaxes topological constraints, allowing diverse communities to be explored. Consequently, the community search accuracy is enhanced compared to traditional community search algorithms. Additionally, we present a novel heuristic algorithm to solve the F-ATC problem. This effective algorithm detects more accurate communities from attributed graphs than the traditional algorithms. Finally, extensive experiments are conducted using real-world attributed graphs to demonstrate that our approach achieves a higher accuracy than the state-of-the-art method.

Given a bi-type information network, which is an extended model of well-known bipartite graphs, how can clusters be efficiently found in graphs? Graph clustering is now a fundamental tool to understand overviews from graph-structured data. The RankClus framework accurately performs clustering for bi-type information networks using ranking-based graph clustering techniques. It integrates a graph ranking algorithms such as PageRank or HITS into graph clustering procedures to improve the clustering quality. However, this integration incurs a high computational cost to handle large bi-type information networks since RankClus repeatedly computes the ranking algorithm for all nodes and edges until the clustering procedure converges. To overcome this runtime limitation, herein we present a novel RankClus algorithm that reduces the running time for large bi-type information networks. Our proposed method employs dynamic graph processing techniques into the ranking procedures included in RankClus. By dynamically updating ranking results, our proposal reduces the number of computed nodes and edges during repeated ranking procedures. We experimentally verify using real-world datasets that our proposed method successfully reduces the running time while maintaining the clustering quality of RankClus.

Worker-task assignments represent one of the critical issues in crowdsourcing, as they affect the quality of task results. This study addresses the problem of forming worker groups assigned to the same task in a task stream that requires more than one worker. We introduce a worker-group queue model that covers practical and common scenarios for task-stream crowdsourcing, and compare three strategies in terms of the skill balance among worker groups, the quality of the final outputs, the number of worker re-assignments of workers, and psychological stress felt by workers. We found that one of the compared strategies that employs multiple worker queues yields good results based on these measures.

We demonstrate CrowdSheet, a spreadsheet interface for implementing complex crowdsourcing. Despite its appeal, adoption of the spreadsheet paradigm is associated with two nontrivial problems: (1) how to design the interface, which must be a natural extension of existing spreadsheets, while guaranteeing a reasonable expressive power, and (2) how to incorporate techniques for improving data quality without sacrificing the spreadsheet's easy-to-use feature. In this demo, we show three things. First, CrowdSheet allows non IT experts to easily implement crowdsourcing applications with complex workflows. Second, CrowdSheet adopts only new two spreadsheet functions to implement a fairly wide range of real-world applications. Third, its modular architecture gives CrowdSheet a declarative feature that lets users choose alternative plans for improving data quality, while keeping the CrowdSheet description simple.

Affinity Propagation is one of the fundamental clustering algorithms used in various Web-based systems and applications. Although Affinity Propagation can find highly accurate clusters, it is computationally expensive to apply Affinity Propagation to a large dataset since it requires to iteratively compute all possible pairs of data objects in the dataset. In this paper, we propose a novel Affinity Propagation algorithm named C-AP for tackling this problem. Towards the problem, C-AP employs cell-based index to reduce the number of the computed pairs in the clustering procedure. By using the cell-based index, C-AP efficiently detects unnecessary pairs, which do not contribute to its clustering result. As a result, C-AP detects the same clusters as those of Affinity Propagation with much shorter computation time. Extensive evaluations demonstrate the performance superiority of C-AP over the state-of-the-art algorithms.

The demands for graph data analysis methods, e.g., clustering and ranking, are increasing. RankClus is a framework to extract good clusters by integrating clustering and ranking on heterogeneous graphs; it enhances the clustering results by alternately updates the results of clustering and ranking for the better understanding of the clusters. However, RankClus is computationally expensive if a graph is large since it needs to iterate both clustering and ranking for all nodes. In this paper, to address this problem, we propose a novel fast RankClus algorithm for heterogeneous graphs. To speed up the entire procedure of RankClus, our proposed algorithm reduces the computational cost of the ranking process in each iteration. Our proposal measures how each node affects the clustering result; if it is not significant, we prune the node. Our extensive evaluations showed that our proposal is much faster than the original method.

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.

Current era is witnessing a tremendous growth in the volume of data that is being generated in the form of data streams by the omnipresent sensors, micro-blogs, e-businesses, etc. Many organizations require on-line processing of their data for real time analysis and actionable alerts. It is not possible to process such voluminous and velocious data in real time using the traditional centralized stream processing engines. Hence distributed stream processing has emerged to facilitate such large scale real time processing. In this work we present a smart distributed event-driven stream processing approach. In contrast to the ordinary stream processing, event-driven stream processing generates query results on the occurrence of specified events only. In the basic event-driven stream processing, even when no event is raised input stream tuples are continuously processed by query operators, though they do not generate any query result. This results in increased system load and wastage of system resources. Whereas in the smart event-driven stream processing scheme, incoming tuples are processed in the presence of events only resulting in reduced system load. The proposed smart distributed event-driven stream processing utilizes the concept of smart query execution to distribute the data stream among the distributed worker nodes in the presence of events only; while in the absence of events no data is distributed as it can not generate query output. This smart data distribution can significantly reduce the network traffic in the absence of events and ultimately results in improved overall system throughput. Detailed experiments are performed to prove the effectiveness of the proposed framework.

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.

In most streaming applications, the data streams need to be analyzed continuously to make instant decisions exploiting latest information. Often data streams are multidimensional and are at the low-level of abstraction, whereas analysts are interested in multi-level interactive analysis of data streams across several dimensions. On-line analytical processing (OLAP) is a proven technique for such analysis of static data and has also been studied by some researchers for data streams. Traditionally this is achieved by coupling a stream processing engine with an OLAP engine. We believe that coupling multiple systems is not an efficient solutions as it results in lower performance (due to the transfer of data between multiple systems), resource wastage (due to replication of data for each coupled system) and increased complexity and maintenance cost. To this end, we present StreamingCube, a unified framework for data stream processing and its interactive OLAP analysis. The proposed framework possesses all the essential operators to process data streams and introduces a new operator, cubify, to maintain OLAP lattice nodes (materialized views) incrementally. The novelty of the introduced cubify operator lies in the incremental maintenance of the materialized views. To demonstrate StreamingCube, a web-based GUI has been developed which enables users to register continuous queries (CQs). Once a CQ has been registered, users can perform different OLAP operations through the GUI for the interactive analysis. The results of the OLAP queries/operations are displayed in the form of tables and graphs.

How can we collect non-geotagged tweets posted by users in a specific location as many as possible in a limited time span? How can we find such users if we do not have much information about the specified location? Although there are varieties of methods to estimate the locations of users, these methods are not directly applicable to this problem because they require collecting a large amount of random tweets and then filter them to obtain a small amount of tweets from such users. In this paper, we propose a framework that incrementally finds such users and continuously collects tweets from them. Our framework is based on the bandit algorithm that adjusts the trade-off between exploration and exploitation, in other words, it simultaneously finds new users in the specified location and collects tweets from already-found users. The experimental results show that the bandit algorithm works well on this problem and outperforms the carefully-designed baselines.

Given brain and myoelectric signals taken from a mouse, how can we classify its sleep stages accurately? Classifying sleep stages is the fundamental problem in recent diagnoses and clinical researches. However, sleep staging suffers from a serious weakness, clinical experts visually inspect the brain and myoelectric signals to improve sleep staging accuracy. This is because recent diagnoses and clinical researches require classification accuracy at least 95% so as to enhance preciseness of their analyses. In this paper, we present an automatic classification method MASC based on the following three approaches: (1) it extracts effective features for fully representing each sleep stage property, (2) it classifies sleep stages by using temporal patterns of sleep stage transitions, and (3) it re-classifies sleep stages only for the results with low-confidence. As a result, MASC achieves more than 95% accuracy for both noisy and noiseless mice data.

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.

A common workflow to perform a continuous human task stream is to divide workers into groups, have one group perform the newly-arrived task, and rotate the groups. Usually, more than one worker belongs to each group for improving the quality of task results. We call this type of workflow the group rotation. This paper addresses the problem of how to manage Group Rotation Type Crowdsourcing, the group rotation in a crowdsourcing setting. In the group-rotation type crowdsourcing, we must change the group structure dynamically because workers come in and leave frequently. However, changing the group structure will give workers psychological stress, such as surprise, confusion or irritation. This paper explores a design space for group restructuring algorithms in the group rotation type crowdsourcing and compares implemented strategies in terms of the evaluation results on psychological stress with real-world crowd workers.

Entity Linking is the task of assigning a corresponding entity in a knowledge base to each mention in text. Typically, entity linking is a 3-step process: (1) candidate selection, (2) candidate evaluation, and (3) linking decision. Many existing methods including the state-of-the-art mainly discuss the candidate evaluation step, however, the efficiency of the candidate selection has been barely discussed. This paper discusses the importance of the candidate selection step in order to reduce overall processing time, and proposes a recency-based pruning method for efficient entity linking for time-series documents. Our goal is to reduce processing time of entity linking by efficient and effective pruning of candidate entities without losing accuracy. Our experimental evaluation on a benchmark dataset containing tweet data, shows that our proposal improves the processing time by about 15 times than the existing method without losing accuracy.

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.

How can we tell if Alice is a talkative person or a silent person? In this paper, we focus on the node classification problem on networked data such as social networks and the web. There are two open challenges with this problem: (1) we want to handle various kinds of label correlations in real-world networks such as homophily (i.e., love of the same) and heterophily (i.e., love of the different), and (2) we want to exploit the confidence of the inference results to enhance the accuracy. There is no algorithm that solves these two challenges at the same time. We tackle with these two challenges by proposing CAMLP, a novel node classification algorithm. Our contributions are three-fold: (a) Novel algorithm; our algorithm is confidence-aware and is applicable to both homophily and heterophily networks, (b) Theory; we give theoretical analyses of our algorithm, and (c) Practice; we perform extensive experiments on 5 different network datasets including homophily and heterophily networks. Our experiments show that the proposed algorithm improves the precision of major competitors not only on heterophily networks, but also on homophily networks.

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.

Outlier detection over data streams is an increasingly important task in data mining. Traditional distance-based data stream outlier detection is unsuitable for high-dimensional data sets, since the discrimination of distances between different data points becomes rather poor in high dimensional space. ABOD (Angle-based Outlier Detection) is an effective approach to detecting outliers in high-dimensional space. In this paper, the problem of continuous ABOD over data streams is studied. Generally, only a few data objects may change their states during two consecutive timestamps. Therefore, we propose several incremental angle-based outlier detection approaches over data streams based on ABOD and its variants that provide visible speed-up without loss of accuracy. Firstly, the basic ideas of these incremental algorithms are introduced. Then, we explain the time complexity of them. Finally, we use synthetic data streams to prove their efficiency.

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.

Data integrity constraints are fundamental in various applications, such as data management, integration, cleaning, and schema extraction. In this paper, we address the problem of finding inclusion dependencies on the Web. The problem is important because (1) applications of inclusion dependencies, such as data quality management, are beneficial in the Web context, and (2) such dependencies are not explicitly given in general. In our approach, we enumerate pairs of HTML/XML elements that possibly represent inclusion dependencies and then rank the results for verification. First, we propose a bit-based signature scheme to efficiently select candidates (element pairs) in the enumeration process. The signature scheme is unique in that it supports Jaccard containment to deal with the incomplete nature of data on the Web, and preserves the semiorder inclusion relationship among sets of words. Second, we propose a ranking scheme to support a user in checking whether each enumerated pair actually suggests inclusion dependencies. The ranking scheme sorts the enumerated pairs so that we can examine a small number of pairs for simultaneously verifying many pairs.

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.

Distributed stream processing engines (DSPEs) have recently been studied to meet the needs of continuous query processing. Because they are built on the cooperation of several stream processing engines (SPEs), node failures cause the whole system to fail. This paper proposes a new high-availability scheme called Adaptive Semi-Active Standby (A-SAS). A-SAS enables adaptive tradeoff between bandwidth usage and recovery time. This paper presents the properties of A-SAS and experimental results that suggest A-SAS effectiveness.

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 proposes a novel window operator, pattern-based window, for data stream processing. By using pattern-based windows, user-specified complex events can be extracted from data streams under the framework of continuous query language (CQL), which integrates the current data stream processing and event stream processing. In this paper, the pattern-based window is formally defined and the query language of pattern-based windows is designed. A simple pattern matching algorithm is introduced to show logical expression of the query language. We also give simple examples to show the usage of the query language by using pattern-based windows.

This paper addresses the problem of finding new locations of moved Web pages. We discuss why the content-based approach has a limitation in solving the problem and why it is important to exploit the knowledge on where to search for the pages.

Managing frequent updates is greatly important in many update-intensive applications, such as location-aware services, sensor networks, and stream databases. In this paper, we present an R-tree-based index structure (called {\rm R}^{\rm{{sb}}}-tree, R-tree with semibulk loading) for efficiently managing frequent updates from massive moving objects. The concept of semibulk loading is exploiting a small in-memory buffer to defer, buffer, and group the incoming updates and bulk-insert these updates simultaneously. With a reasonable memory overhead (typically only 1 percent of the whole data set), the proposed approach far outperforms the previous works in terms of update and query performance as well in a realistic environment. In order to further increase buffer hit ratio for the proposed approach, a new page-replacement policy that exploits the level of buffered node is proposed. Furthermore, we introduce the concept of deferring threshold ratio (dtr) that simply enables deferring CPU- and I/O-intensive operations such as node splits and removals. Extensive experimental evaluation reveals that the proposed approach is far more efficient than previous approaches for managing frequent updates under various settings.

PageChaser is a system that monitors links between Web pages and searches for the new locations of moved Web pages when it finds broken links. The problem of searching for moved pages is different from typical information retrieval problems. First, it is impossible to identify the final destination until the page is actually moved, so the index-server approach is not necessarily effective. Secondly, there is a large bias about where the new address is likely to be and crawler-based solutions can be effectively implemented, avoiding the need to search the entire Web. PageChaser incorporates a comprehensive set of heuristics, some of which are novel, in a single unified framework. This paper explains the underlying ideas behind the design and development of PageChaser.

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.

Outlier detection, a data mining technique to detect rare events, deviant objects, and exceptions from data, has drawn increasing attention in recent years. Much existing research targets record data constructed with numerical attributes or a set of points having numeric values. However, very few studies have attempted to detect outliers from data having items. We focus on transaction data and propose a framework for detecting outlier transactions that behave abnormally compared to others. As an outlier, we are interested in a transaction t in which more items are not observed even though they should normally have a strong dependency on item sets in t. We use information of association rules with high confidence for the outlier degree calculation. In this paper, we first discuss what outliers of transactions are, and provide an outlier degree for systematically detecting outlier transactions. We also propose algorithms for efficiently detecting outlier transactions from transaction databases. We present two devices for faster detection that (i) remove redundant association rules and (ii) prune candidates of outlier transactions utilizing maximal frequent itemsets. In experiments using synthetic and real world data sets, we show that our proposal can derive enough detection accuracies and detect outlier transactions faster than a brute force algorithm.

With the recent flood of information, trust in that information is gaining a lot of attention in determining how information is used. Social bookmarking is a new information sharing service that allows individuals to bookmark and annotate web pages of interest or those that impress them. It is attracting attention and growing in popularity. In social bookmark services, users' bookmarks and annotations given by tags are informative indicators of user interest in web pages. This paper proposes a method to evaluate the trust and significance of web pages based on social bookmarks. Extending the HITS approach, we regard web pages as Authority and users as Hubs and evaluate trust and significance values of web pages. We show usefulness of the proposed approach through experiments.

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.

With the recent progress of spatial information technologies and communication technologies, it has become easier to track positions of a large number of moving objects in real-time. Mobility statistics plays an important role in the interactive analysis of a large collection of moving objects trajectories and its use of movement pattern prediction. The development of an effective mobility statistics measure and its efficient computation method are critical issues. Thus, we propose an approach for constructing a mobility histogram to summarize a number of moving object trajectories. The histogram is based on a mobility statistics model called the Markov chain model. To facilitate an interactive analysis performed by a user, we provide a mobility histogram data cube-like logical representation and support an OLAP-style analysis. Since trajectory data is often received continuously as a trajectory stream, we have to support dynamic histogram construction and maintenance. We introduce a tree structure as the physical representation of a histogram and present histogram construction and maintenance methods that work efficiently within the given upperbound size. We evaluate the performance and the precision of the proposed method by means of experiments.

Detecting outliers is an important problem. Most of its applications typically possess high dimensional datasets. In high dimensional space, the data becomes sparse which implies that every object can be regarded as an outlier from the point of view of similarity. Furthermore, a fundamental issue is that the notion of which objects are outliers typically varies between users, problem domains or, even, datasets. In this paper, we present a novel robust solution which detects high dimensional outliers based on user examples and tolerates incorrect inputs. It studies the behavior of projections of such a few examples, to discover further objects that are outstanding in the projection where many examples are outlying. Our experiments on both real and synthetic datasets demonstrate the ability of the proposed method to detect outliers corresponding to the user examples.

Abstract Introducing context to a user query is effective to improve the search effectiveness. In this article we propose a method employing the taxonomy‐based search services such as Web directories to facilitate searches in any Web search interfaces that support Boolean queries. The proposed method enables one to convey current search context on taxonomy of a taxonomy‐based search service to the searches conducted with the Web search interfaces. The basic idea is to learn the search context in the form of a Boolean condition that is commonly accepted by many Web search interfaces, and to use the condition to modify the user query before forwarding it to the Web search interfaces. To guarantee that the modified query can always be processed by the Web search interfaces and to make the method adaptive to different user requirements on search result effectiveness, we have developed new fast classification learning algorithms.

We present XLearner, a novel tool that helps the rapid development of XML mapping queries written in XQuery. XLearner is novel in that it learns XQuery queries consistent with given examples (fragments) of intended query results. XLearner combines known learning techniques, incorporates mechanisms to cope with issues specific to the XQuery learning context, and provides a systematic way for the semiautomatic development of queries. We describe the XLearner system. It presents algorithms for learning various classes of XQuery, shows that a minor extension gives the system a practical expressive power, and reports experimental results to demonstrate how XLearner outputs reasonably complicated queries with only a small number of interactions with the user.

We propose a novel Web search scheme TAX-PQ. TAX-PQ enables taxonomy-based topic-focused Web search on ordinary Boolean Web search interfaces. TAX-PQ utilizes a taxonomy and the data set maintained in an existing taxonomy-based search facility for this purpose. The search is initiated by designating an initial query and a context category in the taxonomy. The data set in the taxonomy-based search facility is probed with a technique combining the initial query with sampling, and a decision tree is constructed from the sampled query result. A query modifier is then derived from the decision tree to focus the initial query on the selected context category. To adapt TAX-PQ to different user requirements on search result effectiveness and properties of target Web search interfaces, we have developed a new decision tree construction algorithm. Experiments involving real Web sites show that TAX-PQ can significantly improve the Web search process and result. The results comply with user requirements under constraints of the target Web search interfaces.

Outlier detection is an integral part of data mining and has attracted much attention recently [M. Breunig et al., (2000)], [W. Jin et al., (2001)], [E. Knorr et al., (2000)]. We propose a new method for evaluating outlierness, which we call the local correlation integral (LOCI). As with the best previous methods, LOCI is highly effective for detecting outliers and groups of outliers (a.k.a. micro-clusters). In addition, it offers the following advantages and novelties: (a) It provides an automatic, data-dictated cutoff to determine whether a point is an outlier-in contrast, previous methods force users to pick cut-offs, without any hints as to what cut-off value is best for a given dataset. (b) It can provide a LOCI plot for each point; this plot summarizes a wealth of information about the data in the vicinity of the point, determining clusters, micro-clusters, their diameters and their inter-cluster distances. None of the existing outlier-detection methods can match this feature, because they output only a single number for each point: its outlierness score, (c) Our LOCI method can be computed as quickly as the best previous methods, (d) Moreover, LOCI leads to a practically linear approximate method, aLOCI (for approximate LOCI), which provides fast highly-accurate outlier detection. To the best of our knowledge, this is the first work to use approximate computations to speed up outlier detection. Experiments on synthetic and real world data sets show that LOCI and aLOCI can automatically detect outliers and micro-clusters, without user-required cut-offs, and that they quickly spot both expected and unexpected outliers.

Based on the recent progress of digital cartography, global positioning systems (GPSs), and hand-held devices, there are growing needs of technology that provides neighborhood information to moving objects according to their locations and trajectories. In this paper we propose spatial query generation models that take account of the current position and the past/future trajectories of a moving object to provide appropriate neighborhood information to it. For this purpose, we introduce an influence model of trajectory points and derive neighborhood query generation models using adaptive ellipsoid distances. We describe query processing strategies for these query generation models and show incremental query update procedures to support continual query facilities with low processing cost. Finally, we present experimental results to show the effectiveness of our approach.

With the increased popularity of XML, XML publishing of RDBs has been attracting a lot of research interest. One of the typical approaches is to use a middleware system to render XML views over RDBs and to allow users to access data with XML query languages such as XQuery. The query processing is done efficiently by making the best of the querying power of RDBMSs. Namely, XML queries are translated into SQL queries and tagging operations, which are processed by the RDBMSs and middleware, respectively. In some XML query languages including XQuery, use of user-defined foreign functions is enabled or planned as an extension feature to cope with domain dependent semantics. Foreign functions are defined for XML fragments, and their implementations are often given by codes in a general programming language. The existing query processing schemes on XML views do not consider cases where foreign functions are included in XML queries. We propose extended schemes to process XML queries in such cases. In the proposed schemes, the middleware takes care of processing foreign functions as well as tagging operations. Therefore, the proposed schemes are applicable to XML views on commonly available RDBMSs. Three types of query processing schemes are proposed, and their performance is studied with experiments.

Recent progress of digital cartography and Internet technologies enabled new types of services on the network such as search engines that provide information within some specific geographic areas and retrieval services which allow map-oriented query interfaces. We call such services spatial information sources. In this paper, we propose a framework to integrate heterogeneous spatial information sources to provide an integrated view to users. Our main focus is heterogeneity of spatial information sources-since existing spatial information sources differ in their contents and query capabilities, integration of such sources requires an appropriate framework to describe their contents and query capabilities. In this paper, we show such a description framework and illustrate query processing strategies that utilize source descriptions of spatial information sources.

Integration of heterogeneous information sources has been one of important data engineering research issues. Various type of information sources are available today. They include dissemination-based information sources, which actively and autonomously deliver information from server sites to users. We have been developing a mediator/wrapper-based information integration system, in which we employ ECA (event-condition-action) rules to enable users to define new information delivery services integrating multiple existing dissemination-based information sources. However, it is not easy for users to directly specify ECA rules and to verify them. In this paper, we propose a scheme to specify new information delivery services using the framework of the relational algebra. We discuss some important properties of the specification and show how we can derive ECA rules to implement the delivery services.

A huge amount of multimedia content is available in the current Web environment. Streaming of video programs has become one of the popular Web-based information services. Automatic digest generation is an important application using video program streams. We have developed a digest making method called PDMS (Personal Digest Making Scheme). PDMS extracts significant scenes and constructs digests automatically using the video program meta data. In PDMS, only a successful play event such as a goal scored was considered significant, and a misplay event, such as a shot that did not score was not taken into account, although such an event may affect the game progress. This paper introduces a new concept of turning point analysis into PDMS. The turning point analysis is based on a winning probability for a sports programs. The winning probability indicates the probability of a home team beating an away team at the end of the game, given the current score and the time elapsed since the beginning of the game. Using the winning probability, we can more precisely evaluate the significance of each event, not merely a successful play but also a misplay. This paper presents turning point analysis for a soccer match. It also gives evaluation results of this extended PDMS, including turning point analysis for a recently broadcasted professional soccer match.

This paper explains a novel manipulation framework for XML. The key idea is to choose some example XML elements existing in the database and show the system how to manipulate them. The system then infers how to manipulate the whole collection of XML documents. The framework is unique in that while other approaches require users to write (or draw) explicit query specifications in their own query languages, ours needs implicit specifications through example operations. The problem is challenging, because XML documents can be semistructured data and inferring the intended operation is not trivial. Our algorithm is based on tree-style object modeling and path-expressions with wild-cards to infer the user's intention. The paper presents the object modeling, its inference mechanism, and some results of our preliminary experiments.

XML has been used to code various types of data in a wide range of application domains, and the volume of XML data has been rapidly increasing. XML query languages provide a clue to manipulating huge amounts of XML data. XML data in each application domain have their own structures and associated semantics. Therefore, to appropriately process them, we sometimes need domain dependent functions, taking into account content characteristics. To utilize such functions in XML queries, we need extensibility because they can not be covered by built-in functions. We have developed eXtensible XML Query Language X/sup 2/ QL and its processing system, which feature user-defined foreign functions in the context of XML-QL-based query facilities. Foreign functions are implemented using general programming languages. Extensibility is based on an XML data model in which elements are modeled as stateful objects. This gives "dynamic aspects" (concepts of methods and processing-time properties) to elements, which have been treated as static data in general XML query languages. Our extensibility also enables user-defined aggregation functions and facilities such as sort and top-N selection. This paper explains X/sup 2/QL and its extensibility. Focus is on the data model, Java binding of foreign functions, and how to implement them. The paper also describes development of an X/sup 2/QL query processor working with XML servers.

The integration of heterogeneous information sources is an important data engineering research issue. Various types of information sources are available today. They include dissemination-based information sources, which actively and autonomously deliver information from servers to users. We are developing a mediator/wrapper-based information integration system in which we employ ECA rules to define new information delivery channels, integrating multiple existing dissemination-based information sources. ECA rules in this system are derived from integration requirement specifications based on relational algebra provided by users. Dissemination-based information sources usually have data arrival properties, such as an information delivery schedule. Using the data arrival properties of underlying information sources, the system can derive more appropriate ECA rules and check the consistency of requirements more accurately. This paper proposes an extended scheme to process information integration requirements using source data arrival properties of dissemination-based information sources.

Object-oriented database systems (OODBs) need efficient support for manipulation of complex objects. In particular, support of queries involving evaluations of set predicates is often required in handling complex objects. In this paper, we propose a scheme to apply signature file techniques, which were originally invented for text retrieval, to the support of set value accesses, and quantitatively evaluate their potential capabilities. Two signature file organizations, the sequential signature file and the bit-sliced signature file, are considered and their performance is compared with that of the nested index for queries involving the set inclusion operator (⊆). We develop a detailed cost model and present analytical results clarifying their retrieval, storage, and update costs. Our analysis shows that the bit-sliced signature file is a very promising set access facility in OODBs.