基于吸收态随机行走的两阶段效用性查询推荐方法

搜索引擎已经成为人们获取信息的重要途径,然而对于用户而言如何构造一个合适的查询仍然是一项困难的工作.为了减轻用户搜索信息的负担,查询推荐技术应运而生并且已经成为当今搜索引擎不可或缺的组成部分.传统的查询推荐方法主要关注向用户推荐相关性查询,即推荐与源查询具有相近搜索意图的其他查询.然而查询推荐的根本目标是帮助用户成功完成其搜索任务,而不仅仅是找到相关性查询,尽管相关性查询有时也能得到有用的搜索结果.为了更好地满足用户的搜索目标,一种更直接的查询推荐方式是向用户推荐高效用性查询,即能够更好满足用户信息需求的查询.提出了一个基于吸收态随机行走的2阶段效用性查询推荐方法,该方法能够同时对用户的查询重构行为和查询点击行为进行建模并推导出查询的效用.在真实查询日志上的实验结果表明:新方法在评价指标查询相关率(query relevant ratio, QRR)和平均相关文档数(mean relevant document, MRD)上要显著优于其他5种基准方法.     

Learning to rank code examples for code search engines

Source code examples are used by developers to implement unfamiliar tasks by learning from existing solutions. To better support developers in finding existing solutions, code search engines are designed to locate and rank code examples relevant to user’s queries. Essentially, a code search engine provides a ranking schema, which combines a set of ranking features to calculate the relevance between a query and candidate code examples. Consequently, the ranking schema places relevant code examples at the top of the result list. However, it is difficult to determine the configurations of the ranking schemas subjectively. In this paper, we propose a code example search approach that applies a machine learning technique to automatically train a ranking schema. We use the trained ranking schema to rank candidate code examples for new queries at run-time. We evaluate the ranking performance of our approach using a corpus of over 360,000 code snippets crawled from 586 open-source Android projects. The performance evaluation study shows that the learning-to-rank approach can effectively rank code examples, and outperform the existing ranking schemas by about 35.65 % and 48.42 % in terms of normalized discounted cumulative gain (NDCG) and expected reciprocal rank (ERR) measures respectively.     

基于序列到序列模型的代码片段推荐

在软件开发过程中,开发者经常会以复用代码的方式,提高软件开发效率。已有的研究通常采用传统的信息检索技术来实现代码推荐。这些方法存在自然语言查询的高层级的意图与代码的低层级的实现细节不匹配的问题。提出了一种基于序列到序列模型的代码片段推荐方法DeepCR。该方法结合程序静态分析技术与序列到序列模型,训练自然语言查询生成模型,为代码片段生成查询,通过计算生成的查询和开发者输入的自然语言查询的相似度得分来实现代码片段推荐。所构建的代码库的数据来源于Stack Overflow问答网站,确保了数据的真实性。通过计算代码片段推荐结果的平均倒数排名(MRR)和Hit@K来验证方法的有效性。实验结果表明,DeepCR优于现有研究工作,能够有效提高代码片段推荐效果。     

Deep learning the semantics of change sequences for query expansion

The overexpansion problem negatively affects the quality of query expansion. To improve the quality of queries for searching code, this paper proposed a DBN-based algorithm for effective query expansion. The deep belief network (DBN) model is trained on the code sequences and their change sequences, which aims to capture the meaningful terms during the evolution of source code. In contrast to previous studies, the proposed model not only extracts relevant terms to expand a query but also excludes irrelevant terms from the query. It addresses two problems in query expansion, including the overexpansion of the original query and the negative influence of the changed terms in the target source code. Experiments on both artificial queries and real queries show that the proposed algorithm outperforms several query expansion algorithms for code search.     

基于加权SimRank的中文查询推荐研究

查询推荐是搜索引擎系统中的一项重要技术,其通过推荐更合适的查询以提高用户的搜索体验。现有方法能够找到直接通过某种属性关联的相似查询,却忽略了具有间接关联的语义相关查询。该文将用户查询及查询间直接联系建模为查询关系图,并在图结构相似度算法SimRank的基础上提出了加权SimRank (简称WSimRank)用于查询推荐。WSimRank综合考虑了查询关系图的全局信息,因而能挖掘出查询间的间接关联和语义关系。然而,WSimRank复杂度太高而难以实用,该文将WSimRank转换为一个状态层次图的遍历和计算过程,进而采用动态规划、剪枝等策略对其进行优化从而可以实际应用。在大规模真实Web搜索日志上的实验表明, WSimRank在各项评价指标上均优于SimRank和传统查询推荐方法,其MAP指标接近0.9。     

