LZgrep: a Boyer–Moore string matching tool for Ziv–Lempel compressed text

We present a Boyer–Moore (BM) approach to string matching over LZ78 and LZW compressed text. The idea is to search the text directly in compressed form instead of decompressing and then searching it. We modify the BM approach so as to skip text using the characters explicitly represented in the LZ78/LZW formats, modifying the basic technique where the algorithm can choose which characters to inspect. We present and compare several solutions for single and multipattern searches. We show that our algorithms obtain speedups of up to 50% compared to the simple decompress‐then‐search approach. Finally, we present a public tool, LZgrep, which uses our algorithms to offer grep‐like capabilities directly searching files compressed using Unix's Compress, a LZW compressor. LZgrep can also search files compressed with Unix gzip, using new decompress‐then‐search techniques we develop, which are faster than the current tools. This way, users can always keep their files in compressed form and still search them, uncompressing only when they want to see them. Copyright © 2005 John Wiley & Sons, Ltd.     

JAMES: An object‐oriented Java framework for discrete optimization using local search metaheuristics

This paper describes the Java Metaheuristics Search framework (JAMES, v1.1): an object‐oriented Java framework for discrete optimization using local search algorithms that exploits the generality of such metaheuristics by clearly separating search implementation and application from problem specification. A wide range of generic local searches are provided, including (stochastic) hill climbing, tabu search, variable neighbourhood search and parallel tempering. These can be applied to any user‐defined problem by plugging in a custom neighbourhood for the corresponding solution type. Using an automated analysis workflow, the performance of different search algorithms can be compared in order to select an appropriate optimization strategy. Implementations of specific components are included for subset selection, such as a predefined solution type, generic problem definition and several subset neighbourhoods used to modify the set of selected items. Additional components for other types of problems (e.g. permutation problems) are provided through an extensions module which also includes the analysis workflow. In comparison with existing Java metaheuristics frameworks that mainly focus on population‐based algorithms, JAMES has a much lower memory footprint and promotes efficient application of local searches by taking full advantage of move‐based evaluation. Releases of JAMES are deployed to the Maven Central Repository so that the framework can easily be included as a dependency in other Java applications. The project is fully open source and hosted on GitHub. More information can be found at http://www.jamesframework.org . Copyright © 2016 John Wiley & Sons, Ltd.     

基于压缩后缀数组的搜索引擎技术

搜索引擎(Search Eng ine)技术是在网络数据成指数级增加的情况下出现的新技术。然而现在的搜索引擎在检索时都采用的是倒排文件,从后缀数据技术出发探讨了压缩后缀数组(Com pressed Su ffix A rray)技术在搜索引擎技术中的应用,从而大大提高了搜索引擎的性能。     

Binary search trees in secondary memory

Summary Binary search trees are shown to be reasonable alternatives to multiway trees for files stored in magnetic bubble memory. An algorithm for maintaining AVL trees is shown to be by far the most efficient of eight algorithms considered, when applied to secondary memory. A simplified model for analyzing the AVL algorithm is developed. A practical AVL algorithm for secondary memory is presented. Simulation results showing the performance of the AVL algorithm and a basic nonbalancing algorithm are given.     

Lightweight Data Indexing and Compression in External Memory

In this paper we describe algorithms for computing the Burrows-Wheeler Transform (bwt) and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size n, they use only n bits of working space on disk while all previous approaches use Θ(nlog n) bits. This is achieved by building the bwt directly without passing through the construction of the Suffix Array/Tree data structure. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses. We also present a scan-based algorithm for inverting the bwt that uses Θ(n) bits of working space, and a lightweight internal-memory algorithm for computing the bwt which is the fastest in the literature when the available working space is o(n) bits. Finally, we prove lower bounds on the complexity of computing and inverting the bwt via sequential scans in terms of the classic product: internal-memory space × number of passes over the disk data, showing that our algorithms are within an O(log n) factor of the optimal.     

Probabilistic GRASP-Tabu Search algorithms for the UBQP problem

This paper presents two algorithms combining GRASP and Tabu Search for solving the Unconstrained Binary Quadratic Programming (UBQP) problem. We first propose a simple GRASP-Tabu Search algorithm working with a single solution and then reinforce it by introducing a population management strategy. Both algorithms are based on a dedicated randomized greedy construction heuristic and a tabu search procedure. We show extensive computational results on two sets of 31 large random UBQP instances and one set of 54 structured instances derived from the MaxCut problem. Comparisons with state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that the reinforced GRASP-Tabu Search algorithm is able to improve the previous best known results for 19 MaxCut instances.     

Revisiting bounded context block‐sorting transformations

