A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases

In this paper, an algorithm is proposed for subsequence matching that supports normalization transform in time-series databases. Normalization transform enables finding sequences with similar fluctuation patterns even though they are not close to each other before the normalization transform. Simple application of existing subsequence matching algorithms to support normalization transform is not feasible since the algorithms do not have information for normalization transform of subsequences of arbitrary lengths. Application of the existing whole matching algorithm supporting normalization transform to the subsequence matching is feasible, but requires an index for every possible length of the query sequence causing serious overhead on both storage space and update time. The proposed algorithm generates indexes only for a small number of different lengths of query sequences. For subsequence matching it selects the most appropriate index among them. Better search performance can be obtained by using more indexes. In this paper, the approach is called index interpolation. It is formally proved that the proposed algorithm does not cause false dismissal. The search performance can be traded off with storage space by adjusting the number of indexes. For performance evaluation, a series of experiments is conducted using the indexes for only five different lengths out of lengths 256512 of the query sequence. The results show that the proposed algorithm outperforms the sequential scan by up to 2.4 times on the average when the selectivity of the query is 10^–2 and up to 14.6 times when it is 10^–5. Since the proposed algorithm performs better with smaller selectivities, it is suitable for practical situations, where the queries with smaller selectivities are much more frequent.     

Efficient exact k-flexible aggregate nearest neighbor search in road networks using the M-tree

The Journal of Supercomputing - This study proposes an efficient exact k-flexible aggregate nearest neighbor (k-FANN) search algorithm in road networks using the M-tree. The state-of-the-art...     

Efficient Flexible M-Tree Bulk Loading Using FastMap and Space-Filling Curves

Many database applications currently deal with objects in a metric space. Examples of such objects include unstructured multimedia objects and points of interest (POIs) in a road network. The M-tree is a dynamic index structure that facilitates an efficient search for objects in a metric space. Studies have been conducted on the bulk loading of large datasets in an M-tree. However, because previous algorithms involve excessive distance computations and disk accesses, they perform poorly in terms of their index construction and search capability. This study proposes two efficient M-tree bulk loading algorithms. Our algorithms minimize the number of distance computations and disk accesses using FastMap and a space-filling curve, thereby significantly improving the index construction and search performance. Our second algorithm is an extension of the first, and it incorporates a partitioning clustering technique and flexible node architecture to further improve the search performance. Through the use of various synthetic and real-world datasets, the experimental results demonstrated that our algorithms improved the index construction performance by up to three orders of magnitude and the search performance by up to 20.3 times over the previous algorithm.     

Mining temporal patterns in popularity of web items

Huge amounts of various web items (e.g., images, keywords, and web pages) are being made available on the Web. The popularity of such web items continuously changes over time, and mining for temporal patterns in the popularity of web items is an important problem that is useful for several Web applications; for example, the temporal patterns in the popularity of web search keywords help web search enterprises predict future popular keywords, thus enabling them to make price decisions when marketing search keywords to advertisers. However, the presence of millions of web items makes it difficult to scale up previous techniques for this problem. This paper proposes an efficient method for mining temporal patterns in the popularity of web items. We treat the popularity of web items as time-series and propose a novel measure, a gap measure, to quantify the dissimilarity between the popularity of two web items. To reduce the computational overhead for this measure, an efficient method using the Discrete Fourier Transform (DFT) is presented. We assume that the popularity of web items is not necessarily periodic. For finding clusters of web items with similar popularity trends, we show the limitations of traditional clustering approaches and propose a scalable, efficient, density-based clustering algorithm using the gap measure. Our experiments using the popularity trends of web search keywords obtained from the Google Trends web site illustrate the scalability and usefulness of the proposed approach in real-world applications.     

Deep Learning in DXA Image Segmentation

