Search

Bilevel optimization refers to a specialized class of problems where the optimum of an upper level (UL) problem is sought subject to the optimality of a nested lower level (LL) problem as a constraint. This nested structure necessitates a large number of function evaluations for the solution methods, especially population-based metaheuristics such as evolutionary algorithms (EAs). Reducing this effort remains critical for practical uptake of bilevel EAs, particularly for computationally expensive problems where each solution evaluation may involve a significant cost. This letter aims to contribute toward this field by a novel and previously unexplored proposition that bilevel optimization problems can be posed as multifidelity optimization problems. The underpinning idea is that an informed judgment of how accurate the LL optimum estimate should be to confidently determine its ranking can significantly cut down redundant evaluations during the search. Toward this end, we propose an algorithm which learns the appropriate fidelity to evaluate a solution during the search based on the seen data, instead of resorting to an exhaustive LL optimization. Numerical experiments are conducted on a range of standard as well as more complex variants of the SMD test problems to demonstrate the advantages of the proposed approach when compared to state-of-the-art surrogate-assisted algorithms. [ABSTRACT FROM AUTHOR]

Graphs are a ubiquitous data structure to model processes and relations in a wide range of domains. Examples include control-flow graphs in programs and semantic scene graphs in images. Identifying subgraph patterns in graphs is an important approach to understand their structural properties. We propose a visual analytics system GraphQ to support human-in-the-loop, example-based, subgraph pattern search in a database containing many individual graphs. To support fast, interactive queries, we use graph neural networks (GNNs) to encode a graph as fixed-length latent vector representation, and perform subgraph matching in the latent space. Due to the complexity of the problem, it is still difficult to obtain accurate one-to-one node correspondences in the matching results that are crucial for visualization and interpretation. We, therefore, propose a novel GNN for node-alignment called NeuroAlign, to facilitate easy validation and interpretation of the query results. GraphQ provides a visual query interface with a query editor and a multi-scale visualization of the results, as well as a user feedback mechanism for refining the results with additional constraints. We demonstrate GraphQ through two example usage scenarios: analyzing reusable subroutines in program workflows and semantic scene graph search in images. Quantitative experiments show that NeuroAlign achieves 19%-29% improvement in node-alignment accuracy compared to baseline GNN and provides up to 100× speedup compared to combinatorial algorithms. Our qualitative study with domain experts confirms the effectiveness for both usage scenarios. [ABSTRACT FROM AUTHOR]

Levenshtein edit distance has played a central role—both past and present—in sequence alignment in particular and biological database similarity search in general. We start our review with a history of dynamic programming algorithms for computing Levenshtein distance and sequence alignments. Following, we describe how those algorithms led to heuristics employed in the most widely used software in bioinformatics, BLAST, a program to search DNA and protein databases for evolutionarily relevant similarities. More recently, the advent of modern genomic sequencing and the volume of data it generates has resulted in a return to the problem of local alignment. We conclude with how the mathematical formulation of Levenshtein distance as a metric made possible additional optimizations to similarity search in biological contexts. These modern optimizations are built around the low metric entropy and fractional dimensionality of biological databases, enabling orders of magnitude acceleration of biological similarity search. [ABSTRACT FROM AUTHOR]

Low temperature cofired ceramic (LTCC) ridge waveguide filters are attractive candidates in implementing microwave filters in modern communication systems because of their competitive features, such as low loss, low cost, compact size, lightweight, high-power handling capability, wide spurious-free out-of-band response, and easy integration. However, optimization of LTCC ridge waveguide filters suffers from low speed or imperfect accuracy when the traditional full-wave simulation or the mode-matching method is utilized for analysis. This article makes research on an alternative analysis method based on the network theory for LTCC inline ridge waveguide filters. The method has high speed since it evaluates filter properties by simply making the cumulative product of transfer matrices of all constitutive laminated ridge waveguide (LRWG) sections and laminated coupling (LCP) sections according to their arranging sequence, and transfer matrices of all these sections are calculated from their characteristic parameters (transmission line or equivalent circuit parameters for LRWG or LCP sections) analytically. Another key feature of the method is that all characteristic parameters of LRWG and LCP sections are obtained by searching precreated database. In order to guarantee the analysis accuracy, two special strategies have been proposed and utilized. First, accurate extraction methods of characteristic parameters have been introduced and applied to the creation of a database for LRWG and LCP sections. Second, a piecewise interpolation scheme has been designed and adopted in the database searching process for both kinds of sections. The efficiency of the promoted analysis method has been verified by two analysis examples of LTCC LRWG filters. One is a three-order narrow-band filter and the other is a nine-order wide-band filter. The curves of scattering parameters calculated using the promoted method agree well with the simulated curves and the time consumed by the method is negligible when compared with the simulation time. The effectiveness of the proposed analysis method in filter design is also briefly introduced in this article. [ABSTRACT FROM AUTHOR]

