NDLI: Fast random graph generation

Please wait, while we are loading the content...

Map-reduce extensions and recursive queries

Novel techniques to reduce search space in multiple minimum supports-based frequent pattern mining algorithms

GPX-matcher: a generic boolean predicate-based XPath expression matcher

Energy proportionality for disk storage using replication

Native support of multi-tenancy in RDBMS for software as a service

Answering tree pattern queries using views: a revisit

Keyword-based, context-aware selection of natural language query patterns

Efficient answering of set containment queries for skewed item distributions

SeMiTri: a framework for semantic annotation of heterogeneous trajectories

TAGs: scalable threshold-based algorithms for proximity computation in graphs

Fast random graph generation

Finding closed frequent item sets by intersecting transactions

Data integration with dependent sources

Predicting completion times of batch query workloads using interaction-aware models and simulation

Queries on dates: fast yet not blind

SocialSearch: enhancing entity search with social network matching

Schema matching and mapping: from usage to evaluation

A probabilistic XML merging tool

Database researchers: plumbers or thinkers?

Mining closed discriminative dyadic sequential patterns

An optimal strategy for monitoring top-k queries in streaming windows

Caching query-biased snippets for efficient retrieval

SLA-tree: a framework for efficiently supporting SLA-based decisions in cloud computing

Dynamic reasoning on XML updates

Unified structure and content search for personal information management systems

Subspace clustering for indexing high dimensional data: a main memory index based on local reductions and individual multi-representations

Efficient execution plans for distributed skyline query processing

Projection for XML update optimization

Symmetrizations for clustering directed graphs

Aspect-oriented relational algebra

Constructing concept relation network and its application to personalized web search

Memory-efficient frequent-itemset mining

Designing integration flows using hypercubes

Road crash proneness prediction using data mining

Big data and cloud computing: current state and future opportunities

Taking the OXPath down the deep web

Sequenced event set pattern matching

Fast and accurate computation of equi-depth histograms over data streams

Efficient and scalable data evolution with column oriented databases

On enhancing scalability for distributed RDF/S stores

Algebraic incremental maintenance of XML views

TopRecs: Top-k algorithms for item-based collaborative filtering

On (not) indexing quadratic form distance by metric access methods

Probabilistic range queries for uncertain trajectories on road networks

Efficient reverse skyline retrieval with arbitrary non-metric similarity measures

Efficient discovery of frequent subgraph patterns in uncertain graph databases

Synopses for probabilistic data over large domains

Effective and efficient sampling methods for deep web aggregation queries

Link-based hidden attribute discovery for objects on Web

Experience in Continuous analytics as a Service (CaaaS)

The hidden web, XML and the Semantic Web: scientific data management perspectives

SPRINT: ranking search results by paths

Making interval-based clustering rank-aware

Real-time approximate Range Motif discovery & data redundancy removal algorithm

A query optimization assistant for XPath

TPM: supporting pattern matching queries for road-network trajectory data

QueryViz: helping users understand SQL queries and their patterns

True language-level SQL debugging

SITAC: discovering semantically identical temporally altering concepts in text archives

Unraveling multi-dimensional data using pDView

RanKloud: a scalable ranked query processing framework on hadoop

Fast random graph generation

Content Provider	ACM Digital Library
Author	Lu, Xuesong Karras, Panagiotis Bressan, Stéphane Nobari, Sadegh
Abstract	Today, several database applications call for the generation of random graphs. A fundamental, versatile random graph model adopted for that purpose is the Erdős-Rényi $Γ_{v,p}$ model. This model can be used for directed, undirected, and multipartite graphs, with and without self-loops; it induces algorithms for both graph generation and sampling, hence is useful not only in applications necessitating the generation of random structures but also for simulation, sampling and in randomized algorithms. However, the commonly advocated algorithm for random graph generation under this model performs poorly when generating large graphs, and fails to make use of the parallel processing capabilities of modern hardware. In this paper, we propose PPreZER, an alternative, data parallel algorithm for random graph generation under the Erdős-Rényi model, designed and implemented in a graphics processing unit (GPU). We are led to this chief contribution of ours via a succession of seven intermediary algorithms, both sequential and parallel. Our extensive experimental study shows an average speedup of 19 for PPreZER with respect to the baseline algorithm.
Starting Page	331
Ending Page	342
Page Count	12
File Format	PDF
ISBN	9781450305280
DOI	10.1145/1951365.1951406
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-03-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Parallel algorithm Erdős-rényi Random graphs Gilbert
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in