Comparing inverted files and signature files for searching a large lexicon

Signature files and inverted files are well-known index structures. In this paper we undertake a direct comparison of the two for searching for partially-specified queries in a large lexicon stored in main memory. Using n-grams to index lexicon terms, a bit-sliced signature file can be compressed to a smaller size than an inverted file if each n-gram sets only one bit in the term signature. With a signature width less than half the number of unique n-grams in the lexicon, the signature file method is about as fast as the inverted file method, and significantly smaller. Greater flexibility in memory usage and faster index generation time make signature files appropriate for searching large lexicons or other collections in an environment where memory is at a premium.     

A Zipfian model of an automatic bibliographic system: an application to MEDLINE.

A Zipfian model of an automatic bibliographic system is developed using parameters describing the contents of it database and its inverted file. The underlying structure of the Zipf distribution is derived, with particular emphasis on its application to work frequencies, especially with regard to the inverted flies of an automatic bibliographic system. Andrew Booth developed a form of Zipf's law which estimates the number of words of a particular frequency for a given author and text. His formulation has been adopted as the basis of a model of term dispersion in an inverted file system. The model is also distinctive in its consideration of the proliferation of spelling errors in free text, and the inclusion of all searchable elements from the system's inverted file. This model is applied to the National Library of Medicine's MEDLINE. The model carries implications for the determination of database storage requirements, search response time, and search exhaustiveness.     

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.     

Cost-effectiveness comparison of manual and on-line retrospective bibliographic searching.

A study to compare the cost effectiveness of retrospective manual and on-line bibliographic searching is described. Forty search queries were processed against seven abstracting-indexing publications and the corresponding SDC/ORBIT data bases. Equivalent periods of coverage and searcher skill levels were used for both search models. Separate task times were measured for question analysis, searching, photocopying, shelving, and output distribution. Component costs were calculated for labor, information, reproduction, equipment, physical space, and telecommunications. Results indicate that on-line searching is generally faster, less costly, and more effective than manual searching. However, for certain query/information-source combinations, manual searching may offer some advantages in precision and turn-around time. The results of a number of related studies are reviewed.     

TOXLINE: evolution of an online interactive bibliographic database.

The National Library of Medicine has offered TOXLINE, an online interactive bibliographic database of biomedical (toxicology) information since 1972. Files from 11 secondary sources comprise the TOXLINE database. The sources supplied bibliographic records in different formats and data structures. Data from each supplier's format had to be converted into a format suitable for TOXLINE. Three different, successive retrieval systems were used for the TOXLINE database which required reformatting of the data. Algorithms for generating terms for inverted file search methods were tested. Special characters peculiar to the scientific literature were evaluated during search term generation. Developing search term algorithms for chemical names in the scientific literature required techniques different from those used for nonscientific literature. Problems with replication of bibliographic records from multiple secondary sources are described. Some observations about online interactive databases since TOXLINE was first offered are noted.     

Efficient phrase querying with common phrase index

In this paper, we propose a common phrase index as an efficient index structure to support phrase queries in a very large text database. Our structure is an extension of previous index structures for phrases and achieves better query efficiency with modest extra storage cost. Further improvement in efficiency can be attained by implementing our index according to our observation of the dynamic nature of common word set. In experimental evaluation, a common phrase index using 255 common words has an improvement of about 11% and 62% in query time for the overall and large queries (queries of long phrases) respectively over an auxiliary nextword index. Moreover, it has only about 19% extra storage cost. Compared with an inverted index, our improvement is about 72% and 87% for the overall and large queries respectively. We also propose to implement a common phrase index with dynamic update feature. Our experiments show that more improvement in time efficiency can be achieved.     

Descendants,ancestors, children and parent: A set-based approach to efficiently address XPath primitives

XML is a pervasive technology for representing and accessing semi-structured data. XPath is the standard language for navigational queries on XML documents and there is a growing demand for its efficient processing.In order to increase the efficiency in executing four navigational XML query primitives, namely descendants, ancestors, children and parent, we introduce a new paradigm where traditional approaches based on the efficient traversing of nodes and edges to reconstruct the requested subtrees are replaced by a brand new one based on basic set operations which allow us to directly return the desired subtree, avoiding to create it passing through nodes and edges.Our solution stems from the NEsted SeTs for Object hieRarchies (NEASTOR) formal model, which makes use of set-inclusion relations for representing and providing access to hierarchical data. We define in-memory efficient data structures to implement NESTOR, we develop algorithms to perform the descendants, ancestors, children and parent query primitives and we study their computational complexity.We conduct an extensive experimental evaluation by using several datasets: digital archives (EAD collections), INEX 2009 Wikipedia collection, and two widely-used synthetic datasets (XMark and XGen). We show that NESTOR-based data structures and query primitives consistently outperform state-of-the-art solutions for XPath processing at execution time and they are competitive in terms of both memory occupation and pre-processing time.     

