Voting techniques for expert search

In an expert search task, the users’ need is to identify people who have relevant expertise to a topic of interest. An expert search system predicts and ranks the expertise of a set of candidate persons with respect to the users’ query. In this paper, we propose a novel approach for predicting and ranking candidate expertise with respect to a query, called the Voting Model for Expert Search. In the Voting Model, we see the problem of ranking experts as a voting problem. We model the voting problem using 12 various voting techniques, which are inspired from the data fusion field. We investigate the effectiveness of the Voting Model and the associated voting techniques across a range of document weighting models, in the context of the TREC 2005 and TREC 2006 Enterprise tracks. The evaluation results show that the voting paradigm is very effective, without using any query or collection-specific heuristics. Moreover, we show that improving the quality of the underlying document representation can significantly improve the retrieval performance of the voting techniques on an expert search task. In particular, we demonstrate that applying field-based weighting models improves the ranking of candidates. Finally, we demonstrate that the relative performance of the voting techniques for the proposed approach is stable on a given task regardless of the used weighting models, suggesting that some of the proposed voting techniques will always perform better than other voting techniques. Extended version of ‘Voting for candidates: adapting data fusion techniques for an expert search task’. C. Macdonald and I. Ounis. In Proceedings of ACM CIKM 2006, Arlington, VA. 2006. doi: 10.1145/1183614.1183671.     

A beam search algorithm for PFSA inference

In the past, many methods have been proposed for the inference of probabilistic and non-probabilistic finite state automata from positive examples of their behaviour. In this paper, we introduce a search method guided by the information-theoretic Minimum Message Length principle to infer Probabilistic Finite State Automata (PFSA).¹ The method is a beam search technique that searches for the best PFSA that accounts for a given dataset. Results of testing this method against some earlier algorithms are presented. A simulated annealing version of the beam search algorithm is also described as ongoing research in the area.The abbreviation PFSA is used to denote both the singular and plural of these automata     

Compression techniques for fast external sorting

External sorting of large files of records involves use of disk space to store temporary files, processing time for sorting, and transfer time between CPU, cache, memory, and disk. Compression can reduce disk and transfer costs, and, in the case of external sorts, cut merge costs by reducing the number of runs. It is therefore plausible that overall costs of external sorting could be reduced through use of compression. In this paper, we propose new compression techniques for data consisting of sets of records. The best of these techniques, based on building a trie of variable-length common strings, provides fast compression and decompression and allows random access to individual records. We show experimentally that our trie-based compression leads to significant reduction in sorting costs; that is, it is faster to compress the data, sort it, and then decompress it than to sort the uncompressed data. While the degree of compression is not quite as great as can be obtained with adaptive techniques such as Lempel-Ziv methods, these cannot be applied to sorting. Our experiments show that, in comparison to approaches such as Huffman coding of fixed-length substrings, our novel trie-based method is faster and provides greater size reductions. Preliminary versions of parts of this paper, not including the work on vargram compression” [41]     

新的多八边形快速运动估计算法

由于对编码的高精度和低复杂度的要求,H.264视频编码标准已经采用了UMHexagonS算法作为其可行的块运动估计实施方案。提出了一种新的UMHexagonS改进算法,改进主要在三个方面：第一,增加了一个新的初始预测矢量,以避免过早陷入局部最优;第二,一个小八边形搜索和两个后续的小菱形搜索取代了UMHexagonS算法中的5×5全搜索,这在一定程度上减少了计算量;第三,多八边形格点搜索取代了多六边形格点搜索,这不仅减轻了运算量负担,也在方向上能更好更快地搜索到最佳运动矢量。实验结果表明,所提出的方法不仅能保证UMHexagonS算法的编码效果,同时还能减少5%~10%的运算量,从而节省编码时间。     

改进的矢量量化码字快速搜索法

矢量量化技术是一种高效和有竞争力的数据压缩方法,但由于其编解码过程中需要较大的计算量影响了其使用。提出了一种改进的基于子矢量特征值的码字快速搜索算法。算法充分利用矢量的3个特征值即和值、子矢量和值以及方差,建立起一种5步码字排除法,使得算法能够快速排除大部分不匹配码字,实现减少计算量的目的。仿真实验结果表明,算法的计算量要小于ZhiBin算法、Pan算法以及Chen算法,证明了改进算法的有效性。     

AMR-WB固定码本快速搜索新方法

