ATTENTION: The software behind KU ScholarWorks is being upgraded to a new version. Starting July 15th, users will not be able to log in to the system, add items, nor make any changes until the new version is in place at the end of July. Searching for articles and opening files will continue to work while the system is being updated.
If you have any questions, please contact Marianne Reed at mreed@ku.edu .
Approximate Data Structures with Applications
dc.contributor.author | Matias, Yossi | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.contributor.author | Young, Neal E. | |
dc.date.accessioned | 2011-03-16T17:48:37Z | |
dc.date.available | 2011-03-16T17:48:37Z | |
dc.date.issued | 1994 | |
dc.identifier.citation | Y. Matias, J. S. Vitter, and N. Young. “Approximate Data Structures with Applications,” Proceedings of the 5th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA ’94), Alexandria, VA, January 1994, 361–370. | |
dc.identifier.uri | http://hdl.handle.net/1808/7179 | |
dc.description.abstract | In this paper we introduce the notion of approximate data structures, in which a small amount of error is tolerated in the output. Approximate data structures trade error of approximation for faster operation, leading to theoretical and practical speedups for a wide variety of algorithms. We give approximate variants of the van Emde Boas data structure, which support the same dynamic operations as the standard van Emde Boas data structure [28, 201, except that answers to queries are approximate. The variants support all operations in constant time provided the error of approximation is l/polylog(n), and in O(loglog n) time provided the error is l/polynomial(n), for n elements in the data structure. We consider the tolerance of prototypical algorithms to approximate data structures. We study in particular Prim’s minimumspanning tree algorithm, Dijkstra’s single-source shortest paths algorithm, and an on-line variant of Graham’s convex hull algorithm. To obtain output which approximates the desired output with the error of approximation tending to zero, Prim’s algorithm requires only linear time, Dijkstra’s algorithm requires O(mloglogn) time, and the on-line variant of Graham’s algorithm requires constant amortized time per operation. | |
dc.language.iso | en_US | |
dc.publisher | Society for Industrial and Applied Mathematics | |
dc.relation.isversionof | http://portal.acm.org/citation.cfm?id=314464.314493 | |
dc.title | Approximate Data Structures with Applications | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oaversion | Scholarly/refereed, publisher version | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess |