The DOI matches its Crossref record; 162 of the 162 references it cites were found in a registry or an index.
Ligra: a lightweight graph processing framework for shared memory
Abstract
There has been significant recent interest in parallel frameworks for processing graphs due to their applicability in studying social networks, the Web graph, networks in biology, and unstructured meshes in scientific simulation. Due to the desire to process large graphs, these systems have emphasized the ability to run on distributed memory machines. Today, however, a single multicore server can support more than a terabyte of memory, which can fit graphs with tens or even hundreds of billions of edges. Furthermore, for graph algorithms, shared-memory multicores are generally significantly more efficient on a per core, per dollar, and per joule basis than distributed memory systems, and shared-memory algorithms tend to be simpler than their distributed counterparts.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
A Set of Measures of Centrality Based on Betweenness
Freeman, L. C. (1977) · Sociometry · doi:10.2307/3033543 · Cited by 10,295
What is Twitter, a social network or a news media?
Kwak, H., Lee, C., Park, H., & Moon, S. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772751 · Cited by 6,652
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
Karypis, G., & Kumar, V. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827595287997 · Cited by 5,762
A universal algorithm for sequential data compression
Ziv, J., & Lempel, A. (1977) · IEEE Transactions on Information Theory · doi:10.1109/tit.1977.1055714 · Cited by 5,456
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
A faster algorithm for betweenness centrality*
Brandes, U. (2001) · The Journal of Mathematical Sociology · doi:10.1080/0022250x.2001.9990249 · Cited by 4,936
A fast algorithm for particle simulations
Greengard, L., & Rokhlin, V (1987) · Journal of Computational Physics · doi:10.1016/0021-9991(87)90140-9 · Cited by 4,868
A Bridging Model for Parallel Computation
Valiant, L. G. (1990) · ACM eBooks · doi:10.1145/3749740.3749753 · Cited by 3,664
The university of Florida sparse matrix collection
Davis, T. A., & Hu, Y. (2011) · ACM Transactions on Mathematical Software · doi:10.1145/2049662.2049663 · Cited by 3,630
Design of ion-implanted MOSFET's with very small physical dimensions
Dennard, R. H., Gaensslen, F. H., Yu, H.-N., Rideout, V. L., Bassous, E., & LeBlanc, A. R. (1974) · IEEE Journal of Solid-State Circuits · doi:10.1109/jssc.1974.1050511 · Cited by 3,548
Pregel: a system for large-scale graph processing
Malewicz, G., Austern, M. H., Bik, A. J. C., Dehnert, J. C., Horn, I., Leiser, N., & Czajkowski, G. (2010) · Proceedings of the 2010 ACM SIGMOD International Conference on Management of data · doi:10.1145/1807167.1807184 · Cited by 3,515
Linearizability: a correctness condition for concurrent objects
Herlihy, M. P., & Wing, J. M. (1990) · ACM Transactions on Programming Languages and Systems · doi:10.1145/78969.78972 · Cited by 3,176
Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
Gusfield, D. (1997) · Cambridge University Press eBooks · doi:10.1017/cbo9780511574931 · Cited by 3,078
How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
Lamport (1979) · IEEE Transactions on Computers · doi:10.1109/tc.1979.1675439 · Cited by 2,519
A Block-sorting Lossless Data Compression Algorithm
Burrows, M. T., & Wheeler, D. J. (1994) · Cited by 2,333
Introduction to Algorithms, third edition
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009) · Cited by 2,309
Suffix Arrays: A New Method for On-Line String Searches
Manber, U., & Myers, G. (1993) · SIAM Journal on Computing · doi:10.1137/0222058 · Cited by 1,915
Parallel Computer Architecture: A Hardware/Software Approach
Culler, D., Gupta, A., & SINGH, J. P. (1998) · Cited by 1,716
Algorithms on strings, trees, and sequences
Gusfield, D. (1997) · Cited by 1,697
Distributed GraphLab: a framework for machine learning and data mining in the cloud
Low, Y., Bickson, D., Gonzalez, J., Guestrin, C., Kyrola, A., & Hellerstein, J. M. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2212351.2212354 · Cited by 1,653
An introduction to parallel algorithms
JáJá, J. F. (1992) · Cited by 1,600
A Space-Economical Suffix Tree Construction Algorithm
McCreight, E. M. (1976) · Journal of the ACM · doi:10.1145/321941.321946 · Cited by 1,511
On-line construction of suffix trees
Ukkonen, E. (1995) · Algorithmica · doi:10.1007/bf01206331 · Cited by 1,472
PowerGraph: distributed graph-parallel computation on natural graphs
Gonzalez, J. E., Low, Y., Gu, H., Bickson, D., & Guestrin, C. (2012) · doi:10.5555/2387880.2387883 · Cited by 1,451
Scheduling multithreaded computations by work stealing
Blumofe, R. D., & Leiserson, C. E. (1999) · Journal of the ACM · doi:10.1145/324133.324234 · Cited by 1,336
R-MAT: A Recursive Model for Graph Mining
Chakrabarti, D., Zhan, Y., & Faloutsos, C. (2004) · Proceedings of the 2004 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.43 · Cited by 1,255
The webgraph framework I: compression techniques
Boldi, P., & Vigna, S. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988752 · Cited by 1,201
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Luby, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215074 · Cited by 1,147
MULTILISP: a language for concurrent symbolic computation
Halstead, R. H. (1985) · ACM Transactions on Programming Languages and Systems · doi:10.1145/4472.4478 · Cited by 1,073
Fast algorithms for large-scale genome alignment and comparison
Delcher, A. L. (2002) · Nucleic Acids Research · doi:10.1093/nar/30.11.2478 · Cited by 1,036
PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric
Morrison, D. R. (1968) · Journal of the ACM · doi:10.1145/321479.321481 · Cited by 969
GraphChi: Large-Scale Graph Computation on Just a PC
Kyrola, A., Blelloch, G. E., & Guestrin, C. (2018) · Figshare · doi:10.1184/r1/6605999 · Cited by 868
Self-citationThe Parallel Evaluation of General Arithmetic Expressions
Brent, R. P. (1974) · Journal of the ACM · doi:10.1145/321812.321815 · Cited by 814
Cilk: An Efficient Multithreaded Runtime System
Blumofe, R. D., Joerg, C. F., Kuszmaul, B. C., Leiserson, C. E., Randall, K. H., & Zhou, Y. (1996) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1996.0107 · Cited by 784
Navarro, G., & Mäkinen, V. (2007) · ACM Computing Surveys · doi:10.1145/1216370.1216372 · Cited by 735
Parallel Algorithms for Shared-Memory Machines
Karp, R. M., & Ramachandran, V. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50022-9 · Cited by 687
Replacing suffix trees with enhanced suffix arrays
Abouelhoda, M. I., Kurtz, S., & Ohlebusch, E. (2004) · Journal of Discrete Algorithms · doi:10.1016/s1570-8667(03)00065-0 · Cited by 668
A taxonomy of problems with fast parallel algorithms
Cook, S. A. (1985) · Information and Control · doi:10.1016/s0019-9958(85)80041-3 · Cited by 641
Data compression via textual substitution
Storer, J. A., & Szymanski, T. G. (1982) · Journal of the ACM · doi:10.1145/322344.322346 · Cited by 634
Boldi, P., Rosa, M., Santini, M., & Vigna, S. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963488 · Cited by 592
Callahan, P. B., & Kosaraju, S. R. (1995) · Journal of the ACM · doi:10.1145/200836.200853 · Cited by 543
Intel Threading Building Blocks
Kukanov, A. (2015) · Programming Models for Parallel Computing · doi:10.7551/mitpress/9486.003.0016 · Cited by 521
GPS: a graph processing system
Salihoglu, S., & Widom, J. (2013) · Proceedings of the 25th International Conference on Scientific and Statistical Database Management · doi:10.1145/2484838.2484843 · Cited by 510
Wrench, J. W. (1970) · Mathematics of Computation · doi:10.1090/s0025-5718-1970-0400642-2 · Cited by 482
REPuter: fast computation of maximal repeats in complete genomes.
Kurtz, S., & Schleiermacher, C. (1999) · Bioinformatics · doi:10.1093/bioinformatics/15.5.426 · Cited by 479
Algorithm 235: Random permutation
Durstenfeld, R. (1964) · Communications of the ACM · doi:10.1145/364520.364540 · Cited by 460
Main-memory triangle computations for very large (sparse (power-law)) graphs
Latapy, M. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.07.017 · Cited by 458
Weak ordering—a new definition
Adve, S. V., & Hill, M. D. (1998) · doi:10.1145/285930.285996 · Cited by 450
Linear work suffix array construction
Kärkkäinen, J., Sanders, P., & Burkhardt, S. (2006) · Journal of the ACM · doi:10.1145/1217856.1217858 · Cited by 433
Size-Estimation Framework with Applications to Transitive Closure and Reachability
Cohen, E. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1534 · Cited by 416
The Combinatorial BLAS: design, implementation, and applications
Buluç, A., & Gilbert, J. R. (2011) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342011403516 · Cited by 415
Counting triangles and the curse of the last reducer
Suri, S., & Vassilvitskii, S. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963491 · Cited by 408
Parallel tree contraction and its application
Miller, G. L., & Reif, J. H. (1985) · 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) · doi:10.1109/sfcs.1985.43 · Cited by 404
Simple Linear Work Suffix Array Construction
Kärkkäinen, J., & Sanders, P. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-45061-0_73 · Cited by 404
A scalable approach to thread-level speculation
Steffan, J. G., Colohan, C. B., Zhai, A., & Mowry, T. C. (2000) · Proceedings of the 27th annual international symposium on Computer architecture - ISCA '00 · doi:10.1145/339647.339650 · Cited by 392
Compressed representations of sequences and full-text indexes
Ferragina, P., Manzini, G., Mäkinen, V., & Navarro, G. (2007) · ACM Transactions on Algorithms · doi:10.1145/1240233.1240243 · Cited by 373
On compressing social networks
Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., & Raghavan, P. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557049 · Cited by 349
Approximating Betweenness Centrality
Bader, D. A., Kintali, S., Madduri, K., & Mihail, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-77004-6_10 · Cited by 340
Finding maximal repetitions in a word in linear time
Kolpakov, R. M., & Kucherov, G. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814634 · Cited by 338
Reducing the space requirement of suffix trees
Kurtz, S. (1999) · Software: Practice and Experience · doi:10.1002/(sici)1097-024x(199911)29:13<1149::aid-spe274>3.0.co;2-o · Cited by 334
DMP: deterministic shared memory multiprocessing
Devietti, J., Lucia, B., Ceze, L., & Oskin, M. (2009) · Proceedings of the 14th international conference on Architectural support for programming languages and operating systems · doi:10.1145/1508244.1508255 · Cited by 328
DOULION: counting triangles in massive graphs with a coin
Tsourakakis, C. E., Kang, U., Miller, G. L., & Faloutsos, C. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557111 · Cited by 328
Efficient semi-streaming algorithms for local triangle counting in massive graphs
Becchetti, L., Boldi, P., Castillo, C., & Gionis, A. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401898 · Cited by 319
A taxonomy of suffix array construction algorithms
Puglisi, S. J., Smyth, W. F., & Turpin, A. H. (2007) · ACM Computing Surveys · doi:10.1145/1242471.1242472 · Cited by 312
The tao of parallelism in algorithms
Pingali, K., Nguyen, D., Kulkarni, M., Burtscher, M., Hassaan, M. A., Kaleem, R., Lee, T.-H., Lenharth, A., Manevich, R., Méndez-Lojo, M., et al. (2011) · ACM SIGPLAN Notices · doi:10.1145/1993316.1993501 · Cited by 312
Δ-stepping: a parallelizable shortest path algorithm
Meyer, U., & Sanders, P. (2003) · Journal of Algorithms · doi:10.1016/s0196-6774(03)00076-2 · Cited by 309
MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing
Fan, B., Andersen, D. G., & Kaminsky, M. (2018) · doi:10.1184/r1/6607223 · Cited by 296
Compressed Suffix Trees with Full Functionality
Sadakane, K. (2007) · Theory of Computing Systems · doi:10.1007/s00224-006-1198-x · Cited by 293
Clark, D. R. (1998) · Cited by 269
Efficient Parallel Graph Exploration on Multi-Core CPU and GPU
Hong, S., Oguntebi, T., & Olukotun, K. (2011) · 2011 International Conference on Parallel Architectures and Compilation Techniques · doi:10.1109/pact.2011.14 · Cited by 269
ANF: a fast and scalable tool for data mining in massive graphs
Palmer, C. R., Gibbons, P. B., & Faloutsos, C. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775059 · Cited by 266
TurboGraph: a fast parallel graph engine handling billion-scale graphs in a single PC
Han, W.-S., Lee, S., Park, K., Lee, J.-H., Kim, M.-S., Kim, J., & Yu, H. (2013) · Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2487575.2487581 · Cited by 259
Counting triangles in data streams
Buriol, L. S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., & Sohler, C. (2006) · Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1142351.1142388 · Cited by 252
A scalable pattern mining approach to web graph compression with communities
Buehrer, G., & Chellapilla, K. (2008) · Proceedings of the international conference on Web search and web data mining - WSDM '08 · doi:10.1145/1341531.1341547 · Cited by 246
Dthreads: efficient deterministic multithreading
Liu, T., Curtsinger, C., & Berger, E. D. (2011) · Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles · doi:10.1145/2043556.2043587 · Cited by 240
The tao of parallelism in algorithms
Pingali, K., Nguyen, D., Kulkarni, M., Burtscher, M., Hassaan, M. A., Kaleem, R., Lee, T.-H., Lenharth, A., Manevich, R., Méndez-Lojo, M., et al. (2011) · Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1993498.1993501 · Cited by 234
CoreDet: a compiler and runtime system for deterministic multithreaded execution
Bergan, T., Anderson, O., Devietti, J., Ceze, L., & Grossman, D. (2010) · ACM SIGPLAN Notices · doi:10.1145/1735971.1736029 · Cited by 231
Scalable Graph Exploration on Multicore Processors
Agarwal, V., Petrini, F., Pasetto, D., & Bader, D. A. (2010) · 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc.2010.46 · Cited by 223
Towards compressing Web graphs
Adler, M., & Mitzenmacher, M. (2002) · Proceedings DCC 2001. Data Compression Conference · doi:10.1109/dcc.2001.917151 · Cited by 223
Skew strikes back: new developments in the theory of join algorithms
Ngo, H. Q., Ré, C., & Rudra, A. (2014) · ACM SIGMOD Record · doi:10.1145/2590989.2590991 · Cited by 222
Dynamic decentralized cache schemes for mimd parallel processors
Rudolph, L., & Segall, Z. (1984) · ACM SIGARCH Computer Architecture News · doi:10.1145/773453.808203 · Cited by 213
Efficient system-enforced deterministic parallelism
Aviram, A. F., Weng, S.-C., Hu, S., & Ford, B. (2010) · Operating Systems Design and Implementation · doi:10.5555/1924943.1924957 · Cited by 200
The Cilk++ concurrency platform
Leiserson, C. E. (2010) · The Journal of Supercomputing · doi:10.1007/s11227-010-0405-3 · Cited by 199
Brief announcement: the problem based benchmark suite
Shun, J., Blelloch, G. E., Fineman, J. T., Gibbons, P. B., Kyrola, A., Simhadri, H. V., & Tangwongsan, K. (2012) · Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures · doi:10.1145/2312005.2312018 · Cited by 191
Self-citationCounting and sampling triangles from a graph stream
Pavan, A., Tangwongsan, K., Tirthapura, S., & Wu, K.-L. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2556549.2556569 · Cited by 190
Split-ordered lists: Lock-free extensible hash tables
Shalev, O., & Shavit, N. (2006) · Journal of the ACM · doi:10.1145/1147954.1147958 · Cited by 185
Space efficient linear time construction of suffix arrays
Ko, P., & Aluru, S. (2005) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2004.08.002 · Cited by 180
Deterministic process groups in dOS
Bergan, T., Hunt, N., Ceze, L., & Gribble, S. D. (2010) · Operating Systems Design and Implementation · doi:10.5555/1924943.1924956 · Cited by 169
Commutativity analysis: a new analysis technique for parallelizing compilers
Rinard, M., & Diniz, P. C. (1997) · ACM Transactions on Programming Languages and Systems · doi:10.1145/267959.269969 · Cited by 168
SlashBurn: Graph Compression and Mining beyond Caveman Communities
Lim, Y., Kang, U., & Faloutsos, C. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2014.2320716 · Cited by 163
Multicore triangle computations without tuning
Shun, J., & Tangwongsan, K. (2015) · 2015 IEEE 31st International Conference on Data Engineering · doi:10.1109/icde.2015.7113280 · Cited by 162
Self-citationRank and select revisited and extended
Mäkinen, V., & Navarro, G. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.07.013 · Cited by 161
Permuted Longest-Common-Prefix Array
Kärkkäinen, J., Manzini, G., & Puglisi, S. J. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02441-2_17 · Cited by 160
PEGASUS: mining peta-scale graphs
Kang, U., Tsourakakis, C. E., & Faloutsos, C. (2011) · Knowledge and Information Systems · doi:10.1007/s10115-010-0305-0 · Cited by 159
PATRIC: a parallel algorithm for counting triangles in massive networks
Arifuzzaman, S., Khan, M., & MARATHE, M. V. (2013) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2505515.2505545 · Cited by 153
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
KarypisGeorge, & KumarVipin (1998) · SIAM Journal on Scientific Computing · doi:10.5555/305219.305248 · Cited by 153
Computing Longest Previous Factor in linear time and applications
Crochemore, M., & Ilie, L. (2007) · Information Processing Letters · doi:10.1016/j.ipl.2007.10.006 · Cited by 152
Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors
Bader, D. A., & Madduri, K. (2005) · Lecture notes in computer science · doi:10.1007/11602569_48 · Cited by 151
Reduced-Bandwidth Multithreaded Algorithms for Sparse Matrix-Vector Multiplication
Buluç, A., Williams, S., Oliker, L., & Demmel, J. W. (2011) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2011.73 · Cited by 150
Detecting data races in Cilk programs that use locks
Cheng, G.-I., Feng, M. D., Leiserson, C. E., Randall, K. H., & Stark, A. F. (1998) · ACM Symposium on Parallel Algorithms and Architectures (SPAA) · doi:10.1145/277651.277696 · Cited by 148
HADI: Mining Radii of Large Graphs
Kang, U., Tsourakakis, C. E., Appel, A. P., Faloutsos, C., & Leskovec, J. (2011) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1921632.1921634 · Cited by 146
The Link Database: fast access to graphs of the Web
Randall, K. H., Stata, R., Wickremesinghe, R. G., & Wiener, J. L. (2003) · DCC · doi:10.1109/dcc.2002.999950 · Cited by 146
Linear Suffix Array Construction by Almost Pure Induced-Sorting
Nong, G., Zhang, S., & Chan, W. H. (2009) · DCC · doi:10.1109/dcc.2009.42 · Cited by 143
A uniform approach to accelerated PageRank computation
McSherry, F. (2005) · International World Wide Web Conference (WWW) · doi:10.1145/1060745.1060829 · Cited by 139
Finding a minimum circuit in a graph
Itai, A., & Rodeh, M. (1977) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800105.803390 · Cited by 136
Internally deterministic parallel algorithms can be fast
Blelloch, G. E., Fineman, J. T., Gibbons, P. B., et al. (2012) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2145816.2145840 · Cited by 135
Self-citationSuccinct representations of lcp information and improvements in the compressed suffix arrays
Sadakane, K. (2002) · doi:10.5555/545381.545410 · Cited by 134
Weak ordering—a new definition
Adve, S. V., & Hill, M. D. (1990) · ACM SIGARCH Computer Architecture News · doi:10.1145/325096.325100 · Cited by 129
Revisiting the combining synchronization technique
Fatourou, P., & Kallimanis, N. D. (2012) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2145816.2145849 · Cited by 128
Fast computation of empirically tight bounds for the diameter of massive graphs
Magnien, C., Matthieu Latapy, B., & Habib, M. (2009) · ACM Journal of Experimental Algorithmics · doi:10.1145/1412228.1455266 · Cited by 127
Making asynchronous parallelism safe for the world
Steele, G. L. (1990) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/96709.96731 · Cited by 126
Counting Triangles in Massive Graphs with MapReduce
Kolda, T. G., Pinar, A., Plantenga, T. D., Seshadhri, C., & Task, C. (2014) · SIAM Journal on Scientific Computing · doi:10.1137/13090729x · Cited by 123
Efficient implementation of lazy suffix trees
Giegerich, R., Kurtz, S., & Stoye, J. (2003) · Software Practice and Experience · doi:10.1002/spe.535 · Cited by 123
Naor, M., & Teague, V. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380844 · Cited by 110
Cui, H., Šimša, J., Lin, Y., Li, H., Blum, B., Xu, X., Yang, J., Gibson, G. A., & Bryant, R. E. (2013) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/2517349.2522735 · Cited by 109
Efficient deterministic multithreading through schedule relaxation
Cui, H., Wu, J., Gallagher, J., Guo, H., & Yang, J. (2011) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/2043556.2043588 · Cited by 106
Counting Triangles in Large Graphs using Randomized Matrix Trace Estimation
Avron, H. (2010) · Cited by 104
Meek, C., Patel, J. M., & Kasetty, S. (2003) · Elsevier eBooks · doi:10.1016/b978-012722442-8/50085-9 · Cited by 100
A fast GPU algorithm for graph connectivity
Soman, J., Kothapalli, K., & Narayanan, P. J. (2010) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2010.5470817 · Cited by 99
Genome-scale disk-based suffix tree indexing
Phoophakdee, B., & Zaki, M. J. (2007) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1247480.1247572 · Cited by 96
Triangle listing in massive networks
Chu, S., & Cheng, J. S.-C. (2012) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2382577.2382581 · Cited by 96
Stable deterministic multithreading through schedule memoization
Cui, H., Wu, J., Tsai, C.-C., et al. (2010) · doi:10.5555/1924943.1924958 · Cited by 96
Managing large graphs on multi-cores with graph awareness
Prabhakaran, V., Wu, M., Weng, X., McSherry, F., Zhou, L., & Haridasan, M. (2012) · USENIX Annual Technical Conference · Cited by 94
RCDC: a relaxed consistency deterministic computer
Devietti, J. L., Nelson, J., Bergan, T., Ceze, L., & Grossman, D. (2011) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/1950365.1950376 · Cited by 86
Tsourakakis, C. E., Petros Drineas, B., Michelakis, E., Koutis, I., & Faloutsos, C. (2010) · Social Network Analysis and Mining · doi:10.1007/s13278-010-0001-9 · Cited by 83
When indexing equals compression: Experiments with compressing suffix arrays and applications
Foschini, L., Grossi, R., Gupta, A. K., & Vitter, J. S. (2006) · ACM Transactions on Algorithms · doi:10.1145/1198513.1198521 · Cited by 81
CSX: an extended compression format for spmv on shared memory systems
Kourtis, K., Karakasis, V., Goumas, G., & Koziris, N. (2011) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/1941553.1941587 · Cited by 80
Non-blocking Hashtables with Open Addressing
Purcell, C. J., & Harris, T. (2005) · Lecture notes in computer science · doi:10.1007/11561927_10 · Cited by 79
A Unified Framework for Numerical and Combinatorial Computing
Gilbert, J. R., Reinhardt, S., & Shah, V. B. (2008) · Computing in Science & Engineering · doi:10.1109/mcse.2008.45 · Cited by 76
Random permutations on distributed, external and hierarchical memory
Sanders, P. (1998) · Information Processing Letters · doi:10.1016/s0020-0190(98)00127-6 · Cited by 66
SWARM: A Parallel Programming Framework for Multicore Processors
Bader, D. A., Kanade, V., & Madduri, K. (2007) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2007.370681 · Cited by 66
Makris, C. H. (2012) · Computer Science and Information Systems · doi:10.2298/csis110606004m · Cited by 62
Computing the longest common prefix array based on the Burrows–Wheeler transform
Beller, T., Gog, S., Ohlebusch, E., & Schnattinger, T. (2012) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2012.07.007 · Cited by 61
Strongly History-Independent Hashing with Applications
Blelloch, G. E., & Golovin, D. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.36 · Cited by 60
Self-citationWavelet Trees: From Theory to Practice
Grossi, R., Vitter, J. S., & Xu, B. (2011) · Data Compression, Communications and Processing · doi:10.1109/ccp.2011.16 · Cited by 59
Multiscale approach for the network compression-friendly ordering
Safro, I., & Temkin, B. (2010) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2010.09.007 · Cited by 56
Dimitrov, D. I., Raychev, V., Vechev, M., & Koskinen, E. (2014) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2594291.2594322 · Cited by 55
Parallel SAH k-D tree construction
Choi, B., Komuravelli, R., Lu, V., Sung, H., Bocchino, R. L., Adve, S. V., & Hart, J. C. (2010) · doi:10.5555/1921479.1921492 · Cited by 53
Parallel and I/O efficient set covering algorithms
Blelloch, G. E., Simhadri, H. V., & Tangwongsan, K. (2012) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/2312005.2312024 · Cited by 53
Self-citationPrabhu, P., Ghosh, S., Zhang, Y., Johnson, N. P., & August, D. I. (2011) · ACM SIGPLAN Notices · doi:10.1145/1993316.1993500 · Cited by 52
TRELLIS+: AN EFFECTIVE APPROACH FOR INDEXING GENOME-SCALE SEQUENCES USING SUFFIX TREES
Phoophakdee, B., & Zaki, M. J. (2007) · Pacific Symposium on Biocomputing (PSB) · doi:10.1142/9789812776136_0011 · Cited by 50
Lempel-Ziv Factorization: Simple, Fast, Practical
Kempa, D., & Puglisi, S. J. (2013) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972931.9 · Cited by 50
Counting triangles in real-world networks using projections
Tsourakakis, C. E. (2010) · Knowledge and Information Systems · doi:10.1007/s10115-010-0291-2 · Cited by 49
Parallel algorithms for generating random permutations on a shared memory machine
Anderson, R. (1990) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/97444.97674 · Cited by 49
Kuper, L., Turon, A., Krishnaswami, N. R., & Newton, R. R. (2014) · Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages · doi:10.1145/2535838.2535842 · Cited by 46
Deterministic parallel random-number generation for dynamic-multithreading platforms
Leiserson, C. E., Schardl, T. B., & Sukha, J. (2012) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2145816.2145841 · Cited by 45
Exploiting compression opportunities to improve SpMxV performance on shared memory systems
Kourtis, K., Goumas, G., & Koziris, N. (2010) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/1880037.1880041 · Cited by 44
Sampled Longest Common Prefix Array
Sirén, J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13509-5_21 · Cited by 41
Hybrid algorithms for list ranking and graph connected components
Banerjee, D. S., & Kothapalli, K. (2011) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.1109/hipc.2011.6152655 · Cited by 40
Space Efficient Wavelet Tree Construction
Claude, F., Nicholson, P. K., & Seco, D. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-24583-1_19 · Cited by 40
Distributed search based on self-indexed compressed text
Arroyuelo, D., Gil-Costa, V., González, S., Marín, M., & Oyarzún, M. (2011) · Information Processing & Management · doi:10.1016/j.ipm.2011.01.008 · Cited by 35
Deterministic galois: on-demand, portable and parameterless
Nguyen, D. D., Lenharth, A., & Pingali, K. K. (2014) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/2541940.2541964 · Cited by 35
LCP Array Construction in External Memory
Kärkkäinen, J., & Kempa, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07959-2_35 · Cited by 35
Randomized permutations in a coarse grained parallel environment
Gustedt, J. (2003) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/777412.777454 · Cited by 29
Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel
Shun, J., Gu, Y., Blelloch, G. E., Fineman, J. T., & Gibbons, P. B. (2015) · Cited by 24
Self-citationTaming the parallel effect zoo
Kuper, L., Todd, A., Tobin-Hochstadt, S., & Newton, R. R. (2014) · Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2594291.2594312 · Cited by 19
An Empirical Analysis of Parallel Random Permutation Algorithms on SMPs
Cong, G., & Bader, D. A. (2006) · SMARTech Repository (Georgia Institute of Technology) · Cited by 12
Program-Centric Cost Models for Locality and Parallelism
Simhadri, H. V. (2013) · Cited by 9
Cited by
Apache Spark: A unified engine for big data processing
Zaharia, M., Xin, R. S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M. J., et al. (2016) · Communications of the ACM · doi:10.1145/2934664 · Cited by 2,757
X-Stream: edge-centric graph processing using streaming partitions
Roy, A., Mihailovic, I., & Zwaenepoel, W. (2013) · Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles · doi:10.1145/2517349.2522740 · Cited by 673
A lightweight infrastructure for graph analytics
Nguyen, D., Lenharth, A., & Pingali, K. (2013) · Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles · doi:10.1145/2517349.2522739 · Cited by 579
Gunrock: a high-performance graph processing library on the GPU
Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., & Owens, J. D. (2016) · Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/2851141.2851145 · Cited by 338
Processing data where it makes sense: Enabling in-memory computation
Mutlu, O., Ghose, S., Gómez-Luna, J., & Ausavarungnirun, R. (2019) · Microprocessors and Microsystems · doi:10.1016/j.micpro.2019.01.009 · Cited by 300
Metadata
- Authors
- Shun, J., & Blelloch, G. E.
- Venue
- Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming
- Publisher
- ACM
- Published
- 2013-02-23
- Pages
- 135-146
- OpenAlex
- W2000041758
- Cited by
- 798
- References
- 162
- FWCI
- 30.72
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.