Scaling Graph Query Processing: Focused Exploration on Partitions Using Load Balancing

I. MOTIVATION

• Graphs growing beyond main memory or a single processor create significant challenges for query processing; partitioning must preserve complete and sound answers across partitions.The problem also includes expressive query specification, partitioning, distributed processing, and establishing correctness.Source: §I · p. 1

A. Why Distributed Processing?

• Hadoop Map/Reduce supplies distributed execution, while partition sizes and loading heuristics can be matched to available processing resources.The paper prioritizes scalable query processing rather than absolute response time and describes its framework choice as neutral to that focus.Source: A. Why Distributed Processing? · pp. 1–2, §I · p. 1

B. Choice of Data Sets

• The approach targets directed, undirected, and labeled graphs; supports comparison, range, wildcard, and Boolean operators; and combines variable-size partitioning, distributed querying, and partition-loading heuristics.IMDb and DBLP allow query results to be checked against database versions; the paper also reports experiments on real-world and synthetic data sets.Source: B. Choice of Data Sets · p. 2

II. RELATED WORK

• SPARQL [15] queries RDF graphs primarily through triple-pattern matching with simple constraints on query nodes and edges.RDF represents information as directed, labeled graphs described by triples.Source: §II · p. 2
• Cypher [16], Neo4j’s property-graph language, expresses queries as pictorial node-and-edge patterns, while structured queries require experience with the language and data model.The paper distinguishes its query-as-a-graph approach from subgraph enumeration, which does not address the same evaluation problem.Source: §II · p. 2
• The approach aims to find all or k exact matches in very large graphs, supports expressive queries without limits on query entities or labels, and can incorporate query relaxation.It extends earlier partitioned non-Map/Reduce work,, with a different scalability paradigm and query heuristics.Source: §II · p. 2

III. LARGE GRAPH QUERY PROCESSING CHALLENGES

• Variable-size partitions are needed because existing approaches typically make multiple passes or produce equal-sized partitions, limiting their ability to match heterogeneous processing resources.The paper identifies variability in Map/Reduce resources as a practical reason for matching partition sizes to processing capabilities.Source: §III · p. 3
• Range partitioning assigns contiguous vertex-id ranges to partitions; one example places IDs 1–3 in partition 1 and IDs 4–8 in partition 2.It uses one input pass and Map/Reduce once; the cost is amortized over queries, and range information helps route partial answers to the partition holding a node’s adjacency list.Source: §III · p. 3
• Correct query processing must handle answers contained within one partition, spanning multiple partitions, or returning to a previously processed partition.The section also identifies overlapping answers, where a vertex or edge belongs to multiple answer instances and must be returned separately.Source: Figure 2 · p. 3, §III · p. 3
• In multi-path plans, repeated query labels can make a continuation node expand along the wrong query edge unless the system tracks its query-plan position.Independent one-edge-at-a-time expansion can also generate duplicate instances, which the paper removes using canonical representations.Source: §III · p. 4

IV. QUERY PROCESSING APPROACH AND ITS CORRECTNESS

• For a given k, heuristics select the best k partitions to process in parallel during each iteration of query-plan evaluation.The parameter k represents available resources, identified in the paper as Mappers.Source: §IV · p. 4
• Query expansion follows the query plan one edge at a time; partial answers are routed to partitions holding the next query edges until complete answers are formed.Partitions may be loaded again when an answer returns to one already processed.Source: §IV · p. 4
• Canonical forms identify duplicate expansions using vertex IDs and connectivity, including node labels and edge direction and labels when present.The ordering uses edge labels first, then source and destination vertex labels, and finally vertex IDs when earlier values match.Source: §IV · p. 4
• When a partial answer continues across partitions in a multi-path plan, the system marks the continuing node with its unique query-plan node ID to select the correct next edge.The example continues node (14:4, B) using query edge (14, B) → (15, D).Source: §IV · p. 5

A. Input Query and Plan Representations

• Queries are graph inputs with labels, wild cards, Boolean conditions, BETWEEN, and AND/OR specifications, converted into root-based query plans for constrained answer expansion.OR combines results from two plans; the described examples use plans without wild cards as root or top-level nodes.Source: A. Input Query and Plan Representations · p. 5

B. Correctness of the Proposed Approach

• Correctness is operationally supported by MIF partition tracking, routing marked intermediate results to the right partition, and systematic continuation from the last visited node.The authors also report empirical checks using embedded graphs with known frequencies and structures, though those results are omitted for space.Source: B. Correctness of the Proposed Approach · p. 5

V. MAP/REDUCE ARCHITECTURE FOR PARTITIONING AND QUERY PROCESSING

• The Map/Reduce architecture range-partitions the graph, generates MIF metadata, selects up to k partitions using heuristics, and iterates query expansion until no eligible partitions remain.The processor writes complete answers to a final file and intermediate answers to relevant partition files for further expansion.Source: §V · pp. 5–7

A. Range Partitioning using Map/Reduce