How do users describe their information need: Query recommendation based on snippet click model

Query recommendation helps users to describe their information needs more clearly so that search engines can return appropriate answers and meet their needs. State-of-the-art researches prove that the use of users’ behavior information helps to improve query recommendation performance. Instead of finding the most similar terms previous users queried, we focus on how to detect users’ actual information need based on their search behaviors. The key idea of this paper is that although the clicked documents are not always relevant to users’ queries, the snippets which lead them to the click most probably meet their information needs. Based on analysis into large-scale practical search behavior log data, two snippet click behavior models are constructed and corresponding query recommendation algorithms are proposed. Experimental results based on two widely-used commercial search engines’ click-through data prove that the proposed algorithms outperform practical recommendation methods of these two search engines. To the best of our knowledge, this is the first time that snippet click models are proposed for query recommendation task.     

Query expansion based on statistical learning from code changes

Thesaurus‐based, code‐related, and software‐specific query expansion techniques are the main contributions in free‐form query search. However, these techniques still could not put the most relevant query result in the first position because they lack the ability to infer the expansion words that represent the user needs based on a given query. In this paper, we discover that code changes can imply what users want and propose a novel query expansion technique with code changes (QECC). It exploits (changes, contexts) pairs from changed methods. On the basis of statistical learning from pairs, it can infer code changes for a given query. In this way, it expands a query with code changes and recommends the query results that meet actual needs perfectly. In addition, we implement InstaRec to perform QECC and evaluate it with 195 039 change commits from GitHub and our code tracker. The results show that QECC can improve the precision of 3 code search algorithms (ie, IR, Portfolio, and VF) by up to 52% to 62% and outperform the state‐of‐the‐art query expansion techniques (ie, query expansion based on crowd knowledge and CodeHow) by 13% to 16% when the top 1 result is inspected.     

Concept location using program dependencies and information retrieval (DepIR)

ContextThe functionality of a software system is most often expressed in terms of concepts from its problem or solution domains. The process of finding where these concepts are implemented in the source code is known as concept location and it is a prerequisite of software change.ObjectiveWe investigate a static approach to concept location named DepIR that combines program dependency search (DepS) with information retrieval-based search (IR). In this approach, programmers explore the static program dependencies of the source code components retrieved by the IR search engine.MethodThe paper presents an empirical study that compares DepIR with its constituent techniques. The evaluation is based on an empirical method of reenactment that emulates the steps of concept location for 50 past changes mined from software repositories of five software systems.ResultsThe results of the study indicate that DepIR significantly outperforms both DepS and IR.ConclusionDepIR allows developers to perform concept location efficiently. It allows finding concepts even with queries that do not rank the relevant software components highly. Since formulating a good query is not always easy, this tolerance of lower-quality queries significantly broadens the usability of DepIR compared to the traditional IR.     

基于语义相似度的API使用模式推荐

在软件开发过程中,复用应用程序编程接口(Application Programming Interface,API)可以提高软件开发效率,但是使用不熟悉的API是一项耗时且困难的挑战。已有的研究往往将API作为用户输入的查询,通过在语料库中搜索该API的使用模式来进行推荐,但这并不符合开发人员的查询习惯。文中提出了一种基于自然语言语义相似度的API使用模式推荐方法(Semantic Similazing Based API Recommendation,SSAPIR)。该方法使用层次聚类算法来提取API使用模式,然后通过计算查询信息和API使用模式来描述信息之间的语意相似度,向开发人员推荐相关度高且被广泛使用的API使用模式。为了验证SSAPIR的有效性,文中从GitHub的高质量Java项目中提取9个流行的第三方API库的API使用模式以及API使用模式的描述信息,并根据这9个流行的第三方API库的自然语言查询进行API使用模式推荐。通过计算推荐结果的Hit@K准确率来验证SSAPIR的有效性,实验结果表明,层次聚类能有效提高推荐准确率,且SSAPIR在Hit@10平均准确率上达到了85.02%,优于现有研究工作,能够很好地完成API使用模式推荐任务,为开发人员输入的自然语言查询提供精准的API使用模式。     

