When an Internet router receives a packet p from an input link interface, it uses p’s destination field to look up a routing database. The result of the lookup provides an output link interface, to which packet p is forwarded. In dynamic router tables, where IP lookup is intermixed with table updates, lookups may be delayed while a preceding update completes. To minimize this delay, it is important that updates are performed as fast as possible. In relaxed balanced data structures, rebalancing is uncoupled from updates such that the rebalancing tasks can be performed gradually in less busy times. We investigate how the min-augmented range tree, a structure which can be utilized for IP lookup, can be relaxed. Our experiments with real IPv4 routing data indicate that the relaxed balanced min-augmented range tree has a significant advantage over the strictly balanced version.

Packet classification enables network routers to provide advanced network services including network security, quality of service (QoS) routing, and multimedia communications. In order to classify a packet, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. Viewing the classification problem geometrically, classifying an arriving packet is equivalent to finding the highest priority hyperrectangle among all hyperrectangles that contain the point representing the packet. The R-tree and its variants, being among the most popular access methods for points and rectangles, have not been experimentally evaluated and benchmarked for their eligibility for the packet classification problem. In this paper we investigate how the R*-tree, a dynamic index structure for spatial data, is suited for packet classification. To this end we will benchmark R* with two representative classification algorithms using the ClassBench tools suite.

Packet Alters are rules for classifying packets based on their header fields. In order to avoid ambiguities in packet classification, the set of filters in a router table must be conflict-free, i.e. for any incoming packet p, there must be a unique best matching filter which applies to p. We present the first output-sensitive solution for the offline version of the conflict detection and resolving problem for 1-dimensional arbitrary range filters under the most-specific tie breaking rule. The algorithm achieves a worst case time complexity of O(n log n) and uses space O(n). Instead of reporting and resolving all pairs of conflicting filters, we straight away report those resolve filters that are necessary to make the set conflict-free.

Students' understanding of algorithms and data structures can be assessed with the help of construction tasks where students have to build their own visualizations. It has been claimed that active construction of visualizations results in better learning outcomes than passive viewing or merely changing the input of a visualized algorithm. This paper presents a system for the generation, execution, and evaluation of construction tasks. Its key feature is the flexibility in all three stages, ranging from fully automated to fully manual generation and evaluation as well as several different types of automatic feedback during the execution phase. Besides its use in daily teaching, the system can serve as a test bed for evaluations regarding the effectiveness of visualizations in the learning process.

We present a solution to the dictionary problem, where each subset of size n of an ordered universe is represented by a unique structure containing a (unique) binary search tree. The structure permits the execution of search, insert, and delete operations in $O(n^{1/3})$ time in the worst case. We also give a general lower bound, stating that for any unique representation of a set in a graph of bounded out-degree, one of the operations search or update must require a cost of $\Omega(n^{1/3})$. Therefore, our result sheds new light on previously claimed lower bounds for the unique representation of dictionaries.

The authors present a solution to the dictionary problem where each subset of size n of an ordered universe is represented by a unique structure, containing a (unique) binary search tree. The structure permits the execution of search, insert, and delete operations in O(n/sup 1/3/) time in the worst case. They also give a general lower bound, stating that for any unique representation of a set in a graph of, bounded outdegree, one of the operations search or update must require a cost of Omega (n/sup 1/3/) Therefore, the result sheds new light on previously claimed lower bounds for unique binary search tree representations.>

Article Numerical stability of geometric algorithms Share on Authors: T. Ottmann Institut für Angewandte Informatik, und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, D-7500 Karlsrube, West Germany Institut für Angewandte Informatik, und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, D-7500 Karlsrube, West GermanyView Profile , G. Theimt Institut für Angewandte Informatik, und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, D-7500 Karlsrube, West Germany Institut für Angewandte Informatik, und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, D-7500 Karlsrube, West GermanyView Profile , C. Ullrich Institut für Angewandte Mathematik, Universität Karlsruhe, Postfach 6980, D-7500 Karlsruhe, West Germany Institut für Angewandte Mathematik, Universität Karlsruhe, Postfach 6980, D-7500 Karlsruhe, West GermanyView Profile Authors Info & Claims SCG '87: Proceedings of the third annual symposium on Computational geometryOctober 1987 Pages 119–125https://doi.org/10.1145/41958.41970Online:01 October 1987Publication History 38citation416DownloadsMetricsTotal Citations38Total Downloads416Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Given a point set in plane and a fixed planar region (window) a window query consists of enumerating the points in a translate of the region. A recently presented result shows that a static data structure of optimal size enables window queries for convex regions in optimal time. We show that if the windows are (maybe non-convex) polygons another data structure of optimal size supports not only window queries in optimal time but also allows updating of the point set in optimal time.

