ALEX: An Updatable Adaptive Learned Index Ding, Jialin; Minhas, Umar Farooq; Yu, Jia ...
Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data,
06/2020
Conference Proceeding
Open access
Recent work on "learned indexes" has changed the way we look at the decades-old field of DBMS indexing. The key idea is that indexes can be thought of as "models" that predict the position of a key ...in a dataset. Indexes can, thus, be learned. The original work by Kraska et al. shows that a learned index beats a B+ tree by a factor of up to three in search time and by an order of magnitude in memory footprint. However, it is limited to static, read-only workloads. In this paper, we present a new learned index called ALEX which addresses practical issues that arise when implementing learned indexes for workloads that contain a mix of point lookups, short range queries, inserts, updates, and deletes. ALEX effectively combines the core insights from learned indexes with proven storage and indexing techniques to achieve high performance and low memory footprint. On read-only workloads, ALEX beats the learned index from Kraska et al. by up to 2.2X on performance with up to 15X smaller index size. Across the spectrum of read-write workloads, ALEX beats B+ trees by up to 4.1X while never performing worse, with up to 2000X smaller index size. We believe ALEX presents a key step towards making learned indexes practical for a broader class of database workloads with dynamic updates.
A palindromic substring
T
i
..
j
of a string
T
is said to be a shortest unique palindromic substring (SUPS) in
T
for an interval
p
,
q
if
T
i
..
j
is a shortest palindromic substring such that
...T
i
..
j
occurs only once in
T
, and
i
,
j
contains
p
,
q
. The SUPS problem is, given a string
T
of length
n
, to construct a data structure that can compute all the SUPSs for any given query interval. It is known that any SUPS query can be answered in
O
(
α
)
time after
O
(
n
)-time preprocessing, where
α
is the number of SUPSs to output (Inoue in J Discrete Algorithms 52-53:122–132, 2018). In this paper, we first show that
α
is at most 4, and the upper bound is tight. We also show that the total sum of lengths of minimal unique palindromic substrings of string
T
, which is strongly related to SUPSs, is
O
(
n
). Then, we present the first
O
(
n
)-bits data structures that can answer any SUPS query in constant time. Also, we present an algorithm to solve the SUPS problem for a sliding window that can answer any query in
O
(
log
log
W
)
time and update data structures in amortized
O
(
log
σ
+
log
log
W
)
time, where
W
is the size of the window, and
σ
is the alphabet size. Furthermore, we consider the SUPS problem in the after-edit model and present an efficient algorithm. Namely, we present an algorithm that uses
O
(
n
) time for preprocessing and answers any
k
SUPS queries in
O
(
log
n
log
log
n
+
k
log
log
n
)
time after single character substitution. Finally, as a by-product, we propose a fully-dynamic data structure for range minimum queries (RmQs) with a constraint where the width of each query range is limited to poly-logarithmic. The constrained RmQ data structure can answer such a query in constant time and support a single-element edit operation in amortized constant time.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
3.
Log(graph) Besta, Maciej; Stanojevic, Dimitri; Zivic, Tijana ...
Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques,
11/2018
Conference Proceeding
Today's graphs used in domains such as machine learning or social network analysis may contain hundreds of billions of edges. Yet, they are not necessarily stored efficiently, and standard graph ...representations such as adjacency lists waste a significant number of bits while graph compression schemes such as WebGraph often require time-consuming decompression. To address this, we propose Log(Graph): a graph representation that combines high compression ratios with very low-overhead decompression to enable cheaper and faster graph processing. The key idea is to encode a graph so that the parts of the representation approach or match the respective storage lower bounds. We call our approach "graph logarithmization" because these bounds are usually logarithmic. Our high-performance Log(Graph) implementation based on modern bitwise operations and state-of-the-art succinct data structures achieves high compression ratios as well as performance. For example, compared to the tuned Graph Algorithm Processing Benchmark Suite (GAPBS), it reduces graph sizes by 20-35% while matching GAPBS' performance or even delivering speedups due to reducing amounts of transferred data. It approaches the compression ratio of the established WebGraph compression library while enabling speedups of up to more than 2×. Log(Graph) can improve the design of various graph processing engines or libraries on single NUMA nodes as well as distributed-memory systems.
FITing-Tree Galakatos, Alex; Markovitch, Michael; Binnig, Carsten ...
Proceedings of the 2019 International Conference on Management of Data,
06/2019
Conference Proceeding
Open access
Index structures are one of the most important tools that DBAs leverage to improve the performance of analytics and transactional workloads. However, building several indexes over large datasets can ...often become prohibitive and consume valuable system resources. In fact, a recent study showed that indexes created as part of the TPC-C benchmark can account for 55% of the total memory available in a modern DBMS. This overhead consumes valuable and expensive main memory, and limits the amount of space available to store new data or process existing data. In this paper, we present a novel data-aware index structure called FITing-Tree which approximates an index using piece-wise linear functions with a bounded error specified at construction time. This error knob provides a tunable parameter that allows a DBA to FIT an index to a dataset and workload by being able to balance lookup performance and space consumption. To navigate this tradeoff, we provide a cost model that helps determine an appropriate error parameter given either (1) a lookup latency requirement (e.g., 500ns) or (2) a storage budget (e.g., 100MB). Using a variety of real-world datasets, we show that our index is able to provide performance that is comparable to full index structures while reducing the storage footprint by orders of magnitude.
Rainbow connections are natural combinatorial measures that are used in applications to secure the transfer of classified information between agencies in communication networks. Rainbow Connections ...of Graphs covers this new and emerging topic in graph theory and brings together a majority of the results that deal with the concept of rainbow connections, first introduced by Chartrand et al. in 2006. The authors begin with an introduction to rainbow connectedness, rainbow coloring, and rainbow connection number. The work is organized into the following categories, computation of the exact values of the rainbow connection numbers for some special graphs, algorithms and complexity analysis, upper bounds in terms of other graph parameters, rainbow connection for dense and sparse graphs, for some graph classes and graph products, rainbow k-connectivity and k-rainbow index, and, rainbow vertex-connection number. Rainbow Connections of Graphs appeals to researchers and graduate students in the field of graph theory. Conjectures, open problems and questions are given throughout the text with the hope for motivating young graph theorists and graduate students to do further study in this subject.
Full text
Available for:
FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NUK, OBVAL, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
6.
Array programming with NumPy Harris, Charles R; Millman, K Jarrod; van der Walt, Stéfan J ...
Nature,
09/2020, Volume:
585, Issue:
7825
Journal Article
Peer reviewed
Open access
Array programming provides a powerful, compact and expressive syntax for accessing, manipulating and operating on data in vectors, matrices and higher-dimensional arrays. NumPy is the primary array ...programming library for the Python language. It has an essential role in research analysis pipelines in fields as diverse as physics, chemistry, astronomy, geoscience, biology, psychology, materials science, engineering, finance and economics. For example, in astronomy, NumPy was an important part of the software stack used in the discovery of gravitational waves
and in the first imaging of a black hole
. Here we review how a few fundamental array concepts lead to a simple and powerful programming paradigm for organizing, exploring and analysing scientific data. NumPy is the foundation upon which the scientific Python ecosystem is constructed. It is so pervasive that several projects, targeting audiences with specialized needs, have developed their own NumPy-like interfaces and array objects. Owing to its central position in the ecosystem, NumPy increasingly acts as an interoperability layer between such array computation libraries and, together with its application programming interface (API), provides a flexible framework to support the next decade of scientific and industrial analysis.
Full text
Available for:
FZAB, GEOZS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Abstract This work introduces a lightweight LIO framework employing incremental voxels for enhanced efficiency. We leverage a sparse voxel data structure, replacing the tree structure in the ...Point-LIO open-source framework. Through hash table-managed voxel indexes, we achieve rapid K nearest neighbor search within nearly one voxel size with constant complexity query speed. This approach significantly reduces the time cost associated with tree nodes construction, balancing, and iteration compared to the tree-like structures. Experimental results demonstrate that our proposed enhancement achieves an average speed-up of 21.5% compared to Point-LIO in publicly available datasets. Moreover, it reduces drift by an average of approximately 20(m) and ATE by 1.41(m) under sparse point cloud input conditions.
In recent years, real-world attacks against PKI take place frequently. For example, malicious domains' certificates issued by compromised CAs are widespread, and revoked certificates are still ...trusted by clients. In spite of a lot of research to improve the security of SSL/TLS connections, there are still some problems unsolved. On one hand, although log-based schemes provided certificate audit service to quickly detect CAs' misbehavior, the security and data consistency of log servers are ignored. On the other hand, revoked certificates checking is neglected due to the incomplete, insecure and inefficient certificate revocation mechanisms. Further, existing revoked certificates checking schemes are centralized which would bring safety bottlenecks. In this paper, we propose a blockchain-based public and efficient audit scheme for TLS connections, which is called Certchain. Specially, we propose a dependability-rank based consensus protocol in our blockchain system and a new data structure to support certificate forward traceability. Furthermore, we present a method that utilizes dual counting bloom filter (DCBF) with eliminating false positives to achieve economic space and efficient query for certificate revocation checking. The security analysis and experimental results demonstrate that CertChain is suitable in practice with moderate overhead.
Taichi Hu, Yuanming; Li, Tzu-Mao; Anderson, Luke ...
ACM transactions on graphics,
11/2019, Volume:
38, Issue:
6
Journal Article
Peer reviewed
3D visual computing data are often spatially sparse. To exploit such sparsity, people have developed hierarchical sparse data structures, such as multi-level sparse voxel grids, particles, and 3D ...hash tables. However, developing and using these high-performance sparse data structures is challenging, due to their intrinsic complexity and overhead. We propose
Taichi
, a new data-oriented programming language for efficiently authoring, accessing, and maintaining such data structures. The language offers a high-level, data structure-agnostic interface for writing computation code. The user independently specifies the data structure. We provide several elementary components with different sparsity properties that can be arbitrarily composed to create a wide range of multi-level sparse data structures. This
decoupling
of data structures from computation makes it easy to experiment with different data structures without changing computation code, and allows users to write computation as if they are working with a dense array. Our compiler then uses the semantics of the data structure and index analysis to automatically optimize for locality, remove redundant operations for coherent accesses, maintain sparsity and memory allocations, and generate efficient parallel and vectorized instructions for CPUs and GPUs.
Our approach yields competitive performance on common computational kernels such as stencil applications, neighbor lookups, and particle scattering. We demonstrate our language by implementing simulation, rendering, and vision tasks including a material point method simulation, finite element analysis, a multigrid Poisson solver for pressure projection, volumetric path tracing, and 3D convolution on sparse grids. Our computation-data structure decoupling allows us to quickly experiment with different data arrangements, and to develop high-performance data structures tailored for specific computational tasks. With
1
1
0
th as many lines of code, we achieve 4.55× higher performance on average, compared to hand-optimized reference implementations.
Dynamic provable data possession Erway, Chris; Küpçü, Alptekin; Papamanthou, Charalampos ...
Proceedings of the 16th ACM conference on Computer and communications security,
11/2009
Conference Proceeding
Open access
We consider the problem of efficiently proving the integrity of data stored at untrusted servers. In the provable data possession (PDP) model, the client preprocesses the data and then sends it to an ...untrusted server for storage, while keeping a small amount of meta-data. The client later asks the server to prove that the stored data has not been tampered with or deleted (without downloading the actual data). However, the original PDP scheme applies only to static (or append-only) files.
We present a definitional framework and efficient constructions for dynamic provable data possession (DPDP), which extends the PDP model to support provable updates to stored data. We use a new version of authenticated dictionaries based on rank information. The price of dynamic updates is a performance change from O(1) to O(logn) (or O(nεlog n), for a file consisting of n blocks, while maintaining the same (or better, respectively) probability of misbehavior detection. Our experiments show that this slowdown is very low in practice (e.g. 415KB proof size and 30ms computational overhead for a 1GB file). We also show how to apply our DPDP scheme to outsourced file systems and version control systems (e.g. CVS).
PDF