The Burrows–Wheeler Transform (BWT ) produces a permutation of a string X, denoted X^?, by sorting the n cyclic rotations of X into full lexicographical order and taking the last column of the resulting n×n matrix to be X^?. The transformation is reversible in time. In this paper, we consider an alteration to the process, called k‐BWT , where rotations are only sorted to a depth k. We propose new approaches to the forward and reverse transform, and show that the methods are efficient in practice. More than a decade ago, two algorithms were independently discovered for reversing k‐BWT , both of which run in time. Two recent algorithms have lowered the bounds for the reverse transformation to and, respectively. We examine the practical performance for these reversal algorithms. We find that the original approach is most efficient in practice, and investigates new approaches, aimed at further speeding reversal, which store precomputed context boundaries in the compressed file. By explicitly encoding the context boundaries, we present an reversal technique that is both efficient and effective. Finally, our study elucidates an inherently cache‐friendly – and hitherto unobserved – behavior in the reverse k‐BWT , which could lead to new applications of the k‐BWT transform. In contrast to previous empirical studies, we show that the partial transform can be reversed significantly faster than the full transform, without significantly affecting compression effectiveness. Copyright © 2011 John Wiley & Sons, Ltd.     

Hardware accelerator for solving 0–1 knapsack problems using binary harmony search

The 0–1 knapsack problem (KP) is a well-known intractable optimization problem with wide range of applications. Harmony Search (HS) is one of the most popular metaheuristic algorithms to successfully solve 0–1 KPs. Nevertheless, metaheuristic algorithms are generally compute intensive and slow when implemented in software. In this paper, we present an FPGA-based pipelined hardware accelerator to reduce computation time for solving large dimension 0–1 KPs using Binary Harmony Search algorithm. The proposed architecture exploits the intrinsic parallelism of population based metaheuristic algorithm and the flexibility and parallel processing capabilities of FPGAs to perform the computation concurrently thus enhancing performance. To validate the efficiency of the proposed hardware accelerator, experiments were conducted using a large number of 0–1 KPs. Comparative analysis on experimental results reveals that the proposed approach offers promising speedups of 51× – 111× as compared with a software implementation and 2× – 5× as compared with a hardware implementation of Binary Particle Swarm Optimization algorithm.     

Open source libraries for information retrieval

Information retrieval tools, popularly referred to as indexers or search engines, support searches of a local file system, intranet, database, or desktop as well as the Web. They also let you add IR functionality to any application that needs a search method as part of a more complex procedure -for example, periodic surveys about your customers. When you develop your own applications, you can design a search GUI specially tailored for your employees, customers, or type of business. There are two broad tool classes. Desktop search tools usually browse local files. Yahoo Desktop Search is an example product. However, desktop tools sometimes extend to the Web (for example, Google Desktop Search) or to network drives (MSN Toolbar). Enterprise search tools cover a broader search area - an intranet, IP subnets, file systems, or databases. Google Search Appliance is an example commercial product, and you can integrate it with Google Desktop Search to provide a unified search interface.     

Rank and select revisited and extended

The deep connection between the Burrows–Wheeler transform (BWT) and the so-called rank and select data structures for symbol sequences is the basis of most successful approaches to compressed text indexing. Rank of a symbol at a given position equals the number of times the symbol appears in the corresponding prefix of the sequence. Select is the inverse, retrieving the positions of the symbol occurrences. It has been shown that improvements to rank/select algorithms, in combination with the BWT, turn into improved compressed text indexes.     

Efficient admission control algorithms for multimedia servers

In this paper, we have proposed efficient admission control algorithms for multimedia storage servers that are providers of variable-bit-rate media streams. The proposed schemes are based on a slicing technique and use aggressive methods for admission control. We have developed two types of admission control schemes: Future-Max (FM) and Interval Estimation (IE). The FM algorithm uses the maximum bandwidth requirement of the future to estimate the bandwidth requirement. The IE algorithm defines a class of admission control schemes that use a combination of the maximum and average bandwidths within each interval to estimate the bandwidth requirement of the interval. The performance evaluations done through simulations show that the server utilization is improved by using the FM and IE algorithms. Furthermore, the quality of service is also improved by using the FM and IE algorithms. Several results depicting the trade-off between the implementation complexity, the desired accuracy, the number of accepted requests, and the quality of service are presented.     

Fast algorithms for frequent itemset mining using FP-trees

