It is always well believed that pre-trained vision-language foundation models (e.g., CLIP) would substantially facilitate vision-language tasks. Nevertheless, there has been less evidence in support of the idea on describing novel objects in images. In this paper, we propose the Novel Object Transformer with CLIP (NOTC), a Transformer-based model that innovatively exploits the powerful vision-language representation ability of CLIP to enhance novel object captioning model’s training and sentence decoding processes. Technically, given the primary bag-of-objects extracted by Faster R-CNN, NOTC first capitalize on an object distiller module to emphasize the most salient objects and infer the missing novel ones. The refined object words are additionally fed into the object-centric word predictor to generate sentence word-by-word. During training, we design a CLIP-based self-critical sequence training paradigm to select visually-grounded sampled sentence with higher CLIP score reward, which enables a joint training process of captioning model over out-domain training images with novel objects. Moreover, at inference, a new CLIP beam search algorithm is devised to enforce the existence of novel objects and encourage the partial word sequences with higher CLIP scores, thereby decoding both visually-grounded and comprehensive sentences. Extensive experiments are conducted on held-out COCO and nocaps datasets, and competitive performances are reported when compared to state-of-the-art approaches.

Assembly Calculus (AC), proposed by Papadimitriou et al., aims to reproduce advanced cognitive functions through simulating neural activities, with several applications based on AC having been developed, including a natural language parser proposed by Mitropolsky et al. However, this parser lacks the ability to handle Kleene closures, preventing it from parsing all regular languages and rendering it weaker than Finite Automata (FA). In this paper, we propose a new bionic natural language parser (BNLP) based on AC and integrates two new biologically rational structures, Recurrent Circuit and Stack Circuit which are inspired by RNN and short-term memory mechanism. In contrast to the original parser, the BNLP can fully handle all regular languages and Dyck languages. Therefore, leveraging the Chomsky-Schützenberger theorem, the BNLP which can parse all Context-Free Languages can be constructed. We also formally prove that for any PDA, a Parser Automaton corresponding to BNLP can always be formed, ensuring that BNLP has a description ability equal to that of PDA and addressing the deficiencies of the original parser.

Recent advances on text-to-image generation have witnessed the rise of diffusion models which act as powerful generative models. Nevertheless, it is not trivial to exploit such latent variable models to capture the dependency among discrete words and meanwhile pursue complex visual-language alignment in image captioning. In this paper, we break the deeply rooted conventions in learning Transformer-based encoder-decoder, and propose a new diffusion model based paradigm tailored for image captioning, namely Semantic-Conditional Diffusion Networks (SCD-Net). Technically, for each input image, we first search the semantically relevant sentences via cross-modal retrieval model to convey the comprehensive semantic information. The rich semantics are further regarded as semantic prior to trigger the learning of Diffusion Transformer, which produces the output sentence in a diffusion process. In SCD-Net, multiple Diffusion Transformer structures are stacked to progressively strengthen the output sentence with better visional-language alignment and linguistical coherence in a cascaded manner. Furthermore, to stabilize the diffusion process, a new self-critical sequence training strategy is designed to guide the learning of SCD-Net with the knowledge of a standard autoregressive Transformer model. Extensive experiments on COCO dataset demonstrate the promising potential of using diffusion models in the challenging image captioning task. Source code is available at

QALSH (Query-Aware Locality Sensitive Hashing) is the representative Locality Sensitive Hashing scheme for answering the c-approximate nearest neighbor (c-ANN) search problems in high dimensional Euclidean space. In this paper, we present the first study on parallizing QALSH (P-QALSH) on a single multi-core computer. We first introduce parallel indexing designs to accelerate index construction. Then, we improve query search of QALSH by parallel range query and parallel collision counting technology. Note that the main challenges during the parallel collision counting process are update conflict problems. Hence, we propose a novel K-Counter Parallel Counting technology to ensure the correctness and efficiency of the parallel collision counting. Additionally, while QALSH may search c-ANNs with lots of search radiuses, resulting in large multi-round query overhead, we introduce a novel Search Radius Estimation Strategy to overcome this drawback. Moreover, we modify the termination condition of QALSH to search more nearby objects. Using four publicly available datasets and synthetic datasets, extensive experiments on a 16-core machine well demonstrate the superiority of P-QALSH on parallel computing. Specifically, compared to QALSH, P-QALSH is 9.6-13.8X faster on index construction, achieves 3.5-7.6X speedup on query search, and shows obvious improvement in query accuracy.

