In electronics manufacturing, anomaly detection methods face significant challenges due to class distribution imbalance and training instability when handling multiple classes simultaneously under varying imaging conditions. To address these challenges, we propose Reverse Distillation with Core-Exemplar Learning (RDCEL), a unified anomaly detection framework incorporating domain adaptation and novel metric learning strategies. RDCEL integrates unsupervised domain adaptation to align the covariance of the source and target domains and uses soft label-based coreset learning to handle diverse class distributions. It also leverages a coreset repulsion loss to minimize redundancy among coreset representations, fostering a more stable and dispersed embedding space across multiple classes. By aligning spatial statistics across different classes, RDCEL effectively addresses inter-class discrepancies, enabling consistent anomaly scoring under a unified test setting. Extensive experiments show RDCEL significantly outperforms state-of-the-art methods on MVTec AD and VisA datasets, achieving superior accuracy, stable AUROC performance, and faster convergence.

Graphs are continually growing in size, and processing complex queries, such as multi-hop pattern queries, on them is becoming increasingly important. Although GPUs have received significant attention recently, there is still a notable shortage of efficient GPU-based out-of-memory methods for handling these queries. Three key issues arise when processing multi-hop queries on large-scale graphs using GPUs: the need for an efficient graph format, effective scheduling of accesses to graph partitions on storage, and dynamic buffer management on both the host and GPUs. To address these issues, we propose an efficient GPU-based out-of-memory multi-hop query processing framework called GFlux. Through extensive experiments, we have demonstrated that GFlux significantly improves both the speed and scalability compared to existing state-of-the-art methods.

Recently, full-graph Graph Neural Networks (GNNs) have gained prominence by addressing complex problems such as weather forecasting and material discovery. Existing full-graph training methods do not fully manage intermediate data generated during training and rely on rigid inter-GPU communication, limiting both training speed and scale. We propose FlexGNN, which fully manages intermediate data and adaptively performs inter-GPU communication by generating and optimizing best-effort training execution plans. Extensive experiments demonstrate that FlexGNN significantly outperforms existing full-graph GNN methods in both training speed and scale. Specifically, it is up to 5.4X faster than HongTu and up to 95.5X faster than NeutronStar.

Abstract Graph neural networks (GNNs) have seen significant growth in analyzing heterogeneous graphs, which contain different types of nodes and connections. Recent studies have attempted to analyze heterogeneous graphs without relying on manually selected metapaths. However, existing methods often struggle to learn long-range dependencies between distant nodes because of over-squashing and over-smoothing. This paper presents a new approach, type-aligning graph diffusion network (TAGDN), that effectively addresses these challenges. Our main idea is to boost the power of graph diffusion techniques in heterogeneous graphs with a type-adaptive alignment scheme. This approach allows us to exploit long-range dependencies between nodes in heterogeneous graphs without suffering over-squashing and over-smoothing. Through extensive experiments, we show that TAGDN outperforms state-of-the-art heterogeneous GNNs on diverse graph analysis tasks. Ablation studies show that our alignment scheme enhances the capacity of graph diffusion networks in heterogeneous graph analysis, yielding an average improvement of 5.02% in node classification and 25.43% in node clustering. Our implementation is available at https://github.com/SeongJinAhn/TAGDN .

Subgraph queries are widely used but face significant challenges due to complex patterns such as negative and optional edges. While worst-case optimal joins have proven effective for subgraph queries with regular patterns, no method has been proposed that can process queries involving complex patterns in a single multi-way join. Existing CPU-based and GPU-based methods experience intermediate data explosion when processing complex patterns following regular patterns. In addition, GPU-based methods struggle with issues of wasted GPU memory and redundant computation. In this paper, we propose cuMatch, a GPU-based unified worst-case optimal join processing method for subgraph queries. It avoids intermediate data explosions by processing even complex pattern queries in a single multi-way join. It is also memory-efficient and fast, due to a new partitioning format, scheduling method, and task fusion technique. Extensive experiments demonstrate that cuMatch outperforms state-of-the-art methods by orders of magnitude, without out-of-memory errors.

