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

data Compression conference (DCC)

作者： Balakrishnan, Girish Chakraborty, Sankardeep Narayanaswamy, N. S. Sadakane, Kunihiko Indian Inst Technol Madras Chennai Tamil Nadu India Univ Tokyo Tokyo Japan

ISBN: (纸本)9781665478939

We consider the problem of designing space-efficient data structures for unlabelled path graphs with n vertices while supporting basic navigational queries such as degree, adjacency, and neighborhood queries efficiently. We provide two solutions for this problem. Our first data structure is succinct and occupies n log n + o(n log n) bits while answering adjacency query in O(log n) time, and neighborhood and degree queries in O(d log(2) n) time where d is the degree of the queried vertex. Our second data structure answers all these queries faster at the expense of slightly more space. More specifically, it consumes O(n log(2) n) bits while answering adjacency and degree queries in constant time and neighborhood query in O(d log n) time. Central to our data structures is the usage of the classical heavy path decomposition, followed by a careful bookkeeping using an orthogonal range search data structure among others, which may be of independent interest for designing succinct data structures for other graphs.

关键词： Navigation algorithms data compression data structures

来源：评论

学校读者我要写书评

暂无评论

Succinct Fermion data structures 16

Succinct Fermion Data Structures

引用

16th Innovations in Theoretical Computer Science conference, ITCS 2025

作者： Carolan, Joseph Schaeffer, Luke University of Maryland College ParkMD United States University of Waterloo Canada

ISBN: (纸本)9783959773614

Simulating fermionic systems on a quantum computer requires representing fermionic states using qubits. The complexity of many simulation algorithms depends on the complexity of implementing rotations generated by fermionic creation-annihilation operators, and the space depends on the number of qubits used. While standard fermion encodings like Jordan-Wigner are space optimal for arbitrary fermionic systems, physical symmetries like particle conservation can reduce the number of physical configurations, allowing improved space complexity. Such space saving is only feasible if the gate overhead is small, suggesting a (quantum) data structures problem, wherein one would like to minimize space used to represent a fermionic state, while still enabling efficient rotations. We define a structure which naturally captures mappings from fermions to systems of qubits. We then instantiate it in two ways, giving rise to two new second-quantized fermion encodings of F fermions in M modes. An information theoretic minimum of I := ⌈log2 (MF)⌉ qubits is required for such systems, a bound we nearly match over the entire parameter regime. 1. Our first construction uses I + o(I) qubits when F = o(M), and allows rotations generated by creation-annihilation operators in O(I) gates and O(log M log log M) depth. 2. Our second construction uses I + O(1) qubits when F = Θ(M), and allows rotations generated by creation-annihilation operators in O(I3) gates. In relation to comparable prior work, the first represents a polynomial improvement in both space and gate complexity (against Kirby et al. 2022), and the second represents an exponential improvement in gate complexity at the cost of only a constant number of additional qubits (against Harrison et al. or Shee et al. 2022), in the described parameter regimes. © Joseph Carolan and Luke Schaeffer.

关键词： Qubits

来源：评论

学校读者我要写书评

暂无评论

18th International Symposium on algorithms and data structures, WADS 2023

18th International Symposium on Algorithms and Data Structur...

引用

18th International Symposium on algorithms and data structures, WADS 2023

ISBN: (纸本)9783031389054

