A computational framework designed to recover missing fine particulate matter measurements in Internet of Things sensor networks achieves superior estimation precision and substantially lower processing latency than conventional matrix retrieval baselines, according to a study published in the Journal of Cloud Computing. Developed by researchers Fang Liu and Hamidreza Rabiee, the algorithm, designated PMLSH, applies locality-sensitive hashing principles to high-dimensional environmental monitoring records to estimate absent pollutant readings without exhaustive pairwise comparisons. By transforming continuous temporal sequences into compact Boolean index codes, the proposed system identifies structurally similar monitoring entries across distributed sensor deployments. In benchmark evaluations conducted across varying matrix dimensions and missing-data conditions, the method systematically outperformed item-based collaborative filtering, clustering, and random walk algorithms in both mean absolute error and execution time.
Continuous monitoring of fine particulate matter with aerodynamic diameters of 2.5 micrometers or smaller represents a critical component of municipal air-quality administration and healthcare-oriented smart facilities. Because elevated concentrations of fine particulates stay suspended in urban atmospheres for extended durations and present documented hazards to respiratory and cardiovascular health, reliable sensing streams are essential for exposure control, automated air purification, and early public health advisories. Nevertheless, municipal Internet of Things infrastructures routinely suffer from data loss caused by hardware malfunctions, depleted battery supplies, intermittent wireless transmission channels, and scheduled device maintenance. When environmental agencies and automated building management systems receive sparse or fragmented monitoring streams, downstream analytical models lose diagnostic fidelity, impairing timely intervention for vulnerable demographic groups including children, elderly citizens, and patients with chronic respiratory or cardiovascular conditions.
Within the scope of the investigation, the authors explicitly defined particulate matter prediction as the estimation and imputation of unobserved elements situated within a partially observed historical data matrix, distinguishing the task from conventional forward-looking time-series forecasting. While standard forecasting tools seek to predict atmospheric pollutant concentrations across future hours or days, missing-value imputation addresses internal record voids created during past monitoring intervals. Existing literature in environmental data analysis has largely focused on complex deep-learning architectures, empirical mode decomposition, sparse attention mechanisms, and recurrent neural networks to optimize forward-looking prediction accuracy. However, such neural approaches often introduce substantial parameter volumes, intensive training demands, and high inference latencies that complicate real-time execution across distributed or resource-constrained edge computing hardware.
To overcome the computational bottlenecks associated with conventional similarity-based missing-value imputation, PMLSH leverages locality-sensitive hashing to achieve sub-linear approximate nearest neighbor retrieval. In standard nearest-neighbor algorithms, evaluating an incomplete target entry requires computing distance metrics against every candidate row in an extensive database, yielding an execution cost that scales linearly with the product of entry counts and temporal dimensions. PMLSH alters this process by projecting high-dimensional monitoring records into compact hash buckets where similar entries collide with high mathematical probability. Rather than executing exhaustive distance calculations across the entire dataset, the retrieval mechanism restricts candidate search strictly to items sharing hash codes within identical buckets, drastically trimming computational overhead while preserving high retrieval fidelity.
The system is architected for partitioned deployment across a collaborative cloud-edge infrastructure to align with practical Internet of Things constraints. Individual sensing nodes are deliberately unburdened by algorithmic execution; their role is limited to logging periodic concentration values, flagging unavailable sensor observations, and streaming operational data to local edge gateways. The centralized cloud infrastructure maintains the complete global city-time matrix and executes computationally heavier offline indexing, including the generation of random projection vectors and the periodic construction or refreshing of multiple hash tables. These projection parameters and index tables are subsequently synchronized to edge gateways. When a local sensor gap occurs, the edge gateway maps the incomplete entry into the corresponding hash buckets, gathers candidate neighbors from local cache, and computes the estimated value, querying the central cloud only if a required bucket index is absent locally.
The mathematical operation of PMLSH proceeds through three sequential phases, beginning with entry index generation across an m-by-n city-time particulate matrix where m represents the number of sampled station-hour records and n denotes the total number of discrete weekly time slots. Prior to generating hash indices, unobserved elements within each incomplete entry vector are temporarily populated with the arithmetic mean of that specific entry’s observed readings. These temporary values are strictly confined to the random projection process to maintain vector geometry and are excluded from final prediction calculations. Using an n-dimensional projection vector whose components are drawn randomly from a uniform distribution bounded between negative one and positive one, the algorithm calculates an inner product with the completed entry. The resulting continuous scalar is converted via thresholding into a single Boolean bit, producing a value of one for positive numbers and zero otherwise.
To mitigate the inherent stochastic variance of single random projections, the algorithm repeats the projection process alpha times, transforming each n-dimensional monitoring record into an alpha-bit Boolean index vector. Because alpha is selected to be much smaller than the original temporal dimension n, this mapping achieves dramatic dimensional compression. To prevent erroneous dismissals or false associations between neighboring entries, the architecture constructs beta independent hash tables, each populated by a separate set of alpha random projection vectors. In the second operational stage, two separate entries are classified as candidate neighbors if their Boolean indices match exactly within at least one of the beta hash tables. In the third phase, the missing concentration value of the target record is estimated by taking the unweighted arithmetic mean of the observed readings at that same time slot across all retrieved candidate neighbors.
Theoretical complexity evaluations demonstrate substantial computational advantages for PMLSH over classical exhaustive search frameworks. Offline index construction performed by cloud infrastructure requires a time complexity of O(beta * alpha * m * n), an overhead incurred prior to online query handling that avoids routine full-scale recalculations. In the online recovery stage, querying the beta precomputed hash tables incurs a constant-factor lookup cost of O(beta), while aggregating the retrieved candidate neighbors requires O(s) operations, where s represents the average candidate subset size. Because beta and s are orders of magnitude smaller than the full dataset size m, online latency scales as O(beta + s), offering a marked reduction compared to the O(m * n) per-missing-value cost demanded by exhaustive comparisons. The total space complexity of O(m * n + beta * m * alpha) introduces only modest memory overhead because alpha and beta remain small fixed constants.
The empirical validation was conducted using the public Urban-Air repository compiled by Microsoft Research, comprising hourly atmospheric measurements gathered from 437 monitoring stations situated across 43 Chinese cities between May 2014 and April 2015. To construct consistent experimental inputs, researchers extracted 8,736 continuous hourly observations representing 52 complete consecutive weeks, formatting the data into 52-dimensional entry vectors indexed by station identifier and within-week hour. Candidate matrices were formed with entry sizes m ranging from 1,000 to 5,000 sampled station-hour rows while maintaining the time slot count n fixed at 52. Testing was performed using Python 3.7 on a workstation equipped with an AMD Ryzen 7 5800H central processor running at 3.20 GHz, an NVIDIA GeForce RTX 3060 Laptop graphics processing unit, and 16 gigabytes of system memory under Windows 11. To evaluate estimation robustness, artificial missing masks between 10 percent and 50 percent were applied across 100 repeated trials, and accuracy was quantified via mean absolute error measured in micrograms per cubic meter.
Experimental outcomes demonstrated that PMLSH consistently achieved superior estimation accuracy and faster processing speeds compared to item-based collaborative filtering, clustering, and random walk baselines across all evaluated matrix dimensions. Under baseline conditions with m set to 5,000 entries and a 10 percent missing rate, PMLSH yielded a mean absolute error of 5.0 micrograms per cubic meter. When the missing data proportion escalated to 50 percent, the mean absolute error of PMLSH rose moderately to 8.3 micrograms per cubic meter. In contrast, under identical 50 percent data scarcity, item-based collaborative filtering degraded to 13.4 micrograms per cubic meter, clustering error expanded to 26.8 micrograms per cubic meter, and the random walk technique reached 29.1 micrograms per cubic meter. Across all five tested missing-rate increments, PMLSH posted an overall average error of 6.36 micrograms per cubic meter, outperforming collaborative filtering by 42.0 percent, clustering by 73.1 percent, and random walk estimation by 75.0 percent.
Ablation experiments investigating hyperparameter configurations confirmed that the hash bit count alpha and table count beta govern distinct operational trade-offs between neighborhood selectivity, computational time, and estimation error. Increasing alpha tightens the collision criteria, shrinking candidate group sizes, accelerating online execution, and improving neighbor similarity, with accuracy plateauing once alpha reaches approximately 10. Conversely, expanding beta widens candidate discovery across supplementary hash tables, raising neighbor counts and computational runtimes while risking the inclusion of less correlated records that slightly degrade accuracy. Setting both alpha and beta to 10 established an optimal empirical balance between speed and precision, maintaining low runtime growth as matrix row counts expanded from 1,000 to 5,000. While the authors noted that larger-scale empirical validation, meteorological feature integration, and downstream clinical assessments remain subjects for future inquiry, the current architecture offers an efficient, mathematically grounded mechanism for preserving continuity in healthcare-oriented environmental sensing systems.
Subject of Research: Locality-sensitive hashing for estimating missing PM2.5 monitoring data in IoT smart environments
Article Title: Efficient PM2.5 prediction for healthcare-oriented IoT-enabled smart environments
Article References: Liu, F., & Rabiee, H. (2026). Efficient PM2.5 prediction for healthcare-oriented IoT-enabled smart environments. Journal of Cloud Computing, 15(1), Article 152. https://doi.org/10.1186/s13677-026-00969-4
Image Credits: AI Generated
DOI: 10.1186/s13677-026-00969-4
Keywords: PM2.5 monitoring, locality-sensitive hashing, IoT smart environments, missing value estimation, environmental sensing, data imputation, cloud-edge computing, Urban-Air dataset, air quality management, mean absolute error, collaborative filtering, particulate matter, sensor failure recovery, approximate nearest neighbor, edge gateways, public health decision support
News Source: Russell Cooper. (November 20, 2026). Locality Sensitive Hashing Accurately Estimates Missing Urban Air Quality Sensor Records. Scienmag.