With the introduction of GPUs, which are specialized for iterative parallel computations, the execution of computation-intensive graph queries using a GPU has seen significant performance improvements. However, due to the memory constraints of GPUs, there has been limited research on handling large-scale output graph queries with unpredictable output sizes on a GPU. Traditionally, two-phase methods have been used, where the query is re-executed after splitting it into sub-tasks while only considering the size of the output in a static manner. However, two-phase methods become highly inefficient when used with graph data with extreme skew, failing to maximize the GPU performance. This paper proposes INFINEL, which handles unpredictable large output graph queries in a one-phase method through chunk allocation per thread and kernel stop/restart methods. We also propose applicable optimization techniques due to the corresponding unique characteristics of operating with low time/space overhead and not heavily relying on the GPU output buffer size. Through extensive experiments, we demonstrate that our one-phase method of INFINEL improves the performance by up to 31.5 times over the conventional two-phase methods for triangle listing ULO query.

As graphs are being used increasingly in various industries, a new standard of SQL (called SQL:2023) has incorporated SQL with Property Graph Queries (SQL/PGQ) as a core feature. While some approaches process graph queries within RDBMSs using graph view definition or materialized graph view, their performance is not good enough for interactive SQL/PGQ queries in terms of response time, throughput, and graph size. To address this problem, we propose a novel system design named Chimera , which features a dual-store architecture and a unified query planning called Traversal-Join(TJ). This design treats the topologies of a graph as first-class citizens rather than secondary elements overcoming the graph size limitations of the materialized graph view approach. It also generates an efficient, unified query plan that performs traversal and join in a mixed way, significantly enhancing both response time and throughput. Implemented on the open-source RDBMS, PostgreSQL, our extensive experiments with the LDBC SNB benchmark and microbenchmark show that Chimera significantly outperforms the existing approaches and GRDBMSs.

With the development of the Internet of Things, the sensor usage has been elevated to a new level, and it becomes more crucial to maintain reliable sensor networks. In this article, we provide how to efficiently and reliably manage the sensor monitoring system for ensuring data freshness. A sensor transmits its sensing information regularly to the data center (DC), and the sensed information generally has the correlation over the space and the time. Hence, the accuracy of the estimated information from the sensed information decreases as the target location for information estimation is further away from the sensor or the Age of Information (AoI), the elapsed time from the information generation, increases. Therefore, by considering the effect of the AoI and the distance from the sensor on the estimation error, we newly define an error-tolerable sensing (ETS) coverage as the area that the estimated information at the DC is with smaller error than the target value. To analyze the impact of the AoI on the ETS coverage, we derive the$\eta $-coverage probability, which is the probability that the ETS coverage is greater than$\eta $ratio of the maximum sensor coverage, and the average ETS coverage. We also provide the optimal transmission power of the sensor, which minimizes the average energy consumption while guaranteeing certain level of the$\eta $-coverage probability. Numerical results validate the theoretical analysis and show the tendency of the optimal transmission power according to the maximum number of retransmissions. This article can pave the way to efficient design of the AoI-sensitive sensor networks.

Fatal infectious diseases caused by RNA viruses, such as COVID-19, have emerged around the world. RT-PCR is widely employed for virus detection, and its accuracy depends on the primers and probes since RT-PCR can detect a virus only when the primers and probes bind to the target gene of the virus. Most of primer design methods are for a single host and so require a great deal of effort to design for RNA virus detection, including homology tests among the host and all the viruses for the host using BLAST-like tools. Furthermore, they do not consider variant sequences, which are very common in viruses. In this study, we describe VPrimer, a method of designing high-quality primer-probe sets for RNA viruses. VPrimer can find primer-probe sets that cover more than 95% of the variants of a target virus but do not cover any sequences of other viruses or the host. With VPrimer, we found 381,698,582 primer-probe sets for 3,104 RNA viruses. Multiplex PCR assays using the top 2 primer-probe sets suggested by VPrimer usually cover 100% of variants. To address the rapid changes in viral genomes, VPrimer finds the best and up-to-date primer-probe sets incrementally against the most recently reported variants.