Given a set of objects $O$O (such as hotels), each can be represented as a point in a multi-dimensional feature space where each dimension corresponds to one attribute of the objects (such as price). Given the preference of a customer, the objects in $O$O not dominated by any other object (i.e., beat in all dimensions) are those worthy to be further considered. Such objects are known as skyline objects in database community. Suppose we have an object $o\in O$o∈O. If $o$o is a skyline point, other skyline objects are called peers of $o$o. If $o$o is not a skyline object, it must be dominated by some skyline objects which are called dominators of $o$o. Given a large number of user preferences, an interesting problem is to identify the most frequent peer/dominator (MFP/MFD) of $o$o. The MFP/MFD search has unique values in competitor analysis of various information systems. However, it is a challenging task because of the complexity to process a large number of user preferences. In this work, we provide robust solutions including exact and approximate methods. While the exact solutions explore the dominance relationship in the feature space, the approximate solutions are based on sampling techniques with theoretical bounds. We did extensive tests on large data sets which are up to 100 million user preferences generated from commercial surveys. The test resutls demonstrate the exact algorithms outperform various baseline algorithms significantly, and the approximate algorithms make further improvement by one order of magnitude with 90-98 percent accuracy. [ABSTRACT FROM AUTHOR]

Outsourcing data and computation to cloud server provides a cost-effective way to support large scale data storage and query processing. However, due to security and privacy concerns, sensitive data (e.g., medical records) need to be protected from the cloud server and other unauthorized users. One approach is to outsource encrypted data to the cloud server and have the cloud server perform query processing on the encrypted data only. It remains a challenging task to support various queries over encrypted data in a secure and efficient way such that the cloud server does not gain any knowledge about the data, query, and query result. In this paper, we study the problem of secure skyline queries over encrypted data. The skyline query is particularly important for multi-criteria decision making but also presents significant challenges due to its complex computations. We propose a fully secure skyline query protocol on data encrypted using semantically-secure encryption. As a key subroutine, we present a new secure dominance protocol, which can be also used as a building block for other queries. Furthermore, we demonstrate two optimizations, data partitioning and lazy merging, to further reduce the computation load. Finally, we provide both serial and parallelized implementations and empirically study the protocols in terms of efficiency and scalability under different parameter settings, verifying the feasibility of our proposed solutions. [ABSTRACT FROM AUTHOR]

A well-established technique for capturing database provenance as annotations on data is to instrument queries to propagate such annotations. However, even sophisticated query optimizers often fail to produce efficient execution plans for instrumented queries. We develop provenance-aware optimization techniques to address this problem. Specifically, we study algebraic equivalences targeted at instrumented queries and alternative ways of instrumenting queries for provenance capture. Furthermore, we present an extensible heuristic and cost-based optimization framework utilizing these optimizations. Our experiments confirm that these optimizations are highly effective, improving performance by several orders of magnitude for diverse provenance tasks. [ABSTRACT FROM AUTHOR]

Mining frequent subgraphs from a collection of input graphs is an important task for exploratory data analysis on graph data. However, if the input graphs contain sensitive information, releasing discovered frequent subgraphs may pose considerable threats to individual privacy. In this paper, we study the problem of frequent subgraph mining (FSM) under the rigorous differential privacy model. We present a two-phase differentially private FSM algorithm, which is referred to as DFG. In DFG, frequent subgraphs are privately identified in the first phase, and the noisy support of each identified frequent subgraph is calculated in the second phase. In particular, to privately identity frequent subgraphs, we propose a frequent subgraph identification approach, which can improve the accuracy of discovered frequent subgraphs through candidate pruning. Moreover, to compute the noisy support of each identified frequent subgraph, we devise a lattice-based noisy support computation approach, which leverages the inclusion relations between the discovered frequent subgraphs to improve the accuracy of the noisy supports. Through formal privacy analysis, we prove that DFG satisfies $\epsilon$ -differential privacy. Extensive experimental results on real datasets show that DFG can privately find frequent subgraphs while achieving high data utility. [ABSTRACT FROM AUTHOR]

Searchable Symmetric Encryption (SSE) has been widely studied in cloud storage, which allows cloud services to directly search over encrypted data. Most SSE schemes only work with honest-but-curious cloud services that do not deviate from the prescribed protocols. However, this assumption does not always hold in practice due to the untrusted nature in storage outsourcing. To alleviate the issue, there have been studies on Verifiable Searchable Symmetric Encryption (VSSE), which functions against malicious cloud services by enabling results verification. But to our best knowledge, existing VSSE schemes exhibit very limited applicability, such as only supporting static database, demanding specific SSE constructions, or only working in the single-user model. In this paper, we propose GSSE, the first generic verifiable SSE scheme in the single-owner multiple-user model, which provides verifiability for any SSE schemes and further supports data updates. To generically support result verification, we first decouple the proof index in GSSE from SSE. We then leverage Merkle Patricia Tree (MPT) and Incremental Hash to build the proof index with data update support. We also develop a timestamp-chain for data freshness maintenance across multiple users. Rigorous analysis and experimental evaluations show that GSSE is secure and introduces small overhead for result verification. [ABSTRACT FROM AUTHOR]

Multivariate event sequences are ubiquitous: travel history, telecommunication conversations, and server logs are some examples. Besides standard properties such as type and timestamp, events often have other associated multivariate data. Current exploration and analysis methods either focus on the temporal analysis of a single attribute or the structural analysis of the multivariate data only. We present an approach where users can explore event sequences at multivariate and sequential level simultaneously by interactively defining a set of rewrite rules using multivariate regular expressions. Users can store resulting patterns as new types of events or attributes to interactively enrich or simplify event sequences for further investigation. In Eventpad we provide a bottom-up glyph-oriented approach for multivariate event sequence analysis by searching, clustering, and aligning them according to newly defined domain specific properties. We illustrate the effectiveness of our approach with real-world data sets including telecommunication traffic and hospital treatments. [ABSTRACT FROM PUBLISHER]

