An efficient substring search method by using delayed keyword extraction

In the information retrieval systems, one of the most important and difficult operations is to extract appropriate keywords from documents. This paper proposes an effective substring search method by extending a pattern matching machine for multi-keyword based on Aho and Corasick (AC) called AC machine. The proposed method enables us to extract keyword candidates as much as possible and to select the suitable keywords for users' purpose at a retrieval stage. This method contains four types of substring search methods (exact, prefix, suffix and proper substring search). This paper also proposes a construction algorithm of the retrieval structure for speeding up the substring search. From the simulation results, it is shown that the retrieval time of the presented method is as fast as the key retrieval method based on the trie.     

A dynamic construction algorithm for the Compact Patricia trie using the hierarchical structure

We need to access objective information efficiently and arbitrary strings in the text at high speed. In several key retrieval strategies, we often use the binary trie for supporting fast access method in order. Especially, the Patricia trie (Pat tree) is famous as the fastest access method in binary tries, because it has the shallowest tree structure. However, the Pat tree requires many good physician storage spaces in memory, if key set registered is large. Thereby, an expense problem happens when storing this trie to the main storage unit. We already proposed a method that use compact bit stream and compress a Pat tree to solve this problem. This is called Compact Patricia trie (CPat tree). This CPat tree needs capacity of only a very few memory device. However, if a size of key set increases, the time expense that search, update key increases gradually. This paper proposes a new structure of the CPat tree to avoid that it takes much time in search and update about much key set, and a method to construct a new CPat tree dynamically and efficiently. This method divides a CPat tree consisting of bit string to fixed depth. In addition, it compose been divided CPAT tree hierarchically. A construction algorithm that proves this update time requires alteration of only one tree among whole trees that is divided. From experimental result that use 120,000 English substantives and 70,000 Japanese substantives, we prove an update time that is faster more than 40 times than the traditional method. Moreover, a space efficiency of memory increases about 35% only than the traditional method.     

基于多分支Trie的路由查找算法设计与实现

基于多分支Trie数据结构的查找算法在路由查找中有着广泛的应用。文章对基于多分支Trie的路由查找算法进行了介绍,并对其特点进行了分析。在此基础上,设计实现了便于高速动态路由查找的多分支Trie数据结构,公开了一个使用多分支Trie数据结构的基于前缀值的动态最长前缀匹配算法,提高了路由查找速度。     

Computer use of a medical dictionary to select search words

In a preceding experiment in text-searching retrieval for cancer questions, search words were humanly selected with the aid of a medical dictionary and cancer textbooks. Recall results were (1) using only stems of question words (humanly stemmed): 20%; (2) adding dictionary search words: 29%; (3) adding also textbook search words: 70%. For the experiment reported here, computer procedures for using the medical dictionary to select search words were developed. Recall results were (1) for question stems (computer stemmed): 19%; (2) adding search words computer selected from the dictionary: 24 %. Thus the computer procedures compared to human use of the dictionary were 50% successful. Human and computer false retrieval rates were almost equal. Some hypotheses about computer selection of search words from textbooks are also described.     

Learning ordinal constraint binary codes for fast similarity search

Similarity search with hashing has become one of the fundamental research topics in computer vision and multimedia. The current researches on semantic-preserving hashing mainly focus on exploring the semantic similarities between pointwise or pairwise samples in the visual space to generate discriminative hash codes. However, such learning schemes fail to explore the intrinsic latent features embedded in the high-dimensional feature space and they are difficult to capture the underlying topological structure of data, yielding low-quality hash codes for image retrieval. In this paper, we propose an ordinal-preserving latent graph hashing (OLGH) method, which derives the objective hash codes from the latent space and preserves the high-order locally topological structure of data into the learned hash codes. Specifically, we conceive a triplet constrained topology-preserving loss to uncover the ordinal-inferred local features in binary representation learning. By virtue of this, the learning system can implicitly capture the high-order similarities among samples during the feature learning process. Moreover, the well-designed latent subspace learning is built to acquire the noise-free latent features based on the sparse constrained supervised learning. As such, the latent under-explored characteristics of data are fully employed in subspace construction. Furthermore, the latent ordinal graph hashing is formulated by jointly exploiting latent space construction and ordinal graph learning. An efficient optimization algorithm is developed to solve the resulting problem to achieve the optimal solution. Extensive experiments conducted on diverse datasets show the effectiveness and superiority of the proposed method when compared to some advanced learning to hash algorithms for fast image retrieval. The source codes of this paper are available at https://github.com/DarrenZZhang/OLGH .     