Operator fusion is essentially and widely used in a large number of matrix computation systems in science and industry. The existing distributed operator fusion methods focus on only either low communication cost with the risk of out of memory or large-scale processing with high communication cost. We propose a distributed elastic fused operator called Cuboid-based Fused Operator (CFO) that achieves both low communication cost and large-scale processing. We also propose a novel fusion plan generator called Cuboid-based Fusion plan Generator (CFG) that finds a fusion plan to fuse more operators including large-scale matrix multiplication. We implement a fast distributed matrix computation engine called FuseME by integrating both CFO and CFG seamlessly. FuseME outperforms the state-of-the-art systems including SystemDS by orders of magnitude.

Deep neural networks are trained so as to achieve a kind of the maximum overall accuracy through a learning process using given training data. Therefore, it is difficult to fix them to improve the accuracies of specific problematic classes or classes of interest that may be valuable to some users or applications. To address this issue, we propose the synaptic join method to tweak neural networks by adding certain additional synapses from the intermediate hidden layers to the output layer across layers and additionally training only these synapses, if necessary. To select the most effective synapses, the synaptic join method evaluates the performance of all the possible candidate synapses between the hidden neurons and output neurons based on the distribution of all the possible proper weights. The experimental results show that the proposed method can effectively improve the accuracies of specific classes in a controllable way.

Coronavirus disease (COVID-19) caused by severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) has spread around the world with high mortality rates. Since this virus constantly mutating rapidly, it causes different kinds of variants such as the Delta Plus variant, and this variant even dominated the original Delta variant. Thus, designing a new primer-probe set is required to cope with the new variant effectively. However, the existing primer-probe set design tools are also effective in designing for a given sequence, but it is difficult to consider all variants or off-target. Here, we introduce a web-based method for designing and validating primer-probe sets for SARS-CoV-2. Through the web server we built, a user could get results of the binding site matching, homology tests, and variant coverage calculation of the primer-probe set they designed. Moreover, a user also could find the primer-probe sets which bind as many SARS-CoV-2 variants as possible by using the user-input FASTA sequence. We believe that our web service would help researchers by reducing the difficulty of designing primers and probes of SARS-CoV-2.

The Barabási-Albert(BA) model plays an important role in many domains since it can generate a scale-free graph having the degree exponents that real graphs have. However, due to the dependency among the edges generated at different time steps, the exact generation methods support only a single thread, and the parallel generation methods generate a graph only approximately. There is no method that can generate a large-scale graph following the BA model strictly using multiple threads. We propose a fast, exact, and scalable graph generation method called LineageBA that solves the above issue. We propose the concept of lineage relationship for reducing memory usage significantly and the detection of hash collisions for parallelizing the graph generation. Through extensive experiments, we have shown that LineageBA significantly outperforms the state-of-the-art BA graph generation methods and easily generates 2.5 trillion edges within four hours using a small cluster of PCs.

BACKGROUND: Design of valid high-quality primers is essential for qPCR experiments. MRPrimer is a powerful pipeline based on MapReduce that combines both primer design for target sequences and homology tests on off-target sequences. It takes an entire sequence DB as input and returns all feasible and valid primer pairs existing in the DB. Due to the effectiveness of primers designed by MRPrimer in qPCR analysis, it has been widely used for developing many online design tools and building primer databases. However, the computational speed of MRPrimer is too slow to deal with the sizes of sequence DBs growing exponentially and thus must be improved. RESULTS: We develop a fast GPU-based pipeline for primer design (GPrimer) that takes the same input and returns the same output with MRPrimer. MRPrimer consists of a total of seven MapReduce steps, among which two steps are very time-consuming. GPrimer significantly improves the speed of those two steps by exploiting the computational power of GPUs. In particular, it designs data structures for coalesced memory access in GPU and workload balancing among GPU threads and copies the data structures between main memory and GPU memory in a streaming fashion. For human RefSeq DB, GPrimer achieves a speedup of 57 times for the entire steps and a speedup of 557 times for the most time-consuming step using a single machine of 4 GPUs, compared with MRPrimer running on a cluster of six machines. CONCLUSIONS: We propose a GPU-based pipeline for primer design that takes an entire sequence DB as input and returns all feasible and valid primer pairs existing in the DB at once without an additional step using BLAST-like tools. The software is available at https://github.com/qhtjrmin/GPrimer.git .

