检索结果-内蒙古大学图书馆

Finding Top-k Min-Cost Connected Trees in databases

学校读者我要写书评

暂无评论

Finding Top-k Min-Cost Connected Trees in Databases

International Conference on data engineering

作者： Bolin Ding Jeffrey Xu Yu Shan Wang Lu Qin Xiao Zhang Xuemin Lin Chinese University of Hong Kong China Key Laboratory of Data Engineering and Knowledge Engineering MOE of China Renmin University of China China University of New South Wales Australia

ISBN: (纸本)1424408024

It is widely realized that the integration of database and information retrieval techniques will provide users with a wide range of high quality services. In this paper, we study processing an l-keyword query, p 1 , p 1 , ..., p l , against a relational database which can be modeled as a weighted graph, G(V, E). Here V is a set of nodes (tuples) and E is a set of edges representing foreign key references between tuples. Let V i ⊆ V be a set of nodes that contain the keyword p i . We study finding top-k minimum cost connected trees that contain at least one node in every subset V i , and denote our problem as GST-k When k = 1, it is known as a minimum cost group Steiner tree problem which is NP-complete. We observe that the number of keywords, l, is small, and propose a novel parameterized solution, with l as a parameter, to find the optimal GST-1, in time complexity O(3 l n + 2 l ((l + logn)n + m)), where n and m are the numbers of nodes and edges in graph G. Our solution can handle graphs with a large number of nodes. Our GST-1 solution can be easily extended to support GST-k, which outperforms the existing GST-k solutions over both weighted undirected/directed graphs. We conducted extensive experimental studies, and report our finding.

关键词： Tree graphs Relational databases Costs laboratories data engineering knowledge engineering Australia Information retrieval

Improved Bounds for Sampling Solutions of Random CNF Formulas

学校读者我要写书评

暂无评论

arXiv 2022年

作者： He, Kun Wu, Kewen Yang, Kuan The Key Lab of Data Engineering and Knowledge Engineering MOE Renmin University of China China University of California at Berkeley United States John Hopcroft Center for Computer Science Shanghai Jiao Tong University China

