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

Random indexing of multidimensional data

KNOWLEDGE AND INFORMATION SYSTEMS 2017年第1期52卷 267-290页

作者： Sandin, Fredrik Emruli, Blerim Sahlgren, Magnus Lulea Univ Technol EISLAB S-97187 Lulea Sweden SICS Swedish ICT S-72213 Vasteras Sweden SICS Swedish ICT S-16429 Kista Sweden

Random indexing (RI) is a lightweight dimension reduction method, which is used, for example, to approximate vector semantic relationships in online natural language processing systems. Here we generalise RI to multidimensional arrays and therefore enable approximation of higher-order statistical relationships in data. The generalised method is a sparse implementation of random projections, which is the theoretical basis also for ordinary RI and other randomisation approaches to dimensionality reduction and data representation. We present numerical experiments which demonstrate that a multidimensional generalisation of RI is feasible, including comparisons with ordinary RI and principal component analysis. The RI method is well suited for online processing of data streams because relationship weights can be updated incrementally in a fixed-size distributed representation, and inner products can be approximated on the fly at low computational cost. An open source implementation of generalised RI is provided.

关键词： Data mining Random embeddings Dimensionality reduction Sparse coding Semantic similarity streaming algorithm Natural language processing

来源：评论

学校读者我要写书评

暂无评论

PRACTICAL SKETCHING algorithmS FOR LOW-RANK MATRIX APPROXIMATION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2017年第4期38卷 1454-1485页

作者： Tropp, Joel A. Yurtsever, Alp Udell, Madeleine Cevher, Volkan CALTECH Comp & Math Sci Pasadena CA 91125 USA Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland Cornell Univ Ithaca NY 14853 USA

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image, or sketch, of the matrix. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.

关键词： dimension reduction matrix approximation numerical linear algebra randomized algorithm single-pass algorithm sketching streaming algorithm subspace embedding

来源：评论

学校读者我要写书评

暂无评论

Modification of Retinex algorithm And Its Stream Implementation on FPGA 6

Modification of Retinex Algorithm And Its Stream Implementat...

引用

6th Mediterranean Conference on Embedded Computing (MECO)

作者： Ustukov, Dmitry I. Muratov, Yevgeniy R. Lantsov, Vladimir N. Ryazan State Radio Engn Univ RSREU Elect Comp Dept Ryazan Russia Vladimir State Univ Dept Comp Engn & Control Syst Vladimir Russia

ISBN: (纸本)9781509067428

The article describes the modification of multi scale Retinex algorithm. The modification offers to use alternative method of image blurring instead of Gaussian filter, tabular value substitution instead of calculating logarithm values and some other approaches leading to the increase of algorithm performance. The peculiarities of combining algorithms in the method offered allow to implement modified algorithm on FPGA XILINX XC7VX485T as threading conveyor. The article tries to assess the performance of the algorithm on FPGA, as well as its block implementation on CPU in comparison with original version- Multi Scale Retinex. The increase of the number of blurring scales in the offered threading implementation on FPGA allows to increase the quality of the result due to small increase of FPGA chip resources.

关键词： multi scale Refines image processing box filters light alignment on FPGA streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Parallel and streaming Truth Discovery in Large-Scale Quantitative Crowdsourcing

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2016年第10期27卷 2984-2997页

作者： Ouyang, Robin Wentao Kaplan, Lance M. Toniolo, Alice Srivastava, Mani Norman, Timothy J. Chinese Acad Sci Inst Comp Technol CAS Key Lab Network Data Sci & Technol Beijing Peoples R China US Army Res Lab Networked Sensing Fus Branch Adelphi MD 20783 USA Univ Aberdeen Dept Comp Sci Aberdeen Scotland Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90024 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90024 USA

To enable reliable crowdsourcing applications, it is of great importance to develop algorithms that can automatically discover the truths from possibly noisy and conflicting claims provided by various information sources. In order to handle crowdsourcing applications involving big or streaming data, a desirable truth discovery algorithm should not only be effective, but also be scalable. However, with respect to quantitative crowdsourcing applications such as object counting and percentage annotation, existing truth discovery algorithms are not simultaneously effective and scalable. They either address truth discovery in categorical crowdsourcing or perform batch processing that does not scale. In this paper, we propose new parallel and streaming truth discovery algorithms for quantitative crowdsourcing applications. Through extensive experiments on real-world and synthetic datasets, we demonstrate that 1) both of them are quite effective, 2) the parallel algorithm can efficiently perform truth discovery on large datasets, and 3) the streaming algorithm processes data incrementally, and it can efficiently perform truth discovery both on large datasets and in data streams.