Cardiac output monitoring plays an important role in intraoperative or intensive care medicine. Arterial pressure waveform derived cardiac output monitoring has been mainly used for real clinical fields despite its inexact output because gold standard thermodilution based cardiac output monitoring is too invasive to use it widely. In this study, we propose DLAPCO, the novel deep learning method for the more accurate and age-agnostic arterial pressure waveform derived cardiac output monitoring. DLAPCO exploits two attention mechanism to calibrate the model's output to medical procedure or overcome the locality of convolutional neural network in analyzing raw vital signs. Through the experiments using the real-world hospital intraoperative data, we have shown that DLAPCO significantly outperforms the commercial arterial pressure waveform derived cardiac output monitoring device which use demographic information.

Under the traditional machine learning that optimizes overall accuracy, the accuracy of a model for similar classes tends to be lower than for other classes. In this paper, we propose a method that can improve the accuracy of such problematic similar classes by adopting the concept of slices. The proposed method can improve the accuracy of slices effectively without degrading the overall accuracy.

The concept of OLAP query processing is now being widely adopted in various applications. The number of complex queries containing the joins between non-unique keys (called FK-FK joins) increases in those applications. However, the existing in-memory OLAP systems tend not to handle such complex queries efficiently since they generate a large amount of intermediate results or incur a huge amount of probe cost. In this paper, we propose an effective query planning method for complex OLAP queries. It generates a query plan containing n-ary join operators based on a cost model. The plan does not generate intermediate results for processing FK-FK joins and significantly reduces the probe cost. We also propose an efficient processing method for n-ary join operators. We implement the prototype system SPRINTER by integrating our proposed methods into an open-source in-memory OLAP system. Through experiments using the TPC-DS benchmark, we have shown that SPRINTER outperforms the state-of-the-art OLAP systems for complex queries.

Matrix computation, in particular, matrix multiplication is time-consuming, but essentially and widely used in a large number of applications in science and industry. The existing distributed matrix multiplication methods only focus on either low communication cost (i.e., high performance) with the risk of out of memory or large-scale processing with high communication overhead. We propose a distributed elastic matrix multiplication method called CuboidMM that achieves both high performance and large-scale processing. We also propose a GPU acceleration method that can be combined with CuboidMM. CuboidMM partitions matrices into cuboids for optimizing the network communication cost with considering memory usage per task, and the GPU acceleration method partitions a cuboid into subcuboids for optimizing the PCI-E communication cost with considering GPU memory usage. We implement a fast and elastic matrix computation engine called DistME by integrating CuboidMM with GPU acceleration on top of Apache Spark. Through extensive experiments, we have demonstrated that CuboidMM and DistME significantly outperform the state-of-the-art methods and systems, respectively, in terms of both performance and data size.

As the amount of data to process increases, a scalable and efficient horizontal database partitioning method becomes more important for OLAP query processing in parallel database platforms. Existing partitioning methods have a few major drawbacks such as a large amount of data redundancy and not supporting join processing without shuffle in many cases despite their large data redundancy. We elucidate the drawbacks arise from their tree-based partitioning schemes and propose a novel graph-based database partitioning method called GPT that improves query performance with lower data redundancy. Through extensive experiments using three benchmarks, we show that GPT significantly outperforms the state-of-the-art method in terms of both storage overhead and query performance.

Nowadays, many researchers and industry groups often suffer from the lack of a variety of large-scale real graphs. Although a lot of synthetic graph generation methods,(or models) such as RMAT and BA have been developed, their output graphs tend to be quite different from real-world graphs in terms of graph properties. There are a few graph upscaling methods such as Gscaler, they still fail to preserve important properties of the original graph and fail to upscale due to out of memory or too long runtime. In this paper, we propose a novel graph upscaling method called EvoGraph that can upscale the original graph with preserving its properties regardless of a scale factor. It determines and attaches new edges to the real graph using the preferential attachment mechanism in an effective and efficient way. Through extensive experiments, we have demonstrated that EvoGraph significantly outperforms the state-of-the-art graph upscaling method Gscaler in terms of preserving graph properties and performance measures such as runtime, memory usage, and scalability.