一种基于图数据库的代码结构解析与搜索方法

软件复用是在软件开发中避免重复劳动的解决方案.在复用一个已有的软件项目时,软件开发人员通常需要理解某些代码元素以及其间的关联关系,称之为代码结构.软件开发人员一般通过浏览软件源代码的方式理解代码结构.由于源代码往往规模较大且结构复杂,理解代码结构通常会耗费大量的时间与精力.因此,将软件开发人员想要理解的代码结构自动、清晰地展示出来是很有帮助的.提出一种基于图数据库的代码结构解析与搜索方法以实现这一目的.这一方法可对软件的代码结构进行解析,并在图数据库中对其进行有效的组织和管理.搜索时,软件开发人员输入自然语言查询语句,该方法中的搜索机制会分析查询语句,并从图数据库中截取出与其相对应的代码结构进行展示.该方法具有高度的可扩展性：不同粒度的结点与多样化的关联关系可以容易地存储进图数据库中,且面向不同搜索目的的代码结构搜索算法亦可以容易地集成进搜索机制中.这一方法已在相应的工具中得到了实现,其有效性在一个商业案例研究中得到了验证.     

A field study of how developers locate features in source code

Our current understanding of how programmers perform feature location during software maintenance is based on controlled studies or interviews, which are inherently limited in size, scope and realism. Replicating controlled studies in the field can both explore the findings of these studies in wider contexts and study new factors that have not been previously encountered in the laboratory setting. In this paper, we report on a field study about how software developers perform feature location within source code during their daily development activities. Our study is based on two complementary field data sets: one that reflects complete IDE activity of 67 professional developers over approximately one month, and the other that reflects usage of an IR-based code search tool by nearly 600 developers. Analyzing this data, we report results on how often developers use which type of code search tools, on the types of queries and retreival strategies used by developers, and on patterns of developer feature location behavior following code search. The results of the study suggest that there is (1) a need for helping developers to devise better code search queries; (2) a lack of adoption of niche code search tools; (3) a need for code search tool to handle both lookup and exploratory queries; and (4) a need for better integration between code search, structured navigation, and debugging tools in feature location tasks.     

基于用户意图识别的查询推荐研究

信息检索的效果很大程度上取决于用户能否输入恰当的查询来描述自身信息需求。很多查询通常简短而模糊,甚至包含噪音。查询推荐技术可以帮助用户提炼查询、准确描述信息需求。为了获得高质量的查询推荐,在大规模“查询-链接”二部图上采用随机漫步方法产生候选集合。利用摘要点击信息对候选列表进行重排序,使得体现用户意图的查询排在比较高的位置。最终采用基于学习的算法对推荐查询中可能存在的噪声进行过滤。基于真实用户行为数据的实验表明该方法取得了较好的效果。     

Location-aware query reformulation for search engines

Query reformulation, including query recommendation and query auto-completion, is a popular add-on feature of search engines, which provide related and helpful reformulations of a keyword query. Due to the dropping prices of smartphones and the increasing coverage and bandwidth of mobile networks, a large percentage of search engine queries are issued from mobile devices. This makes it possible to improve the quality of query recommendation and auto-completion by considering the physical locations of the query issuers. However, limited research has been done on location-aware query reformulation for search engines. In this paper, we propose an effective spatial proximity measure between a query issuer and a query with a location distribution obtained from its clicked URLs in the query history. Based on this, we extend popular query recommendation and auto-completion approaches to our location-aware setting, which suggest query reformulations that are semantically relevant to the original query and give results that are spatially close to the query issuer. In addition, we extend the bookmark coloring algorithm for graph proximity search to support our proposed query recommendation approaches online, and we adapt an A* search algorithm to support our query auto-completion approach. We also propose a spatial partitioning based approximation that accelerates the computation of our proposed spatial proximity. We conduct experiments using a real query log, which show that our proposed approaches significantly outperform previous work in terms of quality, and they can be efficiently applied online.     

Adaptive relaxation for querying heterogeneous XML data sources