关键词： Crowdsourcing truth discovery quantitative task big data parallel algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

SPOTHOT: Scalable Detection of Geo-spatial Events in Large Textual Streams 16

SPOTHOT: Scalable Detection of Geo-spatial Events in Large T...

引用

28th International Conference on Scientific and Statistical Database Management (SSDBM)

作者： Schubert, Erich Weiler, Michael Kriegel, Hans-Peter Ludwig Maximilians Univ Munchen Inst Informat Munich Germany

ISBN: (纸本)9781450342155

The analysis of social media data poses several challenges: first of all, the data sets are very large, secondly they change constantly, and third they are heterogeneous, consisting of text, images, geographic locations and social connections. In this article, we focus on detecting events consisting of text and location information, and introduce an analysis method that is scalable both with respect to volume and velocity. We also address the problems arising from differences in adoption of social media across cultures, languages, and countries in our event detection by efficient normalization. We introduce an algorithm capable of processing vast amounts of data using a scalable online approach based on the SigniTrend event detection system, which is able to identify unusual geo-textual patterns in the data stream without requiring the user to specify any constraints in advance, such as hashtags to track: In contrast to earlier work, we are able to monitor every word at every location with just a fixed amount of memory, compare the values to statistics from earlier data and immediately report significant deviations with minimal delay. Thus, this algorithm is capable of reporting "Breaking News" in real-time. Location is modeled using unsupervised geometric discretization and supervised administrative hierarchies, which permits detecting events at city, regional, and global levels at the same time. The usefulness of the approach is demonstrated using several real-world example use cases using Twitter data.

关键词： Local event detection bursty topic detection change detection online control charts time-series analysis anomaly detection trend detection geo-social media rich geospatial data scalable real-time data analysis streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

SUBMODULAR MAXIMIZATION WITH MULTI-KNAPSACK CONSTRAINTS AND ITS APPLICATIONS IN SCIENTIFIC LITERATURE RECOMMENDATIONS

SUBMODULAR MAXIMIZATION WITH MULTI-KNAPSACK CONSTRAINTS AND ...

引用

IEEE Global Conference on Signal and Information Processing (GlobalSIP)

作者： Yu, Qilian Xu, Easton Li Cui, Shuguang Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA Texas A&M Univ Dept Elect & Comp Engn College Stn TX 77843 USA

ISBN: (纸本)9781509045457

Submodular maximization problems belong to the family of combinatorial optimization problems and enjoy wide applications. In this paper, we focus on the problem of maximizing a monotone submodular function subject to a d-knapsack constraint, for which we propose a streaming algorithm that achieves a (1/1+2d - epsilon)-approximation of the optimal value, while it only needs one single pass through the dataset without storing all the data in the memory. In our experiments, we extensively evaluate the effectiveness of our proposed algorithm via an application in scientific literature recommendation. It is observed that the proposed streaming algorithm achieves both execution speedup and memory saving by several orders of magnitude, compared with existing approaches.

关键词： Submodular Optimization streaming algorithm Scientific Literature Recommendation

来源：评论

学校读者我要写书评

暂无评论

Assignment problems and their application in economics

Assignment problems and their application in economics

引用

作者： Melika Abolhassani University of Maryland

学位级别：博士

Four assignment problems are introduced in this thesis, and they are approached based on the context they are presented in. The underlying graphs of the assignment problems in this thesis are in most cases bipartite graphs with two sets of vertices corresponding to the agents and the resources. An edge might show the interest of an agent in a resource or willingness of a manufacturer to produce the corresponding product of a market, to name a few examples. The rst problem studied in this thesis is a two-stage stochastic matching problem in both online and oine versions. In this work, which is presented in Chapter 2 of this thesis, a coordinator tries to benet by having access to the statistics of the future price discounts which can be completely unpredictable for individual customers. In our model, individual risk-averse customers want to book hotel rooms for their future vacation; however, they are unwilling to leave booking to the last minute which might result in huge savings for them since they have to take the risk of all the hotel rooms being sold out. Instead of taking this risk, individual customers make contracts with a coordinator who can spread the risk over many such cases and also has more information on the probability distribution of the future prices. In the rst stage, the coordinator agrees to serve some buyers, and then in the second stage, once the nal prices have been revealed, he books rooms for them just as he promised. An agreement between the coordinator and each buyer consists of a set of acceptable hotels for the customer and a single price. Two models for this problem are investigated. In the rst model, the details of the agreements are proposed by the buyer, and we propose a bicriteria-style approximation algorithm that gives a constant-factor approximation to the objective function by allowing a bounded fraction of our hotel bookings to overlap. In the second model, the details of the agreements are proposed by the coordinator, and we s