Frequent itemset mining is widely used as a fundamental data mining technique. However, as the data size increases, the relatively slow performances of the existing methods hinder its applicability. Although many sequential frequent itemset mining methods have been proposed, there is a clear limit to the performance that can be achieved using a single thread. To overcome this limitation, various parallel methods using multi-core CPU, multiple machine, or many-core graphic processing unit (GPU) approaches have been proposed. However, these methods still have drawbacks, including relatively slow performance, data size limitations, and poor scalability due to workload skewness. In this paper, we propose a fast GPU-based frequent itemset mining method called GMiner for large-scale data. GMiner achieves very fast performance by fully exploiting the computational power of GPUs and is suitable for large-scale data. The method performs mining tasks in a counterintuitive way: it mines the patterns from the first level of the enumeration tree rather than storing and utilizing the patterns at the intermediate levels of the tree. This approach is quite effective in terms of both performance and memory use in the GPU architecture. In addition, GMiner solves the workload skewness problem from which the existing parallel methods suffer; as a result, its performance increases almost linearly as the number of GPUs increases. Through extensive experiments, we demonstrate that GMiner significantly outperforms other representative sequential and parallel methods in most cases, by orders of magnitude on the tested benchmarks.

As many applications encounter exponential growth in graph sizes, a fast and scalable graph generator has become more important than ever before due to lack of large-scale realistic graphs for evaluating the performance of graph processing methods. Although there have been proposed a number of methods to generate synthetic graphs, they are not very efficient in terms of space and time complexities, and so, cannot generate even trillion-scale graphs using a moderate size cluster of commodity machines. Here, we propose an efficient and scalable disk-based graph generator, TrillionG that can generate massive graphs in a short time only using a small amount of memory. It can generate a graph of a trillion edges following the RMAT or Kronecker models within two hours only using 10 PCs. We first generalize existing graph generation models to the scope-based generation model, where RMAT and Kronecker correspond to two extremes. Then, we propose a new graph generation model called the recursive vector model, which compromises two extremes, and so, solves the space and time complexity problems existing in RMAT and Kronecker. We also extend the recursive vector model so as to generate a semantically richer graph database. Through extensive experiments, we have demonstrated that TrillionG outperforms the state-of-the-art graph generators by up to orders of magnitude.

Computing connected components (CC) is a core operation on graph data. Since billion-scale graphs cannot be resident in memory of a single machine, there have been proposed a number of distributed graph processing methods. The representative ones for CC are Hash-To-Min and PowerGraph. Hash-To-Min focuses on minimizing the number of MapReduce rounds, but is still slower than in-memory methods, PowerGraph is a fast and general in-memory graph method, but requires a lot of machines for handling billion-scale graphs. We propose an ultra-fast parallel method DSP-CC, using only a single PC that exploits secondary storage like a PCI-E SSD for handling billion-scale graphs. It can compute connected components I/O efficiently using only a limited size of memory. Our experimental results show that DSP-CC significantly outperforms the representative methods including Hash-To-Min and PowerGraph.

A fast and scalable graph processing method becomes increasingly important as graphs become popular in a wide range of applications and their sizes are growing rapidly. Most of distributed graph processing methods require a lot of machines equipped with a total of thousands of CPU cores and a few terabyte main memory for handling billion-scale graphs. Meanwhile, GPUs could be a promising direction toward fast processing of large-scale graphs by exploiting thousands of GPU cores. All of the existing methods using GPUs, however, fail to process large-scale graphs that do not fit in main memory of a single machine. Here, we propose a fast and scalable graph processing method GTS that handles even RMAT32 (64 billion edges) very efficiently only by using a single machine. The proposed method stores graphs in PCI-E SSDs and executes a graph algorithm using thousands of GPU cores while streaming topology data of graphs to GPUs via PCI-E interface. GTS is fast due to no communication overhead and scalable due to no data duplication from graph partitioning among machines. Through extensive experiments, we show that GTS consistently and significantly outperforms the major distributed graph processing methods, GraphX, Giraph, and PowerGraph, and the state-of-the-art GPU-based method TOTEM.

