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

i/o-efficient algorithms for top-<i>ki> nearest keyword search in massive graphs

VLDB JoURNAL 2017年第4期26卷 563-583页

作者： Zhu, Qiankun Cheng, Hong Huang, Xin Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Fudan Univ Sch Data Sci Shanghai Peoples R China

Networks emerging nowadays usually have labels or textual content on the nodes. We model such commonly seen network as an undirected graph G, in which each node is attached with zero or more keywords, and each edge is assigned with a length. on such networks, a novel and useful query is called top-k nearest keyword (k-NK) search. Given a query node q in G and a keyword lambda, a k-NK query searches k nodes which contain lambda and are nearest to q. The k-NK problem has been studied recently in the literature. But most existing solutions assume that the graph as well as the constructed index can fit entirely in memory. As a result, they cannot be applied directly to very large-scale networks which are commonly found in practice, but cannot fit in memory. in this work, we design an i/o-efficient solution, which uses a compact disk index to answer a k-NK query with constant i/os. The key to an accurate k-NK result is a precise shortest distance estimation in a graph. in our solution, we follow our previous work Qiao et al. (PVLDB 6: 901-912, 2013) which uses the shortest path tree as an approximate representation of a graph and uses the tree distance between two nodes as an accurate estimation of the shortest distance between them on a graph. With such representation, the original k-NK query on a graph can be reduced to answering the query on a set of trees and then assembling the results obtained from the trees. We exploit a compact tree-based index and study how to lay out the index to disk. We design a novel technique which decomposes the index tree into paths and subtrees and stores them in disk. our theoretical analysis shows that the disk-based index is small in size and supports constant query i/os. Extensive experimental study on massive trees and graphs with billions of edges and keywords verifies our theoretical findings and demonstrates the superiority of our method over the state-of-the-art methods in the literature.

关键词： i/o-efficient algorithms Nearest keywords search Top-k Massive graphs

来源：评论

学校读者我要写书评

暂无评论

i/o-efficient algorithms on Triangle Listing and Counting

引用

ACM TRANSACTioNS oN DATABASE SYSTEMS 2014年第4期39卷 27-27页

作者： Hu, Xiaocheng Tao, Yufei Chung, Chin-Wan Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China Korea Adv Inst Sci & Technol Dept Comp Sci Taejon 305701 South Korea Korea Adv Inst Sci & Technol Div Web Sci & Technol Taejon 305701 South Korea

This article studies i/o-efficient algorithms for the triangle listing problem and the triangle counting problem, whose solutions are basic operators in dealing with many other graph problems. in the former problem, given an undirected graph G, the objective is to find all the cliques involving 3 vertices in G. in the latter problem, the objective is to report just the number of such cliques without having to enumerate them. Both problems have been well studied in internal memory, but still remain as difficult challenges when G does not fit in memory, thus making it crucial to minimize the number of disk i/os performed. Although previous research has attempted to tackle these challenges, the state-of-the-art solutions rely on a set of crippling assumptions to guarantee good performance. Motivated by this, we develop a new algorithm that is provably i/o and CPU efficient at the same time, without making any assumption on the input G at all. The algorithm uses ideas drastically different from all the previous approaches, and outperforms the existing competitors by a factor of over an order of magnitude in our extensive experimentation.

关键词： algorithms Theory Performance Triangle listing triangle counting graphs i/o-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

i/o-efficient Shortest Path algorithms for Undirected Graphs with Random or Bounded Edge Lengths

引用

ACM TRANSACTioNS oN algorithms 2012年第3期8卷 22-22页

作者： Meyer, Ulrich Zeh, Norbert Dalhousie Univ Fac Comp Sci Halifax NS B3H 1W5 Canada Goethe Univ Frankfurt Inst Informat D-60325 Frankfurt Germany

We present i/o-efficient single-source shortest path algorithms for undirected graphs. our main result is an algorithm with i/o complexity o(root nm log L)/ B + MST(n, m)) on graphs with n vertices, m edges, and arbitrary edge lengths between 1 and L;MST(n, m) denotes the i/o complexity of computing a minimum spanning tree;B denotes the disk block size. if the edge lengths are drawn uniformly at random from ( 0, 1], the expected i/o complexity of the algorithm is o(root nm/ B + ( m/ B) log B + MST(n, m)). A simpler algorithm has expected i/o complexity o(root nm log B)/ B + MST(n, m) for uniformly random edge lengths.

关键词： algorithms Theory Graph algorithms i/o-efficient algorithms memory hierarchies shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

i/o-efficient planar separators

引用

SiAM JoURNAL oN CoMPUTiNG 2008年第3期38卷 767-801页

作者： Maheshwari, Anil Zeh, Norbert Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Dalhousie Univ Fac Comp Sci Halifax NS B3H 1W5 Canada