Inverted file compression through document identifier reassignment

The inverted file is the most popular indexing mechanism for document search in an information retrieval system. Compressing an inverted file can greatly improve document search rate. Traditionally, the d-gap technique is used in the inverted file compression by replacing document identifiers with usually much smaller gap values. However, fluctuating gap values cannot be efficiently compressed by some well-known prefix-free codes. To smoothen and reduce the gap values, we propose a document-identifier reassignment algorithm. This reassignment is based on a similarity factor between documents. We generate a reassignment order for all documents according to the similarity to reassign closer identifiers to the documents having closer relationships. Simulation results show that the average gap values of sample inverted files can be reduced by 30%, and the compression rate of d-gapped inverted file with prefix-free codes can be improved by 15%.     

Effective top-k computation with term-proximity support

Modern web search engines are expected to return the top-k results efficiently. Although many dynamic index pruning strategies have been proposed for efficient top-k computation, most of them are prone to ignoring some especially important factors in ranking functions, such as term-proximity (the distance relationship between query terms in a document). In our recent work [Zhu, M., Shi, S., Li, M., & Wen, J. (2007). Effective top-k computation in retrieving structured documents with term-proximity support. In Proceedings of 16th CIKM conference (pp. 771–780)], we demonstrated that, when term-proximity is incorporated into ranking functions, most existing index structures and top-k strategies become quite inefficient. To solve this problem, we built the inverted index based on web page structure and proposed the query processing strategies accordingly. The experimental results indicate that the proposed index structures and query processing strategies significantly improve the top-k efficiency. In this paper, we study the possibility of adopting additional techniques to further improve top-k computation efficiency. We propose a Proximity-Probe Heuristic to make our top-k algorithms more efficient. We also test the efficiency of our approaches on various settings (linear or non-linear ranking functions, exact or approximate top-k processing, etc.).     

Bidirectional delta files

A bidirectional delta file is a novel concept, introduced in this paper, for a two way delta file. Previous work focuses on single way differential compression called forwards and backwards delta files. Here we suggest to efficiently combine them into a single file so that the combined file is smaller than the combination of the two individual ones. Given the bidirectional delta file of two files S and T and the original file S, one can decode it in order to produce T. The same bidirectional delta file is used together with the file T in order to reconstruct S. This paper presents two main strategies for producing an efficient bidirectional delta file in terms of the memory storage it requires; a quadratic time, optimal, dynamic programming algorithm, and a linear time, greedy algorithm. Although the dynamic programming algorithm often produces better results than the greedy algorithm, it is impractical for large files, and it is only used for theoretical comparisons. Experiments between the implemented algorithms and the traditional way of using both forwards and backwards delta files are presented, comparing their processing time and their compression performance. These experiments show memory storage savings of about 25% using this bidirectional delta approach as compared to the compressed delta file constructed using the traditional way, while preserving approximately the same processing time for decoding.     

A statistics-based approach to incrementally update inverted files

Many information retrieval systems use the inverted file as indexing structure. The inverted file, however, requires inefficient reorganization when new documents are to be added to an existing collection. Most studies suggest dealing with this problem by sparing free space in an inverted file for incremental updates. In this paper, we propose a run-time statistics-based approach to allocate the spare space. This approach estimates the space requirements in an inverted file using only a little most recent statistical data on space usage and document update request rate. For best indexing speed and space efficiency, the amount of the spare space to be allocated is determined by adaptively balancing the trade-offs between reorganization reduction and space utilization. Experiment results show that the proposed space-sparing approach significantly avoids reorganization in updating an inverted file, and in the meantime, unused free space can be well controlled such that the file access speed is not affected.     

Online community information seeking: The queries of three communities in Southwestern Ontario

