PaperlayerView exact revision on arXiv

Source-linked AI summary

Intelligent Edge Computing

Kalgi Gandhi, Minal Bhise

arXiv:2609.00181v1cs.DBcs.AI

TL;DR

Edge devices face constrained processing, memory, and bandwidth, while CI-HJ can scan unnecessary cachelines and adapt poorly to real-time workloads. WACI-HJ predicts workloads, builds workload-aware bins before queries arrive, and processes relevant WACIs. On benchmark and Smart Transportation data, it improves cacheline reads, query execution time, and measured resource utilization.

  • Problem

    Edge query processing must manage limited processing power, memory, and bandwidth, while CI-HJ scans unnecessary data and adapts poorly to real-time requirements.

  • Method

    WACI-HJ predicts future query workloads and uses them to construct workload-aware bins and Column Imprints before query execution.

  • Results

    54% improvement in PCR and 10% improvement in QET were reported, alongside 1% CPU, 38% RAM, and 49% I/O gains.

  • Takeaways & Limitations

    WACI-HJ enhances real-time traffic analysis, congestion management, and intelligent routing in smart transportation and can accelerate edge query processing in other domains.

  • Takeaways & Limitations

    The authors identify dynamic resource allocation, multi-attribute Column Imprints, and RDF data types as future directions.

Abstract

from arXiv · show

The number of edge devices in large-scale edge systems is rapidly increasing. Edge devices have limited processing power, memory, and network bandwidth, making resource utilization and data management during edge query processing challenging. Joins are among the costliest database operations in terms of time and resources. The State-of-the-Art edge query processing, Column Imprint-Hash Join CI-HJ, addresses this challenge using equi-height binning to accelerate hash joins. However, it lacks efficiency in real-time processing and scans unnecessary cachelines. This paper presents Workload Aware Column Imprint-Hash Join WACI-HJ, which uses a workload-aware approach to accelerate hash joins. Predicting the upcoming query workload in advance further improves its suitability for real-time edge query processing. WACI-HJ comprises two phases: WACI-HJ Generation Phase, including Pre-processing, Prediction, and Blocking and Hashing modules to compute bins based on the predicted workload before query arrival, and Query Processing and Resource Utilization, which handles query processing and CPU, RAM, and I/O utilization. Evaluations on a benchmark dataset and a real-world Smart Transportation dataset show a 54% reduction in cachelines read and 10% improved query execution time. The proposed technique is effective for both scaled and skewed data. Although PCR is an indirect measure of energy consumption, the work also directly measures energy consumption through energy-efficiency experiments. WACI-HJ shows 1%, 38%, and 49% gain in CPU, RAM, and I/O, respectively. Optimizing cache usage and query execution speeds up real-time traffic analysis, congestion management, and routing in Smart Transportation. Additionally, this technology can be applied to other domains to accelerate edge query processing.

1. Introduction

Edge computing brings storage and processing near data sources to reduce latency and bandwidth, but growing data and resource constraints make efficient edge query processing necessary. The paper proposes WACI-HJ to accelerate real-time edge queries while monitoring resource utilization.

  • Edge computing processes data near its source, reducing latency and bandwidth by sending structured or relevant data to the cloud.
  • Growing IoT device and data volumes intensify the need for efficient edge transmission, storage, and data management.
  • WACI-HJ uses workload-aware Column Imprints and predicted workloads to accelerate hash joins in resource-constrained edge systems.
  • The work monitors CPU, RAM, and I/O utilization to assess energy-efficiency and effectiveness during edge query processing.
  • WACI-HJ is evaluated on TPC-H, TPC-D, and MARTA datasets and is reported to work with scaled and skewed data.
  • WACI-HJ outperforms CI-HJ on key evaluation metrics while targeting lower latency, improved energy-efficiency, and optimized data access.

2. Literature Survey

