基于列式数据库的RDF数据分布式存储

由于RDF数据的爆炸式增长以及关系型数据库自身的瓶颈,使得几年来NOSQL数据库成为人们研究的热点,其中列式数据库尤为突出.在比较了目前流行的RDF存储方案前提下,提出了基于列式数据库的RDF数据分布式存储方案,同时还提出了列式数据库的SPARQL查询方案,最后通过实验对比了基于列式数据库与基于图数据库的RDF分布式数据存储方案的处理性能.     

完全相容稳定模糊谓词转换器

谓词转换器语义是用程序验证技术来定义程序语言的一种方式.为描述程序的语义,在稳定模糊谓词的基础上建立完全相容稳定模糊谓词转换器,讨论完全相容稳定模糊谓词转换器的拓扑语义. 同时给出它与状态转换器之间的一个保序关系,说明完全相容稳定模糊谓词转换器一定是状态转换器.     

面向隐私保护的个性化搜索结果排序方法研究

针对个性化搜索中用户隐私保护的需求,提出一种面向隐私保护的个性化搜索结果排序方法.方法基于向量空间模型,引入安全点积计算方法来计算搜索相似度,旨在实现用户隐私保护的同时提高个性化搜索服务质量.首先分析了目前常用的搜索排序相似度计算方法存在的不足,然后分别介绍了向量空间模型和安全点积计算,最后详细介绍了面向隐私保护的个性化搜索结果排序方法,并对其性能进行了分析.     

基于网络搜索数据和机器学习的票房预测模型

电影票房预测对于管理部门一直是一项重要而复杂的工作。电影票房相关变量复杂多变,且数据获取难度较大是制约当前研究的主要因素。相比之下,网络搜索数据是互联网公司发布的用于记录网民搜索行为的结构化数据,能客观及时反映事物的发展趋势。本研究建立了基于网络搜索数据的混合预测模型。首先,匹配与测试集最相似的训练数据构建最优训练集(OTS)。其次,应用帝国竞争算法(ICA)选择最小二乘支持向量机(LSSVM)的最佳参数组合。最后,使用优化模型进行预测。为了测试模型的效果,使用中国大陆上映的电影票房数据进行模拟实验。结果表明混合模型具有更高的预测精度。本研究所构建的模型适用于中国电影业的票房预测,可为有关部门提供决策参考。     

可由用户持续发展的几何自动推理平台

提出并实现了可由用户持续发展的几何自动推理平台(SGARP).它由知识库、知识编辑器、信息库、推理引擎、信息查询窗口和动态几何作图系统等六部分组成.在这个平台上,用户可以添加几何对象、谓词和规则,也可以综合使用多种推理方法进行推理.     

DHT P2P网络中基于RDF的高效资源查询算法

P2P网络中资源的标注和查询是一个NP问题,本文提出了一种从RDF描述和查询的路径表达式中提取哈希串的算法,建立了从RDF描述和查询到DHTP2P路由空间的映射,从而在DHTP2P网络上实现了对以RDF描述的资源进行概念查询的支持,有效地改善了DHTP2P网络的查询处理能力。     

基于模式约束的XML数据存储和索引技术

对XML数据建立有效的索引,是左右XML数据处理性能的重要因素.现有的索引和存储策略,大部分以丢失结构信息为代价,不利于结构查询和更新.XMLSchema作为描述XML文档结构信息的标准,对文档和查询路径进行有效性验证提供保证,基于此提出了一种基于XMLmSchema模式约束的XML文档数据索引技术SBXI,用于文档数据存储和查询的导航,提高了存储和查询效率,具有较高的空间利用率和较低的索引维护代价,并支持含有多个谓词的复杂查询.     

基于抢占优先排队的P2P网络资源搜索机制及性能分析

受移动P2P网络环境影响和节点异构性及自身资源的限制,常存在节点不愿参与资源查询的自私行为,针对该问题,文章基于排队理论建立一个新的资源搜索机制,通过令协同合作度高的节点享有较高的查询优先级,自私性节点需接受第二次查询服务的策略,激励节点积极参与资源查询,减少用户访问时延和资源节点丢失率,提高节点服务质量及系统整体效用,建立P2P网络高效资源搜索机制.构造带有抢占优先、二次可选服务以及同步多重工作休假的排队模型,利用拟生灭过程和矩阵几何解方法得到该资源搜索机制的稳态分布,并求出该机制的平均队长,平均逗留时间,总能耗等性能指标,通过数值实验,分析参数变化对系统的各项性能指标的影响,最后构造系统的效用函数,讨论资源查询节点的最大个人收益,社会收益以及该资源搜索机制的最优服务率.     

