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

作者： Cui, Yi Texas A&M University

The explosion of big data in areas like the web and social networks has posed big challenges to research activities, including data mining, information retrieval, security etc. This dissertation focuses on a particular area, graph mining, and specifically proposes several novel algorithms to solve the problems of triangle listing and computation of neighborhood function in large-scale graphs. We first study the classic problem of triangle listing. We generalize the existing in-memory algorithms into a single framework of 18 triangle-search techniques. We then develop a novel external-memory approach, which we call Pruned Companion Files (PCF), that supports disk operation of all 18 algorithms. When compared to state-of-the-art available implementations MGT and PDTL, PCF runs 5-10 times faster and exhibits orders of magnitude less I/O. We next focus on I/O complexity of triangle listing. Recent work by Pagh etc. provides an appealing theoretical I/O complexity for triangle listing via graph partitioning by random coloring of nodes. Since no implementation of Pagh is available and little is known about the comparison between Pagh and PCF, we carefully implement Pagh, undertake an investigation into the properties of these algorithms, model their I/O cost, understand their shortcomings, and shed light on the conditions under which each method defeats the other. This insight leads us to develop a novel framework we call Trigon that surpasses the I/O performance of both techniques in all graphs and under all RAM conditions. We finally turn our attention to neighborhood function. Exact computation of neighborhood function is expensive in terms of CPU and I/O cost. Previous work mostly focuses on approximations. We show that our novel techniques developed for triangle listing can also be applied to this problem. We next study an application of neighborhood function to ranking of Internet hosts. Our method computes neighborhood functions for each host as an indication of

关键词： graph mining external-memory algorithm Thesis

来源：评论

学校读者我要写书评

暂无评论

Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 1998年第4期9卷 211-236页

作者： Chiang, YJ SUNY Stony Brook Dept Appl Math & Stat Computat Geometry Lab Stony Brook NY 11794 USA

We present an extensive experimental study comparing the performance of four algorithms for the following orthogonal segment intersection problem: given a set of horizontal and vertical line segments in the plane, report all intersecting horizontal-vertical pairs. The problem has important applications in VLSI layout and graphics, which are large-scale in nature. The algorithms under evaluation are our implementations of distribution sweep and three variations of plane sweep. Distribution sweep is specifically designed for the situations in which the problem is too large to be solved in internal memory, and theoretically has optimal I/O cost. Plane sweep is a well-known and powerful technique in computational geometry, and is optimal for this particular problem in terms of internal computation. The three variations of plane sweep differ by the sorting methods (external versus internal sorting) used in the preprocessing phase acid the dynamic data structures (B-tree versus 2-3-4-tree) used in the sweeping phase. We generate the test data by three programs that use a random number generator while producing some interesting properties that are predicted by our theoretical analysis. The sizes of the test data range from 250 thousand segments to 2.5 million segments. The experiments provide detailed quantitative evaluation of the performance of the four algorithms, and the observed behavior of the algorithms is consistent with their theoretical properties. This is, to the best of our knowledge, the first experimental algorithmic study comparing the practical performance between external-memory algorithms and conventional algorithms with large-scale test data. (C) 1998 Elsevier Science B.V.

关键词： segment intersection plane sweep distribution sweep B-tree external-memory algorithm implementation experimentation probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

Quick-VDR: Out-of-core view-dependent rendering of gigantic models

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2005年第4期11卷 369-382页

作者： Yoon, SE Salomon, B Gayle, R Manocha, D Univ N Carolina Dept Comp Sci Chapel Hill NC 27599 USA

We present a novel approach for interactive view-dependent rendering of massive models. Our algorithm combines view-dependent simplification, occlusion culling, and out-of-core rendering. We represent the model as a clustered hierarchy of progressive meshes (CHPM). We use the cluster hierarchy for coarse-grained selective refinement and progressive meshes for fine-grained local refinement. We present an out-of-core algorithm for computation of a CHPM that includes cluster decomposition, hierarchy generation, and simplification. We introduce novel cluster dependencies in the preprocess to generate crack-free, drastic simplifications at runtime. The clusters are used for LOD selection, occlusion culling, and out-of-core rendering. We add a frame of latency to the rendering pipeline to fetch newly visible clusters from the disk and avoid stalls. The CHPM reduces the refinement cost of view-dependent rendering by more than an order of magnitude as compared to a vertex hierarchy. We have implemented our algorithm on a desktop PC. We can render massive CAD, isosurface, and scanned models, consisting of tens or a few hundred million triangles at 15-35 frames per second with little loss in image quality.