Efficient algorithms for mining frequent itemsets are crucial for mining association rules as well as for many other data mining tasks. Methods for mining frequent itemsets have been implemented using a prefix-tree structure, known as an FP-tree, for storing compressed information about frequent itemsets. Numerous experimental results have demonstrated that these algorithms perform extremely well. In this paper, we present a novel FP-array technique that greatly reduces the need to traverse FP-trees, thus obtaining significantly improved performance for FP-tree-based algorithms. Our technique works especially well for sparse data sets. Furthermore, we present new algorithms for mining all, maximal, and closed frequent itemsets. Our algorithms use the FP-tree data structure in combination with the FP-array technique efficiently and incorporate various optimization techniques. We also present experimental results comparing our methods with existing algorithms. The results show that our methods are the fastest for many cases. Even though the algorithms consume much memory when the data sets are sparse, they are still the fastest ones when the minimum support is low. Moreover, they are always among the fastest algorithms and consume less memory than other methods when the data sets are dense.     

ADAPTIVE RANKS CLONE AND k‐NEAREST NEIGHBOR LIST–BASED IMMUNE MULTI‐OBJECTIVE OPTIMIZATION

Artificial immune systems (AIS) are computational systems inspired by the principles and processes of the vertebrate immune system. The AIS‐based algorithms typically exploit the immune system's characteristics of learning and adaptability to solve some complicated problems. Although, several AIS‐based algorithms have proposed to solve multi‐objective optimization problems (MOPs), little focus have been placed on the issues that adaptively use the online discovered solutions. Here, we proposed an adaptive selection scheme and an adaptive ranks clone scheme by the online discovered solutions in different ranks. Accordingly, the dynamic information of the online antibody population is efficiently exploited, which is beneficial to the search process. Furthermore, it has been widely approved that one‐off deletion could not obtain excellent diversity in the final population; therefore, a k‐nearest neighbor list (where k is the number of objectives) is established and maintained to eliminate the solutions in the archive population. The k‐nearest neighbors of each antibody are founded and stored in a list memory. Once an antibody with minimal product of k‐nearest neighbors is deleted, the neighborhood relations of the remaining antibodies in the list memory are updated. Finally, the proposed algorithm is tested on 10 well‐known and frequently used multi‐objective problems and two many‐objective problems with 4, 6, and 8 objectives. Compared with five other state‐of‐the‐art multi‐objective algorithms, namely NSGA‐II, SPEA2, IBEA, HYPE, and NNIA, our method achieves comparable results in terms of convergence, diversity metrics, and computational time.     

On the asymptotic performance of IDA*

Since best‐first search algorithms such as A* require large amounts of memory, they sometimes cannot run to completion, even on problem instances of moderate size. This problem has led to the development of limited‐memory search algorithms, of which the best known is IDA*. This paper presents the following results about IDA* and related algorithms: 1) The analysis of asymptotic optimality for IDA* in [R.E. Korf, Optimal path finding algorithms, in: Search in Artificial Intelligence, eds. L. Kanal and V. Kumar (Springer‐Verlag, 1988) pp. 200-222] is incorrect. There are trees satisfying the asymptotic optimality conditions given in [R.E. Korf, Optimal path finding algorithms, in: Search in Artificial Intelligence, eds. L. Kanal and V. Kumar (Springer‐Verlag, 1988) pp. 200-222] for which IDA* is not asymptotically optimal. 2) To correct the above problem, we state and prove necessary and sufficient conditions for asymptotic optimality of IDA* on trees. On trees not satisfying our conditions, we show that no best‐first limited‐memory search algorithm can be asymptotically optimal. 3) On graphs, IDA* can perform quite poorly. In particular, there are graphs on which IDA* does Ω(2^2N) node expansions where N is the number of nodes expanded by A*. This revised version was published online in June 2006 with corrections to the Cover Date.     

Comparing keyword search to semantic search: a case study in solving crossword puzzles using the Google™ API

Keyword‐based search engines such as Google? index Web pages for human consumption. Sophisticated as such engines have become, surveys indicate almost 25% of Web searchers are unable to find useful results in the first set of URLs returned (Technology Review, March 2004). The lack of machine‐interpretable information on the Web limits software agents from matching human searches to desirable results. Tim Berners‐Lee, inventor of the Web, has architected the Semantic Web in which machine‐interpretable information provides an automated means to traversing the Web. A necessary cornerstone application is the search engine capable of bringing the Semantic Web together into a searchable landscape. We implemented a Semantic Web Search Engine (SWSE) that performs semantic search, providing predictable and accurate results to queries. To compare keyword search to semantic search, we constructed the Google CruciVerbalist (GCV), which solves crossword puzzles by reformulating clues into Google queries processed via the Google API. Candidate answers are extracted from query results. Integrating GCV with SWSE, we quantitatively show how semantic search improves upon keyword search. Mimicking the human brain's ability to create and traverse relationships between facts, our techniques enable Web applications to ‘think’ using semantic reasoning, opening the door to intelligent search applications that utilize the Semantic Web. Copyright © 2007 John Wiley & Sons, Ltd.     