The advent of single-cell RNA sequencing (scRNA-seq) techniques opens up new opportunities for studying the cell-specific changes in the transcriptomic data. An important research problem related with scRNA-seq data analysis is to identify cell subpopulations with distinct functions. However, the expression profiles of individual cells are usually measured over tens of thousands of genes, and it remains a difficult problem to effectively cluster the cells based on the high-dimensional profiles. An additional challenge of performing the analysis is that, the scRNA-seq data are often noisy and sometimes extremely sparse due to technical limitations and sampling deficiencies. In this paper, we propose a biclustering-based framework called DivBiclust that effectively identifies the cell subpopulations based on the high-dimensional noisy scRNA-seq data. Compared with nine state-of-the-art methods, DivBiclust excels in identifying cell subpopulations with high accuracy as evidenced by our experiments on ten real scRNA-seq datasets with different size and diverse dropout rates. The supplemental materials of DivBiclust, including the source codes, data, and a supplementary document, are available at https://www.github.com/Qiong-Fang/DivBiclust.

The problem of Approximate Maximum Inner Product (AMIP) search has received increasing attention due to its wide applications. Interestingly, based on asymmetric transformation, the problem can be reduced to the Approximate Nearest Neighbor (ANN) search, and hence leverage Locality-Sensitive Hashing (LSH) to find solution. However, existing asymmetric transformations such as L2-ALSH and XBOX, suffer from large distortion error in reducing AMIP search to ANN search, such that the results of AMIP search can be arbitrarily bad. In this paper, we propose a novel Asymmetric LSH scheme based on Homocentric Hypersphere partition (H2-ALSH) for high-dimensional AMIP search. On the one hand, we propose a novel Query Normalized First (QNF) transformation to significantly reduce the distortion error. On the other hand, by adopting the homocentric hypersphere partition strategy, we can not only improve the search efficiency with early stop pruning, but also get higher search accuracy by further reducing the distortion error with limited data range. Our theoretical studies show that H2-ALSH enjoys a guarantee on search accuracy. Experimental results over four real datasets demonstrate that H2-ALSH significantly outperforms the state-of-the-art schemes.

The c-Approximate Furthest Neighbor (c-AFN) search is a fundamental problem in many applications. However, existing hashing schemes are designed for internal memory. The old techniques for external memory, such as furthest point Voronoi diagram and the tree-based methods, are only suitable for the low-dimensional case. In this paper, we introduce a novel concept of Reverse Locality-Sensitive Hashing (RLSH) family which is directly designed for c-AFN search. Accordingly, we propose two novel hashing schemes RQALSH and RQALSH for highdimensional c-AFN search over external memory. Experimental results validate the efficiency and effectiveness of RQALSH and RQALSH.

The$c$-Approximate Furthest Neighbor ($c$-AFN) search is a fundamental problem in many applications. However, existing hashing schemes for$c$-AFN search are designed for internal memory. The old techniques for external memory, such as furthest point Voronoi diagram and the tree-based methods, are only suitable for the low-dimensional case. In this paper, we introduce a novel concept of the Reverse Locality-Sensitive Hashing (RLSH) family which is directly designed for$c$-AFN search. Accordingly, we propose a new reverse query-aware LSH function, which is a random projection coupled with query-aware interval identification. Based on the reverse query-aware LSH functions, we introduce a novel Reverse Query-Aware LSH scheme named RQALSH for high-dimensional$c$-AFN search over external memory. Our theoretical studies show that RQALSH enjoys a guarantee on query quality. In addition, in order to further speed up RQALSH, we propose a heuristic variant named RQALSH$^*$which applies a data-dependent objects selection to largely reduce the number of data objects. In the experiment, we compare with two state-of-the-art hashing schemes QDAFN and DrusillaSelect which have been adapted for external memory. Extensive experiments on four real datasets show that our proposed RQALSH and RQALSH$^*$schemes significantly outperform these two methods.

Locality-Sensitive Hashing (LSH) and its variants are the well-known indexing schemes for the c -Approximate Nearest Neighbor ( c -ANN) search problem in high-dimensional Euclidean space. Traditionally, LSH functions are constructed in a query-oblivious manner in the sense that buckets are partitioned before any query arrives. However, objects closer to a query may be partitioned into different buckets, which is undesirable. Due to the use of query-oblivious bucket partition, the state-of-the-art LSH schemes for external memory, namely C2LSH and LSB-Forest, only work with approximation ratio of integer c ≥ 2. In this paper, we introduce a novel concept of query-aware bucket partition which uses a given query as the "anchor" for bucket partition. Accordingly, a query-aware LSH function is a random projection coupled with query-aware bucket partition, which removes random shift required by traditional query-oblivious LSH functions. Notably, query-aware bucket partition can be easily implemented so that query performance is guaranteed. We propose a novel query-aware LSH scheme named QALSH for c -ANN search over external memory. Our theoretical studies show that QALSH enjoys a guarantee on query quality. The use of query-aware LSH function enables QALSH to work with any approximation ratio c > 1. Extensive experiments show that QALSH outperforms C2LSH and LSB-Forest, especially in high-dimensional space. Specifically, by using a ratio c < 2, QALSH can achieve much better query quality.