关键词： interactive display view-dependent rendering occlusion culling external-memory algorithm out-of-core algorithms levels-of-detail

来源：评论

学校读者我要写书评

暂无评论

Quick-VDR: Interactive view-dependent rendering of massive models 04

Quick-VDR: Interactive view-dependent rendering of massive m...

引用

IEEE Visualization 2004 Conference

作者： Yoon, SE Salomon, B Gayle, R Manocha, D Univ N Carolina Chapel Hill NC 27514 USA

ISBN: (纸本)0780387880

We present a novel approach for interactive view-dependent rendering of massive models. Our algorithm combines view-dependent simplification, occulsion culling, and out-of-core rendering. We represent the model as a clustered hierarchy of progressive meshes (CHPM). We use the cluster hierarchy for coarse-grained selective refinement and progressive meshes for fine-grained local refinement. We present an out-of-core algorithm for computation of a CHPM that includes cluster decomposition, hierarchy generation, and simplification. We make use of novel cluster dependencies in the preprocess to generate crack-free, drastic simplifications at runtime. The clusters are used for occulsion culling and out-of-core rendering. We add a frame of latency to the rendering pipeline to fetch newly visible clusters from the disk and to avoid stalls. The CHPM reduces the refinement cost for view-dependent rendering by more than an order of magnitude as compared to a vertex hierarchy. We have implemented our algorithm on a desktop PC. We can render massive CAD, isosurface, and scanned models, consisting of tens or a few hundreds of millions of triangles at 10-35 frames per second with little loss in image quality.

关键词： interactive display view-dependent rendering occlusion culling external-memory algorithm levels-of-detail

来源：评论

学校读者我要写书评

暂无评论

A method for accelerating relations search over big data scenario 22

A method for accelerating relations search over big data sce...

引用

Proceedings of the 2022 5th International Conference on algorithms, Computing and Artificial Intelligence

作者： Lihua Liu Mao Wang Kaiming Xiao Haiwen Chen College of System Engineering National University of Defense Technology China and Laboratory for Big Data and Decision National University of Defense Technology China

ISBN: (纸本)9781450398336

We propose an acceleration method for relations search over big data scenario. The relations search is in essence an induced subgraph search of graph data model, which is to search all edges with all adjacent vertices falling into a given vertex set. For example, in the risk-control scenario for anti-fraud, for a swindling gang of highly similar fraud behaviors, figuring out all relations between these swindlers can be greatly beneficial to precisely attack all similar gangs. In-memory induced subgraph search requires lots of random accesses, while in big data scenario, relations data tend to be stored on disk when the memory is limited, and the corresponding random lookups over disk incorporate huge overhead. Also, even a singleton disk access could be costly since there are usually many properties data in a relation. Hence, existing methods would suffer considerable performance bottlenecks when applied over data on disk. We build graph over disk-based edge index, and propose multiple BFS (Bread First Search) level gaps based induces subgraph acceleration method, with efficient performance guarantee when the memory is limited. We avoid imbalance in performance for query evaluation with edge index based data organization, with which we further reduce redundant I/O accesses. We filter most invalid no-result edge queries based our BFS level gaps framework. We find that, for each BFS, we can confirm the no edge status between a pair of vertices if their BFS accessing level are of distance more than 1, which indicates the nonexistence of edge. Extensive experiments over real world graph datasets confirm the effectiveness of our method. We find that more than 97% invalid edge queries are filtered by our method, which greatly improve the system performance. Hence, our method with multiple BFS level gap encoding over vertices could greatly filter no-result edge queries and improve the relation search performance. Out method also reduce the redundant I/O access over disk wi

关键词： external-memory algorithm Graph Model Induced Subgraph Query Acceleration Big Data

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：