检索结果-内蒙古大学图书馆

HPG-Tree: An Enhanced B+-Tree for Spatial Indexing

IEEE Access 2025年 13卷 91312-91324页

作者： Amal Saif Alaa M. Altarazi Amer Al-Badarneh Mohammad J. Abdel-Rahman Computer Science Department Princess Sumaya University for Technology Amman Jordan Data Science Department Princess Sumaya University for Technology Amman Jordan

In modern applications such as geographic information systems, game development, and image processing, the demand for efficient two-dimensional spatial indexing is rising exponentially. Traditional approaches like R-tree can suffer from excessive overlap and fragmentation, while standard $B^{+}$ -trees are limited to one-dimensional data. Motivated by these gaps, we propose the hyperbolic paraboloid grid (HPG) tree, an enhanced $B^{+}$ -tree structure specifically tailored for two-dimensional datasets. First, we employ a grid-based strategy that maps two-dimensional points into one-dimensional values without resorting to hashing. By combining grid partitioning with the $B^{+}$ -tree’s efficient, self-balancing properties, the HPG-tree simultaneously addresses overlap, storage utilization, and query performance. Unlike purely one-dimensional indexes, this method preserves spatial locality and avoids excessive rebalancing. Further, the HPG-tree integrates a hyperbolic paraboloid-like framework in its node layout, allowing it to halve the number of index nodes in many cases. This optimization is key to reducing disk or memory scans, thereby accelerating point lookups, range queries, and updates. Our experiments demonstrate that the HPG-tree outperforms comparable state-of-the-art structures like $R^{*}$ -tree, achieving up to a 50% improvement in storage utilization and significant gains in query throughput. HPG-tree opens a promising avenue for modern spatial databases that require both high scalability and sub-second response, making it a robust and flexible option for today’s evolving data-intensive environments. These advantages make HPG-tree particularly well-suited to large-scale spatial databases requiring both high scalability and sub-second responsiveness. Following a detailed discussion of the shortcomings in existing methods, the paper presents the HPG-tree methodology, including its grid partitioning, node layout, and insertion procedures, illustrating why

关键词： Indexing Spatial databases Spatial indexes Memory management Standards Nearest neighbor methods Vegetation Taxonomy partitioning algorithms Optimization

来源：评论

学校读者我要写书评

暂无评论

BaPa: A Novel Approach of Improving Load Balance in Parallel Matrix Factorization for Recommender Systems

引用

IEEE TRANSACTIONS ON COMPUTERS 2021年第5期70卷 789-802页

作者： Guo, Ruixin Zhang, Feng Wang, Lizhe Zhang, Wusheng Lei, Xinya Ranjan, Rajiv Zomaya, Albert Y. China Univ Geosci Sch Comp Sci Wuhan 430074 Peoples R China Tsinghua Univ Dept Comp Sci Beijing 100084 Peoples R China Univ Newcastle Sch Comp Newcastle Upon Tyne NE1 7RU Tyne & Wear England Univ Sydney Sch Comp Sci Camperdown NSW 2006 Australia

A simplified approach to accelerate matrix factorization of big data is to parallelize it. A commonly used method is to divide the matrix into multiple non-intersecting blocks and concurrently calculate them. This operation causes the Load balance problem, which significantly impacts parallel performance and is a big concern. A general belief is that the load balance across blocks is impossible by balancing rows and columns separately. We challenge the belief by proposing an approach of "Balanced partitioning (BaPa)". We demonstrate under what circumstance independently balancing rows and columns can lead to the balanced intersection of rows and columns, why, and how. We formally prove the feasibility of BaPa by observing the variance of rating numbers across blocks, and empirically validate its soundness by applying it to two standard parallel matrix factorization algorithms, DSGD and CCD++. Besides, we establish a mathematical model of "Imbalance Degree" to explain further why BaPa works well. BaPa is applied to synchronous parallel matrix factorization, but as a general load balance solution, it has significant application potential.

关键词： Matrix decomposition Task analysis partitioning algorithms Charge coupled devices Sparse matrices Recommender systems Computer science Matrix factorization stochastic gradient descent recommender systems parallel and distributed computing load balancing

来源：评论

学校读者我要写书评