We deal with embedding a large scale knowledge graph composed of entities and relations into a continuous vector space. TransE is a promising method proposed recently, which is very efficient while achieving state-of-the-art predictive performance. We discuss some mapping properties of relations which should be considered in embedding, such as reflexive, one-to-many, many-to-one, and many-to-many. We note that TransE does not do well in dealing with these properties. Some complex models are capable of preserving these mapping properties but sacrifice efficiency in the process. To make a good trade-off between model capacity and efficiency, in this paper we propose TransH which models a relation as a hyperplane together with a translation operation on it. In this way, we can well preserve the above mapping properties of relations with almost the same model complexity of TransE. Additionally, as a practical knowledge graph is often far from completed, how to construct negative examples to reduce false negative labels in training is very important. Utilizing the one-to-many/many-to-one mapping property of a relation, we propose a simple trick to reduce the possibility of false negative labeling. We conduct extensive experiments on link prediction, triplet classification and fact extraction on benchmark datasets like WordNet and Freebase. Experiments show TransH delivers significant improvements over TransE on predictive accuracy with comparable capability to scale up.

We examine the embedding approach to reason new relational facts from a largescale knowledge graph and a text corpus.We propose a novel method of jointly embedding entities and words into the same continuous vector space.The embedding process attempts to preserve the relations between entities in the knowledge graph and the concurrences of words in the text corpus.Entity names and Wikipedia anchors are utilized to align the embeddings of entities and words in the same space.Large scale experiments on Freebase and a Wikipedia/NY Times corpus show that jointly embedding brings promising improvement in the accuracy of predicting facts, compared to separately embedding knowledge graphs and text.Particularly, jointly embedding enables the prediction of facts containing entities out of the knowledge graph, which cannot be handled by previous embedding methods.At the same time, concerning the quality of the word embeddings, experiments on the analogical reasoning task show that jointly embedding is comparable to or slightly better than word2vec (Skip-Gram).

Order-preserving submatrices (OPSMs) capture consensus trends over columns shared by rows in a data matrix. Mining OPSM patterns discovers important and interesting local correlations in many real applications, such as those involving biological data or sensor data. The prevalence of uncertain data in various applications, however, poses new challenges for OPSM mining, since data uncertainty must be incorporated into OPSM modeling and the algorithmic aspects. In this article, we define new probabilistic matrix representations to model uncertain data with continuous distributions. A novel probabilistic order-preserving submatrix (POPSM) model is formalized in order to capture similar local correlations in probabilistic matrices. The POPSM model adopts a new probabilistic support measure that evaluates the extent to which a row belongs to a POPSM pattern. Due to the intrinsic high computational complexity of the POPSM mining problem, we utilize the anti-monotonic property of the probabilistic support measure and propose an efficient Apriori-based mining framework called ProbApri to mine POPSM patterns. The framework consists of two mining methods, UniApri and NormApri , which are developed for mining POPSM patterns, respectively, from two representative types of probabilistic matrices, the UniDist matrix (assuming uniform data distributions) and the NormDist matrix (assuming normal data distributions). We show that the NormApri method is practical enough for mining POPSM patterns from probabilistic matrices that model more general data distributions. We demonstrate the superiority of our approach by two applications. First, we use two biological datasets to illustrate that the POPSM model better captures the characteristics of the expression levels of biologically correlated genes and greatly promotes the discovery of patterns with high biological significance. Our result is significantly better than the counterpart OPSMRM (OPSM with repeated measurement) model which adopts a set-valued matrix representation to capture data uncertainty. Second, we run the experiments on an RFID trace dataset and show that our POPSM model is effective and efficient in capturing the common visiting subroutes among users.

Locality-Sensitive Hashing (LSH) and its variants are well-known methods for solving the c-approximate NN Search problem in high-dimensional space. Traditionally, several LSH functions are concatenated to form a "static" compound hash function for building a hash table. In this paper, we propose to use a base of m single LSH functions to construct "dynamic" compound hash functions, and define a new LSH scheme called Collision Counting LSH (C2LSH). If the number of LSH functions under which a data object o collides with a query object q is greater than a pre-specified collision threhold l, then o can be regarded as a good candidate of c-approximate NN of q. This is the basic idea of C2LSH.

