Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions

No abstract is available for this paper.

• Publication year

  2014

• Venue

  Proceedings of the VLDB Endowment

• Publication date

  2014-11-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.14778/2735508.2735518
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• SIMD compression and the intersection of sorted integers

  2014influential reference
• Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units

  2011cited by this paper
• Fast Sorted-Set Intersection using SIMD Instructions

  2011influential reference
• Fast Set Intersection in Memory

  2011influential reference
• Improving the Performance of List Intersection

  2009cited by this paper
• On efficient posting list intersection with multicore processors

  2009cited by this paper
• Efficient implementation of sorting on multi-core SIMD CPU architecture

  2008cited by this paper
• AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors

  2007cited by this paper
• Fast Evaluation of Union-Intersection Expressions

  2007cited by this paper
• Intersection in Integer Inverted Indices

  2007cited by this paper
• Experimental Analysis of a Fast Intersection Algorithm for Sorted Sequences

  2005influential reference
• A Fast Set Intersection Algorithm for Sorted Sequences

  2004cited by this paper
• Super Scalar Sample Sort

  2004cited by this paper
• Web Search for a Planet: The Google Cluster Architecture

  2003influential reference
• Implementing database operations using SIMD instructions

  2002cited by this paper
• Adaptive set intersections, unions, and differences

  2000cited by this paper
• Introspective Sorting and Selection Algorithms

  1997cited by this paper
• Conversion of control dependence to data dependence

  1983cited by this paper
• An Almost Optimal Algorithm for Unbounded Searching

  1976influential reference

• raxtax: a k-mer-based non-Bayesian taxonomic classifier

  2025cites this paper
• Columnar Formatted Inverted Index for Highly-Paralleled, Vectorized Query Processing

  2025cites this paper
• A powerful reducing framework for accelerating set intersections over graphs

  2024cites this paper
• BigSet: An Efficient Set Intersection Approach

  2024cites this paper
• Differentiating Set Intersections in Maximal Clique Enumeration by Function and Subproblem Size

  2024cites this paper
• Service Recovery in NFV-Enabled Networks: Algorithm Design and Analysis

  2024cites this paper
• HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs

  2024cites this paper
• An Index for Set Intersection With Post-Filtering

  2024cites this paper
• Maximal Clique Enumeration with Hybrid Branching and Early Termination

  2024cites this paper
• DGL: Device Generic Latency Model for Neural Architecture Search on Mobile Devices

  2024cites this paper
• Co-Utilizing SIMD and Scalar to Accelerate the Data Analytics Workloads

  2023cites this paper
• HGMatch: A Match-by-Hyperedge Framework for Efficient and Parallel Subhypergraph Matching (Complete Version)

  2023cites this paper
• HGMatch: A Match-by-Hyperedge Approach for Subgraph Matching on Hypergraphs

  2023cites this paper
• JITSPMM: Just-in-Time Instruction Generation for Accelerated Sparse Matrix-Matrix Multiplication

  2023cites this paper
• A New Fast Intersection Algorithm for Sorted Lists on GPU

  2022influential citation
• A one-for-all and o(v log(v ))-cost solution for parallel merge style operations on sorted key-value arrays

  2022cites this paper
• Efficient $k-\text{clique}$ Listing with Set Intersection Speedup

  2022cites this paper
• <inline-formula><tex-math notation="LaTeX">$TC-Stream$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>T</mml:mi><mml:mi>C</mml:mi><mml:mo>-</mml:mo><mml:mi>S</mml:mi><mml:mi>t</mml:mi><mml:mi>r</mml:mi><mml:mi>e</mml:mi><mml:mi>a</mml:mi><mml:mi>m</mml:mi></mml:mrow></mml:math><inline-graphic x

  2022cites this paper
• FINGERS: exploiting fine-grained parallelism in graph mining accelerators

  2022cites this paper
• Efficient k-clique Listing with Set Intersection Speedup [Technical Report]

  2022influential citation
• Efficient Execution of Graph Algorithms on CPU with SIMD Extensions

  2021cites this paper