在AMR-WB中,固定码本搜索是影响性能和复杂度的关键模块,约占总复杂度的40%。为了降低计算量,提出了一种码字分裂、子码字脉冲取代的高效码本搜索算法。该算法包括四步：一个初始码字分裂为两个或更多的子码字;每个子码字通过最不重要脉冲取代法进行更新;更新后的子码字合成一个候选的码字;比较初始码字和候选码字,选择优者作为最后的码字。实验表明,与传统方法相比,编码时间减小约16%。     

一种改进的快速搜索算法

提出了一种基于预测的自适应六边形搜索方法,并将此算法与其他常用的快速运动估计算法进行实验比较。实验结果表明:该算法有效地降低了搜索点数,搜索精度比较接近于FS算法,在一定程度上提高了搜索的效率。     

Preference-oriented mining techniques for location-based store search

With the development of wireless telecommunication technologies, a number of studies have been done on the issues of location-based services due to wide applications. Among them, one of the active topics is the location-based search. Most of previous studies focused on the search of nearby stores, such as restaurants, hotels, or shopping malls, based on the user’s location. However, such search results may not satisfy the users well for their preferences. In this paper, we propose a novel data mining-based approach, named preference-oriented location-based search (POLS), to efficiently search for k nearby stores that are most preferred by the user based on the user’s location, preference, and query time. In POLS, we propose two preference learning algorithms to automatically learn user’s preference. In addition, we propose a ranking algorithm to rank the nearby stores based on user’s location, preference, and query time. To the best of our knowledge, this is the first work on taking temporal location-based search with automatic user preference learning into account simultaneously. Through experimental evaluations on the real dataset, the proposed approach is shown to deliver excellent performance.     

Using tabu search techniques for graph coloring

Tabu search techniques are used for moving step by step towards the minimum value of a function. A tabu list of forbidden movements is updated during the iterations to avoid cycling and being trapped in local minima. Such techniques are adapted to graph coloring problems. We show that they provide almost optimal colorings of graphs having up to 1000 nodes and their efficiency is shown to be significantly superior to the famous simulated annealing.     

Local search techniques for a routing-packing problem

We propose a complex real-world problem in logistics that integrates routing and packing aspects. It can be seen as an extension of the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) introduced by Gendreau, Iori, Laporte, and Martello (2006). The 3L-CVRP consists in finding a set of routes that satisfies the demand of all customers, minimizes the total routing cost, and guarantees a packing of items that is feasible according to loading constraints. Our problem formulation includes additional constraints in relation to the stability of the cargo, to the fragility of items, and to the loading and unloading policy. In addition, it considers the possibility of split deliveries, so that each customer can be visited more than once. We propose a local search approach that considers the overall problem in a single stage. It is based on a composite strategy that interleaves simulated annealing with large-neighborhood search. We test our solver on 13 real-world instances provided by our industrial partner, which are very diverse in size and features. In addition, we compare our solver on benchmarks from the literature of the 3L-CVRP showing that our solver performs well compared to other approaches proposed in the literature.     

Probabilistic performance analysis for parallel search techniques

This paper discusses the performance analysis of two generic fundamental parallel search techniques on shared memory multi-processor systems in solving the constraint satisfaction problem (CSP). Probabilistic analysis on their expected computation steps needed and their inherent load-balancing capability is performed. Corresponding experimental results are alsoprovided to verify the correctness of the proposed analysis. This fundamental analysis approach can be further applied to various advanced parallel search techniques or various problem solving techniques on parallel platforms. This research was supported in part by the University of Texas at San Antonio under the Faculty Research Award program     

Extended beam search for non-exhaustive state space analysis

State space explosion is a major problem in both qualitative and quantitative model checking. This article focuses on using beam search, a heuristic search algorithm, for pruning weighted state spaces while generating. The original beam search is adapted to the state space generation setting and two new variants, motivated by practical case studies, are devised. These beam searches have been implemented in the μCRL toolset and applied on several case studies reported in the article.     

指令集仿真器的关键技术

为适应嵌入式系统开发中对指令集仿真器仿真速度的要求,提出一种改进的指令集仿真技术.该技术在现有的静态多核仿真器基础上引入指令预处理、动态译码缓存、多线程C函数生成和动态调度运行等技术,以实现对仿真器性能的优化.该技术已成功应用于中国科学院微电子所自主研发的IME-Diamond DSP处理器的多核指令集仿真器OPT-ISS中.实际应用程序测试结果表明,该技术在仿真速度提升方面有明显效果.     

基于差分的块匹配运动估计算法

通过研究块匹配算法当中菱形算法中的冗余性,提出了一种基于差分的块匹配快速搜索算法（DBS）,利用搜索点的匹配误差之间的大小关系,预测最优点的搜索方向,减少了搜索点数,通过实验表明了该算法在保证了匹配精度的同时获得了更高的搜索速度。     