The literature identifies latency, resource management, energy-efficiency, and AI integration as open edge-computing challenges. Existing CI-HJ accelerates joins but can scan unnecessary data and does not adapt effectively to real-time workloads.

  • Edge query processing reduces cloud transmission and latency, but limited processing power, memory, and bandwidth constrain local execution.
  • Hash joins are important for resource-constrained edge systems because hash-table construction requires only one table to be fully stored in memory.
  • CI-HJ precomputes Column Imprints for joined tables to reduce scanned and compared data during hash joins.
  • CI-HJ remains limited by its data-aware approach, which causes unnecessary scans and weak adaptation to real-time query-processing requirements.
  • Open research issues include latency reduction, resource management, energy-efficiency, and AI integration for improving edge performance.
  • The proposed direction combines workload awareness, prediction, and cacheline-focused processing to reduce unnecessary data access and improve resource use.

3. Proposed Technique: Workload Aware Column Imprints-Hash Join (WACI-HJ)

WACI-HJ adapts Column Imprint construction to predicted query workloads rather than relying on equi-height binning alone. It assigns workload-informed bins and imprint vectors to focus hash-join scans on relevant cachelines.

  • WACI-HJ incorporates workload information into binning for hash joins in large-scale edge systems.
  • Unlike equi-height binning, WACI-HJ bases bins on query requirements and frequencies.
  • The method precomputes Column Imprints for each table and generates probe-column imprint vectors for cachelines.
  • Workload-aware bins highlight relevant cachelines and aim to reduce cache misses and unnecessary scans during hash joins.

3.1. WACI-HJ Storage and System Architecture

WACI-HJ uses a compact architecture for resource-constrained edge applications. Its generation phase prepares workload-informed bins before query arrival, while query processing scans the resulting WACIs and monitors CPU, RAM, and I/O.

  • WACI-HJ storage uses a compact, lightweight design tailored to resource-constrained edge applications.
  • The storage workflow accepts data, queries, and query workload as inputs, hashes data, and generates data blocks using WACI.
  • When a query arrives, processing scans WACIs for relevant tuples while monitoring CPU, RAM, and I/O utilization.
  • WACI-HJ comprises Generation and Query Processing and Resource Utilization phases.
  • Generation includes Pre-processing, Prediction, and Blocking and Hashing modules that compute bins from predicted workload before query arrival.

3.2. WACI-HJ Phases

WACI-HJ separates pre-query generation from query execution and resource monitoring. Its generation phase forecasts workload and builds workload-aware structures, while the second phase processes queries and tracks utilization.

  • Phases: WACI-HJ has two phases: generation, followed by query processing and resource utilization.The first phase builds the structure; the second executes queries and monitors system resources.
  • Phase I: WACI-HJ Generation: The generation phase preprocesses data, predicts future query ranges, and organizes data through blocking and hashing.These three modules produce the workload-aware hash-join structure before query processing.
  • Phase II: Query Processing and Resource Utilization: During query processing, the system updates workload structures when required and fetches only necessary cachelines from secondary memory.Relevant cachelines are scanned to generate query output, avoiding unnecessary data access.
  • Phase II: Query Processing and Resource Utilization: Resource utilization monitoring measures CPU, RAM, and I/O usage during WACI-HJ query execution.The framework links reduced cacheline processing, optimized data access, and predictive prefetching to resource-efficiency goals.

3.3. WACI-HJ Data Structures and Algorithm

The WACI-HJ data structures and algorithms use predicted workloads, query imprint vectors, and selective cacheline scanning to support edge query processing. The design also specifies resource monitoring and computational complexity.

  • Data Structures: The Query Workload List stores query frequency, while the Cluster-Range and Cluster-Frequency Tables organize ranges and weekly arrival frequencies.The Usage Matrix Basket records queries and their attributes.
  • WACI-HJ Generation Algorithm: The generation algorithm predicts query workloads before execution and builds a workload-aware hash table from tuples and queries.Its modules cover preprocessing, prediction, and WACI-HJ blocking and hashing.
  • Complexity: WACI-HJ generation has time complexity O(2x(n * t) *64) and space complexity O(n), while query processing has O(n*f) time and O(n*m) space complexity.Here, n denotes probe-column tuples, t data-type size, m query count, and f query frequency.
  • Query Processing Algorithm: Incoming queries create QueryVectors that identify required attributes and guide imprint-vector filtering against the WACI-HJ output.Bitwise filtering selects relevant bins and cachelines before producing query results.
  • Query Processing Algorithm: Selective filtering avoids unnecessary scans and reduces cacheline access during query processing.This is the stated mechanism for improving query-processing efficiency.
  • Resource Utilization: Resource utilization covers CPU, RAM, and I/O monitoring during query processing.The monitoring algorithm uses external tools and records utilization output for analysis.