Searching XML data with a structured XML query can improve the precision of results compared with a keyword search. However, the structural heterogeneity of the large number of XML data sources makes it difficult to answer the structured query exactly. As such, query relaxation is necessary. Previous work on XML query relaxation poses the problem of unnecessary computation of a big number of unqualified relaxed queries. To address this issue, we propose an adaptive relaxation approach which relaxes a query against different data sources differently based on their conformed schemas. In this paper, we present a set of techniques that supports this approach, which includes schema-aware relaxation rules for relaxing a query adaptively, a weighted model for ranking relaxed queries, and algorithms for adaptive relaxation of a query and top-k query processing. We discuss results from a comprehensive set of experiments that show the effectiveness and the efficiency of our approach.     

Visualizing Expanded Query Results

When performing queries in web search engines, users often face difficulties choosing appropriate query terms. Search engines therefore usually suggest a list of expanded versions of the user query to disambiguate it or to resolve potential term mismatches. However, it has been shown that users find it difficult to choose an expanded query from such a list. In this paper, we describe the adoption of set‐based text visualization techniques to visualize how query expansions enrich the result space of a given user query and how the result sets relate to each other. Our system uses a linguistic approach to expand queries and topic modeling to extract the most informative terms from the results of these queries. In a user study, we compare a common text list of query expansion suggestions to three set‐based text visualization techniques adopted for visualizing expanded query results – namely, Compact Euler Diagrams, Parallel Tag Clouds, and a List View – to resolve ambiguous queries using interactive query expansion. Our results show that text visualization techniques do not increase retrieval efficiency, precision, or recall. Overall, users rate Parallel Tag Clouds visualizing key terms of the expanded query space lowest. Based on the results, we derive recommendations for visualizations of query expansion results, text visualization techniques in general, and discuss alternative use cases of set‐based text visualization techniques in the context of web search.     

QUBiC: An adaptive approach to query-based recommendation

Search engine users often encounter the difficulty of phrasing the precise query that could lead to satisfactory search results. Query recommendation is considered an effective assistant in enhancing keyword-based queries in search engines and Web search software. In this paper, we present a Query-URL Bipartite based query reCommendation approach, called QUBiC. It utilizes the connectivity of a query-URL bipartite graph to recommend related queries and can significantly improve the accuracy and effectiveness of personalized query recommendation systems comparing with the conventional pairwise similarity based approach. The main contribution of the QUBiC approach is its three-phase framework for personalized query recommendations. The first phase is the preparation of queries and their search results returned by a search engine, which generates a historical query-URL bipartite collection. The second phase is the discovery of similar queries by extracting a query affinity graph from the bipartite graph, instead of operating on the original bipartite graph directly using biclique-based approach or graph clustering. The query affinity graph consists of only queries as its vertices and its edges are weighted according to a query-URL vector based similarity (dissimilarity) measure. The third phase is the ranking of similar queries. We devise a novel rank mechanism for ordering the related queries based on the merging distances of a hierarchical agglomerative clustering (HAC). By utilizing the query affinity graph and the HAC-based ranking, we are able to capture the propagation of similarity from query to query by inducing an implicit topical relatedness between queries. Furthermore, the flexibility of the HAC strategy makes it possible for users to interactively participate in the query recommendation process, and helps to bridge the gap between the determinacy of actual similarity values and the indeterminacy of users’ information needs, allowing the lists of related queries to be changed from user to user and query to query, thus adaptively recommending related queries on demand. Our experimental evaluation results show that the QUBiC approach is highly efficient and more effective compared to the conventional query recommendation systems, yielding about 13.3 % as the most improvement in terms of precision.     

Incremental computation of time-varying query expressions

We present and analyze algorithms for the incremental computation of time-varying queries in which selection predicates refer to the state of a clock. Such queries occur naturally in many situations where temporal data are processed. Incremental techniques for query computation have proven to be more efficient than other techniques in many situations. However, all existing incremental techniques for query computation assume that old query results remain valid if no intermediate changes are made to the underlying database. Unfortunately, this assumption does not hold for time-varying queries whose results may change just because time passes. In order to solve this problem, we introduce the notion of a superview which contains all current tuples that will eventually satisfy the selection predicate of a time-varying selection. Based on the notion of superview, we develop efficient algorithms for the incremental computation of time-varying selections. Our algorithms, combined with existing incremental algorithms, allow complex time-varying queries to benefit from the proven efficiency of incremental techniques. It is important to notice that without our algorithms, the existing algorithms for incremental computation would be useless for any time-varying query expression