关键词： approximation algorithm bipartite graph cournot competition equilibria Online Matching streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

A revised cache allocation algorithm for VoD multicast service

引用

MULTIMEDIA TOOLS AND APPLICATIONS 2015年第16期74卷 6557-6572页

作者： Lee, Hyun Jong Lee, Wonhyuk Kim, Seunghae Noh, Minki Kim, Jeom Goo Kim, Hyuncheol Kakao Cooperat Seoul South Korea Korea Inst Sci Technol Informat Daejon South Korea Namseoul Univ Dept Comp Sci Cheonan South Korea

The Internet is replacing the traditional telephone network as the ubiquitous network infrastructure. Internet customers are increasing at an exponential rate and will continue to increase in the near future. Among the various Internet services, IPTV VoD (Video on Demand) service is expected to be one of the most popular services. In general, for deploying streamed video service, it is likely to use proxy by locating it nearby end-users. The use of proxy in on-demand media streaming service can help reduce the server streaming load and reduce the startup delay of media playback due to swift retrieval of beginning portion of media. We had proposed a cache allocation scheme for server-proxy media streaming environment by utilizing the advantage of threshold-based multicast mechanism. However it suffer from a little radical change of threshold value. In this paper, enhanced multicast-based server-proxy on-demand media streaming algorithm to IPTV VoD services is presented from the storage, caching size and bandwidth requirement viewpoints.

关键词： streaming algorithm IPTV VoD

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond 16

Brief Announcement: Applications of Uniform Sampling: Denses...

引用

Proceedings of the 28th ACM Symposium on Parallelism in algorithms and Architectures

作者： Hossein Esfandiari MohammadTaghi Hajiaghayi David P. Woodruff University of Maryland College Park MD USA IBM Almaden CA USA

ISBN: (纸本)9781450342100

In this paper we provide a framework to analyze the effect of uniform sampling on graph optimization problems. Interestingly, we apply this framework to a general class of graph optimization problems that we call heavy subgraph problems, and show that uniform sampling preserves a 1-ε approximate solution to these problems. This class contains many interesting problems such as densest subgraph, directed densest subgraph, densest bipartite subgraph, d-max cut, and d-sum-max clustering. As an immediate impact of this result, one can use uniform sampling to solve these problems in streaming, turnstile or Map-Reduce settings. Indeed, our results by characterizing heavy subgraph problems address Open Problem 13 at the IITK Workshop on algorithms for Data Streams in 2006 regarding the effects of subsampling, in the context of graph *** Bhattacharya et al. in STOC 2015 provide the first one pass algorithm for the densest subgraph problem in the streaming model with additions and deletions to its edges, i.e., for dynamic graph streams. They present a (0.5-ε)-approximation algorithm using ~O(n) space, where factors of ε and log(n) are suppressed in the ~O notation. In this paper we improve the (0.5-ε)-approximation algorithm of Bhattacharya et al. by providing a (1-ε)-approximation algorithm using ~O(n) space.

关键词： uniform sampling streaming algorithm densest subgraph

来源：评论

学校读者我要写书评

暂无评论

Real-Time Top-R Topic Detection on Twitter with Topic Hijack Filtering 15

Real-Time Top-R Topic Detection on Twitter with Topic Hijack...

引用

21st ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

作者： Hayashi, Kohei Maehara, Takanori Toyoda, Masashi Kawarabayashi, Ken-ichi Natl Inst Informat Tokyo Japan JST ERATO Kawarabayashi Large Graph Project Kawaguchi Saitama Japan Shizuoka Univ Shizuoka 4228529 Japan Univ Tokyo Tokyo Japan

ISBN: (纸本)9781450336642

Twitter is a "what's-happening-right-now" tool that enables interested parties to follow thoughts and commentary of individual users in nearly real-time. While it is a valuable source of information for real-time topic detection and tracking, Twitter data are not clean because of noisy messages and users, which significantly diminish the reliability of obtained results. In this paper, we integrate both the extraction of meaningful topics and the filtering of messages over the Twitter stream. We develop a streaming algorithm for a sequence of document-frequency tables;our algorithm enables real-time monitoring of the top-10 topics from approximately 25% of all Twitter messages, while automatically filtering noisy and meaningless topics. We apply our proposed streaming algorithm to the Japanese Twitter stream and successfully demonstrate that, compared with other online nonnegative matrix factorization methods, our framework both tracks real world events with high accuracy in terms of the perplexity and simultaneously eliminates irrelevant topics.

关键词： Twitter topic detection streaming algorithm nonnegative matrix factorization noise filtering

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：