Revisiting FastMap: New Applications

• URL: http://arxiv.org/abs/2503.11908v1
• Date: Fri, 14 Mar 2025 22:29:10 GMT
• Title: Revisiting FastMap: New Applications
• Authors: Ang Li,
• Abstract summary: We first present FastMap to generate Euclidean embeddings of graphs in near-linear time.<n>We then apply the graph version of FastMap to efficiently solve various graph-theoretic problems.<n>We also present a novel learning framework, called FastMapSVM, by combining FastMap and Support Vector Machines.
• Score: 9.754590060356119
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: FastMap was first introduced in the Data Mining community for generating Euclidean embeddings of complex objects. In this dissertation, we first present FastMap to generate Euclidean embeddings of graphs in near-linear time: The pairwise Euclidean distances approximate a desired graph-based distance function on the vertices. We then apply the graph version of FastMap to efficiently solve various graph-theoretic problems of significant interest in AI: including facility location, top-K centrality computations, community detection and block modeling, and graph convex hull computations. We also present a novel learning framework, called FastMapSVM, by combining FastMap and Support Vector Machines. We then apply FastMapSVM to predict the satisfiability of Constraint Satisfaction Problems and to classify seismograms in Earthquake Science.

Related papers

• InteractionMap: Improving Online Vectorized HDMap Construction with Interaction [0.4551615447454768]
  State-of-the-art map vectorization methods are mainly based on DETR-like framework to generate HD maps in an end-to-end manner. In this paper, we propose InteractionMap, which improves previous map vectorization methods by fully leveraging local-to-global information interaction.
  arXiv  Detail & Related papers  (2025-03-27T16:23:15Z)
• Compact Neural Graphics Primitives with Learned Hash Probing [100.07267906666293]
  We show that a hash table with learned probes has neither disadvantage, resulting in a favorable combination of size and speed. Inference is faster than unprobed hash tables at equal quality while training is only 1.2-2.6x slower.
  arXiv  Detail & Related papers  (2023-12-28T18:58:45Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• InstaGraM: Instance-level Graph Modeling for Vectorized HD Map Learning [8.556482588459899]
  Online high-definition (HD) map construction plays a significant role in accurate estimation of the pose.<n>Recent advancements in online HD map construction have predominantly investigated on vectorized representation.<n>We propose a novel HD map learning framework that leverages graph modeling.
  arXiv  Detail & Related papers  (2023-01-10T08:15:35Z)
• Primitive Graph Learning for Unified Vector Mapping [14.20286798139897]
  GraphMapper is a unified framework for end-to-end vector map extraction from satellite images. We convert vector shape prediction, regularization, and topology reconstruction into a unique primitive graph learning problem. Our model outperforms state-of-the-art methods by 8-10% in both tasks on public benchmarks.
  arXiv  Detail & Related papers  (2022-06-28T12:33:18Z)
• FastMapSVM: Classifying Complex Objects Using the FastMap Algorithm and Support-Vector Machines [12.728875331529345]
  We present FastMapSVM, a novel framework for classifying complex objects. FastMapSVM combines the strengths of FastMap and Support-Map Machines. We show that FastMapSVM's performance is comparable to that of other state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-04-07T18:01:16Z)
• Guided Interactive Video Object Segmentation Using Reliability-Based Attention Maps [55.94785248905853]
  We propose a novel guided interactive segmentation (GIS) algorithm for video objects to improve the segmentation accuracy and reduce the interaction time. We develop the intersection-aware propagation module to propagate segmentation results to neighboring frames. Experimental results demonstrate that the proposed algorithm provides more accurate segmentation results at a faster speed than conventional algorithms.
  arXiv  Detail & Related papers  (2021-04-21T07:08:57Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  We propose a new algorithm for finding an unknown number of geometric models, e.g., homographies. We present a number of applications where the use of multiple geometric models improves accuracy. These include pose estimation from multiple generalized homographies; trajectory estimation of fast-moving objects.
  arXiv  Detail & Related papers  (2021-03-25T14:35:07Z)
• Embedding Directed Graphs in Potential Fields Using FastMap-D [24.525270899573734]
  We present FastMap-D, an efficient generalization of FastMap to directed graphs. FastMap-D embeds vertices using a potential field to capture the asymmetry between the pairwise distances in directed graphs. In experiments on various kinds of directed graphs, we demonstrate the advantage of FastMap-D over other approaches.
  arXiv  Detail & Related papers  (2020-06-04T19:50:04Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to the low-performing solver, we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin.
  arXiv  Detail & Related papers  (2020-04-16T16:20:53Z)
• Voxel Map for Visual SLAM [57.07800982410967]
  We propose a voxel-map representation to efficiently map points for visual SLAM. Our method is geometrically guaranteed to fall in the camera field-of-view, and occluded points can be identified and removed to a certain extend. Experimental results show that our voxel map representation is as efficient as a map with 5s and provides significantly higher localization accuracy (average 46% improvement in RMSE) on the EuRoC dataset.
  arXiv  Detail & Related papers  (2020-03-04T18:39:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.