Given two points a=(a1,a2,…,ad) and b=(b1,b2,…,bd) in d-dimensional space, a dominates b if a≠b and for each i=1…d holds ai≥bi. The direct dominance problem consists of computing a relation of minimal size on a given set of n points such that the transitive closure of the relation gives all the dominances in the set. We present an Ο(n log n +k) time and Ο(n) space algorithm for the problem of two-dimensional space. The algorithm is optimal within a constant factor. Further, we show that the three-dimensional problem can be solved in Ο((n+k) log2n) time and space, or alternatively in Ο((n+k) log3n) time and Ο((n+k)log n) space.

We investigate three cost measures for the recently introduced brother search trees. In particular we characterize node visit optimal, comparison-cost optimal and space-cost optimal 1-2 brother trees and present linear-time algorithms to construct optimal 1-2 brother trees for each cost measure. Furthermore we also consider, briefly, these cost measures for brother leaf search trees.

We present the design of a dictionary machine that is suitable for VLSI implementation, and we discuss how to realize this implementation efficiently. The machine supports the operations of SEARCH, INSERT, DELETE, and EXTRACTMIN on an arbitrary ordered set. Each of these operations takes time O(log n), where n is the number of entries present when the operation is performed. Moreover, arbitrary sequences of these instructions can be pipelined through the machine at a constant rate (i.e., independent of n and the capacity of the machine). The time O(log n) is an improvement over previous VLSI designs of dictionary machines which require time O(log N) per operation, where N is the maximum number of keys that can be stored.

B-trees of order m are a “balanced” class of m -ary trees, which have applications in the areas of file organization. In fact, they have been the only choice when balanced multiway trees are required. Although they have very simple insertion and deletion algorithms, their storage utilization, that is, the number of keys per page or node, is at worst 50 percent. In the present paper we investigate a new class of balanced m -ary trees, the dense multiway trees, and compare their storage utilization with that of B-trees of order m . Surprisingly, we are able to demonstrate that weakly dense multiway trees have an Ο (log 2 N ) insertion algorithm. We also show that inserting m h - 1 keys in ascending order into an initially empty dense multiway tree yields the complete m -ary tree of height h , and that at intermediate steps in the insertion sequence the intermediate trees can also be considered to be as dense as possible. Furthermore, an analysis of the limiting dynamic behavior of the dense m -ary trees under insertion shows that the average storage utilization tends to 1; that is, the trees become as dense as possible. This motivates the use of the term “dense.”

1-2 brother trees are binary search trees which have similarities to both height balanced search trees and 2-3 trees. Firstly, 0(log2n) insertion and deletion algorithms are demonstrated and their similarities with those for brother trees are noted. Secondly, it is proved that the space utilisation of (random) 1-2 brother trees is much better than that for (random) 2-3 trees. Thirdly, the close relationship between 1-2 brother trees and height balanced trees is demonstrated, and as this also holds for their right-sided counterparts it leads to 0(log2n) insertion and deletion algorithms for right-sided height balanced trees. Finally, this demonstrates that the insertion and deletion algorithms for right-sided height balanced trees were already available, but hidden, in the corresponding algorithms for right brother trees.

An interesting class of "geometric intersection problems" calls for dealing with the pairwise intersections among a set of N objects in the plane, These problems arise in many applications such as printed circuit design, architectural data bases, and computer graphics. Shamos and Hoey have described a number of algorithms for detecting whether any two objects in a planar set intersect. In this paper we extend their work by giving algorithms that count the number of such intersections and algorithms that report all such intersections.