The proceedings contain 47 papers. The special focus in this conference is on algorithms and data structures. The topics include: Compact Distance Oracles with Large Sensitivity and Low Stretch;finding Diameter-Reducing Shortcuts in Trees;approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon;online Interval Scheduling with Predictions;on Length-Sensitive Fréchet Similarity;hardness of Graph-Structured Algebraic and Symbolic Problems;sublinear-space Streaming algorithms for Estimating Graph Parameters on Sparse Graphs;efficient k-Center algorithms for Planar Points in Convex Position;classification via Two-Way Comparisons (Extended Abstract);the Mutual Visibility Problem for Fat Robots;improved Bounds for Discrete Voronoi Games;general space-Time Tradeoffs via Relational Queries;approximate Minimum Sum Colorings and Maximum k-Colorable Subgraphs of Chordal Graphs;differentially Private Range Query on Shortest Paths;revisiting Graph Persistence for Updates and Efficiency;block Crossings in One-Sided Tanglegrams;observation Routes and External Watchman Routes;lower Bounds for Non-adaptive Shortest Path Relaxation;shortest Coordinated Motion for Square Robots;linear Layouts of Bipartite Planar Graphs;faster algorithms for Cycle Hitting Problems on Disk Graphs;adaptive data structures for 2D Dominance Colored Range Counting;zip-Zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent;external-Memory Sorting with Comparison Errors;verifying the Product of Generalized Boolean Matrix Multiplication and Its Applications to Detect Small Subgraphs;reconfiguration of Time-Respecting Arborescences;algorithmic Theory of Qubit Routing;3-Coloring C4 or C3 -Free Diameter Two Graphs;colored Constrained Spanning Tree on Directed Graphs;geometric Hitting Set for Line-Constrained Disks;An ETH-Tight Algorithm for Bidirected Steiner Connectivity;tight Analysis of the Lazy Algorithm for Open Online Dial-a-Ride;from Curves to Words and Back Again: Geometr

关键词：

来源：评论

学校读者我要写书评

暂无评论

Synerise Monad - Real-Time Multimodal Behavioral Modeling 22

Synerise Monad - Real-Time Multimodal Behavioral Modeling

引用

31st ACM International conference on Information and Knowledge Management (CIKM)

作者： Dabrowski, Jacek Rychalska, Barbara Synerise Warsaw Poland

ISBN: (纸本)9781450392365

The growth of time-sensitive heterogeneous data in industry-grade datalakes has recently reached unprecedented momentum. In response to this, we propose Synerise Monad - a prototype of a real-time behavioral modeling platform for event-based data streams. It automates representation learning and model training on massive data sources with arbitrary data structures. With Monad we showcase how to automatically process various data modalities, such as temporal, graph, categorical, decimal, and textual data types, in a time-sensitive way allowing for real-time time feature creation and predictions. Monad's distributed and scalable architecture coupled with efficient award-winning algorithms developed at Synerise - Cleora and EMDE - allows to process real-life datasets composed of billions of events in record time. The Monad ecosystem showcases a viable path towards real-time event-based AutoML.

关键词： autoML big data representation learning graph learning behavioral modeling

来源：评论

学校读者我要写书评

暂无评论

Securing Edge Computing Environments with a Novel Chaos Theory-Based Lightweight Encryption Algorithm for Real-Time data Protection 2

Securing Edge Computing Environments with a Novel Chaos Theo...

引用

2nd IEEE International conference on Integrated Intelligence and Communication Systems, ICIICS 2024

作者： Vanitha, V. Saritha, G. Hemalatha, K. Sathish, P. Devi, P. Gayathri Department of of Computer Science and Engineering Kumaraguru College of Technology Coimbatore India Department of Electronics and Communication Engineering Sri Sai Ram Institute of Technology Chennai India Department of Information Technology Sona College of Technology Salem India Nandha Engineering College Erode India Department of Electronics and Communication Engineering Panimalar Engineering College Chennai India

ISBN: (纸本)9798331504960

In the era of edge computing, securing data transmission has become paramount, especially given the real-time requirements and limited computational resources of edge devices. This study introduces a novel Chaos Theory-Based Lightweight Encryption Algorithm (CTBLEA) designed to enhance data protection in edge computing environments. The proposed algorithm leverages the inherent unpredictability of chaotic maps to secure data streams without imposing significant computational burdens. By adopting a lightweight encryption mechanism, CTBLEA ensures minimal latency and energy consumption, making it ideal for resource-constrained edge devices. Extensive experiments were conducted to evaluate the algorithm’s performance. CTBLEA achieved an encryption and decryption time of 0.25 ms per kilobyte, showing a 35% reduction in latency compared to traditional AES encryption in similar environments. Furthermore, the algorithm demonstrated an energy consumption reduction of 40% while maintaining high security standards with an average key space of 10^15, making brute-force attacks infeasible. Security tests showed a correlation coefficient close to zero (0.003) between the original and encrypted data, indicating high randomness and minimal data correlation. Additionally, the algorithm’s resistance to statistical and differential attacks was validated, with a 99.7% randomness score from the NIST suite tests. These results confirm the potential of CTBLEA for safeguarding real-time data in edge computing, offering a secure, efficient solution for next-generation IoT and edge environments. © 2024 IEEE.