• The mapper emits each input edge under both endpoint vertex IDs, and the range-based partitioner routes keys in the same range to the same reducer.The shuffle groups records with matching vertex IDs before reducer processing.Source: A. Range Partitioning using Map/Reduce · p. 7
• Each reducer writes initial vertex substructures to a graph partition and emits each vertex’s adjacency list into an adjacency-list partition.The reducer receives a vertex ID and its adjacent edges after grouping.Source: A. Range Partitioning using Map/Reduce · p. 7
• Reducers record matching query-plan start and intermediate nodes in local MIF metadata, then use union-find over partition edges to count connected components.The driver collects the local MIFs into a global MIF.Source: A. Range Partitioning using Map/Reduce · p. 7

• Mappers load a partition and query plan, then expand initial or partial answer instances edge by edge using the plan.Expansion follows matching adjacency-list edges; canonical instances are stored to remove duplicates.Source: Figure 11 · p. 7, B. Query Processing using Map/Reduce · p. 8
• When expansion crosses a partition boundary, the mapper emits the partial answer keyed by the destination partition for later processing.The relative query-node marker guides continuation when that partial answer is expanded.Source: B. Query Processing using Map/Reduce · p. 8
• After the shuffle groups mapper outputs by partition ID, reducers update the MIF and write partial answers into the corresponding graph partition.Mappers write completed answers to the Final All Answers file.Source: B. Query Processing using Map/Reduce · p. 8

VI. HEURISTICS FOR SCHEDULING PARTITIONS

• Heuristics use metadata to select partitions for each iteration and reduce the total number loaded while answering a query.The paper says this scheduling approach is validated experimentally.Source: §VI · p. 8

A. Heuristics Derived From Meta Information:

• The authors compare individual and composed heuristics, combining metrics because no single metric captures partition characteristics.Random partition loading serves as the baseline.Source: A. Heuristics Derived From Meta… · pp. 8–9
• SN CC prioritizes partitions with more start nodes and fewer connected components, while SN CC2k selects the k least-connected partitions from the top 2k by start-node count.SN CC uses connected components to dampen the start-node score.Source: A. Heuristics Derived From Meta… · p. 9
• SN IN combines start-node and intermediate-node counts, prioritizing start nodes while lowering priority as intermediate-node counts grow.Partitions with many intermediate nodes relative to start nodes may contain more partial answers and be needed repeatedly.Source: A. Heuristics Derived From Meta… · p. 9

• Experiments run Java with Hadoop on the Comet cluster, whose nodes have 24 cores and 128 GB of memory.The cluster has 1,944 nodes.Source: §VII · p. 9
• The largest DBLP graph contains more than 3 million nodes and 13 million edges, alongside IMDb and synthetic graph datasets.The DBLP graph represents authors, papers, conferences, and years; IMDb represents movie-related entities.Source: Table V · p. 9
• Correctness is checked against QP-Subdue using synthetic graphs with embedded subgraphs and smaller DBLP and IMDb graphs.QP-Subdue is a non-partitioned, main-memory graph query processor that cannot handle larger graph sizes.Source: §VII · p. 10
• DBLP and IMDb queries cover comparison operators, wildcards, range queries, AND and OR, and combinations of logical and comparison operators.The query set includes operators such as > and NOT.Source: §VII · p. 10

• 52% response-time improvement begins for DBLP Q1 and continues through 64 partitions, then tapers; DBLP Q3 improves significantly even at 120 partitions.Similar speedups are reported for the IMDb OR and combination queries.Source: A. Results of Partitioned Graph Querying · p. 10
• With mapper count fixed, increasing partitions processed per iteration raises response time only slightly; increasing mapper count lowers response time, though shuffle time rises at 32 mappers.The authors recommend matching partitions per iteration to available mappers when possible.Source: A. Results of Partitioned Graph Querying · p. 10
• For the DBLP wildcard and IMDb combination queries, SN CC2k, SN CC, and SN IN are the best execution-time heuristics, while RANDOM and individual metrics are worst.The composed heuristics perform better than the individual heuristics in these comparisons.Source: A. Results of Partitioned Graph Querying · p. 10

B. Load Factor Analysis

• Load Factor measures query-processing efficiency by comparing the iterations used with the ideal number of required iterations.The ideal number of iterations is reached when only required partitions are loaded.Source: B. Load Factor Analysis · p. 10
• A load factor closer to 1 indicates better scheduling, with fewer repeated partition loads.When heuristics load the required partitions plus different numbers of additional partitions, the heuristic loading fewer is considered better.Source: B. Load Factor Analysis · p. 11
• Across DBLP and IMDb queries and every tested k, SN CC, SN IN, and SN CC2k are the top three heuristics by load factor.For the DBLP BETWEEN query at k = 1, SN CC has the lowest load factor; RANDOM has the highest.Source: B. Load Factor Analysis · p. 11

VIII. CONCLUSIONS

• The proposed Hadoop Map/Reduce approach correctly computes answers for different graph query types, including queries with wildcards.The paper reports operational correctness and experimental validation on large real-world and synthetic datasets.Source: §VIII · p. 12
• Future work includes adding cost-based optimizations and developing graph partitioning and parallel processing for workloads of multiple queries.The paper also identifies investigating whether partitioning changes matter for multiple-query workloads.Source: §VIII · p. 12