Explore instance similarity: An instance correlation based hashing method for multi-label cross-model retrieval

With the rapid growth of multimedia data, cross-media hashing has gained more and more attention. However, most existing cross-modal hashing methods ignore the multi-label correlation and only apply binary similarity to measure the correlation between two instances. Most existing methods perform poorly in capturing the relevance between retrieval results and queries since binary similarity measurement has limited abilities to discriminate minor differences among different instances. In order to overcome the mentioned shortcoming, we introduce a novel notion of instance similarity method, which is used to evaluate the semantic correlation between two specific instances in training data. Base on the instance similarity, we also propose a novel deep instance hashing network, which utilizes instance similarity and binary similarity simultaneously for multi-label cross-model retrieval. The experiment results on two real datasets show the superiority of our proposed method, compared with a series of state-of-the-art cross-modal hashing methods in terms of several metric evaluations.     

查询翻译方法研究——以汉英跨语言信息检索为例

【目的/意义】跨语言信息检索研究的目的即在消除因语言的差异而导致信息查询的困难,提高从大量纷繁 复杂的查找特定信息的效率。同时提供一种更加方便的途径使得用户能够使用自己熟悉的语言检索另外一种语 言文档。【方法/过程】本文通过对国内外跨语言信息检索的研究现状分析,介绍了目前几种查询翻译的方法,包括： 直接查询翻译、文献翻译、中间语言翻译以及查询—文献翻译方法,对其效果进行比较,然后阐述了跨语言检索关 键技术,对使用基于双语词典、语料库、机器翻译技术等产生的歧义性提出了解决方法及评价。【结果/结论】使用自 然语言处理技术、共现技术、相关反馈技术、扩展技术、双向翻译技术以及基于本体信息检索技术确保知识词典的 覆盖度和歧义性处理,通过对跨语言检索实验分析证明采用知识词典、语料库和搜索引擎组合能够提高查询效 率。【创新/局限】本文为了解决跨语言信息检索使用词典、语料库中词语缺乏的现象,提出通过搜索引擎从网页获 取信息资源来充实语料库中语句对不足的问题。文章主要针对中英文信息检索问题进行了探讨,解决方法还需要 进一步研究,如中文切词困难以及字典覆盖率低等严重影响检索的效率。     

数字资源统一检索系统的设计与实现

通过设计统一检索过程模型,并对统一检索的技术进行分析。采用PHP开发程序与Apache Web应用服务器相结合的方式,利用两者在字符运算处理速度的优异性和可靠性以及稳定性的特点,并采用性能优异的Web信息获取组件Client URLLibrary（CURL）,来实现对科技文献网站的网页进行信息抓取,完成对不同异构数字资源的统一检索、统一显示和二次检索等功能。最后,对目前存在的问题提出了解决的思路。     

Cognitive multi-modal consistent hashing with flexible semantic transformation

Multi-modal hashing can encode the large-scale social geo-media multimedia data from multiple sources into a common discrete hash space, in which the heterogeneous correlations from multiple modalities could be well explored and preserved into the objective semantic-consistent hash codes. The current researches on multi-modal hashing mainly focus on performing common data reconstruction, but they fail to effectively distill the intrinsic and consensus structures of multi-modal data and fully exploit the inherent semantic knowledge to capture semantic-consistent information across multiple modalities, leading to unsatisfactory retrieval performance. To facilitate this problem and develop an efficient multi-modal geographical retrieval method, in this article, we propose a discriminative multi-modal hashing framework named Cognitive Multi-modal Consistent Hashing (CMCH), which can progressively pursue the structure consensus over heterogeneous multi-modal data and simultaneously explore the informative transformed semantics. Specifically, we construct a parameter-free collaborative multi-modal fusion module to incorporate and excavate the underlying common components from multi-source data. Particularly, our formulation seeks for a joint multi-modal compatibility among multiple modalities under a self-adaptive weighting manner, which can take full advantages of their complementary properties. Moreover, a cognitive self-paced learning policy is further leveraged to conduct progressive feature aggregation, which can coalesce multi-modal data onto the established common latent space in a curriculum learning mode. Furthermore, deep semantic transform learning is elaborated to generate flexible semantics for interactively guiding collaborative hash codes learning. An efficient discrete learning algorithm is devised to address the resulting optimization problem, which obtains stable solutions when dealing with large-scale multi-modal retrieval tasks. Sufficient experiments performed on four large-scale multi-modal datasets demonstrate the encouraging performance of the proposed CMCH method in comparison with the state-of-the-arts over multi-modal information retrieval and computational efficiency. The source codes of this work could be available at https://github.com/JunfengAn1998a/CMCH .     