Set queries are fundamental operations in computer networks. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a shifting bloom filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF-based set data structures allocate additional memory to store auxiliary information. We further extend our shifting framework from BF-based data structures to sketch-based data structures, which are widely used to store multiplicities of items. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries. [ABSTRACT FROM PUBLISHER]

Though many tasks in computer vision can be formulated elegantly as pixel-labeling problems, a typical challenge discouraging such a discrete formulation is often due to computational efficiency. Recent studies on fast cost volume filtering based on efficient edge-aware filters provide a fast alternative to solve discrete labeling problems, with the complexity independent of the support window size. However, these methods still have to step through the entire cost volume exhaustively, which makes the solution speed scale linearly with the label space size. When the label space is huge or even infinite, which is often the case for (subpixel-accurate) stereo and optical flow estimation, their computational complexity becomes quickly unacceptable. Developed to search approximate nearest neighbors rapidly, the PatchMatch method can significantly reduce the complexity dependency on the search space size. But, its pixel-wise randomized search and fragmented data access within the 3D cost volume seriously hinder the application of efficient cost slice filtering. This paper presents a generic and fast computational framework for general multi-labeling problems called PatchMatch Filter (PMF). We explore effective and efficient strategies to weave together these two fundamental techniques developed in isolation, i.e., PatchMatch-based randomized search and efficient edge-aware image filtering. By decompositing an image into compact superpixels, we also propose superpixel-based novel search strategies that generalize and improve the original PatchMatch method. Further motivated to improve the regularization strength, we propose a simple yet effective cross-scale consistency constraint, which handles labeling estimation for large low-textured regions more reliably than a single-scale PMF algorithm. Focusing on dense correspondence field estimation in this paper, we demonstrate PMF’s applications in stereo and optical flow. Our PMF methods achieve top-tier correspondence accuracy but run much faster than other related competing methods, often giving over 10-100 times speedup. [ABSTRACT FROM AUTHOR]

This paper presents an intra line copy (ILC) technique for HEVC screen content coding. It shares the same origin with two other prominent techniques, intra string copy (ISC) and intra block copy (IBC), in applying the notion of string matching to intra-frame coding. This work combines their merits in one scheme with both good compression performance and high regularity. Specifically, it forms a prediction of a coding block by decomposing it into horizontal or vertical lines of pixels and performing line-based predictions based on previously coded data from the current frame. To address the massive amounts of search operations, our fast search algorithm first searches in the horizontal and vertical directions, then checks line vector candidates from spatial and temporal neighbors, and finally references lines having an identical hash value as the prediction line. The resulting line vectors are further predicted adaptively to minimize their coding overhead. Extensive experiments based on SCM-4.0, which includes IBC as an integral component, show that ILC can provide an additional 4%–7% BD-rate savings when the search area extends to the entire frame and 3%–4% improvements with a restricted local search. Compared with ISC, it achieves comparable performance without all its complications from sequential string parsing. [ABSTRACT FROM PUBLISHER]

Industry's inability to reduce logic gates' energy consumption is slowing growth in an important part of the worldwide economy. Some scientists argue that alternative approaches could greatly reduce energy consumption. These approaches entail myriad technical and political issues. [ABSTRACT FROM PUBLISHER]

Contrary to the notion that all big data can be processed in "the cloud," each cloud is tied to one or more datacenters, and cloud implementation details matter when data must be distributed over multiple centers. In these cases, approaches are needed to optimize the application's execution path. [ABSTRACT FROM PUBLISHER]

It's time to rethink search and how we interact with information objects to enable a more intuitive discovery of new knowledge. [ABSTRACT FROM PUBLISHER]

In this paper, we present the most recent results on the development of magnonic holographic memory (MHM). MHM is a type of holographic device, which uses spin waves for data transfer and processing. The most appealing properties of MHM include parallel read-out and database search. We present experimental data showing parallel read-out of four magnetic memory states. In this experiment, the internal magnetic state is recognized by the level of the output inductive voltage produced by the spin-wave interference. We also present the experimental data showing database search in the MHM. In this experiment, the search for the maximum output is accomplished by utilizing spin-wave superposition. The experiments were carried out for six- and eight-terminal yttrium iron garnet-based prototypes. Potentially, magnonic holographic devices can be implemented as complementary memory/logic units to digital processors. Physical limitations and technological constraints of the spin-wave approach are also discussed. [ABSTRACT FROM PUBLISHER]