• Origami: A High-Performance Mergesort Framework

  2021influential citation
• Efficient and Scalable Graph Pattern Mining on GPUs

  2021cites this paper
• Accelerating Set Intersections over Graphs by Reducing-Merging

  2021cites this paper
• Filter Representation in Vectorized Query Execution

  2021cites this paper
• CIC-PIM: Trading spare computing power for memory space in graph processing

  2021cites this paper
• FESIA: A Fast and SIMD-Efficient Set Intersection Approach on Modern CPUs

  2020influential citation
• VIP: A SIMD vectorized analytical query engine

  2020cites this paper
• Manycore clique enumeration with fast set intersections

  2020cites this paper
• DSCAN: Distributed Structural Graph Clustering for Billion-Edge Graphs

  2020cites this paper
• Towards an Objective Metric for the Performance of Exact Triangle Count

  2020cites this paper
• Utilizing the column imprints to accelerate no‐partitioning hash joins in large‐scale edge systems

  2020cites this paper
• Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite

  2020cites this paper
• A Survey and Experimental Analysis of Distributed Subgraph Matching

  2019cites this paper
• Finding Mutual X at WeChat-Scale Social Network in Ten Minitues

  2019cites this paper
• Towards Practical Vectorized Analytical Query Engines

  2019cites this paper
• Most similar maximal clique query on large graphs

  2019cites this paper
• Interleaved Multi-Vectorizing

  2019cites this paper
• Learning Multi-Stage Sparsification for Maximum Clique Enumeration

  2019cites this paper
• Accelerating All-Edge Common Neighbor Counting on Three Processors

  2019influential citation
• On Efficient External-Memory Triangle Listing

  2019cites this paper
• An Efficient and Effective Index Structure for Query Evaluation in Search Engines

  2019cites this paper
• Distributed Subgraph Matching on Timely Dataflow

  2019cites this paper
• List Intersection for Web Search: Algorithms, Cost Models, and Optimizations

  2018influential citation
• Conflict-free vectorization of associative irregular applications with recent SIMD architectural advances

  2018cites this paper
• Parallelizing Pruning-based Graph Structural Clustering

  2018cites this paper
• Discovering $k$-Trusses in Large-Scale Networks

  2018cites this paper
• Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions

  2018influential citation
• SCAN-XP: Parallel Structural Graph Clustering Algorithm on Intel Xeon Phi Coprocessors

  2017cites this paper
• Triangle counting via vectorized set intersection

  2017cites this paper
• Application-specific architectures for energy-efficient database query processing and optimization

  2017cites this paper
• EmptyHeaded

  2017influential citation
• Software Optimizations of Multiple Sets Intersection via SIMD Instructions

  2017influential citation
• SIMD-Based Multiple Sets Intersection with Dual-Scale Search Algorithm

  2017influential citation
• PAM: parallel augmented maps

  2016cites this paper
• An efficient method to evaluate intersections on big data sets

  2016cites this paper
• Exploit Every Cycle: Vectorized Time Series Algorithms on Modern Commodity CPUs

  2016cites this paper
• On Efficient External-Memory Triangle Listing

  2016cites this paper
• A database accelerator for energy-efficient query processing and optimization

  2016cites this paper
• Processing and Optimizing Main Memory Spatial-Keyword Queries

  2015cites this paper
• Data Analytics in a Data- and Hardware-Conscious Way

  2015cites this paper
• EmptyHeaded: A Relational Engine for Graph Processing

  2015cites this paper
• EmptyHeaded: Boolean Algebra Based Graph Processing

  2015cites this paper
• Efficient Lightweight Compression Alongside Fast Scans

  2015cites this paper
• SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures

  2015cites this paper
• Input Generated Code Set Repres . Execution EngineQuery Compiler

  2015cites this paper
• Better bitmap performance with Roaring bitmaps

  2014cites this paper
• A Fast and Simple Approach to Merge Sorting using AVX-512

  year unknowncites this paper
• Excavator: Accelerating Graph Pattern Mining on FPGAs ∗

  year unknowncites this paper