Let Φ be a random k-CNF formula on n variables and m clauses, where each clause is a disjunction of k literals chosen independently and uniformly. Our goal is to sample an approximately uniform solution of Φ (or equivalently, approximate the partition function of Φ). Let α = m/n be the density. The previous best algorithm runs in time npoly(k,α) for any α 2k/300 [Galanis, Goldberg, Guo, and Yang, SIAM J. Comput.'21]. Our result significantly improves both bounds by providing an almost-linear time sampler for any α 2k/3. The density α captures the average degree in the random formula. In the worst-case model with bounded maximum degree, current best efficient sampler works up to degree bound 2k/5 [He, Wang, and Yin, FOCS'22 and SODA'23], which is, for the first time, superseded by its average-case counterpart due to our 2k/3 bound. Our result is the first progress towards establishing the intuition that the solvability of the average-case model (random k-CNF formula with bounded average degree) is better than the worst-case model (standard k-CNF formula with bounded maximal degree) in terms of sampling solutions. Copyright © 2022, The Authors. All rights reserved.

关键词：

USER: A unified information search and recommendation model based on integrated behavior sequence

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Yao, Jing Dou, Zhicheng Xie, Ruobing Lu, Yanxiong Wang, Zhiping Wen, Ji-Rong Gaoling School of Artificial Intelligence Renmin University of China WeChat Search Application Department Tencent China Beijing Key Laboratory of Big Data Management and Analysis Methods Key Laboratory of Data Engineering and Knowledge Engineering MOE

Search and recommendation are the two most common approaches used by people to obtain information. They share the same goal - satisfying the user's information need at the right time. There are already a lot of Internet platforms and Apps providing both search and recommendation services, showing us the demand and opportunity to simultaneously handle both tasks. However, most platforms consider these two tasks independently - they tend to train separate search model and recommendation model, without exploiting the relatedness and dependency between them. In this paper, we argue that jointly modeling these two tasks will benefit both of them and finally improve overall user satisfaction. We investigate the interactions between these two tasks in the specific information content service domain. We propose first integrating the user's behaviors in search and recommendation into a heterogeneous behavior sequence, then utilizing a joint model for handling both tasks based on the unified sequence. More specifically, we design the Unified Information SEarch and Recommendation model (USER), which mines user interests from the integrated sequence and accomplish the two tasks in a unified way. Experiments on a dataset from a real-world information content service platform verify that our model outperforms separate search and recommendation baselines. Copyright © 2021, The Authors. All rights reserved.

关键词： Recommender systems

Group based personalized search by integrating search behaviour and friend network

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Zhou, Yujia Dou, Zhicheng Wei, Bingzheng Xie, Ruobing Wen, Ji-Rong Gaoling School of Artificial Intelligence Renmin University of China School of Information Renmin University of China WeChat Search Application Department Tencent China Beijing Key Laboratory of Big Data Management and Analysis Methods Key Laboratory of Data Engineering and Knowledge Engineering MOE

The key to personalized search is to build the user profile based on historical behaviour. To deal with the users who lack historical data, group based personalized models were proposed to incorporate the profiles of similar users when re-ranking the results. However, similar users are mostly found based on simple lexical or topical similarity in search behaviours. In this paper, we propose a neural network enhanced method to highlight similar users in semantic space. Furthermore, we argue that the behaviour-based similar users are still insufficient to understand a new query when user's historical activities are limited. To tackle this issue, we introduce the friend network into personalized search to determine the closeness between users in another way. Since the friendship is often formed based on similar background or interest, there are plenty of personalized signals hidden in the friend network naturally. Specifically, we propose a friend network enhanced personalized search model, which groups the user into multiple friend circles based on search behaviours and friend relations respectively. These two types of friend circles are complementary to construct a more comprehensive group profile for refining the personalization. Experimental results show the significant improvement of our model over existing personalized search models. Copyright © 2021, The Authors. All rights reserved.

关键词： User profile

LotusX: A Position-Aware XML Graphical Search System with Auto-Completion

学校读者我要写书评

暂无评论

LotusX: A Position-Aware XML Graphical Search System with Au...

International Conference on data engineering

作者： Chunbin Lin Jiaheng Lu Tok Wang Ling Bogdan Cautis Key Laboratory of Data Engineering and Knowledge Engineering MOE Renmin University of China China School of Computing National University of Singapore Singapore Télécom Paris Technology France

ISBN: (纸本)9781467300421

The existing query languages for XML (e.g., XQuery) require professional programming skills to be formulated, however, such complex query languages burden the query processing. In addition, when issuing an XML query, users are required to be familiar with the content (including the structural and textual information) of the hierarchical XML, which is diffcult for common users. The need for designing user friendly interfaces to reduce the burden of query formulation is fundamental to the spreading of XML community. We present a twig-based XML graphical search system, called LotusX, that provides a graphical interface to simplify the query processing without the need of learning query language and data schemas and the knowledge of the content of the XML document. The basic idea is that LotusX proposes "position-aware" and "auto-completion" features to help users to create tree-modeled queries (twig pattern) by providing the possible candidates on-the-fly. In addition, complex twig queries (including order sensitive queries) are supported in LotusX. Furthermore, a new ranking strategy and a query rewriting solution are implemented to rank and rewrite the query effectively. We provide an online demo for LotusX system: http://***:8080/LotusX.

关键词： XML database languages Indexes Books Query processing Programming keyword search

Automatic data distribution in large-scale OLTP applications

学校读者我要写书评

暂无评论

International Journal of Database Theory and Application

International Journal of database Theory and Application 2014年第4期7卷 37-46页

作者： Wang, Xiaoyan Fan, Xu Chen, Jinchuan Du, Xiaoyong Key Laboratory of Data Engineering and Knowledge Engineering Renmin University of China MOE Beijing 100872 China School of Information and Electrical Engineering Ludong University Yantai 264025 China School of Information Renmin University of China Beijing 100872 China

With the dramatic increase of data volume, automatic data distribution has been one of the key techniques and intractable problem for distributed systems. This work summarizes the problem of data distribution and abstracts it as a general triangle model called DaWN. Based on data and workload analysis, it presents a novel strategy called ADDS for automatic data distribution in OLTP applications. According to the results of a series of experiments over TPC-C datasets and transactions, the proposed approach shows effective improvements.© 2014 SERSC.

关键词： data handling

SAFL-Net: Semantic-Agnostic Feature Learning Network with Auxiliary Plugins for Image Manipulation Detection

学校读者我要写书评

暂无评论

SAFL-Net: Semantic-Agnostic Feature Learning Network with Au...

International Conference on Computer Vision (ICCV)

作者： Zhihao Sun Haoran Jiang Danding Wang Xirong Li Juan Cao Institute of Computing Technology Chinese Academy of Sciences University of Chinese Academy of Sciences School of Mathematics Science University of Chinese Academy of Sciences MoE Key Lab of Data Engineering and Knowledge Engineering Renmin University of China

Since image editing methods in real world scenarios cannot be exhausted, generalization is a core challenge for image manipulation detection, which could be severely weakened by semantically related features. In this paper we propose SAFL-Net, which constrains a feature extractor to learn semantic-agnostic features by designing specific modules with corresponding auxiliary tasks. Applying constraints directly to the features extracted by the encoder helps it learn semantic-agnostic manipulation trace features, which prevents the biases related to semantic information within the limited training data and improves generalization capabilities. The consistency of auxiliary boundary prediction task and original region prediction task is guaranteed by a feature transformation structure. Experiments on various public datasets and comparisons in multiple dimensions demonstrate that SAFL-Net is effective for image manipulation detection.

关键词：

Pre-training for ad-hoc retrieval: Hyperlink is also you need

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Ma, Zhengyi Dou, Zhicheng Xu, Wei Zhang, Xinyu Jiang, Hao Cao, Zhao Wen, Ji-Rong Gaoling School of Artificial Intelligence Renmin University of China Beijing China Distributed and Parallel Software Lab Huawei Beijing Key Laboratory of Big Data Management and Analysis Methods Beijing China Key Laboratory of Data Engineering and Knowledge Engineering MOE Beijing China

Designing pre-training objectives that more closely resemble the downstream tasks for pre-trained language models can lead to better performance at the fine-tuning stage, especially in the ad-hoc retrieval area. Existing pre-training approaches tailored for IR tried to incorporate weak supervised signals, such as query-likelihood based sampling, to construct pseudo query-document pairs from the raw textual corpus. However, these signals rely heavily on the sampling method. For example, the query likelihood model may lead to much noise in the constructed pre-training data. In this paper, we propose to leverage the large-scale hyperlinks and anchor texts to pre-train the language model for ad-hoc retrieval. Since the anchor texts are created by webmasters and can usually summarize the target document, it can help to build more accurate and reliable pre-training samples than a specific algorithm. Considering different views of the downstream ad-hoc retrieval, we devise four pre-training tasks based on the hyperlinks. We then pre-train the Transformer model to predict the pair-wise preference, jointly with the Masked Language Model objective. Experimental results on two large-scale ad-hoc retrieval datasets show the significant improvement of our model compared with the existing methods. Copyright © 2021, The Authors. All rights reserved.

关键词： Hypertext systems

Vulnerabilities Static Detection for Web Applications with False Positive Suppression

学校读者我要写书评

暂无评论

Vulnerabilities Static Detection for Web Applications with F...

2010 IEEE International Conference on Information Theory and Information Security(2010 IEEE 国际信息论与信息安全会议)

作者： Bin Liang Qianqian Wang Jianjun Huang Jiagui Zhong Jingjing Cai Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China) MOE Schoo School of Information Renmin University of China Beijing 100872 China Beijing Venustech Cybervision Co. Ltd Beijing 100094 China

Web applications become more and more important, and the corresponding security problems have been concerned about. This paper presents TASA, an ASP static analyzer, which employs a path-sensitive, inter-procedural and contextsensitive data flow analysis, mainly concerning the taint propagation and sanitization. This paper also discusses some techniques used in TASA, such as sanitization routines modeling, ASP specific features, alias analysis and path-related routines modeling, to prune false positives. Experiments on four open source applications show that TASA has a rate of false positive of 4.98% and it can avoid certain false warnings owing to the proposed approaches.

关键词： Security Detectors Computer bugs Portals Analytical models Browsers Merging