Show simple item record

Authordc.contributor.authorNavarro, Gonzalo 
Authordc.contributor.authorThankachan, Sharma 
Admission datedc.date.accessioned2016-06-25T19:10:21Z
Available datedc.date.available2016-06-25T19:10:21Z
Publication datedc.date.issued2016
Cita de ítemdc.identifier.citationAlgorithmica Volumen: 74 Número: 3 Páginas: 1082-1098 (2016)en_US
Identifierdc.identifier.issn0178-4617
Identifierdc.identifier.otherDOI: 10.1007/s00453-015-9987-8
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/139140
General notedc.descriptionArtículo de publicación ISIen_US
Abstractdc.description.abstractWe study the problem of designing a data structure that reports the positions of the distinct τ -majorities within any range of an array A[1, n], without storing A. A τ -majority in a range A[i, j ], for 0 < τ < 1, is an element that occurs more than τ( j − i + 1) times in A[i, j ]. We show that (n log(1/τ ) ) bits are necessary for any data structure just able to count the number of distinct τ -majorities in any range. Then, we design a structure using O(n log(1/τ ) ) bits that returns one position of each τ -majority of A[i, j ] in O((1/τ ) log logw(1/τ ) log n) time, on a RAM machine with word size w (it can output any further position where each τ -majority occurs in O(1) additional time). Finally, we show how to remove a log n factor from the time by adding O(n log log n) bits of space to the structure.en_US
Patrocinadordc.description.sponsorshipMillennium Nucleus Information and Coordination in Networks ICM/FIC, Chile P10-024Fen_US
Lenguagedc.language.isoenen_US
Publisherdc.publisherSpringeren_US
Type of licensedc.rightsAtribución-NoComercial-SinDerivadas 3.0 Chile*
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/*
Keywordsdc.subjectRange majority queriesen_US
Keywordsdc.subjectEncoding data structuresen_US
Keywordsdc.subjectSuccinct data structuresen_US
Títulodc.titleOptimal Encodings for Range Majority Queriesen_US
Document typedc.typeArtículo de revista


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record

Atribución-NoComercial-SinDerivadas 3.0 Chile
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 Chile