多重因素约束下的网格搜索对策问题研究

首次基于搜索成本及搜索资源等限制因素,构造局中人面向多重约束条件的可行策略集合,建立相应的搜索空间;在给定搜索点权值的基础上,考虑搜索成本与搜索成功概率等因素,构造相应的支付函数,建立多重因素约束下的网格搜索对策模型.为简化模型求解,将对策论问题转化为约束最优化问题,求解约束问题获得最优值,转化为模型的对策值,并给出双方最优混合策略.最后,给出军事想定实例,说明上述模型的实用性及方法的有效性.     

提高维吾尔文搜索质量的一些关键技术研究

维吾尔语和土耳其语、乌兹别克语、哈萨克语等同属于阿尔泰语系突厥语分支,是一种粘着型语言,具有丰富的构词合构形附加成分.主要分布于中国新疆维吾尔自治区,以及中西亚地区的维吾尔族使用.目前使用基于阿拉伯文字母的维吾尔文.当前用google,bing等搜索引擎搜索维吾尔文时搜索结果不包括该词语的构词合构形附加成分等其它形式.严重影响了搜索结果的准确性.通过词干提取和词缀附加生成词语组合的方法以解决提高维吾尔文搜索质量的问题.此问题解决,将在大幅度提高维吾尔文搜索的准确性,并针对提高其它突厥语族语言(土耳其语、乌兹别克语、哈萨克语等)的搜索质量、数据挖掘、数据分析、数据安全、自然语言理解等研究领域有一定的参考价值.     

Query Optimization in Distributed Relational Databases

The query optimizer is the DBMS (data base management system) component whose task is to find an optimal execution plan for a given input query. Typically, optimization is performed using dynamic programming. However, in distributed execution environments, this approach becomes intractable, due to the increase in the search space incurred by distribution. We propose the use of the tabu search metaheuristic for distributed query optimization. A hashing-based data structure is used to keep track of the search memory, simplifying significantly the implementation of tabu search. To validate this proposal, we implemented the tabu search strategy in the scope of an existing optimizer, which runs several search strategies. We focus our attention on the more difficult problems in terms of the query execution space, in which the solution space includes bushy execution plans and Cartesian products, which are not dealt with very often in the literature. Using a real-life application, we show the effectiveness of tabu search when compared to other strategies.     

Markovian analysis for automatic new topic identification in search engine transaction logs

Topic analysis of search engine user queries is an important task, since successful exploitation of the topic of queries can result in the design of new information retrieval algorithms for more efficient search engines. Identification of topic changes within a user search session is a key issue in analysis of search engine user queries. This study presents an application of Markov chains in the area of search engine research to automatically identify topic changes in a user session by using statistical characteristics of queries, such as time intervals, query reformulation patterns and the continuation/shift status of the previous query. The findings show that Markov chains provide fairly successful results for automatic new topic identification with a high level of estimation for topic continuations and shifts. Copyright © 2009 John Wiley & Sons, Ltd.     

Algorithms for generalized halfspace range searching and other intersection searching problems

In a generalized intersection searching problem, a set S of colored geometric objects is to be preprocessed so that, given a query object q, the distinct colors of the objects of S that are intersected by q can be reported or counted efficiently. These problems generalize the well-studied standard intersection searching problems and have many applications. Unfortunately, the solutions known for the standard problems do not yield efficient solutions to the generalized problems. Recently, efficient solutions have been given for generalized problems where the input and query objects are iso-oriented (i.e., axes-parallel) or where the color classes satisfy additional properties (e.g., connectedness). In this paper, efficient algorithms are given for several generalized problems involving objects that are not necessarily iso-oriented. These problems include: generalized halfspace range searching in , for any fixed d ≥ 2, and segment intersection searching, triangle stabbing, and triangle range searching in for certain classes of line segments and triangles. The techniques used include: computing suitable sparse representations of the input, persistent data structures, and filtering search.     

Finding Robust Solutions Using Local Search