Class evolution, the phenomenon of class emergence and disappearance, is an important research topic for data stream mining. All previous studies implicitly regard class evolution as a transient change, which is not true for many real-world problems. This paper concerns the scenario where classes emerge or disappear gradually. A class-based ensemble approach, namely Class-Based ensemble for Class Evolution (CBCE), is proposed. By maintaining a base learner for each class and dynamically updating the base learners with new data, CBCE can rapidly adjust to class evolution. A novel under-sampling method for the base learners is also proposed to handle the dynamic class-imbalance problem caused by the gradual evolution of classes. Empirical studies demonstrate the effectiveness of CBCE in various class evolution scenarios in comparison to existing class evolution adaptation methods. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a hybrid iterated local search (ILS) heuristic, named GPP4G-ILS, to solve the global planning problem of survivable wireless networks. The planning problem of wireless networks is to determine a set of sites among potential sites to install the various network devices in order to cover a given geographical area. It should also make the connections between the devices in accordance with well-defined constraints. The global planning consists in solving this problem without dividing it into several subproblems. The objective is to minimize the cost of the network while maximizing its survivability. The GPP4G-ILS algorithm is a new form of hybridization between the ILS algorithm and the integer linear programing (ILP) method. We propose a configuration that allows to reuse a previously developed ILP algorithm by integrating it in the ILS algorithm. This allows to benefit from the advantages of both methods. The ILS algorithm is used to effectively explore the search space, while the ILP algorithm is used to intensify the solutions obtained. The performance of the algorithm was evaluated using an exact method that generates optimal solutions for small instances. For larger instances, lower bounds have been calculated using a relaxation of the problem. The results show that the proposed algorithm is able to reach solutions that are, on average, within 0.06% of the optimal solutions and 2.43% from the lower bounds for the instances that cannot be solved optimally, within a reduced computation time. [ABSTRACT FROM AUTHOR]

This paper proposes a new constrained directed graph clustering (DGC) method and segmentation propagation method for the multiple foreground cosegmentation. We solve the multiple object cosegmentation with the perspective of classification and propagation, where the classification is used to obtain the object prior of each class and the propagation is used to propagate the prior to all images. In our method, the DGC method is designed for the classification step, which adds clustering constraints in cosegmentation to prevent the clustering of the noise data. A new clustering criterion such as the strongly connected component search on the graph is introduced. Moreover, a linear time strongly connected component search algorithm is proposed for the fast clustering performance. Then, we extract the object priors from the clusters, and propagate these priors to all the images to obtain the foreground maps, which are used to achieve the final multiple objects extraction. We verify our method on both the cosegmentation and clustering tasks. The experimental results show that the proposed method can achieve larger accuracy compared with both the existing cosegmentation methods and clustering methods. [ABSTRACT FROM AUTHOR]

Systematic defects within integrated circuits (ICs) are a significant source of failures in nanoscale technologies. Identification of systematic defects is therefore very important for yield improvement. This paper discusses a diagnosis-driven systematic defect identification methodology that we call layout analysis for systematic IC-defect identification using clustering (LASIC). By clustering images of the layout locations that correspond to diagnosed sites for a statistically large number of IC failures, LASIC uncovers the common layout features. To reduce computation time, only the dominant coefficients of a discrete cosine transform analysis of the layout images are used for clustering. LASIC is applied to an industrial chip and it is found to be effective. In addition, detailed simulations reveal that LASIC is both accurate and effective. [ABSTRACT FROM PUBLISHER]

Recently, there has been a growing interest in designing differentially private data mining algorithms. Frequent itemset mining (FIM) is one of the most fundamental problems in data mining. In this paper, we explore the possibility of designing a differentially private FIM algorithm which can not only achieve high data utility and a high degree of privacy, but also offer high time efficiency. To this end, we propose a differentially private FIM algorithm based on the FP-growth algorithm, which is referred to as PFP-growth. The PFP-growth algorithm consists of a preprocessing phase and a mining phase. In the preprocessing phase, to improve the utility and privacy tradeoff, a novel smart splitting method is proposed to transform the database. For a given database, the preprocessing phase needs to be performed only once. In the mining phase, to offset the information loss caused by transaction splitting, we devise a run-time estimation method to estimate the actual support of itemsets in the original database. In addition, by leveraging the downward closure property, we put forward a dynamic reduction method to dynamically reduce the amount of noise added to guarantee privacy during the mining process. Through formal privacy analysis, we show that our PFP-growth algorithm is $\epsilon$ -differentially private. Extensive experiments on real datasets illustrate that our PFP-growth algorithm substantially outperforms the state-of-the-art techniques. [ABSTRACT FROM PUBLISHER]

Searching visual objects in large image or video data sets is a challenging problem, because it requires efficient matching and accurate localization of query objects that often occupy a small part of an image. Although spatial context has been shown to help produce more reliable detection than methods that match local features individually, how to extract appropriate spatial context remains an open problem. Instead of using fixed-scale spatial context, we propose a randomized approach to deriving spatial context, in the form of spatial random partition. The effect of spatial context is achieved by averaging the matching scores over multiple random patches. Our approach offers three benefits: 1) the aggregation of the matching scores over multiple random patches provides robust local matching; 2) the matched objects can be directly identified on the pixelwise confidence map, which results in efficient object localization; and 3) our algorithm lends itself to easy parallelization and also allows a flexible tradeoff between accuracy and speed through adjusting the number of partition times. Both theoretical studies and experimental comparisons with the state-of-the-art methods validate the advantages of our approach. [ABSTRACT FROM PUBLISHER]

Functional diagnosis for complex systems can be a very time-consuming and expensive task, trying to identify the source of an observed misbehavior. We propose an automatic incremental diagnostic methodology and CAD flow, based on data mining (DM). It is a model-based approach that incrementally determines the tests to be executed to isolate the faulty component, aiming at minimizing the total number of executed tests, without compromising 100% diagnostic accuracy. The DM engine allows for shorter test sequences with respect to other reasoning-based solutions (e.g., Bayesian belief networks), not requiring complex pre and post-conditions management. Experimental results on a large set of synthetic examples and on three industrial boards substantiate the quality of the proposed approach. [ABSTRACT FROM PUBLISHER]