We present i/o-efficient algorithms for computing optimal separator partitions of planar graphs. our main result shows that, given a planar graph G with N vertices and an integer r > 0, a vertex separator of size o(N/root r) that partitions G into o(N/r) subgraphs of size at most r and boundary size o(v r) can be computed in o(sort(N)) i/os. This bound holds provided that M >= 56r log(2) B. Together with an i/o-efficient planar embedding algorithm presented in [N. Zeh, i/o-efficient algorithms for Shortest Path Related Problems, Ph. D. thesis, School of Computer Science, Carleton University, ottawa, oN, Canada, 2002], this result is the basis for i/o-efficient solutions to many other fundamental problems on planar graphs, including breadth-first search and shortest paths [L. Arge, G. S. Brodal, and L. Toma, J. algorithms, 53 (2004), pp. 186 - 206;L. Arge, L. Toma, and N. Zeh, i/o-efficient algorithms for planar digraphs, in Proceedings of the 15th ACM Symposium on Parallelism in algorithms and Architectures, ACM, New York, 2003, pp. 85 - 93], depth-first search [L. Arge et al., J. Graph algorithms Appl., 7 (2003), pp. 105 - 129;L. Arge and N. Zeh, i/o-efficient strong connectivity and depth-first search for directed planar graphs, in Proceedings of the 44th iEEE Symposium on Foundations of Computer Science, iEEE Press, Piscataway, NJ, 2003, pp. 261 - 270], strong connectivity [L. Arge and N. Zeh, i/o-efficient strong connectivity and depth-first search for directed planar graphs, in Proceedings of the 44th iEEE Symposium on Foundations of Computer Science, iEEE Press, Piscataway, NJ, 2003, pp. 261 - 270], and topological sorting [L. Arge and L. Toma, Simplified external memory algorithms for planar DAGs, in Proceedings of the 9th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Comput. Sci. 3111, Springer-Verlag, Berlin, New York, 2004, pp. 493 - 503;L. Arge, L. Toma, and N. Zeh, i/o-efficient algorithms for planar digraphs, in Proceedings of the 15th ACM

关键词： i/o-efficient algorithms memory hierarchies graph algorithms planar graphs graph separators

来源：评论

学校读者我要写书评

暂无评论

i/o-efficient Computation of Water Flow Across a Terrain 10

I/O-Efficient Computation of Water Flow Across a Terrain

引用

26th Annual Symposium on Computational Geometry

作者： Arge, Lars Revsaek, Morten Zeh, Norbert Univ Aarhus MADALGO Aarhus Denmark

ISBN: (纸本)9781450300162

Consider rain falling at a uniform rate onto a terrain T represented as a triangular irregular network. over time, water collects in the basins of T, forming lakes that spill into adjacent basins. our goal is to compute, for each terrain vertex, the time this vertex is flooded (covered by water). We present an i/o-efficient algorithm that solves this problem using o(sort(X) log(X/M) + sort(N)) i/os, where N is the number of terrain vertices, X is the number of pits of the terrain, sort(N) is the cost of sorting N data items, and M is the size of the computer's main memory. our algorithm assumes that the volumes and watersheds of the basins of T have been precomputed using existing methods.

关键词： Terrains geographical information systems i/o-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

i/o-efficient Batched Union-Find and its Applications to Terrain Analysis

引用

ACM TRANSACTioNS oN algorithms 2010年第1期7卷 11-11页

作者： Agarwal, Pankaj K. Arge, Lars Yi, Ke Duke Univ Dept Comp Sci Durham NC 27708 USA Aarhus Univ Dept Comp Sci MADALGO DK-8200 Aarhus Denmark Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Kowloon Hong Kong Peoples R China

in this article we present an i/o-efficient algorithm for the batched (off-line) version of the union-find problem. Given any sequence of N union and find operations, where each union operation joins two distinct sets, our algorithm uses o(SoRT(N)) = o(N/B logM/B N/B) i/os, where M is the memory size and B is the disk block size. This bound is asymptotically optimal in the worst case. if there are union operations that join a set with itself, our algorithm uses o(SoRT(N) + MST(N)) i/os, where MST(N) is the number of i/os needed to compute the minimum spanning tree of a graph with N edges. We also describe a simple and practical o(SoRT(N) log(N/M))-i/o algorithm for this problem, which we have implemented. We are interested in the union-find problem because of its applications in terrain analysis. A terrain can be abstracted as a height function defined over R-2, and many problems that deal with such functions require a union-find data structure. With the emergence of modern mapping technologies, huge amount of elevation data is being generated that is too large to fit in memory, thus i/o-efficient algorithms are needed to process this data efficiently. in this article, we study two terrain-analysis problems that benefit from a union-find data structure: (i) computing topological persistence and (ii) constructing the contour tree. We give the first o(SoRT(N))-i/o algorithms for these two problems, assuming that the input terrain is represented as a triangular mesh with N vertices.

关键词： i/o-efficient algorithms union-find

来源：评论

学校读者我要写书评

暂无评论

Towards a Worst-Case i/o-optimal Algorithm for Acyclic Joins 16

Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins

引用

35th ACM SiGMoD-SiGACT-SiGART Symposium on Principles of Database Systems (PoDS)

作者： Hu, Xiao Yi, Ke Hong Kong Univ Sci & Technol Hong Kong Peoples R China

ISBN: (纸本)9781450341912

Nested-loop join is a worst-case i/o-optimal algorithm for 2 relations. Recently, a lot of efforts have been devoted to the "triangle query", for which an i/o-optimal algorithm is known. This paper extends these results to a fairly large class of acyclic joins. Acyclic joins can be computed optimally in internal memory using Yannakakis' algorithm from 1981, which simply performs a series of pairwise joins. However, no pairwise join algorithm can be i/o-optimal beyond 2 relations. To achieve i/o-optimality, the algorithm has to handle all the intermediate results carefully without writing them to disk. Unlike the optimal internal memory join algorithm which has a nice tight bound (the AGM bound), the i/o-complexity of joins turns out to be quite complex or even unknown. Yet, we are able to prove that our algorithm is i/o-optimal for certain classes of acyclic joins without deriving its bound explicitly.

关键词： i/o-efficient algorithms acyclic joins worst-case optimal

来源：评论

学校读者我要写书评

暂无评论

External Memory Pipelining Made Easy With TPiE 5

External Memory Pipelining Made Easy With TPIE

引用

iEEE international Conference on Big Data (iEEE Big Data)

作者： Arge, Lars Rav, Mathias Svendsen, Svend C. Truelsen, Jakob Aarhus Univ Dept Comp Sci MADALGO Aarhus Denmark SCALGO Aarhus Denmark

ISBN: (纸本)9781538627150

When handling large datasets that exceed the capacity of the main memory, movement of data between main memory and external memory (disk), rather than actual (CPU) computation time, is often the bottleneck in the computation. Since data is moved between disk and main memory in large contiguous blocks, this has led to the development of a large number of i/o-efficient algorithms that minimize the number of such block movements. However, actually implementing these algorithms can be somewhat of a challenge since operating systems do not give complete control over movement of blocks and management of main memory. TPiE is one of two major libraries that have been developed to support i/o-efficient algorithm implementations. it relies heavily on the fact that most i/o-efficient algorithms are naturally composed of components that stream through one or more lists of data items, while producing one or more such output lists, or components that sort such lists. Thus TPiE provides an interface where list stream processing and sorting can be implemented in a simple and modular way without having to worry about memory management or block movement. However, if care is not taken, such streaming-based implementations can lead to practically inefficient algorithms since lists of data items are typically written to (and read from) disk between components. in this paper we present a major extension of the TPiE library that includes a pipelining framework that allows for practically efficient streaming-based implementations while minimizing i/o-overhead between streaming components. The framework pipelines streaming components to avoid i/os between components, that is, it processes several components simultaneously while passing output from one component directly to the input of the next component in main memory. TPiE automatically determines which components to pipeline and performs the required main memory management, and the extension also includes support for parallelization of i

关键词： i/o-efficient algorithms C plus software framework

来源：评论

学校读者我要写书评

暂无评论

External Memory Stream Sampling 15

External Memory Stream Sampling

引用

33rd ACM Symposium on Principles of Database Systems (PoDS)

作者： Hu, Xiaocheng Qiao, Miao Tao, Yufei CUHK Hong Kong Peoples R China

ISBN: (纸本)9781450327572

This paper aims to understand the i/o-complexity of maintaining a big sample set-whose size exceeds the internal memory's capacity-on a data stream. We study this topic in a new computation model, named the external memory stream (EMS) model, that naturally extends the standard external memory model to stream environments. A suite of EMS-indigenous techniques are presented to prove matching lower and upper bounds for with-replacement (WR) and without-replacement (WoR) sampling on append-only and time-based sliding window streams, respectively. our results imply that, compared to RAM, the EMS model is perhaps a more suitable computation model for studying stream sampling, because the new model separates different problems by their hardness in ways that could not be observed in RAM.

关键词： Stream Sampling i/o-efficient algorithms Lower Bound

来源：评论

学校读者我要写书评

暂无评论

Processing Huge Graphs with Stxxl

引用

Electronic Notes in Discrete Mathematics 2006年第SPEC. ISS.期25卷 37-38页

作者： Dementiev, Roman Fakultät für Informatik Universität Karlsruhe 76131 Karlsruhe Am Fasanengarten 5 Germany

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：