Multi-Sentence Video Captioning using Content-oriented Beam Searching and Multi-stage Refining Algorithm

With the increasing growth of video data, especially in cyberspace, video captioning or the representation of video data in the form of natural language has been receiving an increasing amount of interest in several applications like video retrieval, action recognition, and video understanding, to name a few. In recent years, deep neural networks have been successfully applied for the task of video captioning. However, most existing methods describe a video clip using only one sentence that may not correctly cover the semantic content of the video clip. In this paper, a new multi-sentence video captioning algorithm is proposed using a content-oriented beam search approach and a multi-stage refining method. We use a new content-oriented beam search algorithm to update the probabilities of words generated by the trained deep networks. The proposed beam search algorithm leverages the high-level semantic information of an input video using an object detector and the structural dictionary of sentences. We also use a multi-stage refining approach to remove structurally wrong sentences as well as sentences that are less related to the semantic content of the video. To this intent, a new two-branch deep neural network is proposed to measure the relevance score between a sentence and a video. We evaluated the performance of the proposed method with two popular video captioning databases and compared the results with the results of some state-of-the-art approaches. The experiments showed the superior performance of the proposed algorithm. For instance, in the MSVD database, the proposed method shows an enhancement of 6% for the best-1 sentences in comparison to the best state-of-the-art alternative.     

Efficient online index maintenance for contiguous inverted lists

Search engines and other text retrieval systems use high-performance inverted indexes to provide efficient text query evaluation. Algorithms for fast query evaluation and index construction are well-known, but relatively little has been published concerning update. In this paper, we experimentally evaluate the two main alternative strategies for index maintenance in the presence of insertions, with the constraint that inverted lists remain contiguous on disk for fast query evaluation. The in-place and re-merge strategies are benchmarked against the baseline of a complete re-build. Our experiments with large volumes of web data show that re-merge is the fastest approach if large buffers are available, but that even a simple implementation of in-place update is suitable when the rate of insertion is low or memory buffer size is limited. We also show that with careful design of aspects of implementation such as free-space management, in-place update can be improved by around an order of magnitude over a naïve implementation.     

Dynamic dictionary updating

A method for updating the dictionary in a dynamic information retrieval system is presented. It is shown that as a collection changes through addition and deletion of documents, the appropriate set of index terms may be determined without complete periodic regeneration of the dictionary. Results are presented for experiments involving a complete change in collection membership, with the dynamic dictionary updating methods shown to be effective.     

Compression of double array structures for fixed length keywords

A trie is one of the data structures for keyword matching. It is used in natural language processing, IP address routing, and so on. It is represented by the matrix form, the link form, the double array, and LOUDS. The double array representation combines retrieval speed of the matrix form with compactness of the list form. LOUDS is a succinct data structure using bit-string. Retrieval speed of LOUDS is not faster than that of the double array, but its space usage is smaller. This paper proposes a compressed version of the double array by dividing the trie into multiple levels and removing the BASE array from the double array. Moreover, a retrieval algorithm and a construction algorithm are proposed. According to the presented experimental results for pseudo and real data sets, the retrieval speed of the presented method is almost the same as the double array, and its space usage is compressed to 66% comparing with LOUDS for a large set of keywords with fixed length.     

Semiautomatic disabbreviation of technical text