As the complexity of model transformations grows, there is an increasing need to count on methods, mechanisms, and tools for checking their correctness, i.e., the alignment between specifications and implementations. In this paper we present a light-weight and static approach for locating the faulty rules in model transformations, based on matching functions that automatically establish these alignments using the metamodel footprints, i.e., the metamodel elements used. The approach is implemented for the combination of Tracts and ATL, both residing in the Eclipse Modeling Framework, and is supported by the corresponding toolkit. An evaluation discussing the accuracy and the limitations of the approach is also provided. Furthermore, we identify the kinds of transformations which are most suitable for validation with the proposed approach and use mutation techniques to evaluate its effectiveness. [ABSTRACT FROM PUBLISHER]

In a federated database system, each independent party exports some of its data for information sharing. The information sharing in such a system is very inflexible, as all peer parties access the same set of data exported by a party, while the party may want to authorize different peer parties to access different portions of its information. We propose a novel query evaluation scheme that supports differentiated access control with decentralized query processing. A new efficient join method, named split-join, along with other safe join methods is adopted in the query planning algorithm. The generated query execution reduces the communication cost by pushing partial query computation to data sources in a safe way. The proofs of the correctness and safety of the algorithm are presented. The evaluation demonstrates that the scheme significantly saves the communication cost in a variety of circumstances and settings while enforcing autonomous and differentiated information sharing effectively. [ABSTRACT FROM PUBLISHER]

A moving top-$k$ spatial keyword (M $k$ SK) query, which takes into account a continuously moving query location, enables a mobile client to be continuously aware of the top-$k$ spatial web objects that best match a query with respect to location and text relevance. The increasing mobile use of the web and the proliferation of geo-positioning render it of interest to consider a scenario where spatial keyword search is outsourced to a separate service provider capable at handling the voluminous spatial web objects available from various sources. A key challenge is that the service provider may return inaccurate or incorrect query results (intentionally or not), e.g., due to cost considerations or invasion of hackers. Therefore, it is attractive to be able to authenticate the query results at the client side. Existing authentication techniques are either inefficient or inapplicable for the kind of query we consider. We propose new authentication data structures, the MIR-tree and MIR $^*$ -tree, that enable the authentication of MkSK queries at low computation and communication costs. We design a verification object for authenticating MkSK queries, and we provide algorithms for constructing verification objects and using these for verifying query results. A thorough experimental study on real data shows that the proposed techniques are capable of outperforming two baseline algorithms by orders of magnitude. [ABSTRACT FROM PUBLISHER]

Since many graph data are often noisy and incomplete in real applications, it has become increasingly important to retrieve graphs $g$ in the graph database $D$ that approximately match the query graph $q$ , rather than exact graph matching. In this paper, we study the problem of graph similarity search, which retrieves graphs that are similar to a given query graph under the constraint of graph edit distance. We propose a systematic method for edit-distance based similarity search problem. Specifically, we derive two lower bounds, i.e., partition-based and branch-based bounds, from different perspectives. More importantly, a hybrid lower bound incorporating both ideas of the two lower bounds is proposed, which is theoretically proved to have higher (at least not lower) pruning power than using the two lower bounds together. We also present a uniform index structure, namely u-tree, to facilitate effective pruning and efficient query processing. Extensive experiments confirm that our proposed approach outperforms the existing approaches significantly, in terms of both the pruning power and query response time. [ABSTRACT FROM PUBLISHER]

XML is based on a tree-structured data model. Naturally, the most popular XML querying language (XPath) uses patterns of selection predicates, on multiple elements related by a tree structure, which often may be abstracted by twig patterns. Finding all occurrences of such a twig pattern in an XML database is a basic operation for XML query processing. We present the parallel path stack algorithm (PPS) and the parallel twig stack algorithm (PTS). PPS and PTS are novel and efficient algorithms for matching XML query twig patterns in a parallel multi-threaded computing platform. PPS and PTS are based on the PathStack and TwigStack algorithms [1]. These algorithms employ a sophisticated search technique for limiting processing to specific subtrees. We conducted extensive experimentation with PPS and PTS. We compared PPS and PTS to the standard (sequential) PathStack and TwigStack algorithms in terms of run time (to completion). We checked their performance for varying numbers of threads. Experimental results indicate that using PPS and PTS significantly reduces the running time of queries in comparison with the PathStack/TwigStack algorithm (up to 44 times faster for DBLP queries and up to 22 times faster for XMark queries). [ABSTRACT FROM PUBLISHER]