Fast processing graph algorithms for large-scale graphs becomes increasingly important. Besides, there have been many attempts to process graph applications by exploiting the massive amount of parallelism of GPUs. However, most of the existing methods fail to process large-scale graphs that do not fit in GPU device memory. We propose a fast and scalable parallel processing method GStream that fully exploits the computational power of GPUs for processing large-scale graphs (e.g., billions vertices) very efficiently. It exploits the concept of nested-loop theta-join and multiple asynchronous GPU streams. Extensive experimental results show that GStream consistently and significantly outperforms the state-of-the art method.

Computing connected components is a core operation on graph data. Since billion-scale graphs cannot be resident in memory of a single server, several approaches based on distributed machines have recently been proposed. The representative methods are$\mathsf{Hash\hbox{-}To\hbox{-}Min}$and$\mathsf{PowerGraph}$.$\mathsf{Hash\hbox{-}To\hbox{-}Min}$is the state-of-the artdisk-baseddistributed method which minimizes the number of MapReduce rounds.$\mathsf{PowerGraph}$is the-state-of-the-artin-memorydistributed system, which is typically faster than the disk-based distributed one, however, requires a lot of machines for handling billion-scale graphs. In this paper, we propose an I/O efficient parallel algorithm for billion-scale graphs in a single PC. We first propose theDisk-based Sequential access-oriented Parallel processing(DSP) model that exploits sequential disk access in terms of disk I/Os and parallel processing in terms of computation. We then propose an ultra-fast disk-based parallel algorithm for computing connected components,$\mathsf{DSP\hbox{-}CC}$, which largely improves the performance through sequential disk scan andpage-level cache-conscious parallel processing. Extensive experimental results show that$\mathsf{DSP\hbox{-}CC}$1) computes connected components in billion-scale graphs using the limited memory size whereas in-memory algorithms can only support medium-sized graphs with the same memory size, and 2) significantly outperforms all distributed competitors as well as a representative disk-based parallel method.

Compression has historically been used to reduce the cost of storage, I/Os from that storage, and buffer pool utilization, at the expense of the CPU required to decompress data every time it is queried. However, significant additional CPU efficiencies can be achieved by deferring decompression as late in query processing as possible and performing query processing operations directly on the still-compressed data. In this paper, we investigate the benefits and challenges of performing joins on compressed (or encoded) data. We demonstrate the benefit of independently optimizing the compression scheme of each join column, even though join predicates relating values from multiple columns may require translation of the encoding of one join column into the encoding of the other. We also show the benefit of compressing "payload" data other than the join columns "on the fly," to minimize the size of hash tables used in the join. By partitioning the domain of each column and defining separate dictionaries for each partition, we can achieve even better overall compression as well as increased flexibility in dealing with new values introduced by updates. Instead of decompressing both join columns participating in a join to resolve their different compression schemes, our system performs a light-weight mapping of only qualifying rows from one of the join columns to the encoding space of the other at run time. Consequently, join predicates can be applied directly on the compressed data. We call this procedure encoding translation. Two alternatives of encoding translation are developed and compared in the paper. We provide a comprehensive evaluation of these alternatives using product implementations of each on the TPC-H data set, and demonstrate that performing joins on encoded and partitioned data achieves both superior performance and excellent compression.

