I/O Efficient Dynamic Data Structures for Longest Prefix Queries

I/O Efficient Dynamic Data Structures for Longest Prefix Queries

0.00 Avg rating0 Votes
Article ID: iaor2013680
Volume: 65
Issue: 2
Start Page Number: 371
End Page Number: 390
Publication Date: Feb 2013
Journal: Algorithmica
Authors: ,
Keywords: programming: dynamic, combinatorial optimization
Abstract:

We present an efficient data structure for finding the longest prefix of a query string q in a dynamic database of strings. When the database strings are prefixes of IP‐addresses then this is the IP‐lookup problem. Our data structure is I/O efficient. It supports a query with a string q using O ( log B ( n ) + q B ) equ1 I/O operations, where B is the size of a disk block. It also supports an insertion and a deletion of a string q with the same number of I/Os. The data structure requires O(n/B) blocks, and the running time for each operation is O(Blog B (n)+|q|).

Reviews

Required fields are marked *. Your email address will not be published.