Advancement in information technology is playing an increasing role in the use of information systems comprising relational databases. These databases are used effectively in collaborative environments for information extraction; consequently, they are vulnerable to security threats concerning ownership rights and data tampering. Watermarking is advocated to enforce ownership rights over shared relational data and for providing a means for tackling data tampering. When ownership rights are enforced using watermarking, the underlying data undergoes certain modifications; as a result of which, the data quality gets compromised. Reversible watermarking is employed to ensure data quality along-with data recovery. However, such techniques are usually not robust against malicious attacks and do not provide any mechanism to selectively watermark a particular attribute by taking into account its role in knowledge discovery. Therefore, reversible watermarking is required that ensures; (i) watermark encoding and decoding by accounting for the role of all the features in knowledge discovery; and, (ii) original data recovery in the presence of active malicious attacks. In this paper, a robust and semi-blind reversible watermarking (RRW) technique for numerical relational data has been proposed that addresses the above objectives. Experimental studies prove the effectiveness of RRW against malicious attacks and show that the proposed technique outperforms existing ones. [ABSTRACT FROM PUBLISHER]

We present a $\Lambda$ -fold Redundant Blocking Framework, that relies on the Locality-Sensitive Hashing technique for identifying candidate record pairs, which have undergone an anonymization transformation. In this context, we demonstrate the usage and evaluate the performance of a variety of families of hash functions used for blocking. We illustrate that the performance attained is highly correlated to the distance-preserving properties of the anonymization format used. The parameters, of the blocking scheme, are optimally selected so that we achieve the highest possible accuracy in the least possible running time. We also introduce an SMC-based protocol in order to compare the formulated record pairs homomorphically, without running the risk of breaching the privacy of the underlying records. [ABSTRACT FROM PUBLISHER]

Fractal image compression (FIC) is one of the most widely approved image compression approaches for its high compression ratio and quality of retrieved images. However, FIC suffers from high computational cost in searching local self-similarities in natural image. Although many papers aiming at speeding up FIC have been published, they use pre-processing tools or approximation methods. Reducing the intrinsic computational complexity of FIC is still an open problem. Since quantum mechanics based Grover's quantum search algorithm (QSA) is able to achieve square-root speedup over classical algorithms in unsorted database searching, we propose an interdisciplinary approach by using Grover's QSA to reduce the intrinsic computational complexity of FIC in this letter. In particular, both domain blocks and range blocks are represented as quantum states, then Grover's QSA is employed to search the most similar domain block for each range block under the criterion of maximizing quantum fidelity between these two kinds of quantum states. Without sacrificing compression ratio, experimental results show that the execution time of the proposed method is 100 times shorter than that of the baseline FIC. Moreover, retrieved images from our proposal are also less distorted than those from other state-of-the-art FIC approaches. [ABSTRACT FROM AUTHOR]

Faces convey a wealth of social signals, including race, expression, identity, age and gender, all of which have attracted increasing attention from multi-disciplinary research, such as psychology, neuroscience, computer science, to name a few. Gleaned from recent advances in computer vision, computer graphics, and machine learning, computational intelligence based racial face analysis has been particularly popular due to its significant potential and broader impacts in extensive real-world applications, such as security and defense, surveillance, human computer interface (HCI), biometric-based identification, among others. These studies raise an important question: How implicit, non-declarative racial category can be conceptually modeled and quantitatively inferred from the face? Nevertheless, race classification is challenging due to its ambiguity and complexity depending on context and criteria. To address this challenge, recently, significant efforts have been reported toward race detection and categorization in the community. This survey provides a comprehensive and critical review of the state-of-the-art advances in face-race perception, principles, algorithms, and applications. We first discuss race perception problem formulation and motivation, while highlighting the conceptual potentials of racial face processing. Next, taxonomy of feature representational models, algorithms, performance and racial databases are presented with systematic discussions within the unified learning scenario. Finally, in order to stimulate future research in this field, we also highlight the major opportunities and challenges, as well as potentially important cross-cutting themes and research directions for the issue of learning race from face. [ABSTRACT FROM AUTHOR]

Myriad of graph-based algorithms in machine learning and data mining require parsing relational data iteratively. These algorithms are implemented in a large-scale distributed environment to scale to massive data sets. To accelerate these large-scale graph-based iterative computations, we propose delta-based accumulative iterative computation (DAIC). Different from traditional iterative computations, which iteratively update the result based on the result from the previous iteration, DAIC updates the result by accumulating the “changes” between iterations. By DAIC, we can process only the “changes” to avoid the negligible updates. Furthermore, we can perform DAIC asynchronously to bypass the high-cost synchronous barriers in heterogeneous distributed environments. Based on the DAIC model, we design and implement an asynchronous graph processing framework, Maiter. We evaluate Maiter on local cluster as well as on Amazon EC2 Cloud. The results show that Maiter achieves as much as 60\times speedup over Hadoop and outperforms other state-of-the-art frameworks. [ABSTRACT FROM PUBLISHER]

Result diversification has recently attracted considerable attention as a means of increasing user satisfaction in recommender systems, as well as in web and database search. In this paper, we focus on the problem of selecting the $k$ -most diverse items from a result set. Whereas previous research has mainly considered the static version of the problem, in this paper, we exploit the dynamic case in which the result set changes over time, as for example, in the case of notification services. We define the CONTINUOUS $k$ -DIVERSITY PROBLEM along with appropriate constraints that enforce continuity requirements on the diversified results. Our proposed approach is based on cover trees and supports dynamic item insertion and deletion. The diversification problem is in general NP-hard; we provide theoretical bounds that characterize the quality of our cover tree solution with respect to the optimal one. Since results are often associated with a relevance score, we extend our approach to account for relevance. Finally, we report experimental results concerning the efficiency and effectiveness of our approach on a variety of real and synthetic datasets. [ABSTRACT FROM PUBLISHER]

