Journal of the ACM
0004-5411
1557-735X
Mỹ
Cơ quản chủ quản: Association for Computing Machinery (ACM) , ASSOC COMPUTING MACHINERY
Phân tích ảnh hưởng
Thông tin về tạp chí
Lĩnh vực:
SoftwareArtificial IntelligenceInformation SystemsHardware and ArchitectureControl and Systems Engineering
The best indicator of the scope of the journal is provided by the areas covered by its Editorial Board. These areas change from time to time, as the field evolves. The following areas are currently covered by a member of the Editorial Board: Algorithms and Combinatorial Optimization; Algorithms and Data Structures; Algorithms, Combinatorial Optimization, and Games; Artificial Intelligence; Complexity Theory; Computational Biology; Computational Geometry; Computer Graphics and Computer Vision; Computer-Aided Verification; Cryptography and Security; Cyber-Physical, Embedded, and Real-Time Systems; Database Systems and Theory; Distributed Computing; Economics and Computation; Information Theory; Logic and Computation; Logic, Algorithms, and Complexity; Machine Learning and Computational Learning Theory; Networking; Parallel Computing and Architecture; Programming Languages; Quantum Computing; Randomized Algorithms and Probabilistic Analysis of Algorithms; Scientific Computing and High Performance Computing; Software Engineering; Web Algorithms and Data Mining
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Consider a set of
S
of
n
data points in real
d
-dimensional space, R
d
, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess
S
into a data structure, so that given any query point
q
∈ R
d
, is the closest point of S to
q
can be reported quickly. Given any positive real ϵ, data point
p
is a (1 +ϵ)-
approximate nearest neighbor
of
q
if its distance from
q
is within a factor of (1 + ϵ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of
n
points in R
d
in
O(dn
log
n
) time and
O(dn)
space, so that given a query point
q
∈ R
d
, and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of
q
can be computed in
O
(
c
d
, ϵ
log
n
) time, where
c
d,ϵ
≤
d
⌈1 + 6d/ϵ⌉
d
is a factor depending only on dimension and ϵ. In general, we show that given an integer
k
≥ 1, (1 + ϵ)-approximations to the
k
nearest neighbors of
q
can be computed in additional
O(kd
log
n
) time.
Tập 45 Số 6 - Trang 891-923 - 1998
Initial Algebra Semantics and Continuous Algebras Many apparently divergent approaches to specifying formal semantics of programming languages are applications of initial algebra semantics. In this paper an overview of initial algebra semantics is provided. The major technical feature is an initial continuous algebra which permits unified algebraic treatment of iterative and recursive semantic features in the same framework as more basic operations.
Tập 24 Số 1 - Trang 68-95 - 1977
A polynomial algorithm for the min-cut linear arrangement of trees
An algorithm is presented that finds a min-cut linear arrangement of a tree in
O
(
n
log
n
) time. An extension of the algorithm determines the number of pebbles needed to play the black and white pebble game on a tree.
Tập 32 Số 4 - Trang 950-988 - 1985
Slowing down sorting networks to obtain faster sorting algorithms
Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. This paper provides a general method that trims a factor of
O
(log
n
) time (or more) for many applications of this technique.
Tập 34 Số 1 - Trang 200-208 - 1987
Applying Parallel Computation Algorithms in the Design of Serial Algorithms
Tập 30 Số 4 - Trang 852-865 - 1983
Fast Multiple-Precision Evaluation of Elementary Functions
Let ƒ(
x
) be one of the usual elementary functions (exp, log, artan, sin, cosh, etc.), and let
M
(
n
) be the number of single-precision operations required to multiply
n
-bit integers. It is shown that ƒ(
x
) can be evaluated, with relative error
Ο
(2
-
n
), in
Ο
(
M
(
n
)log (
n
)) operations as
n
→ ∞, for any floating-point number
x
(with an
n
-bit fraction) in a suitable finite interval. From the Schönhage-Strassen bound on
M
(
n
), it follows that an
n
-bit approximation to ƒ(
x
) may be evaluated in
Ο
(
n
log
2
(
n
) log log(
n
)) operations. Special cases include the evaluation of constants such as π,
e
, and
e
π
. The algorithms depend on the theory of elliptic integrals, using the arithmetic-geometric mean iteration and ascending Landen transformations.
Tập 23 Số 2 - Trang 242-251 - 1976
Authoritative sources in a hyperlinked environment The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of context on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of “authorative” information sources on such topics. We propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure. Our formulation has connections to the eigenvectors of certain matrices associated with the link graph; these connections in turn motivate additional heuristrics for link-based analysis.
Tập 46 Số 5 - Trang 604-632 - 1999