This paper investigates how a local search metaheuristic for continuous optimisation can be adapted so that it finds broad peaks, corresponding to robust solutions. This is relevant in problems in which uncertain or noisy data is present. When using a genetic or evolutionary algorithm, it is standard practice to perturb solutions once before evaluating them, using noise from a given distribution. This approach however, is not valid when using population-less techniques like local search and other heuristics that use local search. For those algorithms to find robust solutions, each solution needs to be perturbed and evaluated several times, and these evaluations need to be combined into a measure of robustness. In this paper, we examine how many of these evaluations are needed to reliably find a robust solution. We also examine the effect of the parameters of the noise distribution. Using a simple tabu search procedure, the proposed approach is tested on several functions found in the literature. This revised version was published online in August 2006 with corrections to the Cover Date.     

Continuous functions minimization by dynamic random search technique

Random search technique is the simplest one of the heuristic algorithms. It is stated in the literature that the probability of finding global minimum is equal to 1 by using the basic random search technique, but it takes too much time to reach the global minimum. Improving the basic random search technique may decrease the solution time. In this study, in order to obtain the global minimum fastly, a new random search algorithm is suggested. This algorithm is called as the Dynamic Random Search Technique (DRASET). DRASET consists of two phases, which are general search and local search based on general solution. Knowledge related to the best solution found in the process of general search is kept and then that knowledge is used as initial value of local search. DRASET’s performance was experimented with 15 test problems and satisfactory results were obtained.     

A tabu search algorithm for maximum parsimony phylogeny inference

Phylogeny reconstruction is too complex a combinatorial problem for an exhaustive search, because the number of possible solutions increases exponentially with the number of taxa involved. In this paper, we adopt the parsimony principle and design a tabu search algorithm for finding a most parsimonious phylogeny tree. A special array structure is employed to represent the topology of trees and to generate the neighboring trees. We test the proposed tabu search algorithm on randomly selected data sets obtained from nuclear ribosomal DNA sequence data. The experiments show that our algorithm explores fewer trees to reach the optimal one than the commonly used program “dnapenny” (branch-and-bound based) while it generates much more accurate results than the default options of the program “dnapars” (heuristic search based). The percentage of search space needed to find the best solution for our algorithm decreased rapidly as the number of taxa increased. For a 20-taxon phylogeny problem, it needs on average to examine only 3.92 × 10⁻¹⁵% of the sample space.     

A Math Query Language with an Expanded Set of Wildcards

Math search is a new area of research with many enabling technologies but also many challenges. Some of the enabling technologies include XML, XPath, XQuery, and MathML. Some of the challenges involve enabling search systems to recognize mathematical symbols and structures. Several math search projects have made considerable progress in meeting those challenges. One of the remaining challenges is the creation and implementation of a math query language that enables the general users to express their information needs intuitively yet precisely. This paper will present such a language and detail its features. The new math query language offers an alternative way to describe mathematical expressions that is more consistent and less ambiguous than conventional mathematical notation. In addition, the language goes beyond the Boolean and proximity query syntax found in standard text search systems. It defines a powerful set of wildcards that are deemed important for math search. These wildcards provide for more precise structural search and multi-levels of abstractions. Three new sets of wildcards and their implementation details will also be discussed.      

An iterated local search algorithm for the vehicle routing problem with backhauls

The Vehicle Routing Problem with Backhauls (VRPB) is an extension of the VRP that deals with two types of customers: the consumers (linehaul) that request goods from the depot and the suppliers (backhaul) that send goods to the depot. In this paper, we propose a simple yet effective iterated local search algorithm for the VRPB. Its main component is an oscillating local search heuristic that has two main features. First, it explores a broad neighborhood structure at each iteration. This is efficiently done using a data structure that stores information about the set of neighboring solutions. Second, the heuristic performs constant transitions between feasible and infeasible portions of the solution space. These transitions are regulated by a dynamic adjustment of the penalty applied to infeasible solutions. An extensive statistical analysis was carried out in order to identify the most important components of the algorithm and to properly tune the values of their parameters. The results of the computational experiments carried out show that this algorithm is very competitive in comparison to the best metaheuristic algorithms for the VRPB. Additionally, new best solutions have been found for two instances in one of the benchmark sets. These results show that the performance of existing metaheuristic algorithms can be considerably improved by carrying out a thorough statistical analysis of their components. In particular, it shows that by expanding the exploration area and improving the efficiency of the local search heuristic, it is possible to develop simpler and faster metaheuristic algorithms without compromising the quality of the solutions obtained.