Combining CPU and GPU architectures for fast similarity search

The Signature Quadratic Form Distance on feature signatures represents a flexible distance-based similarity model for effective content-based multimedia retrieval. Although metric indexing approaches are able to speed up query processing by two orders of magnitude, their applicability to large-scale multimedia databases containing billions of images is still a challenging issue. In this paper, we propose a parallel approach that balances the utilization of CPU and many-core GPUs for efficient similarity search with the Signature Quadratic Form Distance. In particular, we show how to process multiple distance computations and other parts of the search procedure in parallel, achieving maximal performance of the combined CPU/GPU system. The experimental evaluation demonstrates that our approach implemented on a common workstation with 2?GPU cards outperforms traditional parallel implementation on a high-end 48-core NUMA server in terms of efficiency almost by an order of magnitude. If we consider also the price of the high-end server that is ten times higher than that of the GPU workstation then, based on price/performance ratio, the GPU-based similarity search beats the CPU-based solution by almost two orders of magnitude. Although proposed for the SQFD, our approach of fast GPU-based similarity search is applicable for any distance function that is efficiently parallelizable in the SIMT execution model.     

Compact and fast algorithms for safe regular expression search

This article describes an improvement of the brute force determinization algorithm in the case of homogeneous nondeterministic finite automata (NFAs), as well as its application to pattern matching. Brute force determinization with limited memory may provide a partially determinized automaton, but its bounded complexity makes it a safe procedure contrary to the classical subset construction. Actually, our algorithm is inspired by both recent results of Champarnaud concerning the subset automaton of a homogeneous NFA and the algorithm recently designed by Navarro and Raffinot to implement the brute force determinization of the Glushkov NFA of a regular pattern. Our algorithm significantly improves Navarro–Raffinot's one since it has an average exponentially smaller memory requirement for a given level of determinization, which, considering a bounded memory, implies a quadratically smaller parsing time. This algorithm has been implemented in CCP software (http://www.univ-rouen.fr/LIFAR/aia/ccp.html). Tests have been carried out in the field of text processing and biology. Experimental results are reported.     

Look-ahead on pushdowns

The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the non-deterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look-ahead on the input, and LL-regular iterated indexed grammars.     

Novel cross-diamond-hexagonal search algorithms for fast block motion estimation

We propose two cross-diamond-hexagonal search (CDHS) algorithms, which differ from each other by their sizes of hexagonal search patterns. These algorithms basically employ two cross-shaped search patterns consecutively in the very beginning steps and switch using diamond-shaped patterns. To further reduce the checking points, two pairs of hexagonal search patterns are proposed in conjunction with candidates found located at diamond corners. Experimental results show that the proposed CDHSs perform faster than the diamond search (DS) by about 144% and the cross-diamond search (CDS) by about 73%, whereas similar prediction quality is still maintained.     

Look-ahead and look-behind shortcuts in large item category hierarchies: The impact on search performance

Websites use shortcuts to facilitate navigation of large hierarchies of item categories. Two common types of shortcuts used for this purpose are location breadcrumbs and down-to-child/up-to-parent links; frequently both are employed simultaneously. The combined used of these shortcuts provide proximal cues which enable the user to look-ahead and look-behind in the navigational structure. In this study, the impact of shortcut usage on search performance on a known-item search task is estimated. A controlled experiment was conducted using a realistic hypertext hierarchy of item categories. The results indicate that greater use of shortcuts decreases both time on task and lostness for the user, and that the decrease is associated with increased depth in the hierarchy. These findings provide insight into possible performance trade-offs involved in website designs that include look-ahead shortcuts for navigating large item category hierarchies.     

A fast VQ codebook search with initialization and search order

Vector quantization (VQ), a lossy image compression, is widely used for many applications due to its simple architecture, fast decoding ability, and high compression rate. Traditionally, VQ applies the full search algorithm to search for the codeword that best matches each image vector in the encoding procedure. However, matching in this manner consumes a lot of computation time and leads to a heavy burden for the VQ method. Therefore, Torres and Huguet proposed a double test algorithm to improve the matching efficiency. However, their scheme does not include an initiation strategy to choose an initially searched codeword for each image vector, and, as a result, matching efficiency may be affected significantly. To overcome this drawback, we propose an improved double test scheme with a fine initialization as well as a suitable search order. Our experimental results indicate that the computation time of the double test algorithm can be significantly reduced by the proposed method. In addition, the proposed method is more flexible than existing schemes.