Graphs are used to model many real objects such as social networks and web graphs. Many real applications in various fields require efficient and effective management of large-scale graph structured data. Although distributed graph engines such as GBase and Pregel handle billion-scale graphs, the user needs to be skilled at managing and tuning a distributed system in a cluster, which is a nontrivial job for the ordinary user. Furthermore, these distributed systems need many machines in a cluster in order to provide reasonable performance. In order to address this problem, a disk-based parallel graph engine called Graph-Chi, has been recently proposed. Although Graph-Chi significantly outperforms all representative (disk-based) distributed graph engines, we observe that Graph-Chi still has serious performance problems for many important types of graph queries due to 1) limited parallelism and 2) separate steps for I/O processing and CPU processing. In this paper, we propose a general, disk-based graph engine called TurboGraph to process billion-scale graphs very efficiently by using modern hardware on a single PC. TurboGraph is the first truly parallel graph engine that exploits 1) full parallelism including multi-core parallelism and FlashSSD IO parallelism and 2) full overlap of CPU processing and I/O processing as much as possible. Specifically, we propose a novel parallel execution model, called pin-and-slide. TurboGraph also provides engine-level operators such as BFS which are implemented under the pin-and-slide model. Extensive experimental results with large real datasets show that TurboGraph consistently and significantly outperforms Graph-Chi by up to four orders of magnitude! Our implementation of TurboGraph is available at ``http://wshan.net/turbograph}" as executable files.

Conventional object-relational database management system (ORDBMS) vendors provide extension mechanisms for adding user-defined types and functions to their own DBMSs. Here, the extension mechanisms are implemented using a high-level (typically, SQL-level) interface. We call this mechanism loose-coupling . The advantage of loose-coupling is that it is easy to implement. However, it is not preferable for implementing new data types and operations in large databases when high performance is required. We have earlier proposed the tight-coupling architecture (Whang et al. 2002 , 2005 ) to satisfy this requirement. In tight-coupling , new data types and operations are integrated into the core of the DBMS engine in the extensible type layer . Thus, they are supported in a consistent manner with high performance. This tight-coupling architecture is being used to incorporate information retrieval features and spatial database features into the Odysseus ORDBMS that has been under development at KAIST/AITrc for 19 years. In this paper, we introduce the tightly-coupled spatial database features of Odysseus/OpenGIS. By taking advantage of tight-coupling, Odysseus/OpenGIS provides excellent performance in processing spatial queries as well as flexible concurrency control and recovery on spatial data. We show the performance through extensive experiments. Finally, we present sample applications of a geographical information system (GIS) implemented using Odysseus/OpenGIS.

Recently, dynamic networks are attracting increasing interest due to their high potential in capturing natural and social phenomena over time. Discovery of evolutionary communities in dynamic networks has become a critical task. The previous evolutionary clustering methods usually adopt the temporal smoothness framework, which has a desirable feature of controlling the balance between temporal noise and true concept drift of communities. They, however, have some major drawbacks: (1) assuming only a fixed number of communities over time; and (2) not allowing arbitrary start/stop of community over time. The forming of new communities and dissolving of existing communities are very common phenomena in real dynamic networks. In this paper, we propose a new particle-and-density based evolutionary clustering method that efficiently discovers a variable number of communities of arbitrary forming and dissolving. We first model a dynamic network as a collection of lots of particles called nano-communities , and a community as a densely connected subset of particles, called a quasi l-clique-by-clique (shortly, l-KK ). Each particle contains a small amount of information about the evolution of data or patterns, and the quasi l-KK s inherent in a given dynamic network provide us with guidance on how to find a variable number of communities of arbitrary forming and dissolving. We propose a density-based clustering method that efficiently finds temporally smoothed local clusters of high quality by using a cost embedding technique and optimal modularity. We also propose a mapping method based on information theory that makes sequences of smoothed local clusters as close as possible to data-inherent quasi l-KK s. The result of the mapping method allows us to easily identify the stage of each community among the three stages: evolving, forming , and dissolving . Experimental studies, by using various data sets, demonstrate that our method improves the clustering accuracy, and at the same time, the time performance by an order of magnitude compared with the current state-of-the art method.

We have earlier proposed the tight-coupling architecture for adding new data types into the DBMS engine. In this paper, we introduce the Odysseus ORDBMS and present its tightly-coupled spatial database features. We demonstrate a geographical information system(GIS) implemented using Odysseus.

We propose the notion of tight-coupling [K. Whang et al., (1999)] to add new data types into the DBMS engine. In this paper, we introduce the Odysseus ORDBMS and present its tightly-coupled IR features (US patented). We demonstrate a Web search engine capable of managing 20 million Web pages in a non-parallel configuration using Odysseus.