The Order-Preserving SubMatrices (OPSMs) are employed to discover significant biological associations between genes and experiment conditions. Herein, we propose a new relaxed OPSM model by considering the linearity relaxation, which is called the Bucket OPSM (BOPSM) model. An efficient method called ApriBopsm is developed to exhaustively mine such BOPSM patterns. We further generalize the BOPSM model by incorporating the similarity relaxation strategy. We develop a generalized BOPSM model called GeBOPSM and adopt a pattern growing method called SeedGrowth to mine GeBOPSM patterns. Informally, the SeedGrowth algorithm adopts two different growing strategies on rows and columns in order to expand a seed BOPSM into a maximal GeBOPSM pattern. We conduct a series of experiments using both synthetic and biological datasets to study the effectiveness of our proposed relaxed models and the efficiency of the relevant mining methods. The BOPSM model is shown to be able to capture the characteristics of noisy OPSM patterns, and is superior to the strict counterparts. ApriBopsm is also significantly more efficient than OPC-Tree, which is the state-of-the-art OPSM mining method. Compared to all the current relaxed OPSM models, the GeBOPSM model achieves the best performance in terms of the number of mined quality patterns.

Identifying differentially expressed genes is an important problem in gene expression analysis, since these genes, exhibiting sufficiently different expression levels under distinct experiment conditions, could be critical for tracing the progression of a disease. In a micro array study, genes are usually sorted in terms of their differentiation abilities with the more differentially expressed genes being ranked higher in the list. As more micro array studies are conducted, rank aggregation becomes an important means to combine such ranked gene lists in order to discover more reliable differentially expressed genes. In this paper, we study a novel weighted gene rank aggregation problem whose complexity is at least NP-hard. To tackle the problem, we develop a new Markov-chain based rank aggregation method called Weighted MC (WMC). The WMC algorithm makes use of rank-based weight information to generate the transition matrix. Extensive experiments on the real biological datasets show that our approach is more efficient in aggregating long gene lists. Importantly, the WMC method is much more robust for identifying biologically significant genes compared with the state-of-the-art methods.

Mining order-preserving submatrix (OPSM) patterns has received much attention from researchers, since in many scientific applications, such as those involving gene expression data, it is natural to express the data in a matrix and also important to find the order-preserving submatrix patterns. However, most current work assumes the noise-free OPSM model and thus is not practical in many real situations when sample contamination exists.

Discovering a bucket order B from a collection of possibly noisy full rankings is a fundamental problem that relates to various applications involving rankings. Informally, a bucket order is a total order that allows "ties" between items in a bucket. A bucket order B can be viewed as a "representative" that summarizes a given set of full rankings {T1, T2, ..., Tm}, or conversely B can be an "approximation" of some "ground truth" G where the rankings {T1, T2, ..., Tm} are simply the "linear extensions" of G.

BST Condensed Cube is a fully computed cube that condenses those tuples, which are aggregated from the same single base relation tuple, into one physical tuple. Although it has been proved to be an effective approach to reduce the size of a data cube, there still exist some redundancies in a BST condensed cube, i.e., prefix redundancy among cube tuples. In this paper, we augument BST condensing with prefix-sharing, and propose an efficient cube structure called PrefixCube, for further reducing a BST condensed data cube's size as well as its computation time. The space and time savings of PrefixCube, compared with its corresponding BST condensed cube, are demonstrated through extensive experiments, using both synthetic and real world data.

OLAP (online analytical processing) servers usually pre-compute data cubes to improve the response time of possible aggregate queries over cuboids with different grouping attributes. To reduce the huge size of a sparse data cube, the base single tuples (BSTs) are explored to condense cube tuples aggregated from the same set of source tuples into one tuple, whenever such condensing will not require further aggregate when the cube is used to answer queries. We propose the CuboidTree to index the BST condensed cube. Using both synthetic and real world data, we conducted experiments to demonstrate query processing and bulk incremental updating performance of the indexing scheme.

Pre-computed data cube facilitates OLAP (on-line analytical processing). It is well-known that data cube computation is an expensive operation. While most algorithms have been devoted to optimizing memory management and reducing computation costs, less work has addressed a fundamental issue: the size of a data cube is huge when a large base relation with a large number of attributes is involved. In this paper, we propose a new concept, called a condensed data cube. The condensed cube is of much smaller size than a complete non-condensed cube. More importantly, it is a fully pre-computed cube without compression, and, hence, it requires neither decompression nor further aggregation when answering queries. Several algorithms for computing a condensed cube are proposed. Results of experiments on the effectiveness of condensed data cube are presented, using both synthetic and real-world data. The results indicate that the proposed condensed cube can reduce both the cube size and therefore its computation time.

Materialized views can provide massive improvements in query processing time, especially for aggregation queries over large tables. To achieve the potential of materialized views, we must determine what views to materialize. An important issue in view selection is view merging. View merging can take a set of candidate views generated by analyzing queries in a workload, and produce a set of merged views by exploiting commonality among those queries. View merging can efficiently reduce candidate views for view selection. We present a merging tree, as well as a fast and scalable algorithm for view merging based on such a tree. The merging tree can significantly reduce the search space of potential views to be merged. Our approach is more scalable than the alternative of sequentially merging all pairs of views every time.