Many existing techniques to acquire dual-energy X-ray absorptiometry (DXA) images are unable to accurately distinguish between bone and soft tissue. For the most part, this failure stems from bone shape variability, noise and low contrast in DXA images, inconsistent X-ray beam penetration producing shadowing effects, and person-to-person variations. This work explores the feasibility of using state-of-the-art deep learning semantic segmentation models, fully convolutional networks (FCNs), SegNet, and U-Net to distinguish femur bone from soft tissue. We investigated the performance of deep learning algorithms with reference to some of our previously applied conventional image segmentation techniques (i.e., a decision-tree-based method using a pixel label decision tree [PLDT] and another method using Otsu’s thresholding) for femur DXA images, and we measured accuracy based on the average Jaccard index, sensitivity, and specificity. Deep learning models using SegNet, U-Net, and an FCN achieved average segmentation accuracies of 95.8%, 95.1%, and 97.6%, respectively, compared to PLDT (91.4%) and Otsu’s thresholding (72.6%). Thus we conclude that an FCN outperforms other deep learning and conventional techniques when segmenting femur bone from soft tissue in DXA images. Accurate femur segmentation improves bone mineral density computation, which in turn enhances the diagnosing of osteoporosis.     

Artificial Intelligence-Based Semantic Segmentation of Ocular Regions for Biometrics and Healthcare Applications

Multiple ocular region segmentation plays an important role in different applications such as biometrics, liveness detection, healthcare, and gaze estimation. Typically, segmentation techniques focus on a single region of the eye at a time. Despite the number of obvious advantages, very limited research has focused on multiple regions of the eye. Similarly, accurate segmentation of multiple eye regions is necessary in challenging scenarios involving blur, ghost effects low resolution, off-angles, and unusual glints. Currently, the available segmentation methods cannot address these constraints. In this paper, to address the accurate segmentation of multiple eye regions in unconstrainted scenarios, a lightweight outer residual encoder-decoder network suitable for various sensor images is proposed. The proposed method can determine the true boundaries of the eye regions from inferior-quality images using the high-frequency information flow from the outer residual encoder-decoder deep convolutional neural network (called ORED-Net). Moreover, the proposed ORED-Net model does not improve the performance based on the complexity, number of parameters or network depth. The proposed network is considerably lighter than previous state-of-theart models. Comprehensive experiments were performed, and optimal performance was achieved using SBVPI and UBIRIS.v2 datasets containing images of the eye region. The simulation results obtained using the proposed OREDNet, with the mean intersection over union score (mIoU) of 89.25 and 85.12 on the challenging SBVPI and UBIRIS.v2 datasets, respectively.     

Type-level access pattern view: Enhancing prefetching performance using the iterative and recursive patterns

Since recent applications such as XML applications, Geographical Information Systems (GIS), and CAD/CAM systems require highly efficient data management, they are built on Object-Relational DBMS (ORDBMS). The applications are called navigational applications, and they navigate the composite objects connected via the reference and the collection attributes in the ORDBMS. When a navigational application accesses an object, it first checks whether the object is stored in the object cache. If not, the object must be fetched from the database in the server, which is a costly operation. Prefetching identifies the objects that are most likely to be accessed in the near future by the navigational applications and stores them in the object cache in advance. Since prefetching reduces the number of object fetches, it is crucial for improving the application performance. However, the experimental result by Han et al. [16] showed that the improvement ratio of application performance is much lower than the reduction ratio of the number of object fetches.In this paper, we claim that the number of disk accesses in the server also considerably affects the application performance, and we propose a technique for minimizing disk accesses to improve the performance of the prefetch method by Han et al. [16] and hence the navigational application. The contributions of this paper are summarized as follows. (1) For the iterative and the recursive patterns, we propose methods for creating materialized views based on the type-level path access logs proposed in [15]. We refer to the materialized views as the type-level access pattern views. (2) We then present the algorithms for minimizing the number of disk accesses using the type-level access pattern views when prefetching the objects from the database in the server. (3) We present an implementation technique that, given a prefetch request from the client, quickly finds the most efficient type-level access pattern view. (4) We perform a series of experiments using a variety of databases to show that the proposed technique significantly improves the overall performance of the navigational application. Experimental result shows that we reduce the number of disk accesses by up to 33.0 times and improve the performance by up to 21.4 times.