暂无评论

Taxi Passenger Hot Spot Mining Based on a Refined K-Means plus plus Algorithm

引用

IEEE ACCESS 2021年 9卷 66587-66598页

作者： Wang, Yuanni Ren, Jiansi China Univ Geosci Sch Comp Sci Wuhan 430078 Peoples R China China Univ Geosci Hubei Key Lab Intelligent Geoinformat Proc Wuhan 430078 Peoples R China

With the development of information technology, it is possible to explore the spatial-temporal distribution characteristics of taxi travel demand by examining taxi GPS location data in order to master the actual supply and demand levels of different hot spots at different time periods. At present, in hot spot mining, the existing research on the clustering of passenger hot spots has some performance problems, such as insufficient clustering accuracy and high algorithm time complexity. The purpose of this paper is to propose a two-level subdivision concept and improve the K-means++ algorithm to finish the fine clustering of hot spots of taxi passengers. The first-level subdivision establishes a dynamic adjustable region with time and geographical range. In the second layer, a Gaussian mixture model is used for the data distribution statistics, and the optimal subdivision area number is determined according to the minimum principle of the Akaike information criterion and Bayesian information criterion. The SSE (sum of the square distance errors) is used to determine the optimal cluster number k for each local area. Finally, the K-means++ algorithm is used to complete the clustering of each local area. A week of green taxi data from New York City was used to validate the method and compare it to the traditional K-means and DBSCAN approaches. The proposed method achieved better accuracy with comparable time consumption. This demonstrated the value of the approach for hot spot data mining although clustering still has some important advantages. In addition, the hot spots in the morning peak and weekend are displayed visually, which is helpful to provide the guidance for urban transportation and planning.

关键词： Clustering algorithms Public transportation partitioning algorithms Data mining Clustering methods Global Positioning System Heuristic algorithms K-means plus clustering hot spot mining two-level subdivision Gaussian mixture model

来源：评论

学校读者我要写书评

暂无评论

Modeling Acceleration Properties for Flexible INTRA HEVC Complexity Control

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY 2021年第11期31卷 4454-4469页

作者： Huang, Yan Song, Li Xie, Rong Izquierdo, Ebroul Zhang, Wenjun Shanghai Jiao Tong Univ Inst Image Commun & Network Engn Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ AI Inst MoE Key Lab Artificial Intelligence Shanghai 200240 Peoples R China Queen Mary Univ London Multimedia & Vis Grp London E1 4NS England

It is a very well-known fact, that the high complexity of the High Efficiency Video Coding standard (HEVC) is the main hurdle for its wide deployment and use. To tackle this problem, a number of recent research outcomes exploit heuristic algorithms and machine learning, including deep learning, to reduce the coding complexity. However, in most cases, each encoder module, i.e., encoding process, is first accelerated individually, and then different acceleration algorithms are manually combined. Without a holistic strategy, the acceleration potential of multi-module combination is not exploited and the Rate-Distortion (RD) loss is generally not well controlled. To tackle these shortcomings, this paper exploits the acceleration properties of different modules, i.e., the numerical representation of potential time saving and possible RD loss, from which a heuristic model is explored. Then a Heuristic Model Oriented Framework (HMOF) is proposed which adapts the properties of modules to underlying acceleration algorithms. In the framework, two advanced acceleration algorithms, including Border Considered CNN (BC-CNN)-based Coding Unit (CU) partition and Naive Bayes-based Prediction Unit (PU) partition, are proposed for the CU and PU modules, respectively. Further, by leveraging the heuristic model as the guidance to combine the proposed acceleration algorithms, HMOF is globally optimized, where different time saving budgets are wisely allocated to different modules and a theoretically minimal RD loss is achieved. According to the experimental results, through fusing a suitable deep learning technique and a Bayes-Based prediction, the proposed acceleration framework HMOF enable multiple acceleration choices. Here the proposed joint optimization strategy help to make a choice leading to the best cost-performance. Furthermore, within the proposed framework, intra coding time can be precisely controlled with negligible Bjontegaard delta bit-rate (BDBR) loss. In this context, a