For over a century, the US National Institute of Standards and Technology (NIST) has made significant contributions to the world of science and technology, affecting not only US businesses and the economy but also the general public. This introduction provides a snapshot of the impact of NIST's contributions over the last century, while the articles in this special issue focus on NIST's recent contributions in the areas of test generation, search engines, cryptographic standards, and biometrics. [ABSTRACT FROM AUTHOR]

Search engines help users locate information within large stores of content developed for human consumption. For example, users expect Web search engines to direct searchers to websites based on the content of the site rather than the site address, and future video search engines to return video clips based on the actions recorded in the clip rather than filenames and donor tags. Search engines are developed using standard sets of realistic test cases that allow developers to measure the relative effectiveness of alternative approaches. The NIST Text Retrieval Conference (TREC) project has been instrumental in creating the necessary infrastructure to measure the quality of search results for more than 20 years, and has thus helped fuel the recent explosive growth in search-related technologies. This article is part of a special issue on NIST contributions to IT. [ABSTRACT FROM AUTHOR]

Goal-oriented visual search is performed when a person intentionally seeks a target in the visual environment. In augmented reality (AR) environments, visual search can be facilitated by augmenting virtual cues in the person's field of view. Traditional use of explicit AR cues can potentially degrade visual search performance due to the creation of distortions in the scene. An alternative to explicit cueing, known as subtle cueing, has been proposed as a clutter-neutral method to enhance visual search in video-see-through AR. However, the effects of subtle cueing are still not well understood, and more research is required to determine the optimal methods of applying subtle cueing in AR. We performed two experiments to investigate the variables of scene clutter, subtle cue opacity, size, and shape on visual search performance. We introduce a novel method of experimentally manipulating the scene clutter variable in a natural scene while controlling for other variables. The findings provide supporting evidence for the subtlety of the cue, and show that the clutter conditions of the scene can be used both as a global classifier, as well as a local performance measure. [ABSTRACT FROM AUTHOR]

Jammers can severely disrupt the communications in wireless networks, and jammers' position information allows the defender to actively eliminate the jamming attacks. Thus, in this paper, we aim to design a framework that can localize one or multiple jammers with a high accuracy. Most of existing jammer-localization schemes utilize indirect measurements (e.g., hearing ranges) affected by jamming attacks, which makes it difficult to localize jammers accurately. Instead, we exploit a direct measurement--the strength of jamming signals (JSS). Estimating JSS is challenging as jamming signals may be embedded in other signals. As such, we devise an estimation scheme based on ambient noise floor and validate it with real-world experiments. To further reduce estimation errors, we define an evaluation feedback metric to quantify the estimation errors and formulate jammer localization as a nonlinear optimization problem, whose global optimal solution is close to jammers' true positions. We explore several heuristic search algorithms for approaching the global optimal solution, and our simulation results show that our error-minimizing-based framework achieves better performance than the existing schemes. In addition, our error-minimizing framework can utilize indirect measurements to obtain a better location estimation compared with prior work. [ABSTRACT FROM AUTHOR]

Shortest distance query is a fundamental operation in large-scale networks. Many existing methods in the literature take a landmark embedding approach, which selects a set of graph nodes as landmarks and computes the shortest distances from each landmark to all nodes as an embedding. To answer a shortest distance query, the precomputed distances from the landmarks to the two query nodes are used to compute an approximate shortest distance based on the triangle inequality. In this paper, we analyze the factors that affect the accuracy of distance estimation in landmark embedding. In particular, we find that a globally selected, query-independent landmark set may introduce a large relative error, especially for nearby query nodes. To address this issue, we propose a query-dependent local landmark scheme, which identifies a local landmark close to both query nodes and provides more accurate distance estimation than the traditional global landmark approach. We propose efficient local landmark indexing and retrieval techniques, which achieve low offline indexing complexity and online query complexity. Two optimization techniques on graph compression and graph online search are also proposed, with the goal of further reducing index size and improving query accuracy. Furthermore, the challenge of immense graphs whose index may not fit in the memory leads us to store the embedding in relational database, so that a query of the local landmark scheme can be expressed with relational operators. Effective indexing and query optimization mechanisms are designed in this context. Our experimental results on large-scale social networks and road networks demonstrate that the local landmark scheme reduces the shortest distance estimation error significantly when compared with global landmark embedding and the state-of-the-art sketch-based embedding. [ABSTRACT FROM AUTHOR]

Quality-of-experience-oriented mechanisms, not currently available in traditional database management systems, allow a system to take into consideration user-specified requirements and to adjust its operations accordingly, based on user expectations. [ABSTRACT FROM PUBLISHER]

The conventional audio fingerprinting system by Haitsma uses a lookup table to identify the candidate songs in the database, which contains the sub-fingerprints of songs, and searches the candidates to find a song whose bit error rate is the lowest. However, this approach has a drawback that the number of database accesses increases dramatically, especially when the database contains a large number of songs or when a matching sub-fingerprint is not found in the lookup table due to a heavily degraded input signal. In this paper, a novel search method is proposed to overcome these difficulties. The proposed method partitions each song found from the lookup table into blocks, assigns a weight to each block, and uses the weight as a search priority to speed up the search process while reducing the number of database accesses. Various results from our experiment show the significant improvement in search speed while maintaining the search accuracy comparable to the conventional method. [ABSTRACT FROM PUBLISHER]