关键词： Encryption algorithms

来源：评论

学校读者我要写书评

暂无评论

Compact data structures for efficient Processing of Distance-Based Join Queries 11th

Compact Data Structures for efficient Processing of Distance...

引用

11th International conference on Model and data Engineering, MEDI 2022

作者： Bernardo, Guillermo de Penabad, Miguel R. Corral, Antonio Brisaboa, Nieves R. Universidade da Coruña Centro de investigación CITIC A Coruña15071 Spain Department of Informatics University of Almeria Almeria04120 Spain

ISBN: (纸本)9783031215940

Compact data structures can represent data with usually a much smaller memory footprint than its plain representation. In addition to maintaining the data in a form that uses less space, they allow us to efficiently access and query the data in its compact form. The k2 -tree is a self-indexed, compact data structure used to represent binary matrices, that can also be used to represent points in a spatial dataset. efficient processing of the Distance-based Join Queries (DJQs) is of great importance in spatial databases due to its wide area of application. Two of the most representative and known DJQs are the K Closest Pairs Query (KCPQ) and the Ε Distance Join Query (Ε DJQ). These types of join queries are executed over two spatial datasets and can be solved by plane-sweep algorithms, which are efficient but with great requirements of RAM, to be able to fit the whole datasets into main memory. In this work, we present new and efficient algorithms to implement DJQs over the k2 -tree representation of the spatial datasets, experimentally showing that these algorithms are competitive in query times, with much lower memory requirements. © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： Random access storage

来源：评论

学校读者我要写书评

暂无评论

An efficient Embedding Framework for Uncertain Attribute Graph 34th

An Efficient Embedding Framework for Uncertain Attribute Gra...

引用

34th International conference on database and Expert Systems Applications (DEXA)

作者： Jiang, Ting Yu, Ting Qiao, Xueting Zhang, Ji Zhejiang Lab Hangzhou Peoples R China Univ Southern Queensland Toowoomba Qld Australia

ISBN: (纸本)9783031398209;9783031398216

Graph data with uncertain connections between entities is commonly represented using uncertain graphs. This paper tackles the challenge of graph embedding within such uncertain attribute graphs. Current graph embedding techniques are typically oriented towards deterministic graphs, or uncertain graphs that lack attribute data. Furthermore, the majority of studies on uncertain graph learning simply adapt conventional algorithms for deterministic graphs to handle uncertainty, leading to compromised computational efficiency. To address these issues, we introduce an optimized embedding framework UAGE for uncertain attribute graphs. In UAGE, nodes are represented within a Gaussian distribution space to learn node attributes. We also propose a Probability Similarity Value (PSV) to manage relationship uncertainty and ensure that nodes with higher-order similar structures are located more closely in the latent space. Real-world dataset experiments confirm that UAGE surpasses contemporary methods in performance for downstream tasks.

关键词： Uncertain graph Gaussian embedding encoder-decoder

来源：评论

学校读者我要写书评

暂无评论

Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices

引用

PROCEEDINGS OF THE VLDB ENDOWMENT 2022年第10期15卷 2175-2187页

作者： Ferragina, Paolo Manzini, Giovanni Gagie, Travis Koppl, Dominik Navarro, Gonzalo Striani, Manuel Tosoni, Francesco Univ Pisa Dept Comp Sci Pisa Italy Dalhousie Univ Fac Comp Sci Halifax NS Canada Tokyo Med & Dent Univ M&D Data Sci Ctr Tokyo Japan Univ Chile Dept Comp Sci IMFD Santiago Chile Univ Piemonte Orientale Dept Sci & Technol Innovat Vercelli Italy

As nowadays Machine Learning (ML) techniques are generating huge data collections, the problem of how to efficiently engineer their storage and operations is becoming of paramount importance. In this article we propose a new lossless compression scheme for real-valued matrices which achieves efficient performance in terms of compression ratio and time for linear-algebra operations. Experiments show that, as a compressor, our tool is clearly superior to gzip and it is usually within 20% of xz in terms of compression ratio. In addition, our compressed format supports matrix-vector multiplications in time and space proportional to the size of the compressed representation, unlike gzip and xz that require the full decompression of the compressed matrix. To our knowledge our lossless compressor is the first one achieving time and space complexities which match the theoretical limit expressed by the.. -th order statistical entropy of the input. To achieve further time/space reductions, we propose columnreordering algorithms hinging on a novel column-similarity score. Our experiments on various data sets of ML matrices show that our column reordering can yield a further reduction of up to 16% in the peak memory usage during matrix-vector multiplication. Finally, we compare our proposal against the state-of-the-art Compressed Linear Algebra (CLA) approach showing that ours runs always at least twice faster (in a multi-thread setting), and achieves better compressed space occupancy and peak memory usage. This experimentally confirms the provably effective theoretical bounds we show for our compressed-matrix approach.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

Fast and space-efficient Parallel algorithms for Influence Maximization 50th

Fast and Space-Efficient Parallel Algorithms for Influence M...

引用

50th International conference on Very Large data Bases, VLDB 2024

作者： Wang, Letong Ding, Xiangyun Gu, Yan Sun, Yihan UC Riverside United States

Influence Maximization (IM) is a crucial problem in data science. The goal is to find a fixed-size set of highly influential seed vertices on a network to maximize the influence spread along the edges. While IM is NP-hard on commonly used diffusion models, a greedy algorithm can achieve (1 − 1/e)-approximation by repeatedly selecting the vertex with the highest marginal gain in influence as the seed. However, we observe two performance issues in the existing work that prevent them from scaling to today’s large-scale graphs: space-inefficient memorization to estimate marginal gain, and timeinefficient seed selection process due to a lack of parallelism. This paper significantly improves the scalability of IM using two key techniques. The first is a sketch-compression technique for the independent cascading model on undirected graphs. It allows combining the simulation and sketching approaches to achieve a time-space tradeoff. The second technique includes new data structures for parallel seed selection. Using our new approaches, we implemented PaC-IM: Parallel and Compressed IM. We compare PaC-IM with state-of-the-art parallel IM systems on a 96-core machine with 1.5TB memory. PaC-IM can process the ClueWeb graph with 978M vertices and 75B edges in about 2 hours. On average, across all tested graphs, our uncompressed version is 5–18× faster and about 1.4× more space-efficient than existing parallel IM systems. Using compression further saves 3.8× space with only 70% overhead in time on average. © 2023, VLDB Endowment. All rights reserved.

关键词： Undirected graphs

来源：评论

学校读者我要写书评

暂无评论

DEMYSTIFYING LINEAR MDPS AND NOVEL DYNAMICS AGGREGATION FRAMEWORK 12

DEMYSTIFYING LINEAR MDPS AND NOVEL DYNAMICS AGGREGATION FRAM...

引用

12th International conference on Learning Representations, ICLR 2024

作者： Lee, Joongkyu Oh, Min-Hwan Graduate School of Data Science Seoul National University Korea Republic of

In this work, we prove that, in linear MDPs, the feature dimension d is lower bounded by S/U in order to aptly represent transition probabilities, where S is the size of the state space and U is the maximum size of directly reachable states. Hence, d can still scale with S depending on the direct reachability of the environment. To address this limitation of linear MDPs, we propose a novel structural aggregation framework based on dynamics, named as the dynamics aggregation. For this newly proposed framework, we design a provably efficient hierarchical reinforcement learning algorithm in linear function approximation that leverages aggregated sub-structures. Our proposed algorithm exhibits statistical efficiency, achieving a regret of (Equation presented), where dψ represents the feature dimension of aggregated subMDPs and N signifies the number of aggregated subMDPs. We establish that the condition (Equation presented) is readily met in most real-world environments with hierarchical structures, enabling a substantial improvement in the regret bound compared to LSVI-UCB, which enjoys a regret of (Equation presented) (Jin et al., 2020). To the best of our knowledge, this work presents the first HRL algorithm with linear function approximation that offers provable guarantees. © 2024 12th International conference on Learning Representations, ICLR 2024. All rights reserved.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：