关键词： Acceleration Complexity theory Encoding Heuristic algorithms Prediction algorithms partitioning algorithms Machine learning algorithms Acceleration complexity control high efficiency video coding intra prediction convolutional neural network Naive Bayes

来源：评论

学校读者我要写书评

暂无评论

Interior point methods are not worse than Simplex 63

Interior point methods are not worse than Simplex

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Allamigeon, Xavier Dadush, Daniel Loho, Georg Natura, Bento Vegh, Laszlo A. Inria Ecole Polytech CNRS CMAPIP Paris Paris France Ctr Wiskunde & Informat Amsterdam Netherlands Univ Twente Enschede Netherlands London Sch Econ & Polit Sci London England

ISBN: (纸本)9781665455190

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2(n)n(1.5) log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most O(n(1.5) log n) times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the `max central path', a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths. From the existence of a line segment in the wide neighborhood we derive strong implications on the structure of the corresponding segment of the central path. Our algorithm is able to detect this structure from the local geometry at the current iterate, and constructs a step direction that descends along this segment. The bound O(n(1.5) log n) that applies for arbitrarily long line segments is derived from a combinatorial progress measure. Our algorithm falls into the family of layered least squares interior point methods introduced by Vavasis and Ye (Math. Prog. 1996). In contrast to previous layered least squares methods that partition the kernel of the constraint matrix into coordinate subspaces, our method creates layers based on a general subspace providing more flexibility. Our result

关键词： Geometry Computer science Upper bound Current measurement Linear programming Time measurement partitioning algorithms

来源：评论

学校读者我要写书评

暂无评论

Three Representations for Set Partitions

引用

IEEE ACCESS 2021年 9卷 34604-34625页

作者： Torres-Jimenez, Jose Lara-Alvarez, Carlos Cardenas-Castillo, Alfredo Blanco-Rocha, Roberto Puga-Sanchez, Oscar CINVESTAV Tamaulipas Ciudad Victoria 87130 Tamaulipas Mexico

The Set partitioning Problem (SPP) aims to obtain non-empty disjoint subsets of objects such that their union equals the whole set of objects, and the partition meets some prespecified criteria. The ubiquity of SPP is impressive, given that it has a lot of theoretical and practical motivations. In the theoretical side, the study of the SPP is closely related to Bell numbers, Stirling numbers of the second kind, integer partitions, Eulerian numbers, Restricted Growth Strings (RGS), factoradic number system, power calculations, etc. In the practical side, SPP is intimately related to classification problems, clustering problems, reduction of dimensionality problems, and so on. In this work, three representations for instances of SPP are presented, these representations use: Restricted Growth Strings (RGS), factoradic number system, and a number system with a fixed base. Two cases for these representations will be presented: where the number of subsets is unbounded (i.e. the number of subsets can be the number of objects);and where the number of subsets is less than the number of objects. Bidirectional mappings between these three representations will be introduced, also the mapping among these three representations and the power of a base is defined. Given, that these three representations can be used to solve instances of SPP using exact, greedy, and metaheuristic algorithms, that require to do small changes to one possible solution and/or recombination of two possible solutions, definitions of mutation and recombination operators for the three representations will be shown. In order to motivate the use of the three representations for the solution of particular instances of SPP, it was decided to present their application to solve an instance of a set partition of integers problem (SPIP) using a simple genetic algorithm.

关键词： Licenses Redundancy partitioning algorithms Genetic algorithms Web mining Self-organizing feature maps Maintenance engineering Bell numbers factoradic number system restricted growth strings number system stirling numbers of the second kind Eulerian numbers

来源：评论

学校读者我要写书评

暂无评论

Graph-Theoretic partitioning for Differential Zone Protection in an Islanded Microgrid

Graph-Theoretic Partitioning for Differential Zone Protectio...

引用

Innovative Smart Grid Technologies (ISGT)

作者： Fahad Alsaeidi Chen-Ching Liu Lung-An Lee

The deployment of microgrids improves the reliability and resiliency of the electric power grid. Microgrids mitigate the impact of power outages. Microgrids, on the other hand, introduce new chal-lenges to the power system. Microgrid protection is a technological issue that arises in microgrid design and operation. These challenges arise due to the dis-tinction between microgrids and conventional electrical grids. Differential protection is fast, selective, and sensitive; it provides a potential solution to microgrid protection. The differential zone protection scheme is a cost-effective variation of differential protection that improves system reliability while decreasing the cost of the protection scheme. To deploy a differential zone protection scheme, it is necessary to divide the network into distinct protection zones. The number of protective zones results in a different level of mi-crogrid system reliability. This paper presents a graph partitioning approach for differential zone protection. Using the algorithm, the microgrid is partitioned into a number of protection zones. The proposed protection method is validated using the IEEE-13 node system as a microgrid.

关键词： Electric potential Costs Microgrids Power system reliability partitioning algorithms Smart grids Reliability

来源：评论

学校读者我要写书评

暂无评论

Comparing Graph Clusterings: Set Partition Measures vs. Graph-Aware Measures

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2021年第6期43卷 2127-2132页

作者： Poulin, Valerie Theberge, Francois Tutte Inst Math & Comp Ottawa ON K1G 3Z4 Canada

In this paper, we propose a family of graph partition similarity measures that take the topology of the graph into account. These graph-aware measures are alternatives to using set partition similarity measures that are not specifically designed for graphs. The two types of measures, graph-aware and set partition measures, are shown to have opposite behaviors with respect to resolution issues and provide complementary information necessary to compare graph partitions.

关键词： partitioning algorithms Indexes Clustering algorithms Mutual information Size measurement Topology Computer vision Graph clustering partition similarity

来源：评论

学校读者我要写书评

暂无评论

A Multi-View Co-Training Clustering Algorithm Based on Global and Local Structure Preserving

引用

IEEE ACCESS 2021年 9卷 29293-29302页

作者： Cai, Weiling Zhou, Honghan Xu, Le Nanjing Normal Univ Dept Comp Sci & Technol Nanjing 210097 Peoples R China

Multi-view clustering which integrates the complementary information from different views for better clustering, is a fundamental and important topic in machine learning. In this paper, we present a multi-view co-training clustering algorithm based on global and local structure preserving. Here the global structure is referred to the integration of the within-cluster compactness and between-cluster separation;the local structure is referred to the neighborhood information. Our algorithm at first preserves both the global and local structure to the subspace in each view. And then, this algorithm obtains the clustering result in the subspace of each view, and utilizes the clustering labels of one view to guide the subspace clustering in another view. In this way, the differences and compatibilities among the multiple views are fused together to form the final cluster partition. Therefore, the clustering result takes full account of the global and local structure information of the multi-view data, which is helpful to improve the of clustering accuracy. Experimental results on the multi-view text datasets and image datasets demonstrate the effectiveness and correctness of the proposed algorithm.

关键词： Clustering algorithms partitioning algorithms Linear programming Training Dimensionality reduction Clustering methods Videos Multi-view clustering subspace learning co-training

来源：评论

学校读者我要写书评

暂无评论

Buffer-Assisted Network Updates in Timed SDN

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第10期69卷 6822-6837页

作者： He, Xin Zheng, Jiaqi Dai, Haipeng Sun, Yuhu Dou, Wanchun Chen, Guihai Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China

Although the logically-centralized perspective is offered in Software-Defined Networking (SDN), the data plane is still distributed. Update commands sent by the centralized controller are executed asynchronously and independently in each switch. The timed SDN enables synchronous and coordinated update operations as each update command can be triggered by a pre-defined timestamp. Prior work on timed update mainly focuses on producing a congestion-free update sequence, whereas finding a congestion-free timed update sequence may prolong the update time. Even worse, such an update order may not exist. In this paper, we propose Chronus(+), a novel timed update system that utilizes the switch buffer to shorten the update time while minimizing the switch buffer during updates. First, we formulate the Minimum Switch Buffer Problem (MSBP) as an integer linear programming and show its hardness. Then, we propose a set of efficient algorithms to solve the problem in polynomial time. Extensive evaluations in Mininet and large-scale simulations show that Chronus(+) can reduce the update time by at least 17% and the switch buffer size by at least 27% compared with state-of-the-art approaches.

关键词： Switches Control systems Propagation delay Protocols partitioning algorithms Network topology Transient analysis Timed SDN network updates switch buffer link congestion

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：