Evaluation is instrumental to developing and managing effective information retrieval systems. For this process, enlisting crowdsourcing has proven viable. However, less understood are crowdsourcing's limits for evaluation, particularly for domain-specific search. The authors compare relevance assessments gathered using crowdsourcing with those from a domain expert to evaluate different search engines in a large government archive. Although crowdsourced judgments rank the tested search engines in the same order as expert judgments, crowdsourced workers appear unable to distinguish different levels of highly accurate search results the way expert assessors can. [ABSTRACT FROM PUBLISHER]

We describe a framework that leverages mixed probabilistic and deterministic networks and their AND/OR search space to efficiently find and track the hands and feet of multiple interacting humans in 2D from a single camera view. Our framework detects and tracks multiple people's heads, hands, and feet through partial or full occlusion; requires few constraints (does not require multiple views, high image resolution, knowledge of performed activities, or large training sets); and makes use of constraints and AND/OR Branch-and-Bound with lazy evaluation and carefully computed bounds to efficiently solve the complex network that results from the consideration of interperson occlusion. Our main contributions are: 1) a multiperson part-based formulation that emphasizes extremities and allows for the globally optimal solution to be obtained in each frame, and 2) an efficient and exact optimization scheme that relies on AND/OR Branch-and-Bound, lazy factor evaluation, and factor cost sensitive bound computation. We demonstrate our approach on three datasets: the public single person HumanEva dataset, outdoor sequences where multiple people interact in a group meeting scenario, and outdoor one-on-one basketball videos. The first dataset demonstrates that our framework achieves state-of-the-art performance in the single person setting, while the last two demonstrate robustness in the presence of partial and full occlusion and fast nontrivial motion. [ABSTRACT FROM PUBLISHER]

Astronomical discoveries often happen at the edge of our observational capabilities. To fully analyze telescopic images, researchers must combine data from separate telescopes, but large volumes of data with intrinsic differences make this difficult. SkyQuery, a scalable query engine, helps with this process. [ABSTRACT FROM PUBLISHER]

In this paper, we describe the design and implementation of a reverse dictionary. Unlike a traditional forward dictionary, which maps from words to their definitions, a reverse dictionary takes a user input phrase describing the desired concept, and returns a set of candidate words that satisfy the input phrase. This work has significant application not only for the general public, particularly those who work closely with words, but also in the general field of conceptual search. We present a set of algorithms and the results of a set of experiments showing the retrieval accuracy of our methods and the runtime response time performance of our implementation. Our experimental results show that our approach can provide significant improvements in performance scale without sacrificing the quality of the result. Our experiments comparing the quality of our approach to that of currently available reverse dictionaries show that of our approach can provide significantly higher quality over either of the other currently available implementations. [ABSTRACT FROM AUTHOR]

Pruning achieves the dual goal of reducing the complexity of the final hypothesis for improved comprehensibility, and improving its predictive accuracy by minimizing the overfitting due to noisy data. This paper presents a new hybrid pruning technique for rule induction, as well as an incremental postpruning technique based on a misclassification tolerance. Although both have been designed for RULES-7, the latter is also applicable to any rule induction algorithm in general. A thorough empirical evaluation reveals that the proposed techniques enable RULES-7 to outperform other state-of-the-art classification techniques. The improved classifier is also more accurate and up to two orders of magnitude faster than before. [ABSTRACT FROM AUTHOR]

We introduce the problem of k-pattern set mining, concerned with finding a set of k related patterns under constraints. This contrasts to regular pattern mining, where one searches for many individual patterns. The k-pattern set mining problem is a very general problem that can be instantiated to a wide variety of well-known mining tasks including concept-learning, rule-learning, redescription mining, conceptual clustering and tiling. To this end, we formulate a large number of constraints for use in k-pattern set mining, both at the local level, that is, on individual patterns, and on the global level, that is, on the overall pattern set. Building general solvers for the pattern set mining problem remains a challenge. Here, we investigate to what extent constraint programming (CP) can be used as a general solution strategy. We present a mapping of pattern set constraints to constraints currently available in CP. This allows us to investigate a large number of settings within a unified framework and to gain insight in the possibilities and limitations of these solvers. This is important as it allows us to create guidelines in how to model new problems successfully and how to model existing problems more efficiently. It also opens up the way for other solver technologies. [ABSTRACT FROM AUTHOR]

Detecting intrinsic loop structures of a data manifold is the necessary prestep for the proper employment of the manifold learning techniques and of fundamental importance in the discovery of the essential representational features underlying the data lying on the loopy manifold. An effective strategy is proposed to solve this problem in this study. In line with our intuition, a formal definition of a loop residing on a manifold is first given. Based on this definition, theoretical properties of loopy manifolds are rigorously derived. In particular, a necessary and sufficient condition for detecting essential loops of a manifold is derived. An effective algorithm for loop detection is then constructed. The soundness of the proposed theory and algorithm is validated by a series of experiments performed on synthetic and real-life data sets. In each of the experiments, the essential loops underlying the data manifold can be properly detected, and the intrinsic representational features of the data manifold can be revealed along the loop structure so detected. Particularly, some of these features can hardly be discovered by the conventional manifold learning methods. [ABSTRACT FROM AUTHOR]