Minkowski‐type distance measures for generalized orthopair fuzzy sets

The generalized orthopair fuzzy set inherits the virtues of intuitionistic fuzzy set and Pythagorean fuzzy set in relaxing the restriction on the support for and support against. The very lax requirement provides decision makers great freedom in expressing their beliefs about membership grades, which makes generalized orthopair fuzzy sets having a wide scope of application in practice. In this paper, we present the Minkowski‐type distance measures, including Hamming, Euclidean, and Chebyshev distances, for q‐rung orthopair fuzzy sets. First, we introduce the Minkowski‐type distances of q‐rung orthopair membership grades, based on which we can rank orthopairs. Second, we propose several distances over q‐rung orthopair fuzzy sets on a finite discrete universe and subsequently discuss their applications to multiattribute decision‐making problems. Then we extend these results to a continuous universe, both bounded and unbounded cases are considered. Some illustrative examples are employed to substantiate the conceptual arguments.     

Seeker optimization algorithm for interference suppression of linear antenna arrays by controlling position‐only,phase‐only,and amplitude‐only

In this article, a stochastic search technique based on seeker optimization algorithm (SOA) is proposed for null steering of linear antenna arrays by controlling the position‐only, phase‐only, and amplitude‐only. The SOA is relatively new optimization algorithm based on the concept of simulating the act of humans' intelligent search with their memory, experience, and uncertainty reasoning. Several numerical examples of Chebyshev pattern with the single, multiple, and broad nulls imposed at the directions of interference are given to illustrate the performance and flexibility of the proposed algorithm. For a comparison, the nulling patterns obtained by simulated annealing (SA) and tabu search (TS) algorithms are also given. Furthermore, the results of SOA are statistically compared with those of SA and TS algorithms. The statistical results of simulations show that SOA is superior to the other compared algorithms. © 2011 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2011.     

Register spilling via transformed interference equations for PAC DSP architecture

Digital signal processors (DSPs) with very long instruction word (VLIW) data‐path architectures are increasingly being deployed on embedded devices for multimedia processing applications. To reduce the power consumption and design cost of VLIW DSP processors, distributed register files and multibank register architectures are being adopted to reduce the number of read and write ports associated with register files, which presents new challenges for devising compiler optimization schemes. This paper addresses the issues of reducing the spill code for a VLIW DSP with distributed register files. Spill code produced by register allocation is traditionally handled by memory spills, but the multibank register‐file architecture provides the opportunity to spill‐out register values onto different register banks. We present a conceptual framework based on the universal and the proxy interference graphs to model the live ranges of registers for spilling codes to different register banks. Heuristic algorithms are then developed on the basis of this concept. By heuristically estimating the register pressure for each register file, we treat different register banks as optional spilling locations in addition to traditional spilling to memory. Experiments were performed on the parallel architecture core VLIW DSP with distributed register files by incorporating our proposed optimization schemes into an Open64‐based compiler. The experimental results show that our approach can improve the performances on average for DSPStone and MiBench benchmarks with spilling cases by 7.1% and 21.6%, respectively, compared with the one always handling spill code in memory. Copyright © 2013 John Wiley & Sons, Ltd.     

A secure framework exploiting content guided and automated algorithms for real time video searching

This paper presents an architecture that allows End Users, via the services of Search Engines, to search, in a secure and efficient way, the video content belonging to Content Providers. The search can be accomplished with any searching scheme that the Search Engines wish to provide, as long as certain security constraints are met. However we propose specific algorithms that demonstrate an efficient way to search video data without sacrificing security effectiveness of the system. The search is completed without the End Users or Search Engines needing to purchase the premium content beforehand, and without the Content Providers needing to purchase the search technology. The business motivation of this technique is to assist End Users to purchase content best suiting their requirements—they are offered search results only, not actual content. The objective is to face the problem caused by the current segregation between content ownership and video processing technology ownership. To face this segregation, we present an architecture that guarantees security of Content Provider’s data and Search Engine’s technology and we also present two innovative algorithms that make real time video searching a feasible process. Particularly these algorithms (a) organize video content into a graph based hierarchical structure and (b) perform content guided, non interactive and real time search by exploiting the graph based video structures. The proposed algorithms are incorporated in the presented architecture under the given security constraints. Experimental results and comparisons with conventional techniques are presented to demonstrate the outperformance of the proposed algorithms.