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.
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.
Array programming with NumPy Harris, Charles R; Millman, K Jarrod; van der Walt, Stéfan J ...
Nature (London),
09/2020, Letnik:
585, Številka:
7825
Journal Article
Recenzirano
Odprti dostop
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.
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.
Approximate set membership data structures (ASMDSs) are ubiquitous in computing. They trade a tunable, often small, error rate (
ϵ
) for large space savings. The canonical ASMDS is the Bloom filter, ...which supports lookups and insertions but not deletions in its simplest form. Cuckoo filters (CFs), a recently proposed class of ASMDSs, add deletion support and often use fewer bits per item for equal
ϵ
. This work introduces the Morton filter (MF), a novel CF variant that introduces several key improvements to its progenitor. Like CFs, MFs support lookups, insertions, and deletions, and when using an optional batching interface raise their respective throughputs by up to 2.5
×
, 20.8
×
, and 1.3
×
. MFs achieve these improvements by (1) introducing a compressed block format that permits storing a logically sparse filter compactly in memory, (2) leveraging succinct embedded metadata to prune unnecessary memory accesses, and (3) more heavily biasing insertions to use a single hash function. With these optimizations, lookups, insertions, and deletions often only require accessing a single hardware cache line from the filter. MFs and CFs are then extended to support self-resizing, a feature of quotient filters (another ASMDS that uses fingerprints). MFs self-resize up to 13.9
×
faster than rank-and-select quotient filters (a state-of-the-art self-resizing filter). These improvements are not at a loss in space efficiency, as MFs typically use comparable to slightly less space than CFs for equal
ϵ
.
PDF