Abbreviations adversely affect information retrieval and text comprehensibility. We describe a software tool to decipher abbrevations by finding their whole-word equivalents or “disabbreviations”. It uses a large English dictionary and a rule-based system to guess the most-likely candidates, with users having final approval. The rule-based system uses a variety of knowledge to limit its search, including phonetics, known methods of constructing multiword abbrevations, and analogies to previous abbreviations. The tool is especially helpful for retrieval from computer programs, a form of technical text in which abbreviations are notoriously common; disabbreviation of programs can make programs more reusable, improving software engineering. It also helps decipher the often-specialized abbreviations in technical captions. Experimental results confirm that the prototype tool is easy to use, finds many correct disabbreviations, and improves text comprehensibility.     

A compact static double-array keeping character codes

A trie represented by a double-array enables us to search a key fast with a small space. However, the double-array uses extra space to be updated dynamically. This paper presents a compact structure for a static double-array. The new structure keeps character codes instead of indices in order to compress elements of the double-array. In addition, the new structure unifies common suffixes and consists of less elements than the old structure. Experimental results for English keys show that the new structure reduces space usage of the double-array up to 40%.     

Multi-facet product information search and retrieval using semantically annotated product family ontology

With the advent of various services and applications of Semantic Web, semantic annotation has emerged as an important research topic. The application of semantically annotated ontology had been evident in numerous information processing and retrieval tasks. One of such tasks is utilizing the semantically annotated ontology in product design which is able to suggest many important applications that are critical to aid various design related tasks. However, ontology development in design engineering remains a time consuming and tedious task that demands considerable human efforts. In the context of product family design, management of different product information that features efficient indexing, update, navigation, search and retrieval across product families is both desirable and challenging. For instance, an efficient way of retrieving timely information on product family can be useful for tasks such as product family redesign and new product variant derivation when requirements change. However, the current research and application of information search and navigation in product family is mostly limited to its structural aspect which is insufficient to handle advanced information search especially when the query targets at multiple aspects of a product. This paper attempts to address this problem by proposing an information search and retrieval framework based on the semantically annotated multi-facet product family ontology. Particularly, we propose a document profile (DP) model to suggest semantic tags for annotation purpose. Using a case study of digital camera families, we illustrate how the faceted search and retrieval of product information can be accomplished. We also exemplify how we can derive new product variants based on the designer’s query of requirements via the faceted search and retrieval of product family information. Lastly, in order to highlight the value of our current work, we briefly discuss some further research and applications in design decision support, e.g. commonality analysis and variety comparison, based on the semantically annotated multi-facet product family ontology.     

跨语言信息检索查询翻译词典自动构建研究

双语机读词典是基于查询翻译的跨语言信息检索中的常用资源,但是传统的手工构建词典的方法费时费力,本文利用统计方法从英汉句对齐平行语料库中自动获取翻译词典,以用于查询翻译过程中。     

New methods for compression of MP double array by compact management of suffixes

Minimal Prefix (MP) double array is an efficient data structure for a trie. However, its space efficiency is degraded by the non-compact management of suffixes. This paper presents three methods to compress the MP double array. The first two methods compress the MP double array by accommodating short suffixes inside the leaf nodes, and pruning leaf nodes corresponding to the end marker symbol. These methods achieve size reduction of up to 20%, making insertion and deletion faster at the same time while maintaining the retrieval time of O(1). The third method eliminates empty spaces in the array that holds suffixes, and improves the maximum size reduction further by about 5% at the cost of increased insertion time. Compared to a Ternary Search Tree, the key retrieval of the compressed MP double array is 50% faster and its size is 3–5 times smaller.     

Knowledge organization and access in a conceptual information system

Traditional approaches to information retrieval, based on automatic or manually constructed keywords, are inappropriate for certain desirable tasks in an intelligent information system. Obtaining simple answers to direct questions, a summary of an event sequence that could span multiple documents, and an update of recent developments in an ongoing event sequence are three examples of such tasks.In this paper, the SCISOR system is described. SCISOR illustrates the potential for increased recall and precision of stored information through the understanding in context of articles in its domain of corporate takeovers. A constrained form of marker passing is used to answer queries of the knowledge base posed in natural language. Among other desirable characteristics, this method of retrieval focuses search on likely candidates, and tolerates incomplete or incorrect input indices very well.