This paper presents not only mycommunityinfo.ca (MCI) as an innovative World Wide Web (WWW)-based community information (CI) site, but also how its unique approach to facilitating online CI searching on the Web reveals through empirical data how people use such information and communication technologies (ICTs) to address their everyday information needs. The geographic focus for this study is on three communities in Southwestern Ontario. MCI collects unobtrusively query data that are logged daily from its own Web site, the Web sites of three municipal governments, and one municipal agency from this region. One year’s worth of these data was supplied to determine the types of CI that are sought through Web searching. A content analysis of a large purposive sample of all of MCI’s query data reveals more specific and diverse conceptual CI needs between and within communities than those reported in other studies employing different data collection methods. As a result, using a centralized approach to online CI access via the WWW by other CI providers such as the 211 network may be a disservice to its users. Additionally, the findings demonstrate how a thorough analysis of such data may improve the informational content and overall design of municipal government Web sites. The analysis of these data also has the potential of improving current CI taxonomies.     

Generating suggestions for queries in the long tail with an inverted index

This paper proposes an efficient and effective solution to the problem of choosing the queries to suggest to web search engine users in order to help them in rapidly satisfying their information needs. By exploiting a weak function for assessing the similarity between the current query and the knowledge base built from historical users’ sessions, we re-conduct the suggestion generation phase to the processing of a full-text query over an inverted index. The resulting query recommendation technique is very efficient and scalable, and is less affected by the data-sparsity problem than most state-of-the-art proposals. Thus, it is particularly effective in generating suggestions for rare queries occurring in the long tail of the query popularity distribution. The quality of suggestions generated is assessed by evaluating the effectiveness in forecasting the users’ behavior recorded in historical query logs, and on the basis of the results of a reproducible user study conducted on publicly-available, human-assessed data. The experimental evaluation conducted shows that our proposal remarkably outperforms two other state-of-the-art solutions, and that it can generate useful suggestions even for rare and never seen queries.     

Ambiguous author query detection using crowdsourced digital library annotations

The name ambiguity problem is especially challenging in the field of bibliographic digital libraries. The problem is amplified when names are collected from heterogeneous sources. This is the case in the Scholarometer system, which performs bibliometric analysis by cross-correlating author names in user queries with those retrieved from digital libraries. The uncontrolled nature of user-generated annotations is very valuable, but creates the need to detect ambiguous names. Our goal is to detect ambiguous names at query time by mining digital library annotation data, thereby decreasing noise in the bibliometric analysis. We explore three kinds of heuristic features based on citations, metadata, and crowdsourced topics in a supervised learning framework. The proposed approach achieves almost 80% accuracy. Finally, we compare the performance of ambiguous author detection in Scholarometer using Google Scholar against a baseline based on Microsoft Academic Search.     

Analyzing imbalance among homogeneous index servers in a web search system

The performance of parallel query processing in a cluster of index servers is crucial for modern web search systems. In such a scenario, the response time basically depends on the execution time of the slowest server to generate a partial ranked answer. Previous approaches investigate performance issues in this context using simulation, analytical modeling, experimentation, or a combination of them. Nevertheless, these approaches simply assume balanced execution times among homogeneous servers (by uniformly distributing the document collection among them, for instance)—a scenario that we did not observe in our experimentation. On the contrary, we found that even with a balanced distribution of the document collection among index servers, correlations between the frequency of a term in the query log and the size of its corresponding inverted list lead to imbalances in query execution times at these same servers, because these correlations affect disk caching behavior. Further, the relative sizes of the main memory at each server (with regard to disk space usage) and the number of servers participating in the parallel query processing also affect imbalance of local query execution times. These are relevant findings that have not been reported before and that, we understand, are of interest to the research community.     

Visual C~# .NET实现信息系统客户端软件升级方法

在VISUAL C# .NET中使用数据库表和配置文件相结合的方法,在服务器上建立虚拟目录存放需要下载的升级文件,通过比对表数据和本地配置文件以判断是否需要下载升级文件来实现信息系统客户端软件的自动升级。     

Storage and retrieval considerations of binary data bases

A binary approach to data storage and retrieval is introduced. It views the data base as a two-dimensional matrix that relates entities to all possible values the attributes of these entities may take. As such, it provides a unified solution to the two conflicting types of data base transactions—operational and managerial. An analytical investigation of the feasibility of binary storage and a compression method for reducing meaningless areas of the matrix are presented. Storage efficiencies of binary and conventional inverted file methods are compared and evaluated. An analysis of retrieval considerations associated with the binary matrix is given, particularly the issue of going from high to low orders of compression. Results of these analyses indicate that the binary data base's efficiency increases with increases in query complexity. Future research directions are sited and discussed.