Journal of the ACM
Công bố khoa học tiêu biểu
Sắp xếp:
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.
Journal of the ACM - 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.
Journal of the ACM - 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.
Journal of the ACM - Tập 32 Số 4 - Trang 950-988 - 1985
Cost Trade-offs in Graph Embeddings, with Applications
Journal of the ACM - Tập 30 Số 4 - Trang 709-728 - 1983
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.
Journal of the ACM - Tập 34 Số 1 - Trang 200-208 - 1987
Applying Parallel Computation Algorithms in the Design of Serial Algorithms
Journal of the ACM - 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.
Journal of the ACM - 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.
Journal of the ACM - Tập 46 Số 5 - Trang 604-632 - 1999
Tổng số: 65
- 1
- 2
- 3
- 4
- 5
- 6
- 7