Arrow Research search

Author name cluster

Lars Arge

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

FOCS Conference 2009 Conference Paper

Orthogonal Range Reporting in Three and Higher Dimensions

  • Peyman Afshani
  • Lars Arge
  • Kasper Green Larsen

In orthogonal range reporting we are to preprocess N points in d-dimensional space so that the points inside a d-dimensional axis-aligned query box can be reported efficiently. This is a fundamental problem in various fields, including spatial databases and computational geometry. In this paper we provide a number of improvements for three and higher dimensional orthogonal range reporting: In the pointer machine model, we improve all the best previous results, some of which have not seen any improvements in almost two decades. In the I/O-model, we improve the previously known three-dimensional structures and provide the first (non-trivial) structures for four and higher dimensions.

Details

FOCS Conference 2006 Conference Paper

Improved Dynamic Planar Point Location

  • Lars Arge
  • Gerth Stølting Brodal
  • Loukas Georgiadis

We develop the first linear-space data structures for dynamic planar point location in general subdivisions that achieve logarithmic query time and poly-logarithmic update time

Details

FOCS Conference 2003 Conference Paper

I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs

  • Lars Arge
  • Norbert Zeh

We present the first I/O-efficient algorithms for the following fundamental problems on directed planar graphs: finding the strongly connected components, finding a simple-path 2/3-separator, and computing a depth-first spanning (DFS) tree. Our algorithms for the first two problems perform O(sort(N)) I/Os, where N = V + E and sort(N) = /spl Theta/((N/B)) is the number of I/Os required to sort N elements. The DFS-algorithm performs O(sort(N) log(N/M)) I/Os, where M is the number of elements that fit into main memory.

Details

STOC Conference 2002 Conference Paper

Cache-oblivious priority queue and graph algorithm applications

  • Lars Arge
  • Michael A. Bender
  • Erik D. Demaine
  • Bryan Holland-Minkley
  • J. Ian Munro

(MATH) In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O ( 1 \over B log M/B N \over B ) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache-oblivious data structure, M and B are not used in the description of the structure. The bounds match the bounds of several previously developed external-memory (cache-aware) priority queue data structures, which all rely crucially on knowledge about M and B . Priority queues are a critical component in many of the best known external- memory graph algorithms, and using our cache-oblivious priority queue we develop several cache- oblivious graph algorithms.

Details

FOCS Conference 1996 Conference Paper

Optimal Dynamic Interval Management in External Memory (extended abstract)

  • Lars Arge
  • Jeffrey Scott Vitter

The authors present a space- and I/O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The data structure settles an open problem in databases and I/O algorithms by providing the first optimal external-memory solution to the dynamic interval management problem, which is a special case of 2-dimensional range searching and a central problem for object-oriented and temporal databases and for constraint logic programming. The data structure simultaneously uses optimal linear space (that is, O(N/B) blocks of disk space) and achieves the optimal O(log/sub B/ N+T/B) I/O query bound and O(log/sub B/ N) I/O update bound, where B is the I/O block size and T the number of elements in the answer to a query. The structure is also the first optimal external data structure for a 2-dimensional range searching problem that has worst-case as opposed to amortized update bounds. Part of the data structure uses a novel balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest.

Details