3.4. Integrating WACI-HJ Phases

WACI-HJ integrates workload-aware generation with query-time processing and resource monitoring. It computes bins before query arrival, stores generated structures, fetches needed cachelines, and reports complexity trade-offs.

  • Phase I: WACI-HJ Generation: Phase I loads data, generates a Zipf-based queryset, and constructs a Usage Matrix to identify common attribute usage.The integrated workflow uses these inputs to prepare workload-aware structures.
  • Data Structures: Table 1 presents the WACI-HJ data structures used across the system modules.The supplied table caption identifies the table but does not specify its row or column encoding.
  • Phase II: Query Processing and Resource Utilization: Phase II updates workload and WACI-HJ output when needed, then brings necessary cachelines into main memory for query output.CPU, RAM, and I/O utilization are monitored during execution.
  • Complexity: WACI-HJ complexity is slightly higher than CI-HJ because of workload awareness and prediction capabilities.The reported complexities are O(nf.2x(nt)64) for time and O(n+ n*m) for space.

3.5. Technical Challenges

Implementing WACI-HJ requires workload prediction, workload-based bin allocation, cacheline-selection logic, and resource-monitoring integration. The algorithms operationalize these choices across generation, query processing, and utilization monitoring.

  • Workload Prediction: ARIMA was selected for workload prediction because the paper describes it as robust and accurate for time-series forecasting.The choice responds to variation in query complexity, data distribution, and dataset size.
  • WACI-HJ Generation: The generation algorithm builds a Usage Matrix, creates cluster-frequency structures, predicts workload, allocates bins, and computes bin borders.It then initializes imprint vectors for cachelines and marks bins associated with predicted workloads.
  • Blocking and Hashing: Blocking and hashing retain values whose bins occur in the predicted query workload.The algorithm hashes retained build-column values after checking their assigned bins.
  • Query Processing: Query processing generates a QueryVector, loads the predicted or existing WACI-HJ structure, and scans cachelines selected by imprint vectors and bin mappings.Matching hash values are stored in the query output.
  • Resource Utilization: Resource monitoring executes external commands, reads utilization output, filters records for each query, and writes the results to a specified path.The paper identifies top and iotop as tools integrated with WACI-HJ for CPU, RAM, and I/O assessment.

4. Implementation Details

The implementation uses C, MonetDB, Python, and Google Colab to build and predict WACI-HJ workloads, then evaluates performance across datasets, scales, skewness, and resource metrics.

  • Hardware and Software Setup: The system uses VS Code for C development, MonetDB as a column-store database, and Google Colab with Python 3.10 for prediction tasks.The operating environment is Ubuntu 20.04.6 LTS, with top and iotop monitoring resource usage.
  • System Implementation: The implementation block diagram combines preprocessing, prediction, blocking and hashing, followed by query processing and resource utilization.The generation modules use C and MonetDB, while workload prediction uses Python on Google Colab.
  • Experimental Design: The evaluation is organized into configuration, basic, scaling, skewness, and energy-efficiency experiments.The sets determine optimal parameters, test standard and enlarged datasets, vary skewness, and monitor CPU, RAM, and I/O usage.
  • Evaluation Parameters: The experiments vary bit size from 8 to 128 bits, data size from x to 10x, and skewness from 50% to 99%.Outputs include PCR, QET, and AET, while resource metrics cover CPU, RAM, and I/O efficiency.

5. Results and Discussions

Results show that WACI-HJ improves cacheline use and query execution over CI-HJ across benchmark, scaled, skewed, and MARTA workloads, with performance depending on configuration.

  • Evaluation Scope: The results cover CI-HJ and WACI-HJ, with and without workload prediction, across TPC-H, TPC-D, skewed TPC-H, and MARTA.MARTA lacks skewed-data experiments because a skewed version was unavailable.
  • Set 0: Configuration: 32-bit configuration minimizes WACI-HJ PCR by 2% to 9% and QET by 2% to 5% versus other bit sizes.For MARTA, two clusters scan approximately 1% fewer cachelines and improve QET by 1% to 3% over four or six clusters.
  • Set I: Basic Experiments: 50% fewer cachelines are scanned by WACI-HJ than CI-HJ for high-frequency MARTA queries, with workload prediction adding 4% improvement.The reduction is associated with lower RAM and I/O usage and reduced system latency.
  • Set I: Basic Experiments: 5% overall improvement is achieved by WACI-HJ over CI-HJ, with an additional 5% enhancement when workload prediction is integrated.The reported query-execution improvements are observed across queries with different numbers of joins.
  • Set II: Data Scaling Experiments: 45% to 51% PCR improvement is recorded as data scales from x to 10x, while WACI-HJ PCR remains constant with respect to data size.The scaled query-execution results are described as consistent when data size increases.
  • Set III: Varying Skewness Levels Experiments: WACI-HJ improves PCR by 5% to 50% over CI-HJ as skewness increases and becomes 2% to 10% faster at higher skewness levels.The evaluation uses TPC-D at skewness levels from 60% to 99%, with 50% representing uniform distribution.

5.5. Set IV: Energy-Efficiency Experiments

WACI-HJ improves resource utilization and query performance over CI-HJ by using predicted workload information to reduce unnecessary data access. The approach incurs prediction-related overhead but performs better for larger datasets and supports resource-constrained edge environments.

  • I/O Efficiency: 49% fewer I/O operations make WACI-HJ more efficient than CI-HJ in resource-constrained edge environments.The reduction is attributed to reading an effective number of cachelines.
  • Workload-Aware Design: WACI-HJ predicts upcoming workloads and creates bins accordingly to reduce cache misses and support real-time query processing.Its workload-aware design avoids scanning unnecessary cachelines and manages skewed data.
  • Quantitative Comparison: 54% PCR enhancement and a 10-second QET reduction are reported for WACI-HJ on the MARTA dataset.WACI-HJ incurs a 2% AET increase because of prediction overhead.
  • CPU and RAM Utilization: 38% RAM utilization gain and 1% CPU utilization gain are observed for WACI-HJ compared with CI-HJ.The RAM improvement is associated with the optimal number of cachelines read, while CPU improvement is reported as marginal.
  • Energy-Efficiency Comparison: WACI-HJ requires 18% fewer I/O scans on TPC-H and 49% fewer on MARTA than CI-HJ.The comparison evaluates energy efficiency through resource usage.

6. Conclusions and Future Work

WACI-HJ improves edge query processing by combining workload awareness and predictive data-storage optimization. Experiments report lower cacheline reads and query execution time, with gains in CPU, RAM, and I/O utilization.

  • WACI-HJ improves upon CI-HJ through workload-aware strategies and predictive data-storage optimization before queries arrive.
  • WACI-HJ significantly reduces PCR and QET compared with CI-HJ in experimental evaluations.
  • 54% improvement in PCR and 10% improvement in QET were achieved on a real-world Smart Transportation dataset.
  • Resource-utilization gains were 1% in CPU, 38% in RAM, and 49% in I/O.PCR is an indirect measure of energy consumption, while energy-efficiency experiments measure energy consumption directly.
  • By optimizing data access patterns and incorporating predictive capabilities, WACI-HJ reduces query latency and conserves energy resources.
  • Minimizing cacheline reads and optimizing query execution enhances real-time traffic analysis, congestion management, and intelligent routing in smart transportation systems.The technology is also described as applicable to other domains for accelerating edge query processing.
  • Future directions include dynamic resource allocation, multi-attribute column imprints, and integration of